From: Kaldrenon <kaldrenon@...>
Date: 2007-07-26T00:45:00+09:00
Subject: Efficiency/runtime trouble - may not be Ruby-specific

Hi all - apologies in advance since this issue is not necessarily a
Ruby issue, but I've written the program in Ruby and the community
here has been very helpful/friendly in my experience.

I'm working on another problem from Project Euler ( http://www.projecteuler.net
). This one is problem 73 (I'm not actually that smart, I just jump
around ;-) ):

"Consider the fraction, n/d, where n and d are positive integers. If
nd and HCF(n,d)=1, it is called a reduced proper fraction. How many
fractions lie between 1/3 and 1/2 in the sorted set of reduced proper
fractions for d  10,000?"

So I set up an hcf(n,d) function that prime-factor-izes n and d to see
if n/d is reduced and proper:

Primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                    43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
def hcf(n,d)
  Primes_under_100.each do |prime|
    if (prime < Math.sqrt(d) &&
        n % prime == 0 &&
        d % prime == 0) ||
        d % n == 0
      return 2
    end
  end
  return 1
end

Then I ran that through a loop that builds an array of unique
instances of fractions between 1/2 and 1/3:

red_prop_fract = []
for d in 2..10_000 do
  for n in 1...d do
    if hcf(n,d) == 1 && n.to_f/d > 1.0/3 && n.to_f/d < 0.5
      red_prop_fract.push(n.to_f/d) unless red_prop_fract.include?
(n.to_f/d)
    end
  end
end

#Get the answer
p red_prop_fract.length


Now, I'm fairly certain that the algorithm is right, because I ran it
on their example of d < 9 and got the correct answer. However, this
setup is taking ridiculously long and I can't determine why. Running
on a computer with a 2.4GHz CPU and 256 Mb of RAM, I started it at
4:30 yesterday and it hasn't terminated!

I know that a nested 'for' loop that goes to n is O(n^2). And I know
that the array I'm building is rather big, and growing it gradually is
going to cause a lot of allocations and GCs. But I can't figure out
why it's being so ridiculous.

My first rule as a programmer is "Assume all problems are my fault."

Insights?

TIA,
Andrew