フィボナッチ数列を計算してみよう1 C言語 の続きです。

前回はC言語だけでフィボナッチ数列を計算していました。

それだけだとunsigned long型の上限があり、大きな数字が計算できません。

今回はgmpライブラリを使ってフィボナッチ数列 1000001番目を計算してみます。

fibo.cというファイル名で保存してください。 

//gcc fibo.c -o fibo -lgmp
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <gmp.h>

void omg_i_love_leonardo_of_pisa(uint32_t num, mpz_t * result) 
mpz_t retval, last, tmp;
mpz_init(retval);
  mpz_init(last);
mpz_init(tmp);

uint32_t i = 1;
if(num == 0) {
return;
}
  mpz_set_ui(retval, 1U);
mpz_set_ui(last, 0U);

for(; i < num; i++) {
mpz_set(tmp, retval);
mpz_add(retval, retval, last);

mpz_set(last, tmp);
}

mpz_set(*result, retval);
 }

int main() 
{
uint32_t num;
mpz_t fibo;
mpz_init(fibo);

//1000001
omg_i_love_leonardo_of_pisa(1000001, &fibo);
mpz_out_str(stdout, 10, fibo);
printf("\n");
return 1;
}

$ gcc fibo.c -o fibo -lgmp
$ ./fibo

すぐに計算結果が出てきます。
科学技術すげー。

http://www.wolframalpha.com/input/?i=fibonacci+1000001


実はgmpにはmpz_fib_uiというフィボナッチ関数が用意されています。
mpz_fib_ui関数を実行するだけフィボナッチ数列を求めることができます。

fibo3.cというファイル名で保存してください。
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <gmp.h>

int main()
{
  int n = 1000000;
  mpz_t fm2;
  mpz_inits(fm2, NULL);
  mpz_fib_ui(fm2, n);
  gmp_printf("fib(%d) = %Zd\n", n, fm2);
  return 1;
}
 
$ gcc fibo3.c -o fibo3 -lgmp
$ ./fibo3
 
参考サイト
1,000,000th Fibonacci Number One-Liner in C