我已经实现了 fractran 并在 C 中迭代地使用序列。
https://mathworld.wolfram.com/FRACTRAN.html
我可以生成正确的结果，但我想以小时而不是几周为单位测量时间......我有一台 2 CPU Ultrasparc III 机器（区域）。pthreads 略微提高了吞吐量。
我必须遍历每个“分数”以确定第一个成功的操作。代码片段 -
for(j=0; j< 14 ;j++)
{
mpz_mul(tmp, elem, num[j]);
mpz_tdiv_qr(q, r, tmp, denom[j]);
if ( mpz_cmp(r, zero) == 0)
{
mpz_set(elem, q);
break;
}
}
每个“分数”一次 gmp 乘法，一次除法，一次比较。是的，这是蛮力。
建议？
如果你分析过它，你会发现问题是分裂。这是您要避免的真正缓慢的操作，但避免乘法也不会受到伤害。
真正的 FRACTRAN 程序（是的，我将使用“真正的 FRACTRAN 程序”这个短语，就好像有这样的东西）在素因数分解方面倾向于在更深层次上工作。例如，考虑这个实现 GCD 的程序（由我编写；不客气）：
2/7 3/11 13/17 19/23 51/65 1/13 46/95 1/19 5/6 91/2 209/3
你给它 2^p 3^q 它返回 5^gcd(p,q)。
这表明实现 FRACTRAN 的更好方法是使用完全分解的数字。而不是 46/95（上述程序中的一条指令），您可以将其表示为一个由素数索引的整数数组：
# 2, 3, 5, 7, 11, 13, 17, 19, 23
{ 1, 0, -1, 0, 0, 0, 0, -1, 1 }
# Verify that 2^1 5^-1 19^-1 23^1 = 46/95
机器状态类似地是一个由素数索引的数组。要执行一条指令，请确保执行减法运算不会使状态下溢，如果检查成功，只需将两个数组按元素相加即可。
有两个悬而未决的问题需要考虑。
首先，数组应该有多长？也就是说，你需要多少个素数？值得庆幸的是，这可以从指令流中静态确定。如果输入中存在程序中未提及的素数，则可以将它们复制到输出中。所以选择程序的数组大小，你应该没问题。
另一个问题是每个数组条目的容量应该有多大。对于指令，再一次，可以静态确定。但是，对于机器状态，尚不清楚。当然，对于任何人来说，64 位都应该足够了（著名的遗言），但是如果您尝试在 FRACTRAN 中实现 FRACTRAN，则可能不是。使事情复杂化的是，真正的 FRACTRAN 程序倾向于使用大量标志（即在机器状态下其幂始终为 0 或 1 的素数）作为伪程序计数器，因此为每个条目使用 MPZ 可能会很浪费。
所以对于机器状态，我会考虑混合。如果一个素幂适合一个机器字，请使用一个机器字。否则，请使用 MPZ 或（因为您只需要加法和减法）本土的等价物。如果您可以使用 SIMD 指令，则可获得奖励积分。
祝你好运，请随时通知我。我很想在 github 上看到这个。