円周率の計算 (4)

8 月 9 日版のプログラムを改訂し、ATmega168 使用の Arduino でも修正なく実行可能にした 8 月 13 日版のプログラムを作りました。 バイナリ・スケッチ・サイズは 5602 バイトです。
プログラム・リストは次回、掲載します。
今回のプログラムでは、arctan級数の計算で、多倍長整数配列が 2 本必要なアルゴリズムから、多倍長乗算の手間が増加するのと引き換えに多倍長整数配列が 1 本ですむアルゴリズムに変更しました。
そのため、内蔵 RAM が 1 Kバイトの ATmega168 でも 10 進 608 桁の計算ができるようになりました。
また、いわゆる「Spigot」アルゴリズムによる計算も追加しました。 「8 ビット」縛りでは、有効桁数は 38 桁です。
各公式ごとの実行結果を下の表にまとめました。

公式 有効桁数 実行時間 (s)
(加減算のみ)
実行時間 (s)
(シフトあり)
多倍長配列
(バイト)
Spigot 38 --- --- 128 x 1
Machin 180 2.0 0.3 77 x 2
Gauss 322 6.8 0.9 137 x 2
Stoermer 451 13.7 1.9 191 x 2
atan255 608 36.0 4.9 255 x 2

Spigot アルゴリズムでは実行時間の計測を行っていません。
加減算命令だけの 608 桁計算では、前回のプログラムで約 30 秒のところ、今回のプログラムでは約 36 秒かかっており、実行時間が増加しています。
乗算 / シフト命令ありの場合の結果では、その差は 0.1 秒程度になっており、ATmega がハードウェア乗算命令を持っていることが有利に働いています。
加減算命令に限った場合の実行結果を下に示します。

Spigot (nterms = 128)
pi = 3.
1415926535 8979323846 2643383279 5028841927 9

Machin (digits = 182), Elapsed time = 2027 ms
pi = 3.
1415926535 8979323846 2643383279 5028841971 6939937510 
5820974944 5923078164 0628620899 8628034825 3421170679 
8214808651 3282306647 0938446095 5058223172 5359408128 
4811174502 8410270193 8521105559 51

Gauss (digits = 325), Elapsed time = 6849 ms
pi = 3.
1415926535 8979323846 2643383279 5028841971 6939937510 
5820974944 5923078164 0628620899 8628034825 3421170679 
8214808651 3282306647 0938446095 5058223172 5359408128 
4811174502 8410270193 8521105559 6446229489 5493038196 
4428810975 6659334461 2847564823 3786783165 2712019091 
4564856692 3460348610 4543266482 1339360726 0249141273 
7245870066 0631558817 48768

Stoermer (digits = 453), Elapsed time = 13718 ms
pi = 3.
1415926535 8979323846 2643383279 5028841971 6939937510 
5820974944 5923078164 0628620899 8628034825 3421170679 
8214808651 3282306647 0938446095 5058223172 5359408128 
4811174502 8410270193 8521105559 6446229489 5493038196 
4428810975 6659334461 2847564823 3786783165 2712019091 
4564856692 3460348610 4543266482 1339360726 0249141273 
7245870066 0631558817 4881520920 9628292540 9171536436 
7892590360 0113305305 4882046652 1384146951 9415116094 
3305727036 5759591953 0921861173 8193261179 3105118548 
036

atan255 (digits = 610), Elapsed time = 35954 ms
pi = 3.
1415926535 8979323846 2643383279 5028841971 6939937510 
5820974944 5923078164 0628620899 8628034825 3421170679 
8214808651 3282306647 0938446095 5058223172 5359408128 
4811174502 8410270193 8521105559 6446229489 5493038196 
4428810975 6659334461 2847564823 3786783165 2712019091 
4564856692 3460348610 4543266482 1339360726 0249141273 
7245870066 0631558817 4881520920 9628292540 9171536436 
7892590360 0113305305 4882046652 1384146951 9415116094 
3305727036 5759591953 0921861173 8193261179 3105118548 
0744623799 6274956735 1885752724 8912279381 8301194912 
9833673362 4406566430 8602139494 6395224737 1907021798 
6094370277 0539217176 2931767523 8467481846 7669405132 
0005681261