IchigoJam でフィボナッチ数列 (多倍長)

今日は、
日本語プログラミング言語「なでしこ」 - Qiita Advent Calendar 2025 - Qiita
でフィボナッチ数列を扱う記事が公開された。
そこで、こっちでもフィボナッチ数列を計算してみることにした。
そう、簡単にいうとパクリである。ああ頭が悪い。

プログラム

10 'ﾌｨﾎﾞﾅｯﾁ ｽｳﾚﾂ (ﾀﾊﾞｲﾁｮｳ)
20 CLV:[51]=1:?1
30 S=51-D
40 FORI=0TO50:C=[D+I]+[S+I]+C
50 [D+I]=C%10000:C=C/10000
60 NEXT
70 F=-1:FORI=50TO0STEP-1
80 IF[D+I]ANDF<0F=I
90 NEXT:IFCF=51:?1;ELSE?[D+F];
100 IFF<1GOTO140
110 FORI=F-1TO0STEP-1
120 ?DEC$([D+I]+10000,4);
130 NEXT
140 ?CHR$(10);:D=51-D
150 IF!CGOTO30

DEC$ を使用しているので、古い環境では動かない可能性がある。
それいったら FOR も古い環境では動かないだろ……

実行結果

IchigoKamuy (1.4.1) で実行したところ、約10分で計算が終了した。

シリアル出力の内容

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
(中略)
160131437125022133570186981636530600256034719271619021063640417693436516163698377535248015679488033602845112321108929620534730439060000506398830226180857811739131287777823445209422467744194016647915972857
259098107935652557104489133457117935287501385615468464797658075441635685688364082902818922538578546112563887878124152051556445086889386828976126497605113833423713583754975704308251673170580841059906839650
419229545060674690674676115093648535543536104887087485861298493135072201852062460438066938218066579715409000199233081672091175525949387335374956723785971645162844871532799149517674140914774857707822812507
678327652996327247779165248550766470831037490502555950658956568576707887540426543340885860756645125827972888077357233723647620612838774164351083221391085478586558455287774853825925814085355698767729652157
1097557198057001938453841363644415006374573595389643436520255061711780089392489003778952798974711705543381888276590315395738796138788161499726039945177057123749403326820574003343599955000130556475552464664

解説

フィボナッチ数列は、前2項の和が次の項になる数列である。
値がどんどん大きくなり、IchigoJam BASIC の変数1個で扱える最大値の 32,767 はすぐに超えてしまう。
そこで、複数の変数 (配列) を並べたものを用いて、大きい数を表現する。
今回は、1要素に十進数4桁を格納することにした。
IchigoJam BASIC の配列は 102 要素あるので、半分の 51 要素で1個の数を表すことにした。

今回の多倍長計算は、加算のみを扱う。
加算は、繰り上がりを 0 で初期化し、下の位を表す要素から順に以下を行うことでできる。
今回のプログラムでは、40～60行目でこれを行っている。

1. 対応する要素2個と、繰り上がりの和を求める
2. この要素の値を、この和を(1要素の最大値+1)で割った余りとする
3. 繰り上がりを、この和を(1要素の最大値+1)で割った商とする

今回の多倍長整数を出力する際は、まず 0 でない最上位の要素をそのまま出力し、続いてそれより下位の要素を4桁に0埋めして出力する。
ただし、最後に繰り上がりが残った場合は、それを「1」として出力し、要素を全て0埋めして出力する。
最上位の要素の探索と出力を70～90行目で、下位の要素の出力を100～130行目で行う。
0埋め出力には、
IchigoJam BASIC で非負の数値を十進数で0埋め指定桁数出力する #BASIC - Qiita
で紹介した方法を用いた。

140行目で足される数と足す数を入れ替え、150行目で次の計算に移る。
ただし、最後に繰り上がりが残っていた場合は、このプログラムではもう計算結果を格納できないため、終了する。

裏を返せば、次の計算に移る場合は必ず繰り上がりが 0 になっているので、繰り上がりを明示的に初期化しなくてもよい。
計算開始時には、CLV により繰り上がりも初期化される。

まとめ

IchigoJam BASIC の配列を利用し、1要素に十進数4桁を格納する形式で表現できるだけフィボナッチ数列を計算することができた。

※IchigoJamはjig.jpの登録商標です。