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

Solving Fizz Buzz with Cosines

susam.net

Post reply on HN
Print view View original

31–40 of 69 posts

Re: Solving Fizz Buzz with Cosines

#31

Post by susam »

susam wrote: post #16
nine_k wrote: post #13

Well, there must be an obvious solution where the fizzbuzz sequence is seen as a spectrum of two frequencies (1/3 and 1/5), and a Fourier transform gives us a periodic signal with peaks of one amplitude at fizz spots, another amplitude at buzz spots, and their sum at fizzbuzz spots. I mean. that would be approximately the same solution as the article offers, just through a more straightforward mechanism.

That is precisely how I began writing this post. I thought I'd demonstrate how to apply the discrete Fourier transform (DFT) but to do so for each of the 15 coefficients turned out to be a lot of tedious work. That's when I began noticing shortcuts for calculating each coefficient c_k based on the divisibility properties of k. One shortcut led to another and this post is the end result. It turns out it was far less t…

Update: I went ahead and added the method of obtaining the coefficients using DFT anyway. Like I mentioned above, this approach is quite tedious by hand, so I only work out the first few coefficients explicitly. In practice, these are almost always computed using numerical software. But for some people it may still be interesting to see a direct calculation rather than relying on shortcuts.

Here is the direct link to the new section on DFT: https://susam.net/fizz-buzz-with-cosines.html#dft

Re: Solving Fizz Buzz with Cosines

#32

Post by [deleted] »

Terretta wrote: post #30

The article conceit is fantastic. That said, is the going-in algo wrong? I see a case for 3 * 5 in here: for n in range(1, 101): if n % 15 == 0: print('FizzBuzz') elif n % 3 == 0: print('Fizz') elif n % 5 == 0: print('Buzz') else: print(n) Why? If we add 'Bazz' for mod 7, are we going to hardcode: for n in range(1, 105): if n % 105 == 0: # 3 * 5 * 7 print('FizzBuzzBazz') elif n % 15 == 0: # 3 * 5 print('FizzBuzz') el…

[deleted]

Re: Solving Fizz Buzz with Cosines

#33

Post by xbar »

susam wrote: post #31
susam wrote: post #16

Earlier quoted context omitted.

That is precisely how I began writing this post. I thought I'd demonstrate how to apply the discrete Fourier transform (DFT) but to do so for each of the 15 coefficients turned out to be a lot of tedious work. That's when I began noticing shortcuts for calculating each coefficient c_k based on the divisibility properties of k. One shortcut led to another and this post is the end result. It turns out it was far less t…

Update: I went ahead and added the method of obtaining the coefficients using DFT anyway. Like I mentioned above, this approach is quite tedious by hand, so I only work out the first few coefficients explicitly. In practice, these are almost always computed using numerical software. But for some people it may still be interesting to see a direct calculation rather than relying on shortcuts. Here is the direct link to…

This is a joy.

Re: Solving Fizz Buzz with Cosines

#34

Post by pbsd »

burnt-resistor wrote: post #28

While it's cute use of mathematics, it's extremely inefficient in the real world because it introduces floating point multiplications and cos() which are very expensive. The only thing it lacks is branching which reduces the chances of a pipeline stall due to branch prediction miss. (The divisions will get optimized away.)

This can be translated to the discrete domain pretty easily, just like the NTT. Pick a sufficiently large prime with order 15k, say, p = 2^61-1. 37 generates the whole multiplicative group, and 37^((2^61-2)/3) and 37^((2^61-2)/5) are appropriate roots of unity. Putting it all together yields

    f(n) = 5226577487551039623 + 1537228672809129301*(1669582390241348315^n + 636260618972345635^n) + 3689348814741910322*(725554454131936870^n + 194643636704778390^n + 1781303817082419751^n + 1910184110508252890^n) mod (2^61-1).
This involves 6 exponentiations by n with constant bases. Because in fizzbuzz the inputs are sequential, one can further precompute c^(2^i) and c^(-2^i) and, having c^n, one can go to c^(n+1) in average 2 modular multiplications by multiplying the appropriate powers c^(+-2^i) corresponding to the flipped bits.

Re: Solving Fizz Buzz with Cosines

#35

Post by michaelcampbell »

Terretta wrote: post #30

