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.
I 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.
You'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.
If 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."
Perhaps, 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.
It's a joke post with some interesting bits and details.