William James
1/19/2007 2:44:00 AM
Ryan Davis wrote:
> On Jan 18, 2007, at 11:10 AM, William James wrote:
>
> > Ryan Davis wrote:
> >> I wrote mine a bit different:
> >>
> >> def prime(n)
> >> return false if n > 2 and n % 2 == 0
> >> max = sqrt(n)
> >> 3.upto(max) do |i|
> >> return false if i % 2 != 0 and n % i == 0
> >> end
> >> return true
> >> end
> >>
> >> optimize :prime
> >
>
> > You're saying that pure Ruby took less than 2 seconds?
> > I don't see how that is possible. On the faster of the two
> > computers at my disposal your version ran in 207 seconds.
>
> Yes, on my computer it ran in 2 seconds, but I didn't have the same
> driver as you did because I couldn't go into the bignum range. So I
> did the biggest you had an extra 20 times instead.
Your mentioning bignums made me wonder whether my previous
benchmark was fair to Ruby, since Lua was using 64-bit floats
instead of bignums. Here's a revised version that doesn't use
bignums.
# Ruby
def prime(n)
if n > 2 and n % 2 == 0
return false
end
3.step( Math.sqrt(n).floor, 2){|i|
if n % i == 0
return false
end
}
true
end
reps = 10
puts "Testing each number #{reps} times."
time = Time.now
count, prime_count = 0, 0
"
27 39, 79, 111, 115, 135, 187, 199, 219, 231, 235
28 57, 89, 95, 119, 125, 143, 165, 183, 213, 273
29 3, 33, 43, 63, 73, 75, 93, 99, 121, 133
30 35, 41, 83, 101, 105, 107, 135, 153, 161, 173
".scan( /[^\n]+/ ){|line|
exp = nil
line.scan( /\d+/ ){|digits|
if exp
number = 2**exp - digits.to_i
bool = false
reps.times { bool = prime( number ) }
if bool then
prime_count += 1
end
count += 1
else
exp = digits.to_i
end
}
}
puts Time.now - time
puts format("Of %d numbers, %d were prime.", count, prime_count )
-- Lua
function prime(n)
if n > 2 and n % 2 == 0 then
return false
end
for i = 3, math.floor(math.sqrt(n)), 2 do
if n % i == 0 then
return false
end
end
return true
end
reps = 10
io.write( "Testing each number ", reps, " times.\n" )
time = os.clock()
count, prime_count = 0, 0
for line in string.gmatch( [[
27 39, 79, 111, 115, 135, 187, 199, 219, 231, 235
28 57, 89, 95, 119, 125, 143, 165, 183, 213, 273
29 3, 33, 43, 63, 73, 75, 93, 99, 121, 133
30 35, 41, 83, 101, 105, 107, 135, 153, 161, 173
]] , "[^\n]+" ) do
exp = nil
for digits in string.gmatch( line, "%d+" ) do
if exp then
num = 2^exp - tonumber( digits )
for i = 1, reps do
bool = prime( num )
end
if bool then
prime_count = prime_count + 1
end
count = count + 1
else
exp = tonumber( digits )
end
end
end
print(os.clock() - time)
print( string.format("Of %d numbers, %d were prime.", count,
prime_count ) )
-----
Results on my old laptop:
Ruby 9.674 sec.
Lua 1.922
LuaJIT .210
Based upon these results and your experiment with optimize:
Speedup compared to pure Ruby
-----------------------------
optimize 4.397
Lua 5.033
LuaJIT 46.066