フラクトラン：84分数
FTEVAL = [197*103/(2^11*101), 101/103, 103*127/(2*101), 101/103, 109/101,
2*23/(197*109), 109/23, 29/109,197*41*47/(31*59), 11^10*53/(127*197), 197/53,
37/197, 7^10*43/(11^10*37), 37/43, 59/(37*47), 59/47, 41*61/59, 31*67/(41*61),
61/67, 7*67/(127*61), 61/67,101/71, 73/(127^9*29), 79/(127^2*73),
83/(127*73), 89/(2*29), 163/29, 127^11*89/79, 337/83, 2*59/89, 71/61,
7*173/(127*163), 163/173, 337*167/163, 347/(31*337), 337/347, 151/337,
1/71,19*179/(3*7*193), 193/179, 157/(7*193), 17*181/193, 7*211/(19*181),
181/211, 193/181, 157/193, 223/(7*157), 157/223, 281*283/239,
3*257*269/(7*241), 241/269, 263/241, 7*271/(257*263), 263/271, 281/263,
241/(17*281), 1/281, 307/(7*283), 283/307, 293/283, 71*131/107, 193/(131*151),
227/(19*157), 71*311/227, 233/(151*167*311), 151*311/229, 7*317/(19*229),
229/317, 239*331/217, 71*313/157, 239*251/(151*167*313), 239*251/(151*313),
149/(251*293), 107/(293*331), 137/199, 2^100*13^100*353/(5^100*137),
2*13*353/(5*137), 137/353, 349/137, 107/349, 5^100*359/(13^100*149),
5*359/(13*149), 149/359, 199/149]
これは完全に手書きです。私は物事をより明確に表現できるように疑似言語を作成しましたが、コンパイラーを作成せず、最適化されたFractranコードを直接作成することを選択しました。
FTEVALは入力を受け取り3^initial_state * 5^encoded_program * 199、中間結果を生成3^interpreted_program_state * 199し、で割り切れる数で完全に停止し233ます。
解釈されたプログラムは、単一の基数11の数字の中に基数10の数字のリストとして埋め込まれ、最後を除いて境界を示すために数字「a」を使用します。追加プログラム[3/2]は次のようにエンコードされます
int("3a2", 11) = 475.
乗算プログラム[455/33、11 / 13、1 / 11、3 / 7、11 / 2、1/3]は次のようにエンコードされます。
int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657
これは本当に大きな数です。
最初のテストベクトルは1秒未満で終了し、4545回の反復後に目的の結果を生成し、6172回の反復後に停止しました。これが完全な出力です。
残念ながら、2番目のテストベクトルを試したときにsageは失敗しました（ただし、プライム指数ベクトルを使用したNickの実装では機能すると思います）。
ここのスペースは本当に小さすぎてすべてを説明できません。しかし、これが私の擬似コードです。うまくいけば、私は数日以内に私のプロセスを書き留めます。
# Notations:
# %p
# designates the exponent of prime factor p that divides the
# current state.
# mov x y
# directly translates to the fraction y/x; its meaning: test if x divides
# the current state, if so divide the current state by x and multiply it by
# y. In effect, the prime exponents of x and y are exchanged. A Fractran
# program only comprises of these instructions; when one is executable, the
# program continues from the beginning.
# dec x => mov x, 1
# wipes out all factors of x
# inc x => mov 1, x
# this form is here for the sake of clarity, it usually appears in a
# loop's entry statement and is merged as such when compiled
# sub n ret m {...}
# conceptually represents a Fractran sub-program, which will execute just
# like a normal Fractran program, that is, the sub-program's statements
# execute when triggered and loop back. The sub-program only exits when none of
# its statement is executable, in which occasion we multiply the program's
# state by m. We can also explicitly break out early on some conditions.
# It is also possible to enter a sub-prorgram via multiple entry points and
# we must take care to avoiding this kind of behavior (except in case where
# it is desirable).
# entry point 101: return 29
# Divide %2 modulo 11:
# - quotient is modified in-place
# - remainder goes to %127
sub 101 ret 101 { mov 2^11, 197 }
sub 101 ret 109 { mov 2, 127 }
sub 109 ret 29 { mov 197, 2 }
# entry point 59: return 61
# Multiply %127 by 10^%31 then add result to %7,
# also multiply %31 by 10 in-place.
sub 59 ret 41*61 {
mov 31, 197*41
sub 197 ret 37 { mov 127, 11^10 }
sub 37 { mov 11^10, 7^10 }
}
sub 61 ret 61 { mov 41, 31 }
sub 61 ret 61 { mov 127, 7 } # the case where %31==0
# entry point 71: return 151 if success, 151*167 if reached last value
# Pop the interpreted program stack (at %2) to %7.
sub 71 {
# call sub 101
inc 101
# if remainder >= 9:
mov 29*127^9, 73
# if remainder == 11, goto 79
mov 73*127^2, 79
# else:
# if remainder == 10, goto 83
mov 73*127, 83
# else:
# if quotient >= 1: goto 89
mov 29*2, 89
# else: goto 163
mov 29, 163
# 79: restore remainder to original value, then goto 89
mov 79, 127^11*89
# 83: reached a border marker, ret
mov 83, 337
# 89: the default loop branch
# restore quotient to original value, call 59 and loop when that rets
mov 2*89, 59
mov 61, 71
# 163: reached stack bottom,
# ret with the halt signal
sub 163 ret 337*167 { mov 127, 7 }
# 337: clean up %31 before ret
sub 337 ret 151 { dec 31 }
}
# entry point 193, return 157
# Divide %3 modulo %7:
# - quotient goes to %17
# - remainder goes to %19
sub 193 ret 17*181 {
mov 3*7, 19
}
mov 7*193, 157
sub 181 ret 193 { mov 19, 7 }
mov 193, 157
sub 157 ret 157 { dec 7 }
# entry point 239: return 293
# Multiply %17 by %7, result goes to %3
mov 239, 281*283
sub 241 { mov 7, 3*257 }
sub 263 ret 281 { mov 257, 7 }
mov 281*17, 241
sub 283 ret 293 { dec 7 }
# entry point 107: return 149 if success, 233 if stack empty
# Pop the stack to try execute each fraction
sub 107 {
# pop the stack
inc 71*131
# 151: popped a value
# call divmod %3 %7
mov 131*151, 193
# if remainder > 0:
mov 19*157, 227
# pop and throw away the numerator
mov 227, 71*311
# if stack is empty: halt!
mov 151*167*311, 233
# else: call 239 to multiply back the program state and gave loop signal
mov 151*311, 229
sub 229 ret 239*331 { mov 19, 7 }
# else: (remainder == 0)
# pop the numerator
mov 157, 71*313
# clear the stack empty signal if present
# call 239 to update program state and gave ret signal
mov 151*167*313, 239*251
mov 151*313, 239*251
# after program state is updated
# 313: ret
mov 293*251, 149
# 331: loop
mov 293*331, 107
}
# main
sub 199 {
# copy the stack from %5 to %2 and %13
sub 137 ret 137 { mov 5^100, 2^100*13^100 }
sub 137 ret 349 { mov 5, 2*13 }
# call sub 107
mov 349, 107
# if a statement executed, restore stack and loop
sub 149 ret 149 { mov 13^100, 5^100 }
sub 149 ret 199 { mov 13, 5 }
}