mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2015-02-06, 00:04   #1
mnh001
 
Apr 2011

26 Posts
Default downloading primes?

I've noticed on factordb that you can download primes but only 5000 at a time. It would
take forever to get them all that way. Is there a way to download all 100M+ at once? And in text format?
mnh001 is offline   Reply With Quote
Old 2015-02-06, 00:15   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

112·79 Posts
Default

Quote:
Originally Posted by mnh001 View Post
I've noticed on factordb that you can download primes but only 5000 at a time. It would
take forever to get them all that way. Is there a way to download all 100M+ at once? And in text format?
To what end? The first few million can be rapidly generated when needed.
Uncwilly is offline   Reply With Quote
Old 2015-02-06, 09:10   #3
mnh001
 
Apr 2011

10000002 Posts
Default

Just an experiment I'd like to try where I need all of them. I know I can generate the first few million easily but
to generate them all myself would also take forever.
mnh001 is offline   Reply With Quote
Old 2015-02-06, 14:52   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by mnh001 View Post
Just an experiment I'd like to try where I need all of them.
There are an infinite number of primes (as you may know), and factorDB's are generally only of interest because they are known as factors of numbers. Why are you interested in factorDB's primes in particular? I suspect that you're not really, and are just asking the wrong question, which should be something like "how can I quickly generate a list of x primes with y-z digits?"

By the way, all of their primes are 126GB. Are you really prepared to deal with that much data?

Last fiddled with by Mini-Geek on 2015-02-06 at 14:58
Mini-Geek is offline   Reply With Quote
Old 2015-02-06, 15:18   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24E016 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
By the way, all of their primes are 126GB. Are you really prepared to deal with that much data?
Huh? Only?
You can generate 200GB of primes in a night**, with a pari line like "n=1; while(1,write("primefile.txt", n=nextprime(n+1)))" or something equivalent. In the morning your HDD will be full and the windoze stuck with "low disk space".

edit **well, joking apart, you would need SSD or a ramdisk program, I just tried and can't write more than 5-6MB/minute, so this would mean about 3-4GB all night,

Last fiddled with by LaurV on 2015-02-06 at 15:25
LaurV is offline   Reply With Quote
Old 2015-02-06, 20:52   #6
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

22·227 Posts
Default

I used forprime(p=2,10^8,write("primefile.txt",p)) to an SSD and only get about 1.2 MB/s (5.8M primes in 42 seconds).

Using perl -Mntheory=forprimes -E 'forprimes { say } 10**8' >primefile.txt completes in 2 seconds for 23.3 MB/s.

Using primesieve -p1 1e8 >primefile.txt takes 4.7 seconds for 10.4 MB/s.

Using a trivial odd-only SoE in C plus buffered I/O takes only 0.51 seconds for 95.4 MB/s. About 73 MB/2 for 10^9.

The slowest prime generator is the fastest to output, while prime sieve (the fastest sieve by far) isn't that great for printing. Printing takes more time than sieving as long as it's reasonable.

Last fiddled with by danaj on 2015-02-06 at 20:52
danaj is offline   Reply With Quote
Old 2015-02-06, 23:41   #7
mnh001
 
Apr 2011

26 Posts
Default

Actually, my idea was a pre-test for factoring difficult composites.

A number may have a factor in common with another, which may have already been
done and entered in factordb. I did a speed test to try it out with the
numbers 2 to 100M in a text file. I chose a large prime (~30 digit) and
performed a mod test using the numbers in the text file.

It completed the test in 9 min 21 sec. Granted the primes in factordb are
a lot larger than my test numbers but I was just looking for a general
time frame.

If the computer is going to be spending weeks or months trying to factor
a difficult composite then doing this pre-test for 10 min or so could be
well worth it.

And since factordb already has primes over a very large range... who knows.
mnh001 is offline   Reply With Quote
Old 2015-02-07, 00:01   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

22×227 Posts
Default

Just for fun, I ran some more tests, this time to 10^10 (ASCII output is 4,948,214,537 bytes). Clearly this would be faster in binary, but the OP wanted text output, so why not. On a 1 month old Macbook Pro.

