mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2016-05-15, 20:42   #34
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

I was actually lucky that I got a 1/28676 chance for being prime and only nextprime(x)-x was 2652 for the number I picked. (Could have been worse) or even a 1/120000 chance, so I picked a good range for pfgw's calculations.
PawnProver44 is offline   Reply With Quote
Old 2016-05-15, 21:13   #35
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·3·17·19 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
I was actually lucky that I got a 1/28676 chance for being prime and only nextprime(x)-x was 2652 for the number I picked. (Could have been worse) or even a 1/120000 chance, so I picked a good range for pfgw's calculations.
I ran my pari script with 10000 random(10^12000) numbers which produced ~450 candidates, fed those into PFGW and had a PRP within 14 minutes, whereas yours took a "few weeks" and were "actually lucky"!


Last fiddled with by paulunderwood on 2016-05-15 at 21:17
paulunderwood is offline   Reply With Quote
Old 2016-05-15, 21:23   #36
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

19710 Posts
Post

I generated 1000 random 1000 digit numbers, manually used pfgw, and found 2 PRPs. (Which I will eventually prove with Primo.)
PawnProver44 is offline   Reply With Quote
Old 2016-05-15, 22:25   #37
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

387610 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I ran my pari script with 10000 random(10^12000) numbers which produced ~450 candidates, fed those into PFGW and had a PRP within 14 minutes, whereas yours took a "few weeks" and were "actually lucky"!
Checking the log, I actually found 2 ~12000 digit PRPs
paulunderwood is offline   Reply With Quote
Old 2016-05-15, 22:51   #38
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

3058 Posts
Post

Thanks for helping me bring up another point:

My pfgw.out file is too large (I cannot open it with notepad at least), can I create a second file or delete some output?
PawnProver44 is offline   Reply With Quote
Old 2016-05-15, 23:31   #39
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I am not sure how efficient nextprime() is at 500k digits. Anyone?
Pari's nextprime isn't the best choice even at 2000 digits. Perl's ntheory module using GMP is much better. Somewhere between 2000 and 4000 digits gwnum starts being faster than GMP, so it doesn't take long before using PFGW is a big time savings. At 500k digits doing a simple sieve+PFGW is probably a couple orders of magnitude faster.

Sieving and the compositeness test are both important. Perl/ntheory does deep sieving, while the other tools do not. Paul's script isn't the most efficient, but it's a hell of a lot better than not doing it, and it's simple and concise. For the compositeness tests, GMP is great under 1k digits, gwnum can be much faster with big inputs. In 2013 I did some tests on a 140k digit PRP and PFGW's Fermat was 5x faster than GMP M-R (from Perl/ntheory, essentially identical to WraithX's M-R code), and 11x faster than Pari/GP's M-R.

At 8000 digits, Perl/ntheory is about 4x faster than Pari/GP. I suspect most of this is the sieving.


Timing for 10^8000 on an i6700:

58 min 3s PFGW's nextprime
17min 53.5s Pari/GP
4min 29.5s Perl/ntheory
41.7s the script below using Perl/ntheory for sieve and calls to PFGW's PRP test for each candidate

Code:
perl -Mntheory=:all -E 'use Math::GMP qw/:constant/; $n=10**8000; @f=Math::Prime::Util::GMP::sieve_primes($n+1,$n+500000,5e8); for (@f) { $i=$_-$n; last if !system("./pfgw64s -k -Cquiet -f0 -u0 -q\"10^8000+$i\"") && is_bpsw_prime($n+$i); }'
Note that script is really crude -- you'd want to change the width and depth appropriately for your value or better yet, make it automatic. It ought to print something nice for PRP and not nice if your width was too short. It could quiet PFGW completely if desired. Using system calls for each candidate is inefficient. On the bright side, it is a fairly small one-command-line solution that is faster than the other tools.

Plugging in 10^12000 I got a PRP (including the BPSW test) in 75 seconds.