The article conceit is fantastic. That said, is the going-in algo wrong? I see a case for 3 * 5 in here: for n in range(1, 101): if n % 15 == 0: print('FizzBuzz') elif n % 3 == 0: print('Fizz') elif n % 5 == 0: print('Buzz') else: print(n) Why? If we add 'Bazz' for mod 7, are we going to hardcode: for n in range(1, 105): if n % 105 == 0: # 3 * 5 * 7 print('FizzBuzzBazz') elif n % 15 == 0: # 3 * 5 print('FizzBuzz') el…

> Sort of fun to muse whether almost all FizzBuzz implementations are a bit wrong.

They're only wrong if they provide output that isn't in the spec. Adding "bazz" isn't in the spec, and assuming that something indeterminate MIGHT come later is also not part.

Re: Solving Fizz Buzz with Cosines

#36

Post by econ »

Made me envision this terrible idea.

arr = [];

y = 0;

setInterval(()=>{arr[y]=x},10)

setInterval(()=>{x=y++},1000)

setInterval(()=>{x="fizz"},3000)

setInterval(()=>{x="buzz"},5000)

setInterval(()=>{x="fizzbuzz"},15000)

Re: Solving Fizz Buzz with Cosines

#37

Post by theendisney »

Terretta wrote: post #30

The article conceit is fantastic. That said, is the going-in algo wrong? I see a case for 3 * 5 in here: for n in range(1, 101): if n % 15 == 0: print('FizzBuzz') elif n % 3 == 0: print('Fizz') elif n % 5 == 0: print('Buzz') else: print(n) Why? If we add 'Bazz' for mod 7, are we going to hardcode: for n in range(1, 105): if n % 105 == 0: # 3 * 5 * 7 print('FizzBuzzBazz') elif n % 15 == 0: # 3 * 5 print('FizzBuzz') el…

If we are going to be like that we should just increment a var by 3,5 or 7 and compare it rather than %3 as the later seems expensive.

Re: Solving Fizz Buzz with Cosines

#38

Post by Terretta »

michaelcampbell wrote: post #35
Terretta wrote: post #30

The article conceit is fantastic. That said, is the going-in algo wrong? I see a case for 3 * 5 in here: for n in range(1, 101): if n % 15 == 0: print('FizzBuzz') elif n % 3 == 0: print('Fizz') elif n % 5 == 0: print('Buzz') else: print(n) Why? If we add 'Bazz' for mod 7, are we going to hardcode: for n in range(1, 105): if n % 105 == 0: # 3 * 5 * 7 print('FizzBuzzBazz') elif n % 15 == 0: # 3 * 5 print('FizzBuzz') el…

> Sort of fun to muse whether almost all FizzBuzz implementations are a bit wrong. They're only wrong if they provide output that isn't in the spec. Adding "bazz" isn't in the spec, and assuming that something indeterminate MIGHT come later is also not part.

Yep, that's how people answer.

Folks really really don't like thinking that "FizzBuzz" case maybe shouldn't be there, future extension or factor edit or no.

// And as long as we're just manually computing factor times factor and typing out the results for it like "FizzBuzz" we might as well just hardcode the whole series...

Re: Solving Fizz Buzz with Cosines

#39

Post by mikestaas »

isoprophlex wrote: post #15

What a neat trick. I'm thinking you can abuse polynomials similarly. If the goal is to print the first, say, 100 elements, a 99-degree polynomial would do just fine :^) EDIT: the llm gods do recreational mathematics as well. claude actually thinks it was able to come up with and verify a solution... https://claude.ai/share/5664fb69-78cf-4723-94c9-7a381f947633

absolute madlad

Re: Solving Fizz Buzz with Cosines

#40

Post by theendisney »

jiggawatts wrote: post #26
isoprophlex wrote: post #15

What a neat trick. I'm thinking you can abuse polynomials similarly. If the goal is to print the first, say, 100 elements, a 99-degree polynomial would do just fine :^) EDIT: the llm gods do recreational mathematics as well. claude actually thinks it was able to come up with and verify a solution... https://claude.ai/share/5664fb69-78cf-4723-94c9-7a381f947633

That's the most expletive-laden LLM output I've ever seen. ChatGPT would have aborted half way through to protect its pure and unsullied silicon mind from the filthy impure thoughts.

It would find a therapist contact your employer, your wife and your dad.
Post reply on HN