找出与给定数之和的4个方格

Question

我用JS写了这个算法，它的主要目标是在2-3秒内给出10^750-10^1000的答案，但是它在2-3秒内解决了10^150，所以我离我的目标有点远，问题是我筛选了几次算法，但我做的任何事情似乎都没有显著加快算法的速度。

如果有人能增强我的代码，或者在JS中给出一个新的代码，以达到我在3秒内解决10^750-10^1000的目标，我将不胜感激。

我实现了MichaelO.Rabin和Jeffrey算法，以求4个平方之和到给定数n和Miller-Rabin进行素数检验，我认为这些都是最好的和快速的，那么为什么我的算法不像“理论上可能是”那样快呢?！

编辑:我首先上传到堆栈溢出，但建议来这个网站。

编辑:经过一些工作，我设法使它在0.4秒内运行，比如10^300，但我的目标仍然是10^750，这是我的目标(但现在的代码要快得多)，我还对代码进行了分段，并对其进行了调试，以查看什么进程是耗时的，在fourSquares中，我试图找到一个素数，它是我数n的倍数的-1。

let primes = [2n, 3n, 5n, 7n];

function power(x, y, p) {
    let res = 1n;
    x %= p;
    while (y > 0n) {
        if (y % 2n == 1n)
            res = (res * x) % p;
        x = (x * x) % p;
        y /= 2n;
    }
    return res;
}

function millerTest(a, d, n) {
    let x = power(a, d, n);
    if (x == 1n || x == n - 1n)
        return true;
    while (d != n - 1n) {
        x = (x * x) % n;
        d *= 2n;
        if (x == 1n)
            return false;
        if (x == n - 1n)
            return true;
    }
    return false;
}

function isPrime(n) {
    if (n <= 1n || n == 4n) return false;
    for (let i = 0; i < primes.length; i++) if (n == primes[i]) return true;
    let d = n - 1n;
    while (d % 2n == 0)
        d /= 2n;
    for (let i = 0; i < primes.length; i++)
        if (!millerTest(primes[i], d, n))
            return false;
    return true;
}

function abs(a) {
    if (a < 0n) return -a;
    return a;
}

function round(a, b) {
    if (b == 0n) return undefined;
    if (a % b == 0n) return a / b;
    let d = a / b;
    let x = abs(a - (d - 1n) * b);
    let y = abs(a - d * b);
    let z = abs(a - (d + 1n) * b);
    if (x <= y && x <= z) return d - 1n;
    if (z <= y && z <= x) return d + 1n;
    return d;
}

function complexIsZero(c) {
    if (c[0] == 0n && c[1] == 0n) return true;
    return false;
}

function complexNorm(c) {
    return c[0] * c[0] + c[1] * c[1];
}

function complexGCD(c1, c2) {
    if (complexIsZero(c1)) return c2;
    if (complexIsZero(c2)) return c1;
    let u = c1[0];
    let v = c1[1];
    let x = c2[0];
    let y = c2[1];
    let a = round(u * x + v * y, x * x + y * y);
    let b = round(v * x - u * y, x * x + y * y);
    while (!complexIsZero(c2)) {
        c1 = c2;
        c2 = [u - a * x + b * y, v - b * x - a * y];
        u = c1[0];
        v = c1[1];
        x = c2[0];
        y = c2[1];
        a = round(u * x + v * y, x * x + y * y);
        b = round(v * x - u * y, x * x + y * y);
    }
    return c1;
}

function twoSquares(p) {
    if (isPrime(p) && p % 4n == 1n) {
        for (let i = 0; i < primes.length; i++)
            if (power(primes[i], (p - 1n) / 2n, p) == p - 1n) {
                let x = power(primes[i], (p - 1n) / 4n, p);
                return complexGCD([x, 1n], [p, 0n]);
            }
    }
    return [0n, 0n];
}


//Quaternion Class
function QIsZero(q1) {
    for (let i = 0; i < q1.length; i++) q1[i] = BigInt(q1[i]);
    for (let i = 0; i < q1.length; i++) if (q1[i] != 0n) return false;
    return true;
}

function Qadd(q1, q2) {
    for (let i = 0; i < q1.length; i++) q1[i] = BigInt(q1[i]);
    for (let i = 0; i < q2.length; i++) q2[i] = BigInt(q2[i]);
    let a1 = q1[0];
    let b1 = q1[1];
    let c1 = q1[2];
    let d1 = q1[3];
    let a2 = q2[0];
    let b2 = q2[1];
    let c2 = q2[2];
    let d2 = q2[3];
    return [a1 + a2, b1 + b2, c1 + c2, d1 + d2];
}

function Qsub(q1, q2) {
    for (let i = 0; i < q1.length; i++) q1[i] = BigInt(q1[i]);
    for (let i = 0; i < q2.length; i++) q2[i] = BigInt(q2[i]);
    let a1 = q1[0];
    let b1 = q1[1];
    let c1 = q1[2];
    let d1 = q1[3];
    let a2 = q2[0];
    let b2 = q2[1];
    let c2 = q2[2];
    let d2 = q2[3];
    return [a1 - a2, b1 - b2, c1 - c2, d1 - d2];
}

function Qconj(q1) {
    for (let i = 0; i < q1.length; i++) q1[i] = BigInt(q1[i]);
    let a1 = q1[0];
    let b1 = q1[1];
    let c1 = q1[2];
    let d1 = q1[3];
    return [a1, -b1, -c1, -d1];
}

