Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Euler's Fizzbuzz (2020)

philcrissman.net

Post reply on HN
Print view View original

61–70 of 92 posts

Re: Euler's Fizzbuzz (2020)

#61

Post by sblom »

ChrisLomont wrote: post #55
nickcw wrote: post #34

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 >> timeit("pow(1 >> 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.…

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

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.

Re: Euler's Fizzbuzz (2020)

#62

Post by anthk »

tlaundal wrote: post #3

This is of course a really neat solution, but the proof doesn't really give me much value as a reader. I am much more interested in an explanation of how to find this solution, than a theoretical solution of why it is correct. Specifically I don't understand from the article why the trick of raising n to the power of LCM(phi(3), phi(5)) works.

https://medium.com/hackernoon/algorithms-explained-diffie-he...

Re: Euler's Fizzbuzz (2020)

#64

Post by anthk »

Jtsummers wrote: post #39
kirillcool wrote: post #33

Good luck running ^4 on larger numbers and overflowing integer / long bounds orders of magnitude faster than the plain "boring" solutions

The trick is to do the modulus before the exponentiation. It gives the same result. n^4 % x = m == (n % x)^4 % x = m By way of demonstration: n = 18, x = 15 18^4 = 104976 = 6 (mod 15) ---- 18 % 15 = 3 3^4 = 81 = 6 (mod 15) A very handy result to remember for cases where you don't want to use or don't have easy access to arbitrary precision integers.

Well, this doesn't need much of a demonstration. The rest of a division will be the same "visually" if you keep "stacking" the same number on top.

Re: Euler's Fizzbuzz (2020)

#65

Post by Jtsummers »

anthk wrote: post #63
kirillcool wrote: post #33

Good luck running ^4 on larger numbers and overflowing integer / long bounds orders of magnitude faster than the plain "boring" solutions

https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e EDIT: Pasting into Lynx screwed formatting from Groff.

> a^n % b = a % b.

That is not generally true. A quick counterexample:

  a = 2, n = 3, b = 5
  2^3 % 5 = 8 % 5 = 3
  2 % 5 = 2
  3 != 2

Re: Euler's Fizzbuzz (2020)

#66

Post by layoutIfNeeded »

nickcw wrote: post #34

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 >> timeit("pow(1 >> 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.…

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

Re: Euler's Fizzbuzz (2020)

#67

Post by einpoklum »

Qub3d wrote: post #4

The fundamental mathematical concepts revealed in this answer, especially the use of Euler's totient theorem, are worth pondering because it is this branch of modular arithmetic that Diffie and Hellman first proposed, and then Rivest, Shamir, and Adleman concretely used to produce, well, RSA: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation Sadly, quantum supremacy may mean this form of cryptography will so…

IMHO Quantum supremacy is pie in the sky, which will stay in the sky. So, you can probably pursue modular arithmetic safely for the foreseeable future.

Re: Euler's Fizzbuzz (2020)

#68

Post by layoutIfNeeded »

nonameiguess wrote: post #43
Sharlin wrote: post #17

Earlier quoted context omitted.

Well, the loop in your `map()` does obviously have a halting condition. But I believe by map, the GP meant the associative array used by the implementations to lookup the correct output.

In most languages, looping is implemented with conditional jumps, but I actually think Python is unique in this case because of the way it uses exceptions for flow control. Rather than checking an index to see if the loop has reached the end of an iterator, the iterator just raises a StopIteration exception and the runtime catches it. The key lookup in dict definitely has conditionals, though. Of course, the guy coul…

>Rather than checking an index to see if the loop has reached the end of an iterator, the iterator just raises a StopIteration exception and the runtime catches it.

And how does the iterator know that it should raise an exception? A conditional.

Re: Euler's Fizzbuzz (2020)

#69

Post by henryfjordan »

sblom wrote: post #61
ChrisLomont wrote: post #55

Earlier quoted context omitted.

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

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

Re: Euler's Fizzbuzz (2020)

#70

Post by anthk »

Jtsummers wrote: post #65
anthk wrote: post #63

Earlier quoted context omitted.

https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e EDIT: Pasting into Lynx screwed formatting from Groff.

> a^n % b = a % b. That is not generally true. A quick counterexample: a = 2, n = 3, b = 5 2^3 % 5 = 8 % 5 = 3 2 % 5 = 2 3 != 2

I missed something from Groff, sorry.
Post reply on HN