Surely any solution that claims to be performant would use a binary search, rather than looping through every number. Would be a little trickier to generate the code though.
Edit: /s of course
Edit: /s of course
While this example is obviously silly because loading a number into a register and performimg some operations on it is going to be faster than a cache miss from jumping into a massive table, the general technique can absolutely be applied in the real world.
Hmm... Nevermind. A really smart way to solve this would be to store the result of the "isEven" computation directly on the b-tree, so the whole problem can be solved with a simple database query!
“We’ve got to scale the maths engine cluster to handle the load!”
https://github.com/i-voted-for-trump/is-even/blob/master/ind...
Is-thirteen, now THAT is a troll package.
0xC3C033C340C033
Then cast the array as if it was a uint32_t* add the number you want to check, cast it again as a function pointer of a function returns a int and voilà
It should take 16G of space to encode but it should require only a single page fault to load from disk.
uint64_t a[] = { [ 0 .. INT_MAX ] = 0xC3C033C340C033 } ;
int is_even(uint32_t n) {
return ((int (*)())((uint32_t *)a + n))();
}
Explaination:
That magic number is actually two 32-bit numbers juxtaposed:
The first one is 0xC340C033, which encodes the following instructions:
xor eax, eax ; 33 C0
inc eax ; 40
ret ; C3
The second number is similar but it doesn't include the "inc" instruction.
When casting as a int array we end up with an array with alternating function bodies. At even positions we have functions that return 1 (true) and at odd positions it returns 0 (false)
The interesting thing is each of those function bodies fit into a 32-bit number. A single jump to an arbitrary address would require larger array.
Of course, it's silly to do this for even/odd but it can be useful to understand how this works.
Go kids, build your own forths!
(Disclaimer: I haven't tried out any of the above and typed this on my phone while walking in the woods, so I'd be surprised if it actually works without some touches, but the gist of the idea should work)
Edit: fixes
.global a
.data
a:
.fill 0x7FFFFFFF, 8, 0xC3C033C340C033