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

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
User avatar
Jaxolotl
Forum Contributor
Posts: 137
Joined: Mon Nov 13, 2006 4:19 am
Location: Argentina and Italy

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

Post 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?
User avatar
superdezign
DevNet Master
Posts: 4135
Joined: Sat Jan 20, 2007 11:06 pm

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

Post 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;
User avatar
arturm
Forum Commoner
Posts: 86
Joined: Fri Apr 13, 2007 8:29 am
Location: NY
Contact:

Post 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";
User avatar
stereofrog
Forum Contributor
Posts: 386
Joined: Mon Dec 04, 2006 6:10 am

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

Post 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?
User avatar
Oren
DevNet Resident
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Post by Oren »

Suppose is_odd() cost $50,000 and 1 sql query $1M, then is_odd() x 20 times = 1 sql query.
User avatar
Oren
DevNet Resident
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Post by Oren »

arturm wrote:They look the same for me.
That's because you are using time() instead of microtime() :P
User avatar
arturm
Forum Commoner
Posts: 86
Joined: Fri Apr 13, 2007 8:29 am
Location: NY
Contact:

Post 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.
User avatar
Oren
DevNet Resident
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Post 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);
:? :?:
User avatar
Jaxolotl
Forum Contributor
Posts: 137
Joined: Mon Nov 13, 2006 4:19 am
Location: Argentina and Italy

Post 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.
User avatar
Oren
DevNet Resident
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Post by Oren »

Jaxolotl wrote:at least you can deduce that the output will be true or false
See Type Casting.
User avatar
RobertGonzalez
Site Administrator
Posts: 14293
Joined: Tue Sep 09, 2003 6:04 pm
Location: Fremont, CA, USA

Post 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; 
}
?>
User avatar
Oren
DevNet Resident
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Post 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:
User avatar
RobertGonzalez
Site Administrator
Posts: 14293
Joined: Tue Sep 09, 2003 6:04 pm
Location: Fremont, CA, USA

Post by RobertGonzalez »

I suppose you're right, it could potentially be the same numbers of characters. Sorry about that.
User avatar
stereofrog
Forum Contributor
Posts: 386
Joined: Mon Dec 04, 2006 6:10 am

Post 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?
User avatar
Jaxolotl
Forum Contributor
Posts: 137
Joined: Mon Nov 13, 2006 4:19 am
Location: Argentina and Italy

Post 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...
Post Reply