[HN Gopher] Euler's Fizzbuzz (2020)
___________________________________________________________________
Euler's Fizzbuzz (2020)
Author : koevet
Score : 182 points
Date : 2021-03-15 22:39 UTC (1 days ago)
(HTM) web link (philcrissman.net)
(TXT) w3m dump (philcrissman.net)
| tlaundal wrote:
| 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.
| qsort wrote:
| Because it doesn't :)
|
| The author is trying to use Euler's theorem (if a, n are
| coprimes, then a^{\phi(n)} \equiv 1 \mod n), but the map
| defined by the exponentiation doesn't say anything about what
| happens when (a, n) are not coprime.
|
| I'd encourage you to read this post, which is linked by the
| article: https://blog.antfeedr.com/posts/fizzbuzz.html.
| anthk wrote:
| https://medium.com/hackernoon/algorithms-explained-diffie-he...
| prionassembly wrote:
| > This is of course a really neat solution, but the proof
| doesn't really give me much value as a reader.
|
| This is because your number theory-fu is poor.
|
| Don't take this in a bad way, I'm probably even less capable.
| What I mean is that readability is predicated on a reader.
| Seasoned number theorists might not be as cool with goroutines
| or walrii operators or virtual DOMs.
| Qub3d wrote:
| 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
| soon be dead, but this curious application is why modular
| arithmetic is a favorite of mine. It was a branch of math that
| historically had a few niche applications, and then in the 21st
| century became an underpinning to global capitalism.
| einpoklum wrote:
| 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.
| enriquto wrote:
| > Sadly, quantum supremacy may mean this form of cryptography
| will soon be dead
|
| I don't think it will be soon, but when it happens it won't
| necessarily be sad.
| Qub3d wrote:
| Well, I suppose I mean sad in the way people are wistful when
| old technology fades into obsolescence, not because the tech
| was better (it clearly isn't) but because the times it
| represents fading with it.
|
| e.g. dumb phones, analog TV, CRT monitors, floppy disks...
| uuidgen wrote:
| I don't believe "quantum computing" will get us any step closer
| to breaking RSA. Similar how complex number theory didn't allow
| us to draw a square with area of -1.
|
| To break RSA-N you need a superposition of all the numbers up
| to 2^N, AFAIK there is even not a hint how to approach it
| physically.
| danbruc wrote:
| A superposition of all n bit integers is no big deal,
| extracting useful information when performing a measurement
| is. If you start with a uniform distribution of all n bit
| integers, you also get each result with equal probability
| unless you manage to manipulate the system in such a way that
| the probability of the correct result gets amplified. This is
| the hard part, finding and implementing operations that
| selectively boost the probability of the correct result while
| reducing the probabilities of all other results.
| MauranKilom wrote:
| 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)).
| kirillcool wrote:
| Good luck running ^4 on larger numbers and overflowing integer /
| long bounds orders of magnitude faster than the plain "boring"
| solutions
| Jtsummers wrote:
| 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.
| anthk wrote:
| 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.
| bidirectional wrote:
| Modular exponentiation can be done very quickly, you don't need
| to compute n^4 at all. Not sure if this particular
| implementation makes use of that, though. In Haskell, I can
| compute (100000 ^ 1000000 `mod` 15) near instantly.
| nonameiguess wrote:
| Python's built in pow function does this, but the ** operator
| does not. Of course, like Haskell, it also uses arbitrary
| precision integers by default, so it might take forever to
| compute something, but it won't overflow unless you actually
| run out of memory.
| anthk wrote:
| https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e
|
| EDIT: Pasting into Lynx screwed formatting from Groff.
| Jtsummers wrote:
| > 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
| tgb wrote:
| This is a cute solution but I feel like the exposition makes it
| more mysterious seeming then necessary. If you have n%15, that's
| enough to do FizzBuzz on it's own, without having to take a
| fourth power. It's just then you need to map n%15=3,6,9,12 to
| "Fizz" instead of just 6. Taking the fourth power simplifies
| things because 3^4, 6^4, 9^4 and 12^4 all equal 6 (mod 15). And
| similarly for the multiples of 5. Though this explanation doesn't
| generalize as well.
| chronolitus wrote:
| Right, but your comment doesn't do justice to the beauty of the
| solution being so concise. Is it a coincidence that the same
| exponent 4 works for both multiples of 3 and 5?
|
| What if instead of 3 and 5, we did FizzBuzz with 7 and 11?
| Let's do n%77, now we need to map 7, 14, 21, 28, 35, 42, 49,
| 56, 63, 70 to Fizz, and 11, 22, 33, 44, 55, 66 to Buzz, unless
| we can find some way to have them all reduce to the same
| number. Is that really so straightforward?
|
| Now that we know the trick with the exponents, we could try a
| few to start.
|
| For multiples of 11 it seems the smallest one which works is 6!
| Great, let's try it on multiples of 7.. Nope. Ok, for multiples
| of 7, I see that ^10 works.. but that doesn't work for
| multiples of 11.
|
| * the article addresses this at the end, and tells us that the
| correct exponent is ^30, the lowest common denominator of 6 and
| 10. But if I'd been given this problem, I'd have remained stuck
| on the second paragraph of this comment, with no idea where to
| start when seeking to reduce the divisors to a single number.
| namelessUser wrote:
| If a^n = 0 (or 1) mod b, then a^(kn) = (a^n)^k = 0 (or 1) mod
| b for any positive integer k.
|
| Therefore you need to pick a common multiple of 6 and 10.
| kingaillas wrote:
| His point was writing a function without conditional logic, and
| then of course generalizing to any "fizzbuzz category" problem.
|
| I thought it was a fantastic post on a extremely well trodden
| subject, up there with solving fizzbuzz in Tensorflow post.
| (https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/)
| uuidgen wrote:
| But there is conditional logic "hidden" in lambda mapping.
|
| You want it without ANY conditional logic try this
|
| (python3): [str(n)*(n%3!=0)*(n%5!=0) + 'Fizz'*(n%3==0) +
| 'Buzz'*(n%5==0) for n in range(1,101)]
| chongli wrote:
| There's tons of hidden conditional logic in the Python
| string multiplication operator. It's implemented via the C
| function unicode_repeat which handles all the conditional
| logic.
| LanceH wrote:
| My entry to use random-isn't-random:
| https://github.com/LanceH/fizzbuzz/blob/master/fb.go
|
| I feel like I need to revisit after seeing tensorflow and
| Euler. I need to find some way of making the lucky number
| using things around a room, like a mentalist or something.
|
| Some other subversive ones I've seen of are the java
| enterprise version, and several that import a fizzbuzz
| library and just run.
| isaacimagine wrote:
| I find that random-not-random implementation pretty
| incredible.
| LanceH wrote:
| Thanks.
|
| It seems kind of obvious compared to the Euler method,
| though. Once you realize it's 4 bits across a cycle of
| 15, it's just just a matter of finding the right seed. It
| should be on the order of 1 in a billion, which is no big
| deal. In hindsight, if I had combined my number theory
| knowledge I might have been able to accomplish the Euler
| solution, but I didn't, so hats off to them.
|
| The presentation of the tensorflow provides more a much
| higher contempt for the question than I've achieved as
| well. The fact it isn't 100% accurate, but can be trained
| to be accurate to a certain level, just makes it better.
|
| I will redouble my research efforts on this or some other
| problem which doesn't need solving.
| johbjo wrote:
| I would do this:
|
| Let i = ((n % 3) == 0) | ((n % 5) == 0) << 1
|
| Then map output as { n, 'Fizz', 'Buzz', 'FizzBuzz' }
| MauranKilom wrote:
| Or, using only elementary math:
|
| Let i = ((n % 3) ** 2) + ((n % 5) ** 4) * 2
|
| Or, given any number n of primes p_j, the "fizzbuzz index" i is
| just
|
| Let i = sum_over_j(((n % p_j) ** (p_j - 1)) * (n ** j))
|
| (This doesn't generalize to non-primes via the totient function
| for the same reason the post's solution doesn't generalize - (a
| % k) * phi(k) for prime k is zero if and only if k divides a,
| but for non-prime k it can also become zero for other a.)
| motohagiography wrote:
| Was this the expected answer to the coding interview question at
| places like Renaissance Technologies, Jane Street Capital, and
| Galois?
|
| This is really funny. I had an intuition there must be a lambda
| function solution for fizzbuzz, but I don't do coding interviews
| and never pursued it. I can see why now, because it's waaay out
| of my skillset, but so neat to read.
| bidirectional wrote:
| Jane Street maybe. I've not heard of Galois having a tricky
| interview process. From what I've heard of Renaissance, this
| would be insultingly trivial to ask.
| leblancfg wrote:
| The lambda's purpose here is only to turn it into a one-liner.
| It can be rewritten as def fizzbuzz(n):
| num_map = { 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }
| return num_map[n**4%15] for i in range(100):
| print(fizzbuzz(i + 1))
|
| The real skill would be to demonstrate that you
| know/remember/can apply Euler's totient theorem off-the-cuff in
| an interview!
| omaranto wrote:
| I don't know about Jane Street or Galois, but Renaissance is
| full of mathematicians so I doubt they'd be impressed by
| Euler's theorem. Math students learn it in undergrad, it is
| considered basic.
| roelschroeven wrote:
| We can even easily write it as a one-line without lambda:
| [{ 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }[n**4%15] for
| n in range(1, 101)]
|
| The lambda in the original code is just used to convert the
| 0..99 that's generated by range(100) to 1..100. Using
| range(1, 101) instead generates the appropriate range of
| numbers from the beginning.
| raverbashing wrote:
| Yeah if I get asked fizzbuzz at an interview I'll really think
| less of the interviewer and will try to propose a solution like
| that ;)
| [deleted]
| draganm wrote:
| Neat trick, the only issue I see is mis-selling the idea that no
| conditionals are used ... map on it's own (independently how it's
| implemented) is a conditional. Also, if you break down how mod
| can be implemented, it definitely requires conditionals. In terms
| of the computational overhead this is way worse than just going
| for mod 15 and then mapping every of the possible 15 results to
| Fizz, Buzz or FizzBuzz.
| 1980phipsi wrote:
| Yeah, they should profile.
| Sharlin wrote:
| In this case though you could just use an 11-element array as a
| lookup table which would technically make this branchless.
| draganm wrote:
| true - but would require modifying the proposed solutions.
| Besides, it does not remove the branching issue of mod ...
| unless you use a lookup table for that too, but then you
| might as well have the lookup table for the whole FizzBuzz
| solution space.
| smlckz wrote:
| heh, the branching is now in the implementation of the
| lookup table
| Jtsummers wrote:
| It's a common pattern in embedded systems (for better or
| worse) when you have something like function pointers or
| computed go tos available. C, of course, has function
| pointers and I've seen dispatch tables like this before:
| message_handler = {type_0, type_1, ..., type_999}; //
| imagine it being generated
| message_handler[message.type](message);
|
| In the case of computed go to in Fortran, it's similar. I
| had the "pleasure" of maintaining this once. It's been a
| while so I had to look up the syntax, IIRC it used
| something like a dispatch tree and dispatched off each
| digit in the type but I could be wrong:
| go to (0, 100, 200, 300, ...), message_type / 100 --
| integer division 0 go to ... 100
| go to ... 200 go to ... ...
| Sharlin wrote:
| Yeah, but given that `mod` (if we're talking native
| integers rather than some bigint type) is implemented as a
| single machine instruction, i'd count that as branchless
| for all reasonable intents and purposes even though the
| hardware has to internally do something equivalent to a
| loop to do division.
| draganm wrote:
| on the CPU level (I'm talking Intel here, but it applies
| to most other chips) DIV/IDIV instructions (returning
| division result and remainder a.k.a. modulo) are the ones
| using up the most CPU cycles. The reason for this is that
| they can't be completely parallelised because of having
| to check conditions.
| smlckz wrote:
| 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
| ufo wrote:
| If we're doing that then we may as well avoid the
| exponentiation with `lookup_table[n % 15]`.
| islon wrote:
| Why would map have conditions? //pseudocode
| map(f, ns) for i in (0 .. ns.length - 1)
| f(ns[i])
| Sharlin wrote:
| 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.
| nonameiguess wrote:
| 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 could get rid of that by just using an
| 11-element array and addressing directly instead of hashing
| integers as keys.
| layoutIfNeeded wrote:
| >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.
| draganm wrote:
| because for has a termination condition ...
| Jtsummers wrote:
| The map data structure, not the map higher order function. As
| implemented, most map data structures will have a conditional
| in their lookup functions to handle the case of collisions or
| a key being absent from the map.
| [deleted]
| chinchilla2020 wrote:
| Fizzbuzz question has a nuance that is not acknowledged by many.
| Read the question carefully.
|
| It should solve:
|
| 3: fizz
|
| 5: buzz
|
| 15: fizzbuzzfizzbuzz
|
| Why is this?
|
| 15 is divisible by 3
|
| 15 is divisible by 5
|
| 15 is divisible by 3 and 5
|
| All three statements in the description are true. You never said
| they were mutually exclusive.
| philcrissman wrote:
| 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 long time.
|
| I have nothing else to promote, haven't even put anything on the
| site since this one and only post... Anyways, thanks, news-YC.
| philcrissman wrote:
| I was actually asked Fizz Buzz in an interview once, but I did
| not have this solution at the time.
|
| My favorite FizzBuzz solution is actually:
|
| ``` ->(n){[[["Fizz"][n%3],["Buzz"][n%5]].join].find(->{n}){|w|
| w if !w.empty?}} ```
|
| This is Ruby, of course, probably something very similar can be
| done in several other languages.
| svat wrote:
| 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 the quantities (x mod 3) and (x
| mod 5) can be rewritten as a function of just (x mod 15). So if
| you used just this one idea and not the next one, you could
| implement FizzBuzz as lambda n: ['FizzBuzz',
| n, n, 'Fizz', n, 'Buzz', 'Fizz', n, n, 'Fizz', 'Buzz', n,
| 'Fizz', n, n][n % 15]
|
| * The second is Fermat's little theorem. It says (x^(p-1) mod
| p) = [x is not a multiple of p], where the notation [...] is
| Iverson bracket, i.e. 1 or 0 depending on whether the condition
| is true or not. So the question of whether x is a multiple of 5
| or not is equivalent to whether x^4 mod 5 is 0 or 1. This just
| gives us a convenient way of restating the divisibility
| condition.
|
| To get from Fermat's little theorem to Euler's theorem (or to
| be pedantic, Carmichael's theorem, as you're not using ph(15)
| which is technically 2*4 = 8, but rather using lcm(2, 4)=4:
| https://en.wikipedia.org/w/index.php?title=Carmichael_functi...
| ) is itself an application of the Chinese remainder theorem,
| which is why I think it's important and mentioned it first.
|
| And putting these two ideas together gives the function in your
| post. Namely: the FizzBuzz you want is a function of [x is a
| multiple of 3] and [x is a multiple of 5], so you can (using
| the second idea) rewrite it as a function of (x^2 mod 3) and
| (x^4 mod 5), and put them together (using the CRT) as a
| function of (x^4 mod 15).
|
| Coincidentally, both the ideas here are connected to Lagrange:
| the Chinese remainder theorem is the same kind of thing as the
| Lagrange interpolation formula (https://artofproblemsolving.com
| /community/c1157h990758_the_c...), and
| Fermat's/Euler's/Carmichael's theorem is the same kind of thing
| as Lagrange's theorem in group theory.
| nickcw wrote:
| 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
| layoutIfNeeded wrote:
| Well, yeah... Exponentiation is O(2^n) (actually it's also
| Omega(2^n)), _modular_ exponentiation is O(n).
| ChrisLomont wrote:
| Modulus and power commute, so you can use ((n%15)**4)%15 to
| keep it small for any integer n
| Jtsummers wrote:
| 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.
| sblom wrote:
| 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 wrote:
| 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
| decker wrote:
| 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.
| wagslane wrote:
| I think it's about the math porn, not execution time.
| jhayward wrote:
| Conditional logic is, in general, harder to analyze for
| correctness than declarative data and mathematical formulae.
| smlckz wrote:
| if you want to practice programming and like mathematics, you
| should try Project Euler *
|
| * heh! https://projecteuler.net
| exdsq wrote:
| I hope I remember this for the next time I have to answer
| fizzbuzz in an interview
___________________________________________________________________
(page generated 2021-03-16 23:01 UTC)