[QUOTE=a1call;432938]So, it turns out there is no free lunch when it comes to lngamma:

* It takes a log at precision x to reliably converge 10^log to a factorial with x digits.[/QUOTE]

Of course!

[QUOTE=a1call;432938]* It's possible to push the envelope by stopping the convergence when we reach the known following 0s, but that's a negligible gain.[/QUOTE]

Both right. You could take this reasoning further by computing the valuation mod the smallest x primes, effectively computing the factorial from both ends. But this will still be [i]sloooooow[/i] compared to reasonable methods.

[QUOTE=a1call;432938]* The GCD Primality Test is faster than trial-by-division any which way you look at it.[/QUOTE]

If you're allowed to precompute the GCD, and it fits into L1/L2 cache, and you compare it only to an unoptimized version of trial division, and your inputs are all either primes or semiprimes with prime factors close to each other, then yes (potentially). But the first two assumptions are unreasonable for numbers of decent size, the third is entirely unreasonable, and the fourth is quite restrictive.

[QUOTE=a1call;432938]lngamma is probably the fastest way of calculating a factorial and I posit that it is faster than calculating the equivalent primorial.[/QUOTE]

Certainly not.

[QUOTE=a1call;432938]The GCD primality test's bottleneck remains at the factorial overflowing the allocated memory.[/QUOTE]

Yes, as I pointed out in my analysis above (and earlier). This is what makes it so slow. Factoring a hard 70-digit semiprime is quite routine and entirely automated -- 23 seconds on my unspectacular machine. But to store a factorial of that size takes a quadrillion zettabytes. (One zettabyte is roughly the worldwide Internet transfer.) Needless to say it would be entirely hopeless to factor a number in this manner. So it's not a question of whether it fails, merely when it does.

[QUOTE=CRGreathouse;433028]

Certainly not.

[/QUOTE]
Hoping that you are not referring to the primorial,
* What is a faster way of calculating a factorial than the gamma function?

Thank you in advance.

ETA:
This is somewhat autoritative, too bad it does not mention the speed of the gamma function, but my timing runs indicate it is not any slower than the built in n!:
[url]http://rosettacode.org/wiki/Factorial#PARI.2FGP[/url]

[QUOTE=a1call;433106]Hoping that you are not referring to the primorial[/QUOTE]

have you considered you don't need to know the numbers until you want to multiply them for the primorial you can sieve using a binary array.

[QUOTE=a1call;433106]Hoping that you are not referring to the primorial,
* What is a faster way of calculating a factorial than the gamma function?[/QUOTE]

No, the factorial. I think the usual reference is Schönhage, Grotefeld, & Vetter's Fast Algorithms: A Multitape Turing Machine Implementation, ISBN 3-411-16891-9. It gives O(n log^(2+e) n) for any e > 0.

Primorial is faster, mostly because it's smaller.

Thank you [B]CRGreathouse[/B].

It's time to move on with the [B]GCD-Deterministic-Primality-Test[/B].

The following code uses multifactorials instead of factorials and can avoid "Stack-Overflow" indefinitely.

This way the current bottleneck shifts from [B][U]factorial calculation memory overflow[/U][/B] to code efficiency. In particular the [B][U]number of "[B]![/B]" in the multifactorial[/U][/B] that will return the fastest result per Prime-Candidate.
What I am hoping to get help with, from the forum members is:

* How could the optimum Multifactorial's [U]Multi [/U](for lack of a better term) be calculated?
This would be a factor of:
** The size of the multifactorial result
** The number of multifactorials to calculate which is equal to about 1/2 of the Multi above
** And to a much lesser extent the GCD test per multifactorial.

Thank you very much in advance.

[CODE]/* GCD Primality Test - Prime Candidate Range= n<p<n^2 - BAR-100-P - by Rashid Naimi */

n=10000001; \\Enter your own n to find precprime(n^2) automatically

thePrecision=1000;
allocatemem(320000000)
\o 3
default(realprecision, thePrecision);
default(primelimit, 1M);
#

fac(n,d)=prod(k=0,(n-1)\d,n-k*d);\\Multifactorial\\Credits: http://rosettacode.org/wiki/Multifactorial#PARI.2FGP

primeCandidate=precprime(n^2);
##
primeCandidate=primeCandidate; \\Enter your own prime candidate here to override the near n^2 prime found
print("Prime Candidate= ",primeCandidate);
if(primeCandidate<n || primeCandidate>n^2, n=1+floor(sqrt(primeCandidate)));

print("\n\nBuilt-in isprime Test")
isprime(primeCandidate)
##

print("\n\nProposed Deterministic GCD Primality Test using MultiFactorials")
greatestCommonDivisor=1;
markCount=10^6\\\\\\\\\
forstep(i=markCount-2,0,-2,{
a=fac(n-i,markCount);
greatestCommonDivisor=gcd(primeCandidate,a);
if(greatestCommonDivisor!=1,break(2);)
})
##
if (greatestCommonDivisor==1,print("**** ",primeCandidate," is Prime.");,print("**** ",primeCandidate," is not Prime."););
#digits(primeCandidate)

[/CODE]

[QUOTE] *** Warning: new stack size = 320000000 (305.176 Mbytes).
output = 3 (external prettyprint)
timer = 1 (on)
*** last result computed in 0 ms.
Prime Candidate= 100000019999977


Built-in isprime Test
1
*** last result computed in 0 ms.


Proposed Deterministic GCD Primality Test using MultiFactorials
1000000
time = 1,616 ms.
*** last result computed in 1,616 ms.
**** 100000019999977 is Prime.
15
[/QUOTE]

