Fractran: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
。
解释的程序作为一个以 10 为基数的列表嵌入到单个以 11 为基数的数字中,使用数字“a”来标记边界,除了最后。加法程序 [3/2] 被编码为
int("3a2", 11) = 475.
乘法程序 [455/33, 11/13, 1/11, 3/7, 11/2, 1/3] 被编码为
int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657
这是一个非常大的数字。
第一个测试向量在不到一秒的时间内完成,在 4545 次迭代后产生了预期的结果,并在 6172 次迭代后停止。这是完整的输出。
不幸的是,当我尝试第二个测试向量时,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 }
}