I'm trying to write a procedure that solves (2^n - 1) mod 1000000007
for a given n
.
n
can be very large (~10^9).
Say m = 1000000007
So this is what I have so far:
func(n):
if n = 1 return 2
if n is even return ((func(n/2) mod m)^2)mod m
else return ((func(n/2) mod m)^2 * 2)mod m
I'll call func
and subtract 1
from the result to get the final answer.
Is it right to use that recursion?
func(n/2)
. Is/
and integer division or a floating point division? If it is not integer then the end condition will not be met. $\endgroup$\pmod
it means a congruence: like $2\equiv7\pmod5$. That (in programming parlance) is a comparison operator taking a T/F value. In this case it evaluates to true because $2-7=-5$ is a multiple of $5$. Notation such as $(2\pmod 5)^2$ is non-sensical (should result in a parsing error), because it is trying to square an incorrectly defined boolean variable :-). $\endgroup$