4 ms·
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.
by nixpulvis 10mo ago
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.
- xnorswap 10mo agoIt'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.
- nixpulvis 10mo ago> 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.
- icambron 10mo agoYou need to read their entire comment as a joke.
- nixpulvis 10mo agoI guess I should have been more clear that I was just pointing out the obvious in case some confused reader missed the joke. lol
- henrikschroder 10mo ago> I just wanted to point out that We already know. Everybody knows. That's the joke. There's no need to point out anything.
- Maxatar 10mo agoThe comment you're replying to is also a joke, with some interesting bits and details.
- nixpulvis 10mo agoI think I'll just avoid commenting on jokes from now on.
- Sohcahtoa82 10mo agoHow are you able to recognize a joke post but not a joke comment?
- nixpulvis 10mo agoI may have missed the * meaning. I got that the bloom filter was an extension of the joke as I mentioned below. I was just clarifying in case someone else missed the joke.
- uplifter 10mo agoYou're absolutely right. The obvious solution would have been to create a boolean table containing all the pre-computed answers, and then simply use the integer you are testing as the index of the correct answer in memory. Now your isEven code is just a simple array lookup! Such an obvious improvement, I can't believe the OP didn't see it. And with a little extra work you can shrink the whole table's size in memory by a factor of eight, but I'll leave that as an exercise for the interested reader.
- mandarax8 10mo agoMaybe we can even find some correlation in the bit pattern of the input and the Boolean table!
- __david__ 10mo agoPerhaps, but I fear you’re veering way too much into “clever” territory. Remember, this code has to be understandable to the junior members of the team! If you’re not careful you’ll end up with arcane operators, strange magic numbers, and a general unreadable mess.
- jiggawatts 10mo agoIf the "exercise" is to strictly rely on if-else statements, then the obvious speedup is to perform a binary search instead of a linear one. The result would still be horrifically space inefficient, but the speed would be roughly the time it takes to load 32x 4KB pages randomly from disk (the article memory-mapped the file). On a modern SSD a random read is 20 microseconds, so that's less than a millisecond for an even/odd check! "That's good enough, ship it to production. We'll optimise it later."
- nrhrjrjrjtntbt 10mo agor/whoosh