[deleted]
Test if a number is even
11–20 of 68 posts
Re: Test if a number is even
#12> I think the optimizer recognizes modulo 2 and converts it to bitwise AND. You don't have to guess, you could turn or O3 or look at the disassembly.
gcc does it even when it's not optimizing
Re: Test if a number is even
#13> Much better :) But what about C? Let’s try it:
> I tried both versions (modulo 2 and bitwise AND) and got the same result. I think the optimizer recognizes modulo 2 and converts it to bitwise AND.
Yes, even without specifying optimizations - https://godbolt.org/z/9se9c6qKT
You can see that the output of the compiler is identical whether you use `i%2 == 0` or `(i&1) == 0`. The bitwise AND is instruction 12 in the output.
Using -O3 like in the post actually compiles to SIMD instructions on x86-64 - https://godbolt.org/z/dWbcK947G
Re: Test if a number is even
#14You can actually generalize i % 2 == i & 1 to larger powers of 2.
Using C Syntax,
i % (1 holds for unsigned integer n and (1 << n) is 2 to the power of n.
Re: Test if a number is even
#15That’s not “even” wrong!
Re: Test if a number is even
#16Optimizing compilers have been able to recognize pretty complicated patterns for many years. For instance if you're making a loop to count the bits that are set in a number, the compiler can recognize the entire loop and turn it into a single popcnt instruction (e.g. https://lemire.me/blog/2016/05/23/the-surprising-cleverness-... )
I feel that the compiler is doing too much work here. I know they are thinking about special cases on generated code, but at some point it feels that it just adds compile time for no good reason.
Look at this --beauty-- eww, thing, should compilers really spend time trying to figure out how to optimise insane code?
def is_even(n):
return str(n)[len(str(n))-1] in [str(2*n) for n in range(5)]Re: Test if a number is even
#17I like the algorithms that are the opposite of this where they try to find the slowest possible way to determine if a number is even.
There’s no upper limit, so there’d have to be some set of rules like no sleep(n).
Also given the halting problem, you could write an algorithm that would be impossible to determine if it loops forever.
Re: Test if a number is even
#18> Much better :) But what about C? Let’s try it: > I tried both versions (modulo 2 and bitwise AND) and got the same result. I think the optimizer recognizes modulo 2 and converts it to bitwise AND. Yes, even without specifying optimizations - https://godbolt.org/z/9se9c6qKT You can see that the output of the compiler is identical whether you use `i%2 == 0` or `(i&1) == 0`. The bitwise AND is instruction 12 in the ou…
That's how you check modulus for powers of 2. 2 is a power of 2. This barely even qualifies as an "optimization".
Re: Test if a number is even
#19I like the algorithms that are the opposite of this where they try to find the slowest possible way to determine if a number is even.
https://github.com/blackburn32/serverlessIsEven "A serverless implementation of isEven. Now you can know if your numbers are even, even at mass scale."
How about sending a packet back and forth to a server in another continent n times, and if it stops coming back, it was odd.
Re: Test if a number is even
#20Optimizing compilers have been able to recognize pretty complicated patterns for many years. For instance if you're making a loop to count the bits that are set in a number, the compiler can recognize the entire loop and turn it into a single popcnt instruction (e.g. https://lemire.me/blog/2016/05/23/the-surprising-cleverness-... )
I feel that the compiler is doing too much work here. I know they are thinking about special cases on generated code, but at some point it feels that it just adds compile time for no good reason. Look at this --beauty-- eww, thing, should compilers really spend time trying to figure out how to optimise insane code? def is_even(n): return str(n)[len(str(n))-1] in [str(2*n) for n in range(5)]
These optimizations are very useful. Consider the only slightly less contrived case where you want to mod an index by the size of an array. And the compiler expands the inline function around a context where the array is a fixed power of two size at compile time. Poof, no division/modulus needed, magically. Lots and lots of code looks like this: general algorithms expressed in simple implementation that has a faster implementation in the specific instance that gets generated.