Is there any way of optimizing a multiplication loop?

Question

Let's say I have to repeat the process of multiplying a variable by a constant and modulus the result by another constant, n times to get my desired result.

the obvious solution is iterating n times, but it's getting time consuming the greater n is.

Code example:

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);

Is there any algebraic solution to optimize this loop?

Is there a mathematical abstraction for iterated multiplication? Then, there are special relations between `A` and `B`: if `A % B == 0`… — greybeard, May 02 '17 at 20:08
You could pre-calculate or cache the values for `c = 0 .. b-1` and store them in a `look-up table`. Within the loop, `c` is always truncated to this range by the modulo operation. — Axel Kemper, May 02 '17 at 20:20
Possible duplicate of [Modulus power of big numbers](http://stackoverflow.com/questions/8287144/modulus-power-of-big-numbers) — Paul Hankin, May 02 '17 at 20:37
@PaulHankin I was initially inclined to agree with you that this was a duplicate but when I saw two high-rep users give answers which seemed predicated on the assumption that this was more than simple modular exponentiation in disguise I decided that the equivalence isn't quite obvious. — John Coleman, May 02 '17 at 21:30

score 4 · Accepted Answer · edited May 23 '17 at 12:26

% has two useful properties:

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

This implies that e.g.

(((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

Hence, in your case the final c that you compute is equivalent to

(c*a^n)%b

This can be computed efficiently using exponentiation by squaring.

To illustrate this equivalence:

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

Patrick87 · Answer 2 · 2017-05-03T02:24:31.113

First, note that c * A^n is never an exact multiple of B = 456 since the former is always odd and the latter is always even. You can generalize this by considering the prime factorizations of the numbers involved and see that no repetition of the factors of c and A will ever give you something that contains all the factors of B. This means c will never turn into 0 as a result of the iterated multiplication.

There are only 456 possible values for c * a mod B = 456; therefore, if you iterate the loop 456 times, you will see at least value of c repeated. Suppose the first value of c that repeats is c', when i= i'. Say it first saw c' when i=i''. By continuing to iterate the multiplication, we would expect to see c' again:

we saw it at i''
we saw it at i'
we should see it at i' + (i' - i'')
we should see it at i' + k(i' - i'') as well

Once you detect a repeat you know that pattern is going to repeat forever. Therefore, you can compute how many patterns are needed to get to N, and the offset in the repeating pattern that you'd be at for i = N - 1, and then you'd know the answer without actually performing the multiplications.

A simpler example:

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

Is there any way of optimizing a multiplication loop?

2 Answers2