Anonymous user
Talk:Primorial numbers: Difference between revisions
→a faster-than-exponential growth rate in CPU time stated by dinosaur: new section
(factor tree?) |
|||
Line 3:
say "First ten primorials: ", join ", ", map { pn_primorial($_) } 0..9;</lang> and all is done ;-)
[[user#Horsth|Horsth]]
== a faster-than-exponential growth rate in CPU time stated by dinosaur ==
school - multiplication ist quadratic in runtime O(count of digits) ~ (count of digits)^2
<pre>Prime(100000) = 1299709, Primorial(100000) ~ 0.1909604E+563921 121.547 seconds.
Prime(1000000) = 15485863, Primorial(1000000) ~ 0.1147175E+6722809 17756.797 seconds.</pre>
10-times Numbers -> ~100-times runtime 121*100-> 12100
the digitcount of the numbers one multiplies grew be a factor of lg10(15.45Mio)/lg10(1.299Mio) =1,17
so you get 10-> (1.17*10) ^ 2 = 136,89*121,547= 16638 thats not far from 17756
Now take into account that the number gets so big, that it doesn't fit in level3 Cache ,which slow things down.Only 3% will be enough
121,547*(1.17*1.03*10)^2 s = 17651 s [[user#Horsth|Horsth]]
| |||