Talk:Primorial numbers: Difference between revisions
(factor tree?) |
|||
| Line 3: | Line 3: | ||
say "First ten primorials: ", join ", ", map { pn_primorial($_) } 0..9;</lang> and all is done ;-) |
say "First ten primorials: ", join ", ", map { pn_primorial($_) } 0..9;</lang> and all is done ;-) |
||
[[user#Horsth|Horsth]] |
[[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]] |
|||
Revision as of 19:47, 8 April 2016
PARI/GP you speak about factor tree, but only primes are used, where is the advantage??? I love such solutions like in perl <lang perl>use ntheory qw(pn_primorial); say "First ten primorials: ", join ", ", map { pn_primorial($_) } 0..9;</lang> and all is done ;-) 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
Prime(100000) = 1299709, Primorial(100000) ~ 0.1909604E+563921 121.547 seconds. Prime(1000000) = 15485863, Primorial(1000000) ~ 0.1147175E+6722809 17756.797 seconds.
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 Horsth