Velocity Reviews > Ruby > simple math question

simple math question

Guest
Posts: n/a

 10-25-2006
What's the quickest way to determine if an int is an even number
2,4,6,8...
Anything such as int.even or int.odd returning true/false? I want to
test the length of an array and add one element to it if it has an odd
number of elements.

Thank you!

--
Posted via http://www.ruby-forum.com/.

Bill Kelly
Guest
Posts: n/a

 10-25-2006
>
> What's the quickest way to determine if an int is an even number
> 2,4,6,8...
> Anything such as int.even or int.odd returning true/false? I want to
> test the length of an array and add one element to it if it has an odd
> number of elements.

class Integer
def even?
(self & 1) == 0
end
end

Hope this helps,

Bill

Rick DeNatale
Guest
Posts: n/a

 10-25-2006
On 10/25/06, Brad Tilley <> wrote:
> What's the quickest way to determine if an int is an even number
> 2,4,6,8...
> Anything such as int.even or int.odd returning true/false? I want to
> test the length of an array and add one element to it if it has an odd
> number of elements.
>
> Thank you!

Integer#[n] returns a 1 or 0 corresponding to bit n, with n=0 being
the least significant bit.

so

Even:
an_int[0].zero?

Odd:
an_int[0].nonzero?

--
Rick DeNatale

My blog on Ruby

Guest
Posts: n/a

 10-25-2006
Thanks for all the examples guys! Being Ruby, I thought there might be
some super simple method that just magically did this. I'll stick with
the old-fashioned modulo test.

--
Posted via http://www.ruby-forum.com/.

Rick DeNatale
Guest
Posts: n/a

 10-26-2006
On 10/25/06, Jeffrey Schwab <> wrote:
> Paul Lutus wrote:
> >
> >> Thanks for all the examples guys! Being Ruby, I thought there might be
> >> some super simple method that just magically did this. I'll stick with
> >> the old-fashioned modulo test.

> >
> > If speed matters, the modulo test is way slower than testing the LSB.

>
> Do you mean on a specific architecture, or is there a Ruby-specific
> reason for one to be slower than the other?

Not really ruby-specific, and for the most part architecture independent.

Modulo basically involves an integer division operation, whereas bit
testing is a simple logical and with a mask.

(int & 1).zero? is probably faster than
int[0].zero?

Since the latter generates the mask using the bit position.

and both should be faster than

(int % 2).zero?

But it it's performance critical, benchmarking is recommended to
verify. One should never simply take 'rules of thumb' for granted.

--
Rick DeNatale

My blog on Ruby

Ken Bloom
Guest
Posts: n/a

 10-26-2006
On Thu, 26 Oct 2006 01:19:08 +0000, Jeffrey Schwab wrote:

> Paul Lutus wrote:
>>
>>> Thanks for all the examples guys! Being Ruby, I thought there might be
>>> some super simple method that just magically did this. I'll stick with
>>> the old-fashioned modulo test.

>>
>> If speed matters, the modulo test is way slower than testing the LSB.

>
> Do you mean on a specific architecture, or is there a Ruby-specific
> reason for one to be slower than the other?

Modulo uses division hardware, which is slower than the hardware for
bitwise operations. Most C compilers know how to optimize this sort of
thing when it's known in advance that you're doing mod 2. I doubt Ruby's
that smart.

--Ken

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

Phrogz
Guest
Posts: n/a

 10-26-2006
Rick DeNatale wrote:
> (int & 1).zero? is probably faster than
> int[0].zero?
>
> Since the latter generates the mask using the bit position.
>
> and both should be faster than
>
> (int % 2).zero?
>
> But it it's performance critical, benchmarking is recommended to
> verify. One should never simply take 'rules of thumb' for granted.

Let's just do it rather than speculating:

require 'benchmark'

ITERATIONS = 1_000_000
MAX_INT = 2 ** 30
NUMS = (1..ITERATIONS).map{ rand(MAX_INT) }
Benchmark.bmbm{ |x|
x.report '(n % 2).zero?' do
NUMS.each{ |n|
(n % 2).zero?
}
end

x.report 'n[0].zero?' do
NUMS.each{ |n|
n[0].zero?
}
end

x.report '(n & 1).zero?' do
NUMS.each{ |n|
(n & 1).zero?
}
end
}

