# Project Euler #48: Self powers

# Project Euler #48: Self powers

+ 0 comments (Python) Spent a long time reading on fast modular exponentiation, implement a lengthy solution which is still not fast enough for the last test case, and then find out someone else use

`pow()`

in place of`**`

to pass everything naively. Lesson learnt. By the way, it took 2.13s for my lengthy solution to pass #4. Interesting, though.

+ 8 comments It may help for people who are using c/c++ or don't want to use any BigInt type libraries (i.e. if you are a performance freak).

using ull = unsigned long long; constexpr ull Modulus = 10000000000ULL; inline ull modMul(const ull x, const ull y) { if (x > (1<<30) && y > (1 << 30)) return ((x >> 30)*((y << 30) % Modulus) + y*(x & ((1 << 30) - 1))) % Modulus; ull z = x*y; if (z >= Modulus) z %= Modulus; return z; }

+ 0 comments https://stackoverflow.com/questions/33273991/modular-exponentiation-fails-for-large-mod-in-c

+ 1 comment test cases 4 and 5 are terminated due to timeout in python 3 even though my code as simple as it can be

+ 2 comments Though I liked this problem, I felt it was really stretching into compiler specifics for people using C/C++ by requiring the use of non-standard types like

`__uint128_t`

or implement your own 64-bit multiplier. For most other languages I believe there is some big or huge integer library to the rescue, but those are standardized.

Sort 57 Discussions, By:

Please Login in order to post a comment