performance - Project Euler #20 的算法缓慢

这是我要解决的问题:http://projecteuler.net/problem=20(找到 100 中的数字之和!)

我正在使用 Lua，它只有 double 作为数字类型，所以我不得不手动处理它。我使用的代码与我在问题 16 中使用的代码几乎相同，它们是相似的(找到 2^1000 中的数字总和)。但是，这一次问题似乎超出了我的算法在相当长的时间内解决的范围 - 它达到了大约 32!之前我必须等待超过 10 秒才能计算下一个总数，然后是 34!它花费的时间比我等待的要长。有什么办法可以加快速度(使用“原始”Lua - 而不是 LuaJIT 或类似的东西)？

local sum = {1}
for i=1,100 do
    local carry = 0
    for v=1,#sum do
        local c = carry
        carry = 0
        local t = sum[v] * i
        while t >= 10 do
            t = t - 10
            carry = carry + 1
        end
        local s = t + c
        while s >= 10 do
            s = s - 10
            carry = carry + 1
        end
        sum[v] = s
    end
    if carry > 0 then
        sum[#sum+1] = carry
    end
    print(""..i.."! = "..getCharactersReversed(sum))
end

最佳答案

您的问题是 (n+1)! 的十进制表示的长度可能比 n! 的长度长一倍以上。这首先发生在 n == 14 ，

14! =   87178291200
15! = 1307674368000

因此这里你的最终 carry 是 13 并且前导“数字”大于 10。从那时起，这个问题变得越来越糟，打印出 #sum 和最终进位 yield

15      11      13
16      12      20
17      13      35
18      14      64
19      15      121
20      16      243
21      17      510
22      18      1124
23      19      2585
24      20      6204
25      21      15511
26      22      40329
27      23      108888
28      24      304888
29      25      884176
30      26      2652528
31      27      8222838
32      28      26313083

通过逐步减法将 leading_number * i 减少到小于 10 的数字需要越来越长的时间。在某些时候(估计约为 45)，该值变得如此之大，以至于 t - 10 == t 并且您陷入了无限循环。 LuaJIT 对此根本无济于事。

因此，您必须确保永远不会写出大于 9 的数字，例如通过减少循环中的最后进位(如前一个数字)并根据需要添加尽可能多的数字。这样做，程序运行时没有明显的延迟。

if carry > 0 then
    local w = #sum+1
    local cc = 0
    while carry > 0 do
        while carry >= 10 do
            carry = carry - 10
            cc = cc + 1
        end
        sum[w] = carry
        w = w+1
        carry = cc
        cc = 0
    end
end

但是除法确定位数和进位要简洁得多，对于较大的因子也更有效(当一个数字乘以100时，结果平均为450，需要45次减法，但对所有因子进行两次除法就足够了)。

关于performance - Project Euler #20 的算法缓慢，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11585717/