function Qmul(q1, q2) {
    for (let i = 0; i < q1.length; i++) q1[i] = BigInt(q1[i]);
    for (let i = 0; i < q2.length; i++) q2[i] = BigInt(q2[i]);
    let a1 = q1[0];
    let b1 = q1[1];
    let c1 = q1[2];
    let d1 = q1[3];
    let a2 = q2[0];
    let b2 = q2[1];
    let c2 = q2[2];
    let d2 = q2[3];
    let x = a1 * a2 - b1 * b2 - c1 * c2 - d1 * d2;
    let y = a1 * b2 + b1 * a2 + c1 * d2 - d1 * c2;
    let z = a1 * c2 - b1 * d2 + c1 * a2 + d1 * b2;
    let w = a1 * d2 + b1 * c2 - c1 * b2 + d1 * a2;
    return [x, y, z, w];
}

function Qnorm(q1) {
    for (let i = 0; i < q1.length; i++) q1[i] = BigInt(q1[i]);
    let a1 = q1[0];
    let b1 = q1[1];
    let c1 = q1[2];
    let d1 = q1[3];
    return a1 * a1 + b1 * b1 + c1 * c1 + d1 * d1;
}

function Qdiv(q, r) {
    let q0 = q[0];
    let q1 = q[1];
    let q2 = q[2];
    let q3 = q[3];
    let r0 = r[0];
    let r1 = r[1];
    let r2 = r[2];
    let r3 = r[3];
    let t0 = r0 * q0 + r1 * q1 + r2 * q2 + r3 * q3;
    let t1 = r0 * q1 - r1 * q0 - r2 * q3 + r3 * q2;
    let t2 = r0 * q2 + r1 * q3 - r2 * q0 - r3 * q1;
    let t3 = r0 * q3 - r1 * q2 + r2 * q1 - r3 * q0;
    let norm = Qnorm(r);
    let a = round(t0, norm);
    let b = round(t1, norm);
    let c = round(t2, norm);
    let d = round(t3, norm);
    return [a, b, c, d];
}

function gcdQuaternion(a, b) {
    if (QIsZero(a)) return b;
    if (QIsZero(b)) return a;
    let c, t;
    while (!QIsZero(b)) {
        c = Qdiv(a, b);
        t = Qsub(a, Qmul(b, c));
        a = b;
        b = t;
    }
    return a;
}

function fourSquares(n) {
    if (n < 0n) return undefined;
    if (n == 0n) return [0n, 0n, 0n, 0n];
    let d = 0n;
    while (n % 2n == 0) {
        n /= 2n;
        d += 1n;
    }
    let e = (-4n) ** (d / 4n);
    let f = d % 4n;
    let M = 30n;
    let k = 1n;
    let p = M * n * k - 1n;
    let add = 2n * M * n;
    while (!isPrime(p))
        p += add;
    let AB = twoSquares(p);
    let A = AB[0];
    let B = AB[1];
    let Q = gcdQuaternion([A, B, 1n, 0n], [n, 0n, 0n, 0n]);
    for (let i = 0; i < Q.length; i++) Q[i] *= e;
    if (f == 1n) Q = Qmul([1n, 1n, 0n, 0n], Q);
    if (f == 2n) Q = Qmul([0n, 2n, 0n, 0n], Q);
    if (f == 3n) Q = Qmul([-2n, 2n, 0n, 0n], Q);
    return Q;
}

console.log(fourSquares(10n ** 300n));

Answer 1

避免线性扫描

for (let i = 0; i < primes.length; i++) if (n == primes[i]) return true;

所以，如果n是6，我们应该将它与primes中的每个值进行比较，以确定它不是其中之一？至少，按排序顺序维护primes并执行二进制搜索。很有可能，您应该将primes保存在一个可以直接回答这个问题的集合中。

只有一个偶数素数

函数nextPrime(n) { n++；while (!isPrimeSimple(n)) n++；返回n；}

如果n是1，我们应该检查2 (OK)，3 (OK)，4？为什么是4，6，8等等？他们永远不会是最优秀的。考虑一下

function nextPrime(n) {
    if (n < 2) {
        return 2;
    }

    // if even, add one to make odd
    // if odd, add two to get the next odd
    n += 1 + (n % 2);

    while (!isPrimeSimple(n)) {
        n += 2;
    }

    return n;
}

括号和花括号没有必要，但我更喜欢它们。如果只使用n值至少为2调用它，则可以省略初始检查。

这只增加了一半。

你不需要乘以

if (n == 2 || n == 3) return true; for (let i = 2; i \* i <= n; i++) if (n % i == 0) return false;

首先，不需要增加1或单独检查3。

    if (n % 2 === 0) {
        return n === 2;
    }

    for (let i = 3; i <= n / i; i += 2) {
        if (n % i === 0) {
            return false;
        }
    }

在这段代码之后，三个将正确返回true。

除了两个本身，我们不检查任何偶数的潜在因素，因为在检查两个因素之后，我们已经返回了。

现在，就乘法与除法而言，您可能会问，为什么计算n / i比i * i更容易。通常情况下，情况并非如此，但在这种特殊情况下，您正在计算n % i。计算n / i和n % i往往是相同的操作。因此，您最好使用您可能已经拥有的n / i。

您的解释器/编译器也可能不会执行这种优化。如果没有，而且您不能切换到更好的编译器，那么计算n的平方根一次可能比反复计算i的平方值要便宜。

特征分析

这些只是从我身上跳出来的东西。一种更好的方法是在分析调试器中运行代码，并让它告诉您大部分时间都花在哪里。在isSimplePrime吗？isPrime？也许BigInt构造函数正在减慢您的速度。找出代码速度慢的地方，然后寻找优化的方法。

一些常见的建议是使用筛子生成nextPrime，例如Eratosthenes的筛子。然后你就可以完全抛出isSimplePrime了。

把你的米勒测试和直接测试进行比较。或者是其中一个替代方案。