Advertisement
v_ignatyev

Optimizing Polynomial Function: Gorner Algorithm

Jan 15th, 2013
35
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.09 KB | None | 0 0
  1. //
  2. //  Gorner's algorithm test
  3. //  
  4. //  See explanation at: http://joydevel.blogspot.com/2012/07/blog-post_05.html
  5. //
  6.  
  7. #include <stdio.h>
  8. #include <sys/time.h>
  9. #include <math.h>
  10.  
  11. #define number float
  12.  
  13. number
  14. polynom (number*a, unsigned int a_length, number x)
  15. {
  16.     number b = a[0];
  17.     for (int i = 1; i < a_length; i++)
  18.     {
  19.         b += a[i]*pow(x, i);
  20.     }
  21.     return b;
  22. }
  23.  
  24. number
  25. gorner_recursive (number* a, unsigned int a_length, number x, unsigned int i)
  26. {
  27.     if (i > a_length - 1) return 0;
  28.     return a[i] + x * gorner_recursive(a, a_length, x, i + 1);
  29. }
  30.  
  31. number
  32. gorner_normal (number* a, unsigned int a_length, number x)
  33. {
  34.     number b = a[a_length - 1];
  35.     for (int i = a_length - 2; i >= 0; i--)
  36.     {
  37.         b = a[i] + x * b;
  38.     }
  39.     return b;
  40. }
  41.  
  42. int
  43. main(int argc, const char * argv[])
  44. {
  45.     #define COEFFS_LENGTH 1000
  46.    
  47.     number a[COEFFS_LENGTH];
  48.     {
  49.         for (int i = 0; i < COEFFS_LENGTH; i++)
  50.         {
  51.             a[i] = i * 0.2f;
  52.         }
  53.     }
  54.    
  55.     number x = .1f;
  56.    
  57.     number normal;
  58.     number recursive;
  59.     number common;
  60.    
  61.     struct timeval t_start;
  62.     gettimeofday(&t_start, NULL);
  63.    
  64.     for (int i = 0; i < 1E2; i++)
  65.     {
  66.         normal = gorner_normal(a, COEFFS_LENGTH, x);        
  67.     }
  68.    
  69.     struct timeval t_normal;
  70.     gettimeofday(&t_normal, NULL);    
  71.    
  72.     for (int i = 0; i < 1E2; i++)
  73.     {
  74.         recursive = gorner_recursive(a, COEFFS_LENGTH, x, 0);
  75.     }
  76.    
  77.     struct timeval t_recursive;
  78.     gettimeofday(&t_recursive, NULL);
  79.    
  80.     for (int i = 0; i < 1E2; i++)
  81.     {
  82.         common = polynom(a, COEFFS_LENGTH, x);
  83.     }
  84.    
  85.     struct timeval t_common;
  86.     gettimeofday(&t_common, NULL);        
  87.    
  88.     printf("Results:\n normal %f\n recursive %f\n common %f\n", normal, recursive, common);
  89.     printf("Time consumption:\n normal %i\n recursive %i\n common %i\n",
  90.            t_normal.tv_usec - t_start.tv_usec,
  91.            t_recursive.tv_usec - t_normal.tv_usec,
  92.            t_common.tv_usec - t_recursive.tv_usec
  93.            );
  94.    
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement