CODEWITHSUNDEEP
algorithmmath
Habibullah Araphat Konok
Habibullah Araphat Konok

Reputation: 474

is there any O(logn) solution for [1+2a+3a^2+4a^3+....+ba^(b-1)] MOD M

Suppose we have a series summation s = 1 + 2a + 3a^2 + 4a^3 + .... + ba^(b-1)

i need to find s MOD M, where M is a prime number and b is relatively big integer.

I have found an O((log n)^2) divide and conquer solution. where, g(n) = (1 + a + a^2 + ... + a^n) MOD M

f(a, b) = [f(a, b/2) + a^b/2*(f(a,b/2) + b/2*g(b/2))] MOD M, where b is even number f(a,b) = [f(a,b/2) + a^b/2*(f(a,b/2) + b/2*g(b/2)) + ba(b-1)] MOD M, where b is odd number

is there any O(log n) solution for this problem?

Upvotes: 1

Views: 189

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Yes. Observe that 1 + 2a + 3a^2 + ... + ba^(b-1) is the derivative in a of 1 + a + a^2 + a^3 + ... + a^b. (The field of formal power series covers a lot of tricks like this.) We can evaluate the latter with automatic differentiation with dual numbers in time O(log b) arithmetic ops. Something like this:

def fdf(a, b, m):
    if b == 0:
        return (1, 0)
    elif b % 2 == 1:
        f, df = fdf((a**2) % m, (b - 1) / 2, m)
        df *= 2 * a
        return ((1 + a) * f % m, (f + (1 + a) * df) % m)
    else:
        f, df = fdf((a**2) % m, (b - 2) / 2, m)
        df *= 2 * a
        return ((1 + (a + a**2) * f) % m, (
            (1 + 2 * a) * f + (a + a**2) * df) % m)

The answer is fdf(a, b, m)[1]. Note the use of the chain rule when we go from the derivative with respect to a**2 to the derivative with respect to a.

Upvotes: 5

Related Questions