Morton Goldberg
7/25/2007 7:24:00 PM
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