alt Hacker NewsHow 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.
Replies
How are you able to recognize a joke post but not a joke comment?
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.
The comment you're replying to is also a joke, with some interesting bits and details.
r/whoosh
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.