5 июля 2012 г.

Оптимизация вычисления некоторых функций: полиномиальная функция (продолжение)

Начало см. здесь
Решил все же определить насколько действительно алгоритм Горнера быстрее вычисляет значение полиномиальной функции. Для этого сделал имплементацию на C. Код под катом, жми "Далее"



//
//  Gorner's algorithm test
//

#include <stdio.h>
#include <sys/time.h>
#include <math.h>

#define number float

number
polynom (number*a, unsigned int a_length, number x)
{
    number b = a[0];
    for (int i = 1; i < a_length; i++)
    {
        b += a[i]*pow(x, i);
    }
    return b;
}

number
gorner_recursive (number* a, unsigned int a_length, number x, unsigned int i)
{
    if (i > a_length - 1) return 0;
    return a[i] + x * gorner_recursive(a, a_length, x, i + 1);
}

number
gorner_normal (number* a, unsigned int a_length, number x)
{
    number b = a[a_length - 1];
    for (int i = a_length - 2; i >= 0; i--)
    {
        b = a[i] + x * b;
    }
    return b;
}

int 
main(int argc, const char * argv[])
{
    #define COEFFS_LENGTH 1000
    
    number a[COEFFS_LENGTH];
    {
        for (int i = 0; i < COEFFS_LENGTH; i++) 
        {
            a[i] = i * 0.2f;
        }
    }
    
    number x = .1f;
    
    number normal;
    number recursive;
    number common;
    
    struct timeval t_start;
    gettimeofday(&t_start, NULL);
    
    for (int i = 0; i < 1E2; i++) 
    {
        normal = gorner_normal(a, COEFFS_LENGTH, x);        
    }
    
    struct timeval t_normal;
    gettimeofday(&t_normal, NULL);    
    
    for (int i = 0; i < 1E2; i++) 
    {
        recursive = gorner_recursive(a, COEFFS_LENGTH, x, 0);
    }
    
    struct timeval t_recursive;
    gettimeofday(&t_recursive, NULL);
    
    for (int i = 0; i < 1E2; i++) 
    {
        common = polynom(a, COEFFS_LENGTH, x);
    }
    
    struct timeval t_common;
    gettimeofday(&t_common, NULL);        
    
    printf("Results:\n normal %f\n recursive %f\n common %f\n", normal, recursive, common);
    printf("Time consumption:\n normal %i\n recursive %i\n common %i\n", 
           t_normal.tv_usec - t_start.tv_usec,
           t_recursive.tv_usec - t_normal.tv_usec,
           t_common.tv_usec - t_recursive.tv_usec
           );
    
    return 0;
}

Результат работы программы слегка обескуражил.
Results:
 normal 0.024691
 recursive 0.024691
 common 0.024691
Time consumption:
 normal 500
 recursive 938
 common 6961

Алгоритм Горнера вычисляет float значение полинома, составленного из 1000 членов, коэффициенты которого определяются выражением ai = 0.2i, а x = 0.1 в более чем 10 раз быстрее, чем при прямом вычислении значения полинома. Рекурсивная версия требует больше времени, чем версия с циклом. Я полагаю, что в основном за счет дополнительного вызова процедуры на каждой итерации.

Использованный компилятор:
i686-apple-darwin11-llvm-gcc-4.2 (GCC) 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.1.00)

Собираем командой или в XCode.
gcc -std=c99 main.c 
Отправить комментарий