Talk:Primorial numbers: Difference between revisions
→a faster-than-exponential growth rate in CPU time stated by dinosaur
Line 19:
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 --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 20:41, 8 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... [[User:Dinosaur|Dinosaur]] ([[User talk:Dinosaur|talk]]) 08:51, 9 April 2016 (UTC)
| |||