### how to calculate the power of large numbers How to write a program in c++ to find the power of x ^ y, where y = 2 ^ k? To avoid overflow for large numbers (10^18 and larger) the program should give modulo 10^9+7 in return. I will be grateful for your help.
Last edited on Its ok to use more words. Can you elaborate? ``1234567891011121314151617181920`` ``````#include using namespace std; unsigned long long pow2k( unsigned long long x, unsigned k, unsigned M ) { unsigned long long ans = x % M; for ( int i = 1; i <= k; i++ ) ans = ( ans * ans ) % M; return ans; } int main() { const unsigned M = 1000000007; unsigned x = 3, k = 4; // check case where modulo is irrelevant cout << x << "^(2^" << k << ") (mod " << M << ") = " << pow2k( x, k, M ) << '\n'; x = 10; // check case where modulo is important cout << x << "^(2^" << k << ") (mod " << M << ") = " << pow2k( x, k, M ) << '\n'; cout << 10000000000000000ull % M; }``````

No fancy large-number library needed.
Last edited on If the numbers are huge, you'll need to use a mathematical C++ library or a different language that supports large numbers, like Python.

You can also program your own way to handle large numbers. This can be done by having an array of 1 byte numbers holding the number, or even just a regular string holding the values. Then you code a way to do operations on them. Pretty much every C/C++ compiler supports 64-Bit integers these days.

In a portable way, you can get a 64-Bit (unsigned) integral type by using uint64_t from <stdint.h>.

uint64_t can handle numbers up to 2^64-1, i.e. two to the power of 64 (minus one).

...sufficient for 10^18, which has about ~60 digits (bits) in base 2.

If that still isn't sufficient, you can use the __int128 type on GCC, Clang/LLVM or Intel's C compiler.

(MSVC still doesn't have a 128-Bit integral type, to the best of my knowledge)

If you actually want "arbitrary precision arithmetic" in C/C++, you need an extra library, such as GMP:
https://gmplib.org/
Last edited on I greatly appreciate your help. Thank you so much!
Topic archived. No new replies allowed.