#=> Rehearsal -------------------------------------------------
#=> (n % 2).zero? 2.060000 0.020000 2.080000 ( 2.244595)
#=> n[0].zero? 1.960000 0.010000 1.970000 ( 2.14523
#=> (n & 1).zero? 1.990000 0.020000 2.010000 ( 2.275232)
#=> ---------------------------------------- total: 6.060000sec
#=>
#=> user system total real
#=> (n % 2).zero? 2.070000 0.010000 2.080000 ( 2.315105)
#=> n[0].zero? 1.960000 0.020000 1.980000 ( 2.14303
#=> (n & 1).zero? 1.990000 0.010000 2.000000 ( 2.173120)

There is a very, very, very small difference in speed.

Rick DeNatale
Guest
Posts: n/a

 10-26-2006
On 10/26/06, Phrogz <> wrote:
> Rick DeNatale wrote:
> > (int & 1).zero? is probably faster than
> > int[0].zero?
> >
> > Since the latter generates the mask using the bit position.
> >
> > and both should be faster than
> >
> > (int % 2).zero?
> >
> > But it it's performance critical, benchmarking is recommended to
> > verify. One should never simply take 'rules of thumb' for granted.

>
> Let's just do it rather than speculating:
>
> require 'benchmark'
>
> ITERATIONS = 1_000_000
> MAX_INT = 2 ** 30
> NUMS = (1..ITERATIONS).map{ rand(MAX_INT) }
> Benchmark.bmbm{ |x|
> x.report '(n % 2).zero?' do
> NUMS.each{ |n|
> (n % 2).zero?
> }
> end
>
> x.report 'n[0].zero?' do
> NUMS.each{ |n|
> n[0].zero?
> }
> end
>
> x.report '(n & 1).zero?' do
> NUMS.each{ |n|
> (n & 1).zero?
> }
> end
> }
>
> #=> Rehearsal -------------------------------------------------
> #=> (n % 2).zero? 2.060000 0.020000 2.080000 ( 2.244595)
> #=> n[0].zero? 1.960000 0.010000 1.970000 ( 2.14523
> #=> (n & 1).zero? 1.990000 0.020000 2.010000 ( 2.275232)
> #=> ---------------------------------------- total: 6.060000sec
> #=>
> #=> user system total real
> #=> (n % 2).zero? 2.070000 0.010000 2.080000 ( 2.315105)
> #=> n[0].zero? 1.960000 0.020000 1.980000 ( 2.14303
> #=> (n & 1).zero? 1.990000 0.010000 2.000000 ( 2.173120)
>
> There is a very, very, very small difference in speed.

Which is why I suggested actually doing the benchmarks after
explaining why mod would be expected to be slower.

Now I took this benchmark and simplified it, taking out the zero? call
in an attempt to isolate the cost of each approach. I also added a
benchmark of an empty loop. On my machine this seems to make the hot
run of mod FASTER than bit testing on 1.8, but not on 1.9:

rick@frodo:/public/rubyscripts\$ ruby bitbm.rb
Rehearsal ----------------------------------------------
empty loop 1.840000 0.410000 2.250000 ( 3.366799)
n % 2 3.680000 0.910000 4.590000 ( 5.636832)
n[0] 3.650000 1.020000 4.670000 ( 9.325569)
(n & 1) 3.890000 0.840000 4.730000 ( 6.346543)
------------------------------------ total: 16.240000sec

user system total real
empty loop 1.790000 0.480000 2.270000 ( 3.695585)
n % 2 3.700000 0.880000 4.580000 ( 8.864955)
n[0] 3.740000 0.910000 4.650000 ( 13.832782)
(n & 1) 3.850000 0.870000 4.720000 ( 12.540741)

