From: Morton Goldberg <m_goldberg@...>
Date: 2007-07-26T04:24:20+09:00
Subject: Re: Efficiency/runtime trouble - may not be Ruby-specific

On Jul 25, 2007, at 11:45 AM, Kaldrenon wrote:

> 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?

Jano Svitok has already given you a good answer, but let me add my 2  
cents. Basically, you need a better algorithm. However, even if you  
were to stick with a brute-force approach, it could be speeded up.  
For one thing, you could just count the reduced fractions as you go  
along rather than accumulating a list of their values and counting  
that. Second, you could use the mathn standard library, which adds a  
gcd method to Integer (gcd is another name for HCF). Third, you can  
avoid converting integers to floats and doing float arithmetic. When  
I made these changes to your algorithm, I got the following results:

~ mg: time /Users/mg/Desktop/test.rb
Number of reduced fractions is 5066251

real    7m52.685s
user    7m22.083s
sys     0m2.275s

This is on a 2-GHz iMac. It's still very slow, but a lot faster than  
what you were experiencing. And it doesn't use much memory. I'm not  
showing my code here for fear of being a spoiler. I will post it if  
you ask.

Regards, Morton