VBとフィボナッチに明るい方、ぜひお願いします。。

質問

VisualBasic2008ExpressEditionにおいて、フィボナッチ数列の剰余の周期性の長さを求めるプログラムを組みましたが、一部正常に動作してくれません。詳しい方がおりましたら、修正点を教えていただけないでしょうか

先に念のため、フィボナッチ数列とその周期について説明しておきます。

まずフィボナッチ数列とは、1,1,2,3,5,8,13,21,34,55,89,144,233,377,610, のような数列のことです。
それぞれの項をある自然数で割った場合、その余りの数には特定の周期性が見られます。具体的な例でいくと、例えば５でそれぞれの項を割り、その余りを書き下していくと

1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0, 1,1,2,3,0,3…

と、あるところから先はそれまでの列の繰り返しになります。この場合、ひと周期の長さは20ということになります。

今回組んだ以下のプログラムは、上記の例のように何らかの自然数でフィボナッチ数列の各項を割った場合、その周期の長さがどうなるかを求めるプログラムです。
しかし、どこかに間違いがあるようで、周期の長さが80以上になるような場合であると、正常に動作してくれません。残念ながら私ではその原因が分からないので、
もしよろしければ修正すべき点を教えていただけないでしょうか？ よろしくお願いいたします。。

Public Class Form1

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

Dim a(1000), b(1000), c, n, x

a(1) = 1 : a(2) = 1 : n = 2

x = Val(TextBox1.Text)

Do

n = n + 1

Label1.Text = n

a(n) = a(n - 2) + a(n - 1)

Label2.Text = a(n)

b(n) = a(n) Mod x

Label3.Text = b(n)

a(n + 1) = a(n - 1) + a(n)

Label4.Text = a(n + 1)

b(n + 1) = a(n + 1) Mod x

Label5.Text = b(n + 1)

If b(n) * b(n + 1) = 1 Then

c = n - 1

Exit Do

End If

Loop

Label6.Text = c

End Sub
End Class

回答No.3

noname#166246 · ベストアンサー

もう見ていないかもしれませんが、さらなる改善案を思いついたので一応。
もともとのプログラムは私のも含めて、一回のループに2回数列計算をしていますが、はじめの計算は前回のループの後半に行ったものと同じなので無駄ですね。

なので、それを省き、かつ、途中経過のTextBoxへの書き込みを省いてみたところ、100,000,000（一億） でも数秒でできましたので一応報告します。

Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
Dim a(3), c, n, x As Integer

a(1) = 1 : a(2) = 1 : n = 2

x = Val(TextBox1.Text)

Do

n = n + 1

a(3) = (a(1) + a(2)) Mod x

If a(2) = 1 AndAlso a(3) = 1 Then

c = n - 2

Exit Do

End If

a(1) = a(2)
a(2) = a(3)

Loop

Label6.Text = c

End Sub

なお、もう一桁多くすると、
Integerの限界を超えてしまうので、最初の宣言文のIntegerを
Longに変えてください。
なお、いっそのこととDecimalにしてしまうと、
急激に遅くなりますのでご注意を。

しかし、10進数できりのいい数値を入れると、
必ずきりのいい数値が求まるんですけど、
なんでなんですかねー。不思議です。
それこそ、だれかこの数列に詳しい人に聞いてみたいです。

100　→　 300
1000　→　 1500
10000　→　 15000
100000　→　 150000
1000000　→　1500000

お礼

rerere123さん、かなり詳しく説明してくださりとても助かりました。
たしかにrerere123さんの仰るように修正したら、格段に計算が速くなりました。本当にありがとうございます。

「きりの良い数値」に関してですが、僕にとってはここからが本題になるので、非常に興味深いところです。大変参考になりました！！

回答No.2

noname#166246

そのときのa(n)の値を表示しなくてもよいならば、
という前提付きですが、ここはひとつ剰余の性質を使っては
いかがでしょう。
a(n+1)の剰余を求めるのに、a(n)とa(n-1)そのものは使わず、
それらの剰余を使えばいいのです。
剰余の数列を使っていくということです。

さらに、nを大きくすると、
aの配列の大きさの問題にぶつかってきりがないので、
使わない部分をシフトしてつぶして使いましょう。

Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click

Dim a(4), c, n, x As Integer

a(1) = 1 : a(2) = 1 : n = 2

x = Val(TextBox1.Text)

Do

n = n + 1

Label1.Text = n

a(3) = a(1) + a(2)
a(3) = a(3) Mod x

Label2.Text = a(3)

a(4) = a(2) + a(3)
a(4) = a(4) Mod x

Label4.Text = a(4)

If a(3) = 1 AndAlso a(4) = 1 Then

c = n - 1

Exit Do

End If

a(1) = a(2)
a(2) = a(3)

Loop

Label6.Text = c

End Sub

20,000を設定したら周期が30,000になりましたが合っていますでしょうか？

回答No.1

うぃず（@Wizard_Zero）

フィボナッチ数列には全く明るくないのですが、周期80以上ともなるとその数値はかなり莫大なものになり、数値がDouble型で処理されているのではないでしょうか？
Double型では、正確な値の計算はできなくなるため、それが原因ではないかと。

正確な計算をするためにDecimal型を指定してみてください。

Dim a(1000), b(1000), c, n, x
　　↓
Dim a(1000) As Decimal, b(1000) As Decimal・・・（略

ただ、Decimal型でコードを組んで試してみたところ、x=50, n=138でオーバーフローしました。x=49までは一応解が出ており、80以上の解も出ていますが、正解を知らないので合っているかは不明です…。
x=25で周期100。これが80以上を示した最初の解です。
最大周期は、x=30, 45で周期120が出ています。

# 全く自信はありません。興味８割で回答してます。

お礼

ありがとうございます！！
自分も試してみましたが、おそらくWizard_Zeroさんのご指摘が正しいと思われます。

私はプログラム専門の者ではないのですが、とはいえdecimalという変数型を知りませんでした。お恥ずかしい…(汗)

今回はありがとうございました！