Hacker News Reader

Comment by nickcw | Hacker News Reader

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

View on HN

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

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.

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.

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.

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

No, it's called distributive property: https://en.m.wikipedia.org/wiki/Distributive_property

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

Right. This is a consequence of compatibility with exponentiation.

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

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.

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

pow4(mod15(x)) is already in Z/15, you can't apply mod15 to it. The point is pow4ing in Z and then reducing mod 15 is the same as reducing mod 15, then pow4ing in Z/15.

It's not actually the same pow4 on the LHS and RHS (the LHS is in Z, the RHS in Z/15), but I think "commutative" still fits.

> as it's, um, not injective

Er, surjection :)

Well, how about this, if we use pow4' to be modular exponentiation, i.e. mod15 o pow4? (of course then changing mod15 to take Z -> Z so the types line up)

Then the desired statement showing commutativity is

    pow4'(mod15(x)) = pow4'(x) = mod15(pow4'(x))

where that last equality is trivial because

    mod15 o mod15 = mod15

    mod15 o pow4' = mod15 o mod15 o pow4 = mod15 o pow4 = pow4'

per associativity of function composition

I'm a PhD in math. Modulo is a function in that it maps integer to integers. Power is a function mall mg integers to integers. Both are operators in the math sense, and one can talk about operators commuting.

So the terms are correct.

As far as programmers, modulus is an operator, complete with operator overloading in many languages and satisfying operator precedence. So operator is the correct word there also.

Here's the idea from math https://mathoverflow.net/questions/20968/rules-for-operator-...

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

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.

Well, yeah... Exponentiation is O(2^n) (actually it’s also Omega(2^n)), modular exponentiation is O(n).

Reply on news.ycombinator.com