4 ms·
No, what is meant by that, is that multiplying 2 by 3 takes about the same time as multiplying 432434232 by 1213213213. Not only bounded time, about the same.
by enedil 7y ago
No, what is meant by that, is that multiplying 2 by 3 takes about the same time as multiplying 432434232 by 1213213213. Not only bounded time, about the same.
- w8rbt 7y agoWhat's the runtime of 75^4096 mod 236?
- jerf 7y agoThat sounds like a problem that is not described by "Standard 32-bit or 64-bit multiplication as implemented in hardware".
- nwallin 7y agoa^n mod m requires O(log(n)) iterations in the outer loop. If m fits in one machine word, each iteration is O(1). If m is large, each iteration is O((log m)^2). For the specific case of m = 236 and n = 4096, it requires 12 multiplication and 12 division operations. For n = 4095, I think it actually requires 22 multiplications and 22 divisions. Also, if m is a compile time constant, the divisions can be implemented as multiplications instead, which gives a constant factor speedup. https://godbolt.org/z/KNX4pi https://godbolt.org/z/KNX4pi https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method https://en.wikipedia.org/wiki/Modular_exponentiation#Right-t...
- brucedawson 7y agoO(1) - constant time. The answer is 29. I just happen to know that. I think you need an 'n' in there before it is meaningful to ask about the runtime.