Fast way of suming up polynoms

Question

You probably will think that this question is more about algorithms, but actually i'am searching for right formula.

What i want to do is to compute

$(A^n + A^{n-1} + .. + A + 1))$ mod $(10^9 + 7)$

fast. Fast is $log(n)$.

$1 <= n <= 10^{18}$

$1 <= A <= 10^9$

What i have tried:

1. Geometric series formula (multiplier = A): https://en.wikipedia.org/wiki/Geometric_series

That is not working because of division - the numbers are too large i.e. i need compute $(a/b)$ mod m , but i can't store the whole numerator in memory, i can only use a mod m, but (a mod m) / (b mod m) != (a / b) mod m

2. It was found that f.e. $ A^{n} + A^{n - 1} + ... + A + 1 = (1 + A^{(n + 1)/2})(1 + A^{(n + 1)/4})...(1 + A)$

so in this case number of multiplications = log(number of sum members). But this formula is ok only for n = (power of 2) - 1 f.e.

$ A^{15} + A^{14} + ... + A + 1 = (1 + A^{8})(1 + A^{4})(1 + A^{2})(1 + A) $

And if n != (power of 2) - 1 i need to sum up the remained members linearly in cycle (what is very bad for performance).

Are there any formula to compute this $ A^{n} + A^{n - 1} + ... + A + 1 $ for arbitrary n, without division and fast (log n)?

Answer 1

We have that: $$A^n+A^{n-1}+...+1=\frac{A^{n+1}-1}{A-1} \equiv (A^{n+1}-1)(A-1)^{-1} \pmod{10^9+7}$$ We know that we can use the Extended Euclidean algorithm to find $(A-1)^{-1}$ because $10^9+7$ is prime, so the only way this wouldn't work is if $A-1$ is a multiple of $10^9+7$, which almost never happens. If we have $1 < A \leq 10^9$, then it definitely won't happen.

However, for $A=1$, we have to make an exception. This is an "edge case" that will lead to a mistake. It's trivial that the answer is $n+1$ for $A=1$, but you need to program this in as an exception because this algorithm won't work for $A=1$.

Also, for $A^{n+1}-1$, we use modular exponentiation to find $A^{n+1} \pmod{10^9+7}$, which works all of the time.

The Extended Euclidean Algorithm runs in $O(\log((10^9+7)A)=O(\log A)$ and the modular exponentiation runs in $O(\log n)$ time, so overall, we get $O(\log A+\log n)$. Since $n$ has a bigger upper bound than $A$, most people would just write $O(\log n)$ here.