Code:
  202.91 MB/s   primegen + my buffered I/O
  171.14 MB/s   Perl/ntheory segmented sieve + my buffered I/O
   62.24 MB/s   Simple SoE + my buffered I/O
   23.66 MB/s   Perl/ntheory from Perl
   18.27 MB/s   primegen 0.97 from Atkin
   10.94 MB/s   primesieve 5.4.1
Bernstein's code is slightly faster than my segmented SoE, and both are much faster than the trivial odd-only SoE. All those with same I/O routines. Standard Perl or Bernstein's putchar stuff is slower, and primesieve using standard printf really cuts down the speed since it is the fastest at actually generating.

Anyway, 200GB of primes shouldn't take too long to generate, albeit they're consecutive primes rather than the ones from factordb. For actual use in a factoring or primality routine, of course you wouldn't want them printed in an ASCII file, so all these numbers are moot (but it was fun to look at).


For pretest, I suggest using mpz_gcd with a primorial and/or a tree sieve. Jens Kruse Andersen has a nice description of the latter. It is quite a bit faster than using mpz_divisible_ui_p once above a certain size. I'm sure others will also have thoughts of time spent in trial division vs. time with Rho, p-1, and ECM -- those are all quite good at finding small factors, and for numbers you're spending months on, you've probably run them already, making small factors that slipped through very unlikely. For checking random large primes, unless there is some reason to suggest those numbers have a good chance of occurring, it seems quite wasteful.
danaj is offline   Reply With Quote
Old 2015-02-07, 00:08   #9
mnh001
 
Apr 2011

26 Posts
Default

True it probably is wasteful but since it will only take a very short time I figure it'll be worth it. I've spent
hours running yafu only to have it tell me that yes the number is composite.
mnh001 is offline   Reply With Quote
Old 2015-02-07, 00:32   #10
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by mnh001 View Post
Actually, my idea was a pre-test for factoring difficult composites.

A number may have a factor in common with another, which may have already been
done and entered in factordb. I did a speed test to try it out with the
numbers 2 to 100M in a text file. I chose a large prime (~30 digit) and
performed a mod test using the numbers in the text file.
A number is more likely to have smaller primes as factors. Thus, the most profitable primes to try are not "what's in factordb", but "the next smallest prime I haven't tried yet.
This is usually known as "trial factoring" (TF). As an early stage in finding primality or finding factors, it is the best. But you would not use it for large (e.g. >2^32) numbers.
Quote:
Originally Posted by mnh001 View Post
If the computer is going to be spending weeks or months trying to factor
a difficult composite then doing this pre-test for 10 min or so could be
well worth it.

And since factordb already has primes over a very large range... who knows.
Factordb has some large-ish primes, which are not useful for TF. It does not necessarily have all small primes.
With the right program, you can generate small primes faster than you can read them from disk, so besides being unwieldy to download or store such large files, it is not useful.

Last fiddled with by Mini-Geek on 2015-02-07 at 00:32
Mini-Geek is offline   Reply With Quote
Old 2015-02-07, 00:43   #11
mnh001
 
Apr 2011

26 Posts
Default

Yes, I know. But like I said this was just going to be an experiment. If I'm trying to factor HP49(119) (which has 2 small
factors 73 and 16249 plus a C251) I'm pretty sure the smallest factor of the c251 has quite a few digits.

What I'm gathering is that there isn't a way to get the factordb primes in one chunk. No problem. I'll just come up with
another experiment.
mnh001 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Downloading prime nekketsu Software 1 2007-12-17 02:25
Downloading and printing Mersenne Primes PrimeCrazzy Lounge 5 2005-12-30 16:48
Downloading Maths devarajkandadai Miscellaneous Math 0 2004-08-12 06:02
Trouble Downloading Factoring File jeff8765 Lone Mersenne Hunters 2 2003-07-16 16:30

All times are UTC. The time now is 06:40.

Sun May 9 06:40:22 UTC 2021 up 31 days, 1:21, 0 users, load averages: 2.77, 2.49, 2.37

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.