Talk:Primorial numbers: Difference between revisions

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.

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) Edit: System Info claims I'm working with an i7: 2.8GHz clock, 256KB L2, 6MB L3 - no mention of L1. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 09:26, 9 April 2016 (UTC)

 

: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)

:These were for data only up to n = 800,000 because there was a change in slope subsequently, probably because I stopped using the computer for other minor activity and thus didn't disrupt its various buffers. The Mersenne prime calculations continued. The points wobble above and below the fitted line across the span, and there is a bend visible at the start where the overall line is too low. That is, at the start the calculation is going a little faster and presumably, one could talk about not yet overflowing some on-chip memory buffer as another reason for non-linearity. Similarly, at the high end the points start to rise above the fitted line, and one could talk about a growth factor such as log(n) rather than a constant. This is obscured by the greater speed later on when I had walked away from the toiling computer. Nevertheless, one can see that a slight curve is being approximated by a straight line over a limited span, which means that using the start to attempt to identify the effect of a cpu buffer size will be tricky. Even so, a log(n) vs. log(t) plot shows a change of slope at the start - except that is for only the first few points. Alas, with "only" a few thousand digits to the big number, the resolution of the CPU timing function is insufficient to show finer details, and repeating the calculation a hundred times (say) will require auxiliary storage to enable the repetition and this will change the workings of the presumed buffering processes away from what was intended to be investigated. A frustrating business.

:Unfortunately, there is no provision for posting images, and anyway I've had a lot of trouble with Octave producing damaged plot files (.svg, .png, etc.) having to resort to screen image captures, so instead, here are the data:

:: You should be able to post images now. Look for an "Upload File" link at the bottom of the page. Also, you might want to look at where the time is going in your implementation - I am going to guess that it's in your code to generate the prime numbers. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 03:00, 10 April 2016 (UTC)

===Grist===

<pre>