How do I estimate how long it will take a calculation to complete?

[Paul]

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.

 

[lith]

Can anyone help? =A0Suggestions?

http://en.wikipedia.org/wiki/Analysis_of_algorithms
http://en.wikipedia.org/wiki/Big_O_notation
http://en.wikipedia.org/wiki/Introduction_to_Algorithms

 

[Fabian Streitel]

[Note: parts of this message were removed to make it a legal post.]

looooooooooooong! if it already takes days to calculate 19 digits, i'd guess


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

T(n) = sum[i = 1..sqrt(n)](sum[1..O(i)](1)) =
= sum[i=1..sqrt(n)](O(i)) =
= sum[i=1..sqrt(n)](O(n)) =
= O(n*sqrt(n)) = bad ;-)

base_primes.each do |factor|

if num % factor == 0
puts "Aha! #{factor} is a factor."
end
end

= sum[i=1..O(sqrt(n))](1) = O(sqrt(n))

So, I conclude that your script is O((n +1)*sqrt(n)) = O(n*sqrt(n)),
meaning, if you input a numer 4 times the size, it will take at maximum
4*2 = 8 times as long.
You input a number 9e10 times as large as the 10 digit version, meaning
it'll take at max 9e10^sqrt(9e10) times as long.
times 30sec that means at max 9375000000000 days to complete... happy
waiting

Greetz!

 

[Fabian Streitel]

[Note: parts of this message were removed to make it a legal post.]

looooooooooooong! if it already takes days to calculate 19 digits, i'd
guess

hm, that looks like an unfinished sentence there.... where'd that come from?

 

[lith]

O((n +1)*sqrt(n)) = O(n*sqrt(n))

I still think people should do their homework (even though it's
August) by themselves. Or learn how to use better algorithms.

 

[Paul Carvalho]

You input a number 9e10 times as large as the 10 digit version, meaning
it'll take at max 9e10^sqrt(9e10) times as long.
times 30sec that means at max 9375000000000 days to complete... happy
waiting

Greetz!

ha ha. I've stopped the script. =D

Thanks!

 

[Fabian Streitel]

[Note: parts of this message were removed to make it a legal post.]

I still think people should do their homework (even though it's
August) by themselves. Or learn how to use better algorithms.

I thought it was a fun excercise But you're right, he should do it
himself.
So: here's your task: calculate how long it would take for the 29 digit
number hehe
And give me the result in Galactic years:
http://en.wikipedia.org/wiki/Galactic_year

Greetz!

 

[William Rutiser]

ha ha. I've stopped the script. =D

Thanks!

Paul,

Now that you have a little experience with the problem, to see what you
were up against, see

http://en.wikipedia.org/wiki/Prime_factorization

-- Bill

 

[Paul Carvalho]

And http://rosettacode.org/wiki/Prime_decompositionto see
implementations in several languages, Ruby included.

That's cool! I've never heard of Rosetta Code before. I've
bookmarked it now!

Cheers! =)