Talk:Primorial numbers: Difference between revisions
→a faster-than-exponential growth rate in CPU time stated by dinosaur
Line 23:
: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)
:: 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. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 01:58, 10 April 2016 (UTC)
| |||