Talk:Primorial numbers

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

The implementation of primorial I am using, running on this laptop, took 0.002909 seconds for primorial 100000 and 0.049093 seconds for primorial 1000000. With digit counts, that became 0.004267 seconds and 0.04369 seconds. I guess that's faster than exponential growth rate if by fast you mean the execution time... but ... actually, I'm not sure where I'm going with this. I am mildly surprised that digit count could be faster than the raw primorial but that might just be random variation --Rdm (talk) 20:41, 8 April 2016 (UTC) Edit: System Info claims I'm working with an i7: 2.8GHz clock, 256KB L2, 6MB L3 - no mention of L1. --Rdm (talk) 09:26, 9 April 2016 (UTC)

According to System Info, the computer has 64KB of L1 I-cache, 16KB L1 D-cache, and 2048KB of L2 cache, with further jargon about 2 way set associative, 64 byte line size, etc. and no mention of L3. However, I have no idea how much of each resource is devoted to the various activities such as running the GIMP crunch and windows itself. This is why experimental timings are tricky to perform as well as being a load on the patience. I am however surprised by the speeds quoted by some contributors, given that towards the end the number has millions of digits.

As for the standard multiplication procedure of n digits by m digits consuming time proportional to n.m, remember that my version cheats by using a one digit multiplicand (err, the second number in a*b) even though it is much larger than the base of arithmetic. Computer crunching of integers is unaffected by whether x is multiplied by 12 or 1234567, except for overflows. Thus, its running time should be proportional to n, the number of digits in the big number. In principle, and ignoring caches. If successive primorials were attained by multiplying by a constant, then that number of digits would increase linearly, but of course the multiplicand is increasing in size itself. If that increase was the same as with factorials then the number of digits would increase according to log(x!) which is proportional to x*log(x) via Stirling's approximation, which is to say a linear growth (the x) multiplied by a factor that grows ever more slowly (the log(x))

But Primorial(x) grows even faster than x! However, I didn't look and think long about the cpu timings before making the remark about "faster than exponential". I shall twiddle the prog. to produce more reports on timing... Dinosaur (talk) 08:51, 9 April 2016 (UTC)

On reading http://rosettacode.org/mw/index.php?title=Primorial_numbers&type=revision&diff=225184&oldid=225110 I think I'm begining to understand your point of view. I guess the issue is "in proportion to what?" For example, if we consider resource consumption (quite a lot) in proportion to the number of arguments (always just one), resource growth is infinite. If we think of resource growth in proportion to the number of digits in the argument we get "resource consumption (time to complete) growth faster than exponential". If we think of resource growth in proportion to the numerical value of the argument time consumed growth grows faster than linear.

Anyways, I guess a general issue here is that we tend to think in "shorthand" and when relating those thought to other people it often takes some extra work to make sure they understand our thinking. --Rdm (talk) 01:58, 10 April 2016 (UTC)