I'll point out again the advantages of starting with some expression rather than 500k random digits. Even if you get it to work, you get a big PRP that you can't submit anywhere because it's 500k random digits. Why not 10^500000 or some other succinctly written number? You also won't have shell input problems -- I'm almost sure this is what's going on with your big input for Perl: the DOS shell is barfing on a giant line. It's possible it is Perl itself -- there are lots of ways around this, but this forum seems like a bad place for elementary how-to-use-a-computer threads.

Something things really messed up if it took more than more than a couple hours for nextprime on a 12k digit input that isn't in a large merit gap. Even PFGW's slow nextprime shouldn't be *that* bad.
danaj is offline   Reply With Quote
Old 2016-05-16, 00:47   #40
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

Using PrimeInc:

Average times for random 1000, 2000, 3000, 4000, 8000, 16000 digit numbers:

1000 digits: 7.8s
2000 digits: 15.9s
3000 digits: 5.0s (25.8s)
4000 digits: 5.9s (50.8s)
5000 digits: 4 min. 51s (2 min. 20s)
6000 digits: 7 min. 22s

I know the time for 3000 and 4000 digits is less extreme for average timing, but my guess for that is I had picked integers close to a prime number. (I'll redo those ones). The 5000 digits is more extreme timing.
PawnProver44 is offline   Reply With Quote
Old 2016-05-17, 05:27   #41
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

I read on another forum when someone told me that I could open a .txt file with Perl functions in the command window (for perl/ntheory). I am basically putting in the commands I would normally use in the command window, except having perl read the .txt file with the commands, then process it:

C:\Users\Username\Documents>perl C:\Users\Username\Documents\Perl Scripts\input.txt

(Nothing)

C:\Users\Username\Documents>

Here is what was in the .txt file:

perl -Mntheory=:all -E "say is_prime('100288370102196085733993')"

With the command window:

C:\Users\Username\Documents> perl -Mntheory=:all -E "say is_prime('100288370102196085733993')"
1

And again does not work after reading it in a Perl Guide for Dummies, so I am doing my last and final solution to see if anyone here knows it.

EDIT: Reason I need to do this in a .txt file is to input all of the digits for a random 500k digit number or more, and output the file back to me with the result.

Last fiddled with by PawnProver44 on 2016-05-17 at 05:36
PawnProver44 is offline   Reply With Quote
Old 2016-05-17, 06:53   #42
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×3×17×19 Posts
Default

You are trying to run a command line program from within a file

You need to structure your program file similarly to this

However, running Dana's perl is_prime() on a random 500k digit number will not work. You will have to call out to PFGW instead.

Last fiddled with by paulunderwood on 2016-05-17 at 07:08
paulunderwood is offline   Reply With Quote
Old 2016-05-17, 07:18   #43
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

110001012 Posts
Post

Okay, thanks for that warning. (I believe perl/ntheory handles about 8,000 digits at most? I'll preform more tasks and report the final limit myself.) I'm assuming it's the same with next_prime(x) and random_ndigit_prime(x) too. I know how to use pfgw for nextprime(x), though I was nearly afraid that the number of digits doubled in x would take 16 times as long to compute, or is that only for ECPP proof?
PawnProver44 is offline   Reply With Quote
Old 2016-05-17, 07:24   #44
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×3×17×19 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
... though I was nearly afraid that the number of digits doubled in x would take 16 times as long to compute, or is that only for ECPP proof?
PFGW will take 4 times as long for a doubling in length of the number, remembering that the primes are sparser for bigger numbers.
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Near- and quasi-repunit PRPs Batalov And now for something completely different 10 2019-09-12 13:31
OEIS - 2^n-5 - LLT-like algorithm for finding PRPs T.Rex Miscellaneous Math 13 2015-09-01 13:09
PRPs not prime schickel FactorDB 1 2015-08-03 02:50
Proven PRPs? Random Poster FactorDB 0 2012-07-24 10:53
PRPs that are composites gd_barnes Conjectures 'R Us 57 2011-09-12 12:31

All times are UTC. The time now is 14:52.


Wed Oct 27 14:52:07 UTC 2021 up 96 days, 9:21, 0 users, load averages: 1.59, 1.35, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.