x = 2**1000000
n = 2**100000000
(x**2-2)%n is too slow. I found pow() but I can't use it because I can't subtract 2. (pow(x, 2)-2)%n and (x*x-2)%n are also slow. When I tested (x*x-2) it was fast but when I added the modulo operator it was slow. Is there a way to compute (x**2-2)%n faster?
Are you running this in the interpreter? I did some testing and the main slowdown seemed to come from the interpreter trying to display the result.
If you assign the expression to a variable, the interpreter won't try to display the result, and it will be very quick:
x = 2**1000000
n = 2**100000000
result = (x**2-2)%n
Addendum:
I was also originally thinking along the same lines as MikeW's answer, and if you wanted every part of the code to be fast, you could take advantage of Python's internal base 2 representation of integers and use bitwise left shifts:
x = 1 << 1000000
n = 1 << 100000000
This comes with the caveat that this only works because x and n are powers of 2, and you have to be more careful to avoid making an off-by-one error. This answer is a good explanation of how bitshifts basically work, but Python is bit different than other languages like C, C++, or Java because Python integers are unlimited precision, so you can never left shift a bit completely away like you could in other languages.
If x is always a power of 2, and n is always a power of 2, then you can you can compute it easily and quickly using bit operations on a byte array, which you can then reconstitute into a "number".
If 2^N is (binary) 1 followed by N zeroes, then (2^N)^2 is (binary) 1 followed by 2N zeros.
2^3 squared is b'1000000'
If you have a number 2^K (binary 1 followed by K zeroes), then 2^K - 2 will be K-1 1s (ones) followed by a zero.
eg 2^4 is 16 = b'10000', 2^4 - 2 is b'1110'
If you require "% 2^M" then in binary, you just select the last (lower) M bits, and disregard the rest .
9999 is b'10011100001111'
9999 % 2^8 is b'00001111'
'
Hence combining the parts, if x=2^A and n=2^B, then
(x^2 - 2 ) % n
will be: (last B bits of) (binary) (2*A - 1 '1's followed by a '0')
Some module rules :
1) (a+b)mod(n) = amod(n)+bmod(N)
2) (a.b)mod(n) = amod(n).bmod(n)
So you can transform your equation into :
(x**2-2)%n ==> (x.x - 2)%n ==> (x%n).(x%n) - (2%n)
If n is always greater than 2, (2%n) is 2 itself.
solving (x%n) :
If x and n are always in 2**value ; if x > n then (x%n)= 0 is the answer and if x < n (x%n)=x
So the answer is either 0-(2%n) or x**2-(2%n)
If you want to compute (x ** y - z) % n
it will be equivalent to ((x ** y) % n - z) % n
Python pow function includes as optional parameter a modulo, as it is very often used and can be computed in an optimized way. So you should use:
(pow(x, y, n) - z) % n
OP says in comment : it's slow because I assign x to the answer and I repeat the process.
I try this :
x = 2**(1000*1000)
n = 2**(100*1000*1000)
import time
t0=time.time()
for i in range(6):
x = (x*x-2)%n
t1=time.time()
print(i,t1-t0)
t0=t1
print(x<n)
"""
0 0.0
1 0.4962291717529297
2 0.5937404632568359
3 1.9043104648590088
4 5.708504915237427
5 16.74528479576111
True
"""
It shows that in this problem, it's just slow because x grows, doubling the number of digit at each loop :
In [5]: %timeit u=x%n
149 ns ± 6.42 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
the %n takes absolutely no time if x<n.