rick@frodo:/public/rubyscripts\$ ruby1.9 bitbm.rb
Rehearsal ----------------------------------------------
empty loop 1.280000 0.010000 1.290000 ( 1.964290)
n % 2 2.900000 0.010000 2.910000 ( 6.053066)
n[0] 2.370000 0.000000 2.370000 ( 3.57292
(n & 1) 2.660000 0.010000 2.670000 ( 4.322753)
------------------------------------- total: 9.240000sec

user system total real
empty loop 1.230000 0.000000 1.230000 ( 2.415479)
n % 2 2.750000 0.010000 2.760000 ( 4.028753)
n[0] 2.390000 0.000000 2.390000 ( 3.322041)
(n & 1) 2.400000 0.010000 2.410000 ( 3.548835)

And n[0] seems faster than n & 1 which is a slight surprise, to me at least.

By the way, is the actual meaning of user, system, total, and real
documented anywhere. I've looked around a few times, and haven't
uncovered it. I guess I could try to devine it by reading the code
for benchmark, but...

Here's my version of Phrogz benchmark code FWIW;
require 'benchmark'

ITERATIONS = 1_000_000
MAX_INT = 2 ** 30
NUMS = (1..ITERATIONS).map{ rand(MAX_INT) }
Benchmark.bmbm{ |x|

x.report 'empty loop' do
NUMS.each {|n|}
end

x.report 'n % 2' do
NUMS.each{ |n|
n % 2
}
end

x.report 'n[0]' do
NUMS.each{ |n|
n[0]
}
end

x.report '(n & 1)' do
NUMS.each{ |n|
(n & 1)
}
end
}
--
Rick DeNatale

My blog on Ruby

Guest
Posts: n/a

 10-26-2006
Paul Lutus wrote:
> Rick DeNatale wrote:
>
> / ...
>
>> By the way, is the actual meaning of user, system, total, and real
>> documented anywhere. I've looked around a few times, and haven't
>> uncovered it. I guess I could try to devine it by reading the code
>> for benchmark, but...

>
> System time is time spent outside userspace, e.g. direct kernel calls.
> User time is time spent directly executing user code in userspace.
>
> I think total time and real time are self-explanatory, but just in case ...
> total time is system + user + kernel overhead not properly accounted for,
> and real time is simply an RTC measurement at the end of the process life
> subtracted from the same at the beginning. It is expected (in a manner of
> speaking) that none of these quantities will add as one would expect.
>

I actually dug into this a few weeks ago for the RHEL 3 version of the
2.4.21 Linux kernel. It's mildly complicated and changes from version to
version of the Linux kernel, especially the scheduler. And the external
tools don't always "do the right thing" either. And I *only* looked at
Linux; I'm not in possession of the same information for BSD or MacOS. I
can probably track it down for Windows, however -- it's documented in
Mark Friedman's book in the Windows 2003 Server Resource Kit.

P.S.: Paul's response is essentially correct and "close enough for all
practical purposes". I get paid to care about the cases when it isn't.

Rick DeNatale
Guest
Posts: n/a

 10-26-2006
On 10/26/06, M. Edward (Ed) Borasky <> wrote:
> Paul Lutus wrote:
> > Rick DeNatale wrote:
> >
> > / ...
> >
> >> By the way, is the actual meaning of user, system, total, and real
> >> documented anywhere. I've looked around a few times, and haven't
> >> uncovered it. I guess I could try to devine it by reading the code
> >> for benchmark, but...

> >
> > System time is time spent outside userspace, e.g. direct kernel calls.
> > User time is time spent directly executing user code in userspace.
> >
> > I think total time and real time are self-explanatory, but just in case ...
> > total time is system + user + kernel overhead not properly accounted for,
> > and real time is simply an RTC measurement at the end of the process life
> > subtracted from the same at the beginning. It is expected (in a manner of
> > speaking) that none of these quantities will add as one would expect.
> >

>
> I actually dug into this a few weeks ago for the RHEL 3 version of the
> 2.4.21 Linux kernel. It's mildly complicated and changes from version to
> version of the Linux kernel, especially the scheduler. And the external
> tools don't always "do the right thing" either. And I *only* looked at
> Linux; I'm not in possession of the same information for BSD or MacOS. I
> can probably track it down for Windows, however -- it's documented in
> Mark Friedman's book in the Windows 2003 Server Resource Kit.
>
> M. Edward "That Guy" Borasky
>
> P.S.: Paul's response is essentially correct and "close enough for all
> practical purposes". I get paid to care about the cases when it isn't.
>

Thanks guys, I figured that it was something like that. I looked at
the source code for benchmark and it's just getting Process.times
before and after the block.

That said, I wonder what these presumably purely computational blocks
are doing in the kernel at all. In a way that's why I wasn't sure, in
the context of ruby benchmarking I was sort of hoping that it was
differentiating between library C code and ruby code, but it really
isn't.

I guess that the system time must be spent in something like process

--
Rick DeNatale

My blog on Ruby