Hi there, I wrote a short ruby script to calculate the prime factors
of a given number. I wrote it based on a question someone asked me.
It seems to work well for “reasonable” numbers but then I fed it an
unreasonable number and it hasn’t stopped running for 6 days now.
So, my question is: how can I estimate how long I can expect a
calculation like this to complete?
Here are some specs:
- system = Intel dual core cpu @ 2.66 GHz, 3 GB RAM
- O/S = WinXP Pro SP2
- Ruby version = 1.8.6-25
----- Ruby script:
num = 100
puts “Finding prime factors for the number: #{num}”
max_factor = Math.sqrt( num )
base_primes = [ 2, 3, 5 ]
prime = true
7.step( max_factor.to_i, 2) do | number |
base_primes.each do | known |
prime = false if number % known == 0
end
base_primes << number if prime == true
prime = true
end
base_primes.each do |factor|
if num % factor == 0
puts “Aha! #{factor} is a factor.”
end
end
----- End of script.
I wrapped some ‘time’ lines around some of the code above so that I
could see how long it took to find the primes for certain inputs. It
might not be the most efficient way to calculate the primes but I
wasn’t worried about that when I wrote it.
For example, it took about 2 seconds to find the primes for a 9-digit
number, and 30 seconds to find the primes for a 10-digit number.
So then I got silly and fed it a 19-digit number (a specific number,
BTW, not just 19 random digits), and it’s been working for 6 days
now. I thought I’d just let it run and see what numbers I get.
What’s the problem? Well, it seems there’s going to be a scheduled
power outage here in about 4 days and I was just wondering if the
script was going to complete before then. =)
That, and the fact that after it works out the primes for the 19-digit
number, I have a 29-digit number that I was hoping to try and factor.
I’d like to have a rough idea of how long that might take on this
system… however, I’m pretty sure I shouldn’t use this computer for
that calculation now.
I’m not familiar with working out how long it takes the CPU to do
certain mathematical calculations so I’m not sure how to estimate how
long it will take to complete the script.
Can anyone help? Suggestions?
Please let me know. TIA.
Cheers. Paul.