PGS (Prime Generator Search)

PGS (Prime Generator Search)

Oct 3, 2016.

If you’ve ever read about primes, you have probably wondered how do we generate them? How do we find more?

If you haven’t read my post on primes, it is a good prerequisite to this post, so I’d suggest trying that first.

Forms

A form is a way to write something.

You can write $ 6 $ as $ 2n $ because $ 6 = 2 * 3 $. Here, $ n = 3 $, so it has this form.

$ 9 $ is part of a form: $ n^2 $ because $ 9 = 3^2 $. Here, $ n = 3 $

Prime Forms

Forms of primes are formulas, like $ 2n $ or $ n^2 $ which hold primes.

For example, all primes except $2$ can be written as $2n+1$. If they were $2n$, then they would not be prime (except for $2$, of course)

Currently, world records for sizes of primes are being broken by GIMPS - which searches for Mersenne primes.

GIMPS searches numbers that are of the form: $ 2^n-1 $, and tests them for primality

Prime Grid searches lots of forms, most notably $ a2^n\pm1 $

They also search prime generators, which they broke a record for $an+b$ which is called AP26

What they found was for $ n = 0 . . . 25 $, $a * n + b$ is prime for $a = 23681770*223092870$ and $b = 43142746595714191$

Which broke the previous world record.

PGS is my program, which searches for polynomials which generate primes for the first values.

Currently, we are searching quadratics, which are of form: $an^2 + bn + c$. We haven’t broken any records yet, but we hope to soon. PGS is running on UTK’s (University of Tennessee Knoxville) super computer, Newton.

Although it is much faster than any home computer, users can donate their CPU time to check a small block of coefficients.

PGS

PGS is a project I have worked on for 3 months now, and just recently added user support and online record keeping.

Here’s how it works.

When you download a release, that includes a few things. A node executable for your platform. Along with the programs:PGS.js, lib.o, CPGS.o.

Note that PGS.js is just source, while the .o files are compiled files. The source for everything in PGS is on Github

You enter in your email and password that you signed up with in my.prefs, and click run.sh. It logs you in, then starts gathering workloads from my server, and runs each using CPGS.o. Once these finish, PGS grabs another one, and starts it. It keeps going and going until it is killed, or your prefs specify to stop. It then gracefully shuts down, and marks all of your jobs as incomplete, so the server knows you didn’t finish them.

You will notice a quite large file - primes.dat which is 250MB. This is not downloaded in the zip. If PGS determines that you don’t have a primes.dat file, it generates one with lib.o. This is a bitset - which I’ll explain later - which stores information so I know whether or not every number below $2,000,000,000$ is prime. This is used later to verify whether numbers are prime.

I’ll go into specific parts down below.

Bitset

I’m going to assume you know the binary number system for this part. If not, just think of 1 as a “yes” and 0 as a “no”.

So, there are plenty of algorithms to generate the first few primes. I use the Sieve of Eratosthenes to compute a list.

But, if we stored the primes as an array, like [2, 3, 5, 7] this would take up too much space. How much space exactly?

Well, 32 bit integers which can store up to 2^32 each take up 4 bytes because each byte is 8 bits, and 32 / 8 = 4

If we wanted to store each prime under 2,000,000,000, we would have to store over 98,000,000,000. This takes up more space, and is slower at runtime than a bitset, which is explained below.

This approach will take 98,000,000 integers of space (each is 32 bits, which is 4 bytes), and when we check at runtime, we will need to check every integer in the array until we find it, or we find a number that is greater than it.

For example, say I give you a small list of primes: [2, 3, 5, 7, 11, 13, 17, 19]. I ask you if 15 is prime. How do you tell me?

Well, you would go through the list and compare each to 15.

Is 2 = 15?

Is 3 = 15?

. . .

Is 17 = 15?

At this point, you can stop because you have passed where 15 would be, so you know it isn’t prime.

Now then, let’s say we use a list of bits to tell you if the number is prime. The list above would look like:

001101010001010001010

This starts at 0, and goes to 19

The 1s mean that the index is prime, so count from the left: 0, 1, 2

001101010001010001010

The last number in red is 1, which indicates that 2 is prime.

In this case, if I asked you to check if 15 is prime, you don’t need to go through all the numbers in the list; All you need to do is skip to 0 . . . 15, and check that single bit.

And for memory usage, the first approach uses 98000000 integers, whereas this one can store 32 numbers in a single integer (using the list of 1s and 0s), so we would need $2000000000/32 = 62500000$ integers.

So it uses about 60% as much memory as the first approach, and is much faster to use.

We store the array of integers from the second approach in a file, then read it back when you run.

So, it uses 250mb of ram per thread you run, which everyone should have.

Checking a polynomials

This part is pretty straight forward. We run 3 for loops which check each possibiliy of a, b, and c within certain ranges.

Then, it keeps evaluating until it finds a value which is not prime. Once it does, if the number of primes was greater than 60, or it has at least 40 distinct in a row, it prints the result out.

It uses the file we created above to verify whether each number is prime, by checking the $(an^2+bn+c)$th bit of the list of 1s and 0s

So, say we are testing $f(n) = an^2+bn+c$

We first plug in n = 0, and we test whether $a0^2+b0^2+c$ is prime

Then, n = 1, and so on until the function isnt prime.

Subscribe

Subscribe to this blog via RSS.

Categories

Math 4

Software 3

School 1

Pgs 2

Question 1

Music 1

Politics 1

Vietnam 1

Notes 1

Recent Posts

Popular Tags

Math (4) Software (3) School (1) Pgs (2) Question (1) Music (1) Politics (1) Vietnam (1) Notes (1)

About

We strive to create high quality, freedom respecting software and solutions.

Social Links

github

Our HQ

401 Henley St
23890, Tennessee
United States.