はじめに
某高専の皆さん、3年生で円周率を1000桁計算しましたね？
さて、その後3年の春に初心者から扱える円周率計算ソフトScratch(+TurboWarp)でうっかり1000桁求めてしまったため(50sec)、今年は円周率ネタがないということで今年はBFで円周率を計算したいと思います。
ゴールは3/14になりますが、諦めるか間に合わない可能性の方が高いです。ホワイトデーって何ですか？
問題設定
はじめに問題設定を考えます。
今回は加減乗除で全部行える$\arctan$系公式でやってみようということで次のような問題設定にしました。
- マチンの公式を用いて円周率を10桁(256進数で)求める
$$\pi = 16\arctan\frac{1}{5} - 4\arctan\frac{1}{239}$$
期間的に桁数はこれで許してください。
基本的な計算方針
$\arctan\frac{1}{x}$は(ライプニッツ式による)マクローリン展開式を使うことで次のように求めていきます。
\arctan\frac{1}{x} = \sum^{\infty}_{k=0}\frac{(-1)^k}{2k+1}\cdot \frac{1}{x^{2k+1}} = \sum^{\infty}_{k=0}\frac{(-1)^k}{A_k}\cdot \frac{1}{B_k}
ここで、 $A_k=2k+1, B_k = x^{A^k} = x^{2k+1}$としています。
これをもとにすると、和記号の値の計算手順は次のようになります。
- $A_k$の更新 ($A_k$ = $A_{k-1}+2$)
- $B_k$の更新 ($B_k$ = $B_{k-1}\times x^2$)
- $A_k$と$B_k$の積を計算し$C_k$とする
- $(-1^k)\times B^{D}$から$C_k$を割った値が和記号の中の値$S_k$となる.
- $S_0$から$S_{N}$を足し合わせる. 終了条件は$S_N < 1$
- 合計値を$B^{D}$で割る
ここで、$B$は基数(BFでは$B=256$)、$D$は桁数(ここでは$D=10$)になります.
このように、四則演算ができれば大体OKということがわかります。
BFってなんやねん
Blainf**k<規制済>は8つの記号とポインタについての知識を覚えるだけで扱えるチューリング完全な言語です。
覚えるべき記号は次のようになります。
- > ポインタを１進める
- < ポインタを１戻す
- + ポインタの指す要素の値を１増やす
- - ポインタの指す要素の値を１減らす
- . ポインタの指す要素の値を外に出力
- , 外から値を入力して、 ポインタの指す場所へ入れる
- [ ポインタの指す要素の値が 0 だったら対応する次の ] までジャンプ
- ] 対応する前の [ までジャンプ
Scratchよりも円周率を求めるのに適していそうですね
BFによる多倍長加算
今回は加算の実装方針だけ考えていきます。
0番地の値に1番地の値を加算する場合にはインクリメントとデクリメントを多用することで次のようにあらわすことができます.
> // 加数(1番地)へ移動
[ // 現在のポインタ値が0でなければ(参照ポインタが加数になるようループ終わりに1番地へ移動する必要がある)
- // 加数を1減らす
< // 被加数(0番地)へ移動
+ // 被加数を1増やす
> // 加数(1番地)に移動(参照ポインタ問題)
]
ここに繰り上がり処理を付加すれば良いというわけになります。
その桁の加算結果が基数$B$以上の時に繰り上がりが発生します。
加算結果が基数$B$以上ということは、今回インクリメントにより加算を実現しているため、もし繰り上がりが発生する場合にはインクリメントをしていったときにどこかで「値が$B$になる瞬間」があるというわけになります。
さらに、符号なし整数型の特徴として、加算結果は$\mod B$で格納されることを考えると、繰り上がりが発生する場合には何度もインクリメントをする中でポインタの中身がどこかで$0$になる瞬間が一度あるということがわかります。
そのため、BFの記号 [ (現在位置のポインタ値が0なら記号 ] へ移動する)をうまく用いることで繰り上げ処理をすることができます。
以上のことから、0番地の値に1番地の値を加算し、2番地をキャリ、3番地を条件分岐脱出用メモリ(0代入)とする場合には、次のようにコードを書くことができます。
> // 加数へ移動
[
- // 加数減算
> // キャリへ移動
+ // 「一旦」キャリ加算
<< // 被加数へ移動
+ // 被加数加算
[ // 被加数が0でなければ
>> // キャリへ移動
- // キャリの加算をなかったことにする
> // ループ脱出用メモリへ移動
]
<< // 加数へ戻る
]
上のコードのコメントを消したものが下のコードになります。
>[->+<<+[>>->]<<]
2桁どうしの加算では、0-1番地の値に2-3番地の値を加算、4-5番地をキャリ、6番地を条件分岐脱出用メモリ(0代入)とする場合には、次のようにコードを書くことができます.
>>> // 加数0桁目へ移動
[
- // 加数0桁目減算
>> // キャリ0桁目へ移動
+ // 「一旦」キャリ0桁目加算
<<<< // 被加数0桁目へ移動
+ // 被加数加算
[ // 被加数が0でなければ
>>>> // キャリ0桁目へ移動
- // キャリ0桁目の加算をなかったことにする
> // ループ脱出用メモリへ移動
]
<<< // 加数0桁目へ戻る
]
< // 加数1桁目へ移動
[
- // 加数1桁目減算
>> // キャリ1桁目へ移動
+ // 「一旦」キャリ1桁目加算
<<<< // 被加数1桁目へ移動
+ // 被加数加算
[ // 被加数が1でなければ
>>>> // キャリ1桁目へ移動
- // キャリ1桁目の加算をなかったことにする
>> // ループ脱出用メモリへ移動
]
<<<< // 加数1桁目へ戻る
]
>>> // キャリ0桁目へ移動
[
- // キャリ0桁目減算
< // キャリ1桁目へ移動
+ // 「一旦」キャリ1桁目加算
<<<< // 被加数1桁目へ移動
+ // 被加数加算
[ // 被加数が1でなければ
>>>> // キャリ1桁目へ移動
- // キャリ1桁目の加算をなかったことにする
>> // ループ脱出用メモリへ移動
]
< // キャリ0桁目へ戻る
]
さて、これで準備が整いました。10桁の場合のコードを記述します。
0-9番地の値に10-19番地の値を加算、20-29番地をキャリ、30番地を条件分岐脱出用メモリ(0代入)とする場合には、次のようなコードになります(あってるか不安)。
>>>>>>>>>>>>>>>>>>>
// 0桁目の加算
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->]<<<<<<<<<<<]
<
// 1桁目の加算+キャリ
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>]<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>]<]
<<<<<<<<<<<<
// 2桁目の加算+キャリ
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>]<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>]<<]
<<<<<<<<<<<<
// 3桁目の加算+キャリ
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>]<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>]<<<]
<<<<<<<<<<<<
// 4桁目の加算+キャリ
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>]<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>]<<<<]
<<<<<<<<<<<<
// 5桁目の加算+キャリ
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>]<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>]<<<<<]
<<<<<<<<<<<<
// 6桁目の加算+キャリ
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>]<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>]<<<<<<]
<<<<<<<<<<<<
// 7桁目の加算+キャリ
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>]<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>]<<<<<<<]
<<<<<<<<<<<<
// 8桁目の加算+キャリ
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>]<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>]<<<<<<<<]
<<<<<<<<<<<<
// 9桁目の加算+キャリ
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
まとめ
一応完成はしましたがBFでは多倍長加算だけでもとんでもないことになりました。
次は多倍長乗算について考えていこうと思います。それではまた。