How to calculate pow(2,n) when n exceeds 64 in c++?
An important detail here is that you're not being asked to compute 2n for gigantic n. Instead, you're being asked to compute 2n mod 109 + 7 for large n, and that's a different question.
For example, let's suppose you want to compute 270 mod 109 + 1. Notice that 270 doesn't fit into a 64-bit machine word. However, 270 = 230 · 235, and 235 does fit into a 64-bit machine word. Therefore, we could do this calculation to get 270 mod 109 + 7:
270 (mod 109 + 7)
= 235 · 235 (mod 109 + 7)
= (235 mod 109 + 7) · (235 mod 109 + 7) mod 109 + 7
= (34359738368 mod 109 + 7) · (34359738368 mod 109 + 7) mod 109 + 7
= (359738130 · 359738130) mod 109 + 7
= 129411522175896900 mod 109 + 7
= 270016253
More generally, by using repeated squaring, you can compute 2n mod 109 + 7 for any value of n in a way that nicely fits into a 64-bit integer.
Hope this helps!
The common approach in serious numerical work is to rewrite the formula's. You store log(x)
instead of x
, and later when you do need x
it will typically be in a context where you didn't need all those digits anyway.