突然常務に、
定理の適用例を与えないといけないのですが桁数が大きすぎて手計算で確認無理！！
U_n=0,U_1=1,U_n=PU_{n-1}-QU_{n-2}
でPとQを変えると数列が変わるのですが、PとQを指定してその数列の第何項目ってのが知りたいのが一つ目です
次が、ある数aをnで割ったときの余りを計算したいのです。
とか言われて、数列の計算はともかく割り算はなんでだと思っていたら、
nはそんなでもないと思うのですがaはとりあえず日本語では読めないくらいにはなるかなぁ
と言われてウイスキーを吹いたのが昨日の話。
とりあえずdoubleで計算してみたが、307桁まで扱えたところで所詮有効桁数15桁。確認例として提示されたP=1,Q=-1,n=100の354224848179261915075すら計算できません。
3垓程度ならlong long intに収まるけれどコンパイラに依存するし、おとなしく桁分割するか思っていたところ、
結局欲しいのが、（P,Q）=（3,5）のときだと550項目と552項目を551で割った余りが欲しいだけなので
数列を逐次あまりに置き換えて計算するとかどうでしょう？
と妥協案が出たので対応。
どうやら期待する値はとれた模様。
流石に余だけの計算ならn=41356154とかわけわかんない数字を提示されても一瞬で計算できるもんですね。周波数の暴力というか。
寝て。起きて。せっかくなので桁分割。
一定の桁で区切って配列に突っ込み、桁上がりと桁借りの処理を自前ですればいいわけだ。
各要素をintにするとして有効桁数は9桁。PもしくはQを乗じた結果がこれを溢れないように桁を区切る必要がある。
とりあえず作ってみたが、354224848179261915075は問題なし。
配列要素数の限界 * 区切り桁数がそのまま計算可能桁数となるので、仮に要素数がunsigned int分持てるとして、さらにPとQが1桁であることが保証されるなら区切りは8桁にでき、34359738368桁まで計算可能ということに？
まぁ、当然要素数の限界より先にメモリが限界に達するだろうわけで、仮に1GB使用可能で区切り桁数は有効桁数をPもしくはQと折半で使うとすると、3億桁くらいまでか。
出力のこととか考えると現実的には100万桁くらいがせいぜいな気はしますが。
と、ここで落札しつつ夜間試験に向かうのでした。
RSS1.0
