mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   The "one billion minus 999,994,000" digits prime number (https://www.mersenneforum.org/showthread.php?t=20568)

 a1call 2015-11-06 19:33

1 Attachment(s)
Please see the attached screenshot along with the command documentation.
It takes less than 2 seconds.

 chalsall 2015-11-06 19:39

[QUOTE=a1call;415157]Please see the attached screenshot along with the command documentation.[/QUOTE]

What you are forgetting is empirical time is different than computational time.

 a1call 2015-11-06 19:42

Which means it actually takes a fraction of a second on the server, right or am I missing something.

 chalsall 2015-11-06 19:50

[QUOTE=a1call;415159]Which means it actually takes a fraction of a second on the server, right or am I missing something.[/QUOTE]

It means you are missing a lot!

Sure, in our modern age, we just "throw hardware at the problem". And that might make some sense. Machines and energy are cheap(ish). Programmers are expensive.

BUT... Some actually want to optimize the equations.

That also makes sense....

 science_man_88 2015-11-06 20:13

[QUOTE=a1call;415159]Which means it actually takes a fraction of a second on the server, right or am I missing something.[/QUOTE]

I think what is being pointed out is that:

this code takes 4 milliseconds for this single computation isn't necessarily useful ( though I do that a lot myself) because without knowing how the time scales people won't be sure if it's worth putting in the time it would take for other inputs for example two inputs a and b=2*a;

if for input of b we double the time then the algorithm may be linear time complexity, if it quadruples the time it may be exponential, if b=a^2 and time doubles then maybe the algorithm may be logarithmic. same with number of operations if you say this algorithm takes 4 operations okay is that 4 additions, 4 multiplications, 4 divisions ( divisions are typically slow for computations unless they use a way of dividing that doesn't use much if any actual dividing). that and that it takes time to display an answer.

 danaj 2015-11-07 00:20

The point is that you're comparing two [I]completely[/I] different operations.

PrimeQ is similar to Pari/GP's ispseudoprime, Perl/ntheory's is_prime, or mpz_prp's mpz_bpsw_prp (used by Python's gmpy 2.0). It runs very fast. It is a [B]probable prime[/B] test. Nobody really knows what the Wolfram / Mathematica implementation really is (Pinch noted their "Lucas test" was not what the rest of the world calls a Lucas test and was strictly weaker than what BPSW should use, but that was 22 years ago). BPSW is great test, but I'm not sure how it applies here. It's meaningless in the EFF challenges. I have an [URL="http://sti15.com/nt/primality.cgi"]old web page[/URL] that does similar tests, though not factoring. It runs on the slow web host server rather than the browser, so the proof size is pretty limited.

The test you're running with alpertron is a proof. APR-CL I believe (but could be wrong). That would be similar to Pari/GP's isprime, mpz_aprcl's mpz_aprcle, or FLINT's new APRCL code (not in master yet). Comparable to the ECPP methods of Primo or Perl/ntheory's is_provable_prime. They take massively longer to run than the probable prime test. A certificate (ECPP, Pratt, etc.) would work for EFF, but you can't just give a general form number of 1M digits to Primo and expect it to ever produce something. Hence the idea of building up the certificate, which at least isn't loony with today's resources (I was going to say practical, but that's stretching it).

 a1call 2015-11-07 00:54

There is nothing in the documentation about the command being a probable prime test.
For the record none of these has anything to do with the EFF challenge. I think that can only be satisfied with mathematical proof and without calculating the the digits of the prime.

 danaj 2015-11-07 03:56

[QUOTE=a1call;415199]There is nothing in the documentation about the command being a probable prime test.[/QUOTE]

Under "Implementation notes":

[URL]http://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.html#6849[/URL]

It states that PrimeQ does trial division with small primes (typical for performance), then M-R bases 2 and 3, then a Lucas test. M-R base 2 plus a proper Lucas test makes the BPSW test. Adding base 3 is either to add more certainty over just BPSW, or (the cynical view) to mask an improper Lucas test.

It points out you need to use ProvablePrimeQ to get a proof.

 a1call 2015-11-07 04:42

[QUOTE=danaj;415217]Under "Implementation notes":

[URL]http://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.html#6849[/URL]

It states that PrimeQ does trial division with small primes (typical for performance), then M-R bases 2 and 3, then a Lucas test. M-R base 2 plus a proper Lucas test makes the BPSW test. Adding base 3 is either to add more certainty over just BPSW, or (the cynical view) to mask an improper Lucas test.

It points out you need to use ProvablePrimeQ to get a proof.[/QUOTE]

I stand corrected.
Thank you again for your insight [B]danaj[/B].

 a1call 2015-11-07 05:02

I tried the ProvablePrimeQ command it aborted after 1 minute. The online tool is still running with no end in sight.
My PARI/gp is not configured yet because of memory shortages on my desktop, but someone told me that the test took 8 minutes on a slow computer.

Can someone please let me know if the [B]2947digit[/B] integer that I posted is prime or not.

 Batalov 2015-11-07 05:26

[QUOTE=a1call;415223]...someone told me that the test took 8 minutes on a slow computer.
[/QUOTE]
That someone also doesn't know how to do primality tests.

The 2947digit candidate can be tested with Primo in ~1 hour with 4-8 threads (surely not 8 minutes).
Get Primo and run the test.

All times are UTC. The time now is 12:10.