Talk:Primorial numbers: Difference between revisions
no edit summary
(→Story: Another plot. Rather linear.) |
No edit summary |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 3:
say "First ten primorials: ", join ", ", map { pn_primorial($_) } 0..9;</lang> and all is done ;-)
[[user#Horsth|Horsth]]
: I just added a version using the new vecprod command. It is quite a bit faster. It uses a product tree for efficient large vector products -- the old comment was misleading about using a factor tree. [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 16:50, 9 October 2018 (UTC)
::Once I figured out what a "product tree" is, simply multiplying in pairs (technically adjacent, not that my Phix entry does that) I was positively ''shocked'' to see a better than 50-fold performance improvement (6 mins => 6 secs). --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 04:28, 22 March 2020 (UTC)
== a faster-than-exponential growth rate in CPU time stated by dinosaur ==
Line 20 ⟶ 22:
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)
: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. Later, I see that the GIMP calculation gives 8MB for L3 on this AMD k10. 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)
Line 44 ⟶ 46:
::::And I can't replace the .svg file by a .jpg because I can't change the name of the file. So, a new file (only 38KB in this format), and damnit, I forgot to give the name the prefix "Primorial.cpu" [[File:Time.jpg]]
And here is a plot of cpu time against the number of digits in the big number, which is successively being multiplied by a ''single'' digit value. [[File:Primorial.CPUtime.digits.jpg]]
:::::Only admins are allowed to delete files. I've removed "Primorial.cpuTime.svg". --[[User:AndiPersti|Andreas Perstinger]] ([[User talk:AndiPersti|talk]]) 18:36, 10 April 2016 (UTC)
===Grist===
| |||