VBAHaskellでのコラッツ数列（その2）

以前この記事で　コラッツの問題 - Wikipedia　にある数列をVBAHaskellで生成するというのをやってみた。

mmyymmdd.hatenablog.com

今回は、多倍長整数を使ってもっと多くの初期値で試してみた。
このついでに以下の3つのモジュールに変更をしたので、その気があればダウンロードしてお試し願います。
VBA/misc_ratio.bas at master · mYmd/VBA · GitHub（bigIntの実装がある）
VBA/Haskell_2_stdFun.bas at master · mYmd/VBA · GitHub
VBA/Haskell_4_vector.bas at master · mYmd/VBA · GitHub

まずはコラッツ列の漸化式を定義する。
とても泥臭～いコードだが、数の大きさによって Long と 多倍長整数 bigInt をそのつど使い分けるようにしている。bigInt の計算はとても遅いからだ。

Function collatz_u(ByRef i As Variant, ByRef dummy As Variant) As Variant
    If IsNumeric(i) Then
        If 0 = i Mod 2 Then
            collatz_u = i / 2
        Else
            If i <= 715827882 Then    '715827882 = (2 ^ 31 - 2) / 3
                collatz_u = i * 3 + 1
            Else
                collatz_u = bigInt_plus(bigInt_mult(i, 3), 1)
            End If
        End If
    Else
        If bigInt_equal(bigInt_mod(i, 2), 0) Then
            collatz_u = bigInt_divide(i, 2)
            If bigInt_less(collatz_u, 2 ^ 31 - 1) Then
                collatz_u = CLng(bigInt2double(collatz_u) + 0.1)
            End If
        Else
            collatz_u = bigInt_plus(bigInt_mult(i, 3), 1)
        End If
    End If
End Function

    Function p_collatz_u(Optional ByRef firstParam As Variant, Optional ByRef secondParam As Variant) As Variant
        p_collatz_u = make_funPointer(AddressOf collatz_u, firstParam, secondParam)
    End Function

---

そして次に、初期値を与えてコラッツ数列を生成する関数を書く。 generate_while_not は VBA/Haskell_1_Core.bas at master · mYmd/VBA · GitHub にある関数で、述語による条件が「満たされない間」繰り返し関数適用の履歴を生成するものだ。コラッツ数列の終了条件は値が 1 の項が発生することなので、述語 p_bigInt_equal(1) で表せる。

' // limit < 0 なら回数上限制約なし
Function collatz_seq(ByRef i As Variant, ByRef limit As Variant) As Variant
    collatz_seq = generate_while_not(i, p_bigInt_equal(1), p_collatz_u, limit)
End Function

    Function p_collatz_seq(Optional ByRef firstParam As Variant, Optional ByRef secondParam As Variant) As Variant
        p_collatz_seq = make_funPointer(AddressOf collatz_seq, firstParam, secondParam)
    End Function

---

これで出来上がりなので、とりあえず100万までやってみる。

' // 1から1000000までの整数を初期値としたコラッツ配列を生成（長時間かかる）
m = mapF(p_collatz_seq(, -1), iota(1, 1000000))
' // 列の最大の長さを求める
?foldl1(p_max, mapF(p_sizeof, m))
 525
' // 長さ525の配列を探す
?find_pred(p_equal(525), mapF(p_sizeof, m))
 837798
' // 見てみる（この記事では途中を省略）
printM m(837798)
  837799  2513398  1256699  3770098  1885049  5655148  2827574   ・・・
  ・・・ 53  160  80  40  20  10  5  16  8  4  2  1

'// m(837798)の中の最大数は何か？
?bigInt2Str(foldl1(p_bigInt_max, m(837798)))
2974984576

これは確かに VBA の Long の最大数を超えている。

qiita.com