このページではCodeIQ&note{codeiq-official:CodeIQ|ITエンジニアのための実務スキル評価サービス, 2015-12-06閲覧};で結城浩先生から出題されたマヨイドーロ問題について解説しています。

マヨイドーロ

幾つか手で動かしてみる

N=0のとき

N=1のとき

N=2のとき

N=3のとき

まとめてみる

単純な実装

単純な実装の限界

一般項を用いた実装

#geshi(C++,number){{

#include <cmath> const double positivleHalfRoot5 = 1.618033988749894848204586834365638117720309179805762862135448; const double negativeHalfRoot5 = -0.61803398874989484820458683436563811772030917980576286213544; const double inverseRoot5 = 0.447213595499957939281834733746255247088123671922305144854179;

unsigned long long powerComputationFibonacciNumber(int n) {

	double retValue;
	retValue  = pow(positivleHalfRoot5, n);
	retValue -= pow(negativeHalfRoot5, n);
	retValue *= inverseRoot5;
	return (unsigned long long)(retValue + 0.5f);

} }}

一般項を用いた実装の限界

n73747576777879
べき乗で求めた結果8065155330493931304969544928657211148507797805034164546229067065527939700884756894439432379146414472334024676218
足し算で求めた結果8065155330493931304969544928657211148507797805034164546229067075527939700884757894439432379146414472334024676221
桁数(10進数)15桁16桁16桁16桁16桁16桁17桁
ここまで計算結果OK丸め誤差が整数として現れる桁が上がる度に
丸め誤差がどんどん大きくなる

計算速度と精度を考慮した実装

計算速度と精度を考慮した実装での限界

N   フィボナッチ数       フィボナッチ数の16進数表現
89  1779979416004714189  0x18B3C1D91E77DECD
90  2880067194370816120  0x27F80DDAA1BA7878
91  4660046610375530309  0x40ABCFB3C0325745
92  7540113804746346429  0x68A3DD8E61ECCFBD
93  12200160415121876738 0xA94FAD42221F2702 ←ここでMSBが埋まる(=64bitすべて使って表現が必要になる)
94  1293530146158671551  0x111F38AD0840BF6BF ←オーバーフローが発生

多倍長整数の実装の前に

感想


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2015-12-17 (木) 12:33:38