81–90 of 92 posts
The 3c^4 ≡ 6 (mod 15) line is missing parentheses... As written, it means 3 * (c^4) ≡ 6 (mod 15), which is demonstrably false (e.g. 3 * (4^4) = 768 ≡ 3 (mod 15)).
In general (ab) mod n == (a mod n)(b mod n) mod n
In the case of (3*c)^4, 3^4 mod 15 -> 108 mod 15 -> 3.
Earlier quoted context omitted.
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...
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.
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).
Not sure how this came back around into the zeitgeist today, but this is my post from awhile back. Thanks to all who had nice things to say about it. I'm definitely an amateur mathematician, though I tried my best to write the post like I think I'd try to write a proof. It came about because I stumbled across the equation, but I did not know _why_ it worked, so I was semi-obsessed with figuring out the _why_ for a lo…
This is a nice post; thanks for writing it! (A minor thing: the margin notes completely disappear on mobile, i.e. at width of 760px or less.) You probably know this already, but I'd think of this the following way. There are two main mathematical ideas involved here: • The first, easy to underrate because it can seem "obvious", is the Chinese remainder theorem. This, for instance, here implies that any function of th…
Earlier quoted context omitted.
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 step…
Earlier quoted context omitted.
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...
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-...
Earlier quoted context omitted.
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).
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 :)
char ds[5];
char * words[4] = {ds, "Fizz\n", "Buzz\n", "FizzBuzz\n"};
for (i = 1; i Earlier quoted context omitted.
In this case though you could just use an 11-element array as a lookup table which would technically make this branchless.
If your compiler is optimizing for speed, you can you write the program in a way so that the compiler can unroll the loop and hopefully make it branchless as well
Earlier quoted context omitted.
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 :)
Then the desired statement showing commutativity is
pow4'(mod15(x)) = pow4'(x) = mod15(pow4'(x))
mod15 o mod15 = mod15
mod15 o pow4' = mod15 o mod15 o pow4 = mod15 o pow4 = pow4'
Maybe I'm being old and grumpy, but is there really a point to writing python without conditional logic? Each operation is going to have all sorts of stuff going in the interpreter, and the amount of code being executed that tiny snippet is way more than one would expect.
Conditional logic is, in general, harder to analyze for correctness than declarative data and mathematical formulae.
E.g., considering `var rectified = x*(x>0);` or `var foo = predicate ? bar : baz;` both lend themselves to having their invariants easily verified, even if many such constructions are littered through a program. Contrast that with something like `if (predicate) {/*nightmares*/} else {/*slightly changed nightmares*/}` -- too many branches can quickly lead to an explosion of possible execution paths and all the problems that entails.