4 ms·

Modulus and power commute, so you can use ((n%15)**4)%15 to keep it small for any integer n

Jtsummers 6y ago
That 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 ago
  You 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 ago
Is "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 ago
  According 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 ago
    No, it's called distributive property: https://en.m.wikipedia.org/wiki/Distributive_property https://en.m.wikipedia.org/wiki/Distributive_property
    - henryfjordan 6y ago
      After 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 ago
        Right. 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 ago
        The 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.
        vitus 6y ago
        Well, not quite. You really want to say that mod15(pow4(x)) == mod15(pow4(mod15(x))). Example: (3 ** 4) % 15 = 81 % 15 = 6. But, (3 % 15) ** 4 = 3 ** 4 = 81. (That said, the two functions do commute when you restrict your domain and range to Z/15.) edit: also, I wouldn't consider mod15 to be an injection, as it's, um, not injective (it maps multiple inputs to the same output).
        6y ago
- joppy 6y ago
  It's roughly the right word for it - mathematicians would say that operations f and g commute if f(g(x)) = g(f(x)) for all x. In this specific case it is not quite true that (^4) and (%15) commute, but if we treat (%15) as returning an element of the-integers-modulo-15 then it is true that the two operations precisely commute. (I think people would say "they commute" anyway, because colloquially it's close enough).
contravariant 6y ago
Of 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.

That 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 ago
You 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 ago

Is "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 ago
According 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 ago
  No, it's called distributive property: https://en.m.wikipedia.org/wiki/Distributive_property https://en.m.wikipedia.org/wiki/Distributive_property
  - henryfjordan 6y ago
    After 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 ago
      Right. 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 ago
      The 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.
      - vitus 6y ago
        Well, not quite. You really want to say that mod15(pow4(x)) == mod15(pow4(mod15(x))). Example: (3 ** 4) % 15 = 81 % 15 = 6. But, (3 % 15) ** 4 = 3 ** 4 = 81. (That said, the two functions do commute when you restrict your domain and range to Z/15.) edit: also, I wouldn't consider mod15 to be an injection, as it's, um, not injective (it maps multiple inputs to the same output).
        6y ago
joppy 6y ago
It's roughly the right word for it - mathematicians would say that operations f and g commute if f(g(x)) = g(f(x)) for all x. In this specific case it is not quite true that (^4) and (%15) commute, but if we treat (%15) as returning an element of the-integers-modulo-15 then it is true that the two operations precisely commute. (I think people would say "they commute" anyway, because colloquially it's close enough).

contravariant 6y ago

Of 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.