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