有什么方法可以优化乘法循环吗？

Question

假设我必须重复将一个变量乘以一个常数并将结果与另一个常数取模的过程，n 次以获得我想要的结果。

显而易见的解决方案是迭代 n 次，但随着 n 的增加，它会越来越耗时。

代码示例：

const N = 1000000;

const A = 123;
const B = 456;

var c = 789;

for (var i = 0; i < n; i++)
{
    c = (c * a) % b;
}

log("Total: " + c);

是否有优化此循环的代数解决方案？

Answer 1

首先，请注意 c * A^n 永远不是 B = 456 的精确倍数，因为前者总是奇数而后者总是偶数。您可以通过考虑所涉及数字的质因数分解来概括这一点，并发现 c 和 A 的因数的重复不会给您包含 B 的所有因数的结果。这意味着 c 永远不会因为迭代乘法而变成 0。

c * amodB = 456只有456个可能值；因此，如果您将循环迭代 456 次，您将看到至少重复了 c 的值。假设c第一个重复的值是c'，当i= i'。说它第一次看到 c' 时 i=i''。通过继续迭代乘法，我们希望再次看到 c'：

我们在 i''
我们在 i'
我们应该在 i' + (i' - i'')
我们也应该在 i' + k(i' - i'') 看到它

一旦检测到重复，您就知道该模式将永远重复。因此，您可以计算达到 N 需要多少模式，以及 i = N - 1 时重复模式中的偏移量，然后您无需实际执行乘法即可知道答案。

一个更简单的例子：

A = 2
B = 3
C = 5

c[0] = 5
c[1] = 5 * 2 % 3 = 1
c[2] = 1 * 2 % 3 = 2
c[3] = 2 * 2 % 3 = 1 <= duplicate

i' = 3
i'' = 1
repeating pattern: 1, 2, 1

c[1+3k] = 1
c[2+3k] = 2
c[3+3k] = 1

10,000 = 1 + 3k for k = 3,333
c[10,000] = 1
c[10,001] = 2
c[10,002] = 1

Answer 2

% 有两个有用的属性：

1) (x % b) % b = x % b
2) (c*a) % b = ((c%b) * (a%b))%b

这意味着例如

(((c*a)%b)*a) % b = ((((c*a)%b)%b) * (a%b)) % b
                   = (((c*a) % b) * (a%b)) % b
                   = (c*a*a) % b
                   = (c*a^2) % b

因此，在您的情况下，您计算的最终 c 等同于

(c*a^n)%b

这可以使用 exponentiation by squaring.

高效计算

为了说明这种等价性：

def f(a,b,c,n):
    for i in range(n):
        c  = (c*a)%b
    return c

def g(a,b,c,n):
    return (c*pow(a,n,b)) % b

a = 123
b = 456
c = 789
n = 10**6

print(f(a,b,c,n),g(a,b,c,n)) #prints 261, 261

有什么方法可以优化乘法循环吗？

Is there any way of optimizing a multiplication loop?

algorithm

math

algebra