4 ms·
That was fun! Not that anyone cares for FizzBuzz but I'll just note that n**4%15 is more efficiently written using the 3 argument pow function in python, eg po
by nickcw 6y ago
That was fun!
Not that anyone cares for FizzBuzz but I'll just note that n**4%15 is more efficiently written using the 3 argument pow function in python, eg pow(n, 4, 15).
>>> timeit("(1<<100000000)**4%15", number=1)
1.5620321459136903
>>> timeit("pow(1<<100000000, 4, 15)", number=1)
0.05834826407954097
>>>
If n gets large then n**4 is very large so the % 15 has to deal with a big number. pow runs the modulo operation at the same time as the power operation so the intermediates never get bigger than 15.
https://docs.python.org/3/library/functions.html#pow https://docs.python.org/3/library/functions.html#pow
- ChrisLomont 6y agoModulus and power commute, so you can use ((n%15)**4)%15 to keep it small for any integer n
- Jtsummers 6y agoThat starts it small, but doesn't necessarily keep it small. For instance, if n is 1000 and the mod is 1001, we still end up with 1,000,000,000,000 as an intermediate value before the final mod 1001. That's not too bad (fits in a 64-bit integer), but it's easy to see how (with different exponents or bases) it can still blow up. The second python example in GP comment keeps it small by making use of the mod as it steps through the exponentiation, not just at the start and end. EDIT: What I wrote was more about the general case. In this specific case, the largest number we get after modulo would be 14, and 14^4 is only 38,416 so it does actually stay small for this specific instance of the problem.
- ChrisLomont 6y agoYou don't have to do the power all at once - use powermod - then you need at most a square to fit. And when that doesn't fit, there are still more math tricks to keep it small and fast.
- sblom 6y agoIs "commute" the right word for that? I'm not a mathematician, but it doesn't match any usage in my poorly trained math-lang semantic net.
- henryfjordan 6y agoAccording to the Wikipedia page on the commutative property, "commute" is the right word. > If the commutative property holds for a pair of elements under a certain binary operation then the two elements are said to commute under that operation. https://en.wikipedia.org/wiki/Commutative_property https://en.wikipedia.org/wiki/Commutative_property
- konjin 6y agoNo, it's called distributive property: https://en.m.wikipedia.org/wiki/Distributive_property https://en.m.wikipedia.org/wiki/Distributive_property
- henryfjordan 6y agoAfter some further reading, I don't think anyone in this thread is correct. Modulo in math is not an operator like a programmer might think of it. See: https://math.stackexchange.com/questions/2832649/modular-arithmetic-and-the-distributive-property https://math.stackexchange.com/questions/2832649/modular-ari...
- vitus 6y agoRight. This is a consequence of compatibility with exponentiation. https://en.wikipedia.org/wiki/Modular_arithmetic#Properties https://en.wikipedia.org/wiki/Modular_arithmetic#Properties It should be easy to see that n ≡ (n % 15) (mod 15) which, applying compatibility of exp, then gives us n^4 ≡ (n % 15)^4 (mod 15) which can be rewritten in Python's notation as n**4 % 15 == (n % 15) ** 4 % 15
- edflsafoiewq 6y agoThe injection mod15: Z -> Z/15 is an operation and the basic idea here is mod15(pow4(x)) = pow4(mod15(x)), so I think it's correct to call it commutativity.
- contravariant 6y agoOf course at that point you may as well just calculate gcd(n, 15) entirely since the fast version of Euclids algorihtm only needs 2 divisions at most anyway.
- layoutIfNeeded 6y agoWell, yeah... Exponentiation is O(2^n) (actually it’s also Omega(2^n)), modular exponentiation is O(n).