Page 1 of 1

even/odd bitwise or module operation the most efficient way?

Posted: Tue Jul 10, 2007 10:02 am
by Jaxolotl
Hi guys, it's me again with a freak question.

there are two well known ways to return an "odd/even" result when analyzing a number.

1 - Usign bitwise operation

Code: Select all

function is_odd($number){
  return ($number & 1) ? true:false;
}
where the $number and the number 1 will be converted to binary and we know that all odd numbers have the 1 as LSB and the even numbers have 0 as LSB so:
(0000 & 0001) -> 0000 -> false
(0001 & 0001) -> 0001 -> true
(0010 & 0001) -> 0000 -> false
(0011 & 0001) -> 0001 -> true

and we have the % Modulus that calculates the Remainder of $a divided by $b
so

Code: Select all

function is_odd($number){
  return ($number % 2) ? true:false;
}
where if any number divided by 2 returns a reminder different than 0 we are pretty shure it's not an even value.

Well here's my queastion:
Which one is more efficient? the division or the binary conversion and then the bitwise comparison?
It seems that the division would be better, is it wright?

how could I benchmark this?

Re: even/odd bitwise or module operation the most efficient

Posted: Tue Jul 10, 2007 11:00 am
by superdezign
Jaxolotl wrote:how could I benchmark this?

Code: Select all

$start = microtime(true);
func1(5);
$time = microtime(true) - $start;
echo 'func1(): ' .$time . "<br />\n";

$start = microtime(true);
func2(5);
$time = microtime(true) - $start;
echo 'func2(): ' .$time;

Posted: Tue Jul 10, 2007 11:10 am
by arturm
They look the same for me.

My benchmark:

Code: Select all

function is_odd($number){
  return ($number & 1) ? true:false;
}
function is_odd2($number){
  return ($number % 2) ? true:false;
} 

$time1 = time();

for ($i = 0; $i <= 10000000; $i++) {
    $number = rand(1,1000);
    $tmp = is_odd($number);
}

$time2 = time();

for ($i = 0; $i <= 10000000; $i++) {
    $number = rand(1,1000);
    $tmp = is_odd2($number);
}

$time3 = time();

echo "odd using bitwise comparison: ".($time2-$time1)." sec\n";
echo "odd using remainder: ".($time3-$time2)." sec\n";

Re: even/odd bitwise or module operation the most efficient

Posted: Tue Jul 10, 2007 11:23 am
by stereofrog
Jaxolotl wrote: Which one is more efficient? the division or the binary conversion and then the bitwise comparison?
It seems that the division would be better, is it wright?
Think of it this way. Suppose bitwise and (in the C library code) costs 50 cent, and modulus, say, 70 cent. Then, the mere translation from php to library call would cost $50,000 and one single SQL query - about one million. So, does it really matter, what is more efficient?

Posted: Tue Jul 10, 2007 11:50 am
by Oren
Suppose is_odd() cost $50,000 and 1 sql query $1M, then is_odd() x 20 times = 1 sql query.

Posted: Tue Jul 10, 2007 11:51 am
by Oren
arturm wrote:They look the same for me.
That's because you are using time() instead of microtime() :P

Posted: Tue Jul 10, 2007 12:01 pm
by arturm
as you can see I have a loop with 10 million function calls.
If there was a difference it would be in seconds.

if you use microtime() it will be more accurate but in this case it is not a big difference.

Posted: Tue Jul 10, 2007 12:31 pm
by Oren
I actually didn't read your code, but I still prefer microtime - even though that I do agree with you :P

By the way, Jaxolotl - what's the point of doing:

Code: Select all

return ($number & 1) ? true:false;
instead of this:

Code: Select all

return ($number & 1);
:? :?:

Posted: Tue Jul 10, 2007 1:07 pm
by Jaxolotl
Oren wrote:By the way, Jaxolotl - what's the point of doing:.........
good point Oren!!! good observer!!!
the only one point is that I work with php beginners too and that way is kind of self explained, so when you don't know what the code is doing, at least you can deduce that the output will be true or false, that's all



By the way, as I said before all this staff is just a theorical curiosity of mine, more you understand the environment, better you know how to adapt it for your needs.

Posted: Tue Jul 10, 2007 2:30 pm
by Oren
Jaxolotl wrote:at least you can deduce that the output will be true or false
See Type Casting.

Posted: Tue Jul 10, 2007 2:31 pm
by RobertGonzalez
I think in this case I would tend to go with a bitwise comparison just because there is less code involved.

Code: Select all

<?php
function is_odd($number){ 
  return $number & 1; 
}
?>

Posted: Tue Jul 10, 2007 2:38 pm
by Oren
Well, I would go this route too, but how is it less code?
I'd do a small type cast to boolean too by the way :wink:

Posted: Tue Jul 10, 2007 2:43 pm
by RobertGonzalez
I suppose you're right, it could potentially be the same numbers of characters. Sorry about that.

Posted: Tue Jul 10, 2007 3:40 pm
by stereofrog
Jaxolotl wrote: By the way, as I said before all this staff is just a theorical curiosity of mine, more you understand the environment, better you know how to adapt it for your needs.
Well, if you're *really* intersted... here's an AT&T assembly code that implements "b = a % 2" in glibc

Code: Select all

movl	-4(%ebp), %edx
	movl	%edx, %eax
	sarl	$31, %eax
	shrl	$31, %eax
	leal	(%edx,%eax), %eax
	sarl	%eax
	addl	%eax, %eax
	subl	%eax, %edx
	movl	%edx, %eax
	movl	%eax, -8(%ebp)
compared to this, "a = b & 1" code is quite laconic

Code: Select all

movl	-4(%ebp), %eax
	andl	$1, %eax
	movl	%eax, -8(%ebp)
so, we have 3 commands against 10. Binary seems to be a winner, but does it make any practical difference? No, because before php executor reaches glibc code, it runs several thousand other, not immediately relevant assembly commands. As some people didn't get my money metaphor ;) here's another one: if you're going to drive from LA to NY, would it matter if there's 3961 or 3962 km?

Posted: Tue Jul 10, 2007 5:10 pm
by Jaxolotl
stereofrog wrote: so, we have 3 commands against 10. Binary seems to be a winner, but does it make any practical difference? No, because before php executor reaches glibc code, it runs several thousand other, not immediately relevant assembly commands. As some people didn't get my money metaphor ;) here's another one: if you're going to drive from LA to NY, would it matter if there's 3961 or 3962 km?
Thank you really much for your peace of code above stereofrog and all of you people!! all this answers give me very intresting points to aproach the theorical problem.
There's a key point in the question I make that maybe is not really visible, I'm asking (to use your metaphore) "if I'm walking from LA to NY which is the difference between using rubber shoes or leather ones", what about my feets, knees, bones,etc.. This is a kind of "backstage" question because even if the difference between using the modulus or bitwise operation for web applications is practically irrelevant, the comprehension of what all of you post here is really precious for the inner understanding of my programming environment. I'm just a PHP programmer and never deal with any other language, so I'm trying to grow up. Or maybe I'm going crazy...