From: Fabian Streitel <karottenreibe@...>
Date: 2009-08-21T01:45:11+09:00
Subject: Re: How do I estimate how long it will take a calculation to 	complete?

--0015174c128673c36404719579cd
Content-Type: text/plain; charset=ISO-8859-1

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!

--0015174c128673c36404719579cd--