2011年12月4日日曜日

平方根の連分数展開

Norman Lehmerの論文に, factor stencilはNの連分数展開でも使えると書いてあった.

その始めの方. まずx1=√N=q1+1/x2とおく. 但し, q1はNの平方根の最大整数. 同様にx2=(√N+P2)/Q2=q2+1/x3のようにする. (ははぁ. TAOCPの連分数展開のUとVがPとQになっているわけだ.)

順に進んで, xn=(√N+Pn)/Qn=qn+1/xn+1になるというまでは明快だが, その後に
「従って
Pn=qn-1Qn-1-Pn-1,
Qn=qn-1(Pn-1-Pn)+Qn-2
がexpediouslyに得られる」
と書いてある.

上の方の式は11月30日のブログの(4)と(5)の間にあるUn=AnVn-Un-1と同じだが, 下の方の式はどう導くか.

今回のブログはその計算法である.

(0)はxnの標準形である. (1)はxn-1で, そのxnに(0)を代入し, 前回のように計算を続けると(1)の最後になる. (1)の最初と分母を等しいとしたのが(2)で, ただちに(3)と書ける. 分子の√Nの後に続く項を等しいとしたのが(4)で, 途中で(3)を利用する. PnとPn-1を交換したのが上の式(5)だ.

一方, (3)の添字を1減らしたのが(6)で, (3)-(6)が(7),(8)である. 1/Qn-1は, (5)を移項した(9)から(10)のように得られ, これを(8)に代入すると(11)を経て, 下の方の式(12)になるのが分かる.

漸化式はP1=0, Q1=1から始まるが, 問題は, Qn-2があるので, Q0が必要なことだ.

実はQ0=Nなのだが, この計算は次の通り.

これで, 連分数のP,Q,qが次々と求まることになる. なんだかまた久しぶりにこのような計算をした.

0 件のコメント: