javascript - 如何更快地进行 > 10^11 次迭代的 for 循环？

Question

我正在尝试在 JS 中实现 2 个数学函数，但是我还需要调用S(10**11) % 10**9这需要很长时间。这些函数基于我拥有的 2 个数学函数： 我尝试将其写入我的计算器（ti nspire）但是，它没有足够的内存，这就是我编写这个脚本的原因。

除了我已经完成的或可能解决求和之外，我真的不确定如何优化它，但我不确定如何使用 floor 函数来做到这一点。

function d(k){
    var a = 0;
    for(l=1;l<=k;l++){
        a += Math.floor(1/(1+k%l))*l;
    }
    return a;
}

function S(N){
    var a = 0;
    for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
            a += d(i*j);
        }
    }
    return a;
}

标签： javascriptmathcalculus

Answer 1

方程可以简化很多，以使计算更容易。

首先，您需要存储 d(i) 的结果，因此您永远不需要重新计算它们。从 d(i) 中找到 d(i+1) 很容易，只需使用

第二对循环可以简化很多。让我们考虑 S(5)

           i
       1     2     3     4     5
    1  d(1) d(2)  d(3)  d(4)   d(5)
    2  d(2) d(4)  d(6)  d(8)  d(10)
  j 3  d(3) d(6)  d(9)  d(12) d(15)
    4  d(4) d(8)  d(12) d(16) d(20)
    5  d(5) d(10) d(15) d(20) d(25)

我们可以看到有多少值被重新计算。首先注意矩阵如何关于对角线对称，节省一半。重新计算了许多其他值。

现在，如果我们看一下 d(k) 中的各个项。首先查看不同 k 和 i 的 mod(k,i) 的结果

        i
     123456789
     ---------
 1 | 0
 2 | 00
 3 | 010
k4 | 0010
 5 | 01210
 6 | 000210
 7 | 0113210
 8 | 00203210
 9 | 010143210

再次缓存值将有所帮助。除法是一个相对昂贵的操作，所以定义一个函数

f(m) = floor( 1 / ( 1 + m ) )

并在计算 d(k) 时将此函数与缓存结果一起使用。实际上让我们计算 f(m) 的值。现在 f(0) = floor(1/1) = 1。f(1) = floor(1/2) = 0 并且对于任何 m>1 f(m) = 0。

这极大地简化了计算。我们基本上只对 mod(k,i) = 0 的情况感兴趣。那是 k 是 i 的倍数的时候。

所以 d(k) 只是 k 的因子之和。

与其试图找到 k 的因数，不如更容易地查看 i 的倍数。

for(i=1;i<N;++i) {
    // find multiples of i
    for(j=1;j<???;++j) {
       m = i * j;
       d(m) += i;
    }
 }

现在我们得出d(k)是k的因子之和，我们可以简化S(N)的计算。

基本上对于给定的因子 m，我们想要找到 m 是 i*j 的因子的所有情况。

显然，1 是每个数字的因数，因此 1 出现 N N 次。如果 i 或 j 是偶数，则 2 是一个因子。乘积 i j 是奇数 N/2 * N/2 次，所以偶数是 3/4 N*N 次。（我假设 N 是偶数）

对于 3，如果我们绘制乘法

*  1  2  3  4  5  6
1        3        6
2        6       12
3  3  6  9 12 15 18
4       12       24
5       15       30
6  6 12 18 24 30 36

只需填写 3 的倍数。我们看到有 (1 - 2/3 * 2/3) N*N 倍数。

同样，对于 4，有 (1 - 3/4 * 3/4) N*N 倍数。

因此，如果我们考虑将倍数相加，整个事情就会变得容易得多。