From: "Peña, Botp" <botp@...>
Date: 2008-06-23T13:08:48+09:00
Subject: Re: little problem (google hiring puzzle)

From: Calamitas [mailto:calamitates@gmail.com] 
# But you are likely to see widely varying results. The puzzle assumes
# that multiplication is O(1). That's true for Fixnums , but not for
# Bignums. Bignum multiplication is O(n.log(n)) or O(n^2) depending on
# Ruby's implementation. So say your random array starts and ends with
# 0,then you will stay in the Fixnum range and you will measure O(n)
# performance. If your random array happens to be full of numbers around
# 100 or so, your benchmark should show O(n^2.log(n)) or O(n^3)
# behavior. To stay in the Fixnum range and get O(1) performance for
# multiplication, use an array of all 0 or 1. Then you should see linear
# performance. Using an array of all 100 should give predictable
# results, but you should see O(n^2.log(n)) or O(n^3) behavior.

totally.
i tested it again by using different array values, and using a simple loop like,

Benchmark.bmbm do |x|
  0.step(10_000,100) do |i|
    x.report(i.to_s) { ohwan(array[0,i]) }
  end
end

the difference is tremendous.

thank you for the enlightenment, Peter.
kind regards -botp