ソースコードの説明.

Hash 単純なハッシュ

上式いおいて、a_nx^n、a_{n-1}x^{n-1}、...、a_1x、a_0の各項を独立に計算して加えるという単純な方法では、n(n+1)/2+n回の掛け算とn回の足し算を行うことになる。具体例として、a_0=1、a_1=2、a_2=3、a_3=4、a_4=5のf(x) = 5x^4 + 4x^3 + 3x^2 + 2x + 1について考える。

• f_4 = f_3 ・x + a_0
• f_3 = f_2 ・x + a_1
• f_2 = f_1 ・x + a_2
• f_1 = f_0 ・x + a_3
• f_0 = a_4

• f_i = f_{i-1}・x + a_{n-i}
• f_0 = a_n

/*
 *-----------------------------
 *   Horner（ホーナー）の方法
 *-----------------------------
 * Great by liang@Ryukyus
 * Compiler : gcc (GCC) 4.1.2 20080704 (Red Hat 4.1.2-48)
 * Date : 28/12/2010
 */

#include <stdio.h>

double fn(double,double *,int);
int main(void){

  double a[]={1,2,3,4,5};
  double x;

  for(x=1; x<=5;x++){
    printf("fn(%f)=%f\n",x,fn(x,a,4));
  }
  return 0;
}

double fn(double x, double a[],int n){

  double p;
  int i;

  p = a[n];
  for(i=n-1; i>=0; i--){
    p = p*x+a[i];
  }
  return p;
}

fn(1.000000)=15.000000
fn(2.000000)=129.000000
fn(3.000000)=547.000000
fn(4.000000)=1593.000000
fn(5.000000)=3711.000000

• 漸化式の例
  • 階乗（かいじょう）
    • n! = n・(n-1)!
    • 0! = 1
  • 冪乗（べきじょう）
    • x^n = x・x^{n-1}
    • x^0 = 1
  • フィボナッチ（Fibonacci）数列
    • 1,1,2,3,5,8,13,21,34,55,...という数列は
    • F_n = F_{n-1} + F_{n-2}
    • F_1 = F_2 = 1
  • テイラー展開 （２章２−３参照）
    • e^xをテイラー展開するとe^x = 1 + x/1! + x^2/2! + x^3/3! + ...となる。このときの第n項Enは
    • E_n = x/n・E_{n-1}
    • E_0 = 1