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

4 billion if statements (2023)

andreasjhkarlsson.github.io

Post reply on HN
Print view View original

101–110 of 183 posts

Re: 4 billion if statements (2023)

#101

Post by weli »

thedougd wrote: post #99

I took an ASIC design class in college, unfortunately with a heavy course load that didn't allow me to focus on it. For our final project we were given a numbered dictionary and asked to design a chip that would accept the characters on a 7 bit interface (ASCII), one character per clock cycle and output the dictionary number on an output interface but I can't remember how wide. We were graded on the size of the resul…

Yep! Something a bit counterintuitive on circuit design is that dedicated transistors will always beat reusing existing components. If we do reuse existing components like ALUs, multipliers, or state machines, we save on chip area but pay the penalty in clock cycles. Your approach was the extreme version of this tradeoff. You essentially unrolled the entire dictionary lookup into pure combinatorial logic (well, with registers for the input characters). One clock cycle latency because you weren't doing any sequential searching, comparing, or state machine transitions just racing electrons through logic gates.

Re: 4 billion if statements (2023)

#102

Post by xnorswap »

nixpulvis wrote: post #98
xnorswap wrote: post #91

This is time efficient* but rather wasteful of space. The best way to save space is to use a Bloom Filter. If we capture all the even numbers, that would sadly only give us "Definitely not Even" or "Maybe Even". But for just the cost of doubling our space, we can use two Bloom filters! So we can construct one bloom filter capturing even numbers, and another bloom filter capturing odd numbers. Now we have "Definitely…

How is this time efficient at all? It takes upwards of 40 seconds to compute on large 32bit values. It's a joke post with some interesting bits and details.

It's a constant number of lookups, and all good Computer Scientists know that it is therefore an O(1) algorithm.

It is hard to imagine better efficiency than O(1)!

Indeed we could improve it further by performing all evaluations even when we find the answer earlier, ensuring it is a true Constant Time algorithm, safe for use in cryptography.

Re: 4 billion if statements (2023)

#103

Post by gopalv »

xnorswap wrote: post #91

This is time efficient* but rather wasteful of space. The best way to save space is to use a Bloom Filter. If we capture all the even numbers, that would sadly only give us "Definitely not Even" or "Maybe Even". But for just the cost of doubling our space, we can use two Bloom filters! So we can construct one bloom filter capturing even numbers, and another bloom filter capturing odd numbers. Now we have "Definitely…

> But for just the cost of doubling our space, we can use two Bloom filters!

We can optimize the hash function to make it more space efficient.

Instead of using remainders to locate filter positions, we can use a mersenne prime number mask (like say 31), but in this case I have a feeling the best hash function to use would be to mask with (2^1)-1.

Re: 4 billion if statements (2023)

#104

Post by catigula »

xg15 wrote: post #10

> Now, this is a time-memory tradeoff, but my time on this earth is limited so I decided to meta-program the if statements using a programmer program in a different programming language. for i in range(2*8): if i % 2 == 0: No comment...

Claude's version:

  even, odd = "even", "odd"
  for i in range(2\*32):
      print(f'    if (number == {i}) puts("{even}");')
      even, odd = odd, even
As usual, a non-marginally superior mind to commentators.

Re: 4 billion if statements (2023)

#105

Post by waisbrot »

thih9 wrote: post #82
mft_ wrote: post #53

Similar humour if opposite directions to an old favourite: https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/

I expected some job interview meme[1][2] but I did not know this one and it looks like a real story too! Thanks for sharing, that was a fun read. [1]: https://aphyr.com/posts/342-typing-the-technical-interview [2]: https://www.richard-towers.com/2023/03/11/typescripting-the-...

I love the Aphyr posts.

> “Can I use any language?” > > “Sure.” > > Move quickly, before he realizes his mistake.

Re: 4 billion if statements (2023)

#106

Post by kayge »

> any value over 2^31 seems to give random results.

Wow he really lucked out... On his way to perfecting a fully functioning and performant Even/Odd Detector, he stumbled upon a fully functioning and performant Coin Flip Simulator!

Re: 4 billion if statements (2023)

#107

Post by PurpleRamen »

travisgriggs wrote: post #90
PurpleRamen wrote: post #31

Earlier quoted context omitted.

I think we can improve this. Just make a microservice who generates the code on the fly and streams it to the compiler. Then you also just have to create the necessary code and don't waste the SSD with unused code-paths.

I’m disappointed there is no docker image for this. How will I test it out?

Microservice kinda implies usage of a container for me. How else would we google-scale it to serve all requests in parallel?

But thinking about, we probably have to use some more microservices, we can't put all that burden on the requester. So a dedicated service for compiling and executing in sandboxes would be necessary. Also, some local load balancers to control the flow and filter out the useless answers. So I'm not an expert on that devops-magic, but I guess this means ~12.5 billion pods fast enough result. Do Amazon or Google offer planetary scale for services?

Re: 4 billion if statements (2023)

#108

Post by nixpulvis »

xnorswap wrote: post #102
nixpulvis wrote: post #98

Earlier quoted context omitted.

How is this time efficient at all? It takes upwards of 40 seconds to compute on large 32bit values. It's a joke post with some interesting bits and details.

It's a constant number of lookups, and all good Computer Scientists know that it is therefore an O(1) algorithm. It is hard to imagine better efficiency than O(1)! Indeed we could improve it further by performing all evaluations even when we find the answer earlier, ensuring it is a true Constant Time algorithm, safe for use in cryptography.

> This is time efficient* but rather wasteful of space.

You're saying that the blog's solution is time efficient. Which it is not. Your solution may be O(1) but it is also not efficient. As I'm sure you are aware.

I can tell you a practical solution which is also O(1) and takes up maybe 2 or 3 instructions of program code and no extra memory at all.

`x & 1` or `x % 2 != 0`

This blog post was taking a joke and running with it. And your comment is in that spirit as well, I just wanted to point out that it's by no means time efficient when we have 2s or 1s complement numbers which make this algorithm trivial.

Re: 4 billion if statements (2023)

#109

Post by icambron »

nixpulvis wrote: post #108
xnorswap wrote: post #102

Earlier quoted context omitted.

It's a constant number of lookups, and all good Computer Scientists know that it is therefore an O(1) algorithm. It is hard to imagine better efficiency than O(1)! Indeed we could improve it further by performing all evaluations even when we find the answer earlier, ensuring it is a true Constant Time algorithm, safe for use in cryptography.

> This is time efficient* but rather wasteful of space. You're saying that the blog's solution is time efficient. Which it is not. Your solution may be O(1) but it is also not efficient. As I'm sure you are aware. I can tell you a practical solution which is also O(1) and takes up maybe 2 or 3 instructions of program code and no extra memory at all. `x & 1` or `x % 2 != 0` This blog post was taking a joke and running…

You need to read their entire comment as a joke.
Post reply on HN