Please let me know if any part of the code needs clarification.
The upper parts are general initialization included for the record and future reference and can be ignored. The GCD test code starts after the related print and has only 1 function call to the multifactorial [B]fac()[/B].
the [B]markCount[/B] is the variable that contains the Multi of the Multifactorial.

[QUOTE=a1call;433276]
[CODE]/* GCD Primality Test - Prime Candidate Range= n<p<n^2 - BAR-100-P - by Rashid Naimi */

n=10000001; \\Enter your own n to find precprime(n^2) automatically

thePrecision=1000;
allocatemem(320000000)
\o 3
default(realprecision, thePrecision);
default(primelimit, 1M);
#

fac(n,d)=prod(k=0,(n-1)\d,n-k*d);\\Multifactorial\\Credits: http://rosettacode.org/wiki/Multifactorial#PARI.2FGP

primeCandidate=precprime(n^2);
##
primeCandidate=primeCandidate; \\Enter your own prime candidate here to override the near n^2 prime found
print("Prime Candidate= ",primeCandidate);
if(primeCandidate<n || primeCandidate>n^2, n=1+floor(sqrt(primeCandidate)));

print("\n\nBuilt-in isprime Test")
isprime(primeCandidate)
##

print("\n\nProposed Deterministic GCD Primality Test using MultiFactorials")
greatestCommonDivisor=1;
markCount=10^6\\\\\\\\\
forstep(i=markCount-2,0,-2,{
a=fac(n-i,markCount);
greatestCommonDivisor=gcd(primeCandidate,a);
if(greatestCommonDivisor!=1,break(2);)
})
##
if (greatestCommonDivisor==1,print("**** ",primeCandidate," is Prime.");,print("**** ",primeCandidate," is not Prime."););
#digits(primeCandidate)

[/CODE]
[/QUOTE]

using the fact that there's always a prime between x and 2x you can prove that precprime(n^2) will be at least (n^2\2) which is only less than n if n<2. also since precprime checks to find the next pseudoprime lower than the input it will never make primecandidate >n^2 even if it did floor(sqrt(primecandidate)) can be done with sqrtnint(primecandidate,2) ... etc. edit: oh and of course if you take into consideration if n is odd or not that can affect what you gcd because the divisors of an odd number must be only odd and so using an odd d won't get rid of evens that can't possibly divide n if n is odd. for example n*(n-3)*(n-6) ... etc will not always be odd or even for the things multiplied together so the gcd of the whole thing with an odd value will have the same gcd as only the odd values multiplied together.

[QUOTE=science_man_88;433284]using the fact that there's always a prime between x and 2x you can prove that precprime(n^2) will be at least (n^2\2) which is only less than n if n<2. also since precprime checks to find the next pseudoprime lower than the input it will never make primecandidate >n^2 even if it did floor(sqrt(primecandidate)) can be done with sqrtnint(primecandidate,2) ... etc.[/QUOTE]
Thank you for the reply [B][B]science_man_88[/B][/B],
Since the GCD-Deterministic-Primality-Test has a Prime-Candidate range of:
n<primeCandidate<n[SUP]2[/SUP]
the code:
primeCandidate=precprime(n^2)
returns the largest prime in the range which is used to verify the operation of the routine.
The above mentioned primeCandidate (i.e. any integer) can be overridden if desired by inputting it in the line commented in the code for the purpose. The code will then find/change the n value if required(i.e. The input PrimeCandidate is not in the range n<p<n[SUP]2[/SUP]).
But all this is housekeeping code and not significant. The significant code is after the

print("\n\nProposed Deterministic GCD Primality Test using MultiFactorials")

line in the code.
Thanks again for the reply.

[QUOTE=a1call;433287]primeCandidate=precprime(n^2)
returns the largest prime in the range which is used to verify the operation of the routine.
[/QUOTE]
[QUOTE]
(13:28) gp > ??precprime
precprime(x):

Finds the largest pseudoprime (see ispseudoprime) less than or equal to x. x can be of any real type. Returns 0 if x <= 1. Note that if x is a prime, this function returns x and not the largest prime strictly smaller than x. To rigorously prove that the result is prime, use isprime.

The library syntax is GEN precprime(GEN x).
[/QUOTE]

so it's not guaranteed prime.

[QUOTE=science_man_88;433288]so it's not guaranteed prime.[/QUOTE]
The primeCandidate can be any positive integer, prime or composite. It's just a number to input/feed to the test which will test it to see if it is prime. If the GCD-Deterministic-Primality-Test determines it to be a prime then and only then it is a guaranteed prime.

ETA
BTW the term pseudoprime is no longer used as a synonym for probable-prime which makes your quoted help line outdated/incorrect. The term pseudoprime now only refers to composite probable primes.
ETA-II
[QUOTE]While there may be probable primes that are composite (called pseudoprimes), the condition is generally chosen in order to make such exceptions rare.[/QUOTE]

[url]https://en.wikipedia.org/wiki/Probable_prime[/url]

[QUOTE=a1call;433289]BTW the term pseudoprime is no longer used as a synonym for probable-prime which makes your quoted help line outdated/incorrect.[/QUOTE]

okay well if you know that but don't know that's what the function does then that means you can't code what you want properly. in coding it doesn't matter if the meaning of the function is no longer used as such, the function used as such. also do you get my argument in the edit above at least to help you speed things up potentially.

Thank you science_man_88 for pointing out that the precprime() returns a probable-prime and not a proven prime.
But as it turns out this is not significant at the moment, since it is only used to find a Prime-Candidate for input to the test. So Any positive integer will do, even a proven composite:smile: