The Prime Tableau and the Rational Primitive Mask

Test

October 2013

In order to test the Tableau procedure, first 2 published tables of prime numbers were downloaded and converted to a single column of text:

1. http://www.math.utah.edu/~pa/math/p10000.html
2. http://primes.utm.edu/lists/small/10000.txt

These two lists are identical.

Next, the C program shown on a previous page was modified to output just the prime numbers it finds, rather than the entire Tableau.

// list_primes.c
// converted from bootstrap_pm.c
// generate prime tableau by column method
// output only list of primes
// 10/5/13
// Copyright Sky Coyote 2013

// compile with: cc -O3 -o list_primes list_primes.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
if (argc < 2)
   {
   printf("Usage: list_primes nlines\n");
   return 1;
   }
int nlines = strtol(argv[1], 0, 10);
   
int nx = nlines, ny = nlines;
char *pm = (char *) malloc(nx * ny); // rational primitive mask
int i, j;
for (i = 0; i < nx * ny; i ++) pm[i] = -1;

unsigned char *isPrime = (unsigned char *) malloc(ny); // prime mask
isPrime[0] = 0; // 0 is not prime

// the "column" method: first column
pm[0] = 1;
pm[nx] = 1;
for (j = 2; j < ny; j ++)
   pm[nx * j] = 0;
   
// all other columns
for (i = 1; i < nx; i ++)
   {
   int k = 0; // index into ith row sequence
   for (j = i; j < ny; j ++)
      {
      // set value in column to value in row sequence
      pm[i + j * nx] = pm[k + i * nx];
      // increment index and possibly wrap
      k ++;
      if (k >= i) k = 0;
      }
   }
   
// detect primes
for (j = 1; j < ny; j ++)
   {
   int ok = 1;
   // pm must be all 1s between (not including) first column and diagonal
   for (i = 1; i < j; i ++)
      if (pm[i + j * nx] == 0)
         {
         ok = 0;
         break;
         }
   isPrime[j] = ok;
   }
   
// print (skipping 1 for compatibility with other lists)
for (j = 2; j < ny; j ++)
   if (isPrime[j]) printf("%d\n", j);

return 0;
}

This program was then used to create a Tableau with 40000 lines (about the biggest I could do with a single block malloc call) and output only the primes (omitting 1 for compatibility). This produced output of 4203 primes, from 2 to 39989, which was then compared to the 2 published lists, and is found to be identical up through the first 4203 lines. The file 'primes3_list.txt' shown below was created by the Tableau program.

In order to test the time/space properties of the Tableau, and to illustrate the row method of Tableau construction, a new program was created that builds the Tableau row-by-row rather than column-by-column. This program also allocates individual arrays for each row of the table to avoid memory waste and multiplication to find element offsets. To also avoid modulo math, indices for each row sequence are maintained, which makes the logic slightly more complicated than the column method. This code is also available as a file for download.

// pt_by_rows.c
// generate prime tableau row-by-row rather than column-by-column
// gather statistics on run time and memory usage wrt tableau size
// 10/5/13
// Copyright Sky Coyote 2013

// compile with: cc -O3 -o pt_by_rows pt_by_rows.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

// vars to hold time
struct timeval tv;
double t0 = 0.0;

// data
unsigned long allocated = 0;
unsigned char **rows;
int printData = 1;

// get elapsed time
double elapsedTime()
{
gettimeofday(&tv, 0);
double t = tv.tv_sec + tv.tv_usec * 1.0e-6;
return t - t0;
}

// detect primes
int isPrime(int j)
{
if (j < 1) return 0; // 0 is not prime
int i;
// row must be all 1s between (not including) first column and diagonal
for (i = 1; i < j; i ++)
   if (rows[j][i] == 0) return 0;
return 1;
}

// print row plus time and space
void printRow(int j)
{
printf("%7d  %10.3f %12lu", j + 1, elapsedTime(), allocated);
int is_prime = isPrime(j);
if (is_prime) printf("  %7d", j);
if (printData)
   {
   if (is_prime) printf(" - ");
   else printf("            ");
   int i;
   for (i = 0; i <= j; i ++)
      printf("%1d", rows[j][i]);
   }
printf("\n");
}
 
int main(int argc, char *argv[])
{
if (argc < 2)
   {
   printf("Usage: pt_by_rows nlines {0 to suppress row data}\n");
   return 1;
   }
int nlines = strtol(argv[1], 0, 10);
if (argc > 2) printData = strtol(argv[2], 0, 10);

// initialize time
gettimeofday(&tv, 0);
t0 = tv.tv_sec + tv.tv_usec * 1.0e-6;
//printf("t0 = %.3f\n", t0);

// initial allocation
int nx = nlines, ny = nlines;
rows = (unsigned char **) malloc(ny * sizeof(unsigned char *));
allocated += ny * sizeof(unsigned char *);
int *rowIndices = (int *) malloc(ny * sizeof(int));
allocated += ny * sizeof(int);

// create and print first two rows
int i, j;
rows[0] = (unsigned char *) malloc(1);
allocated += 1;
rows[0][0] = 1;
printRow(0);

rows[1] = (unsigned char *) malloc(2);
allocated += 2;
rows[1][0] = 1;
rows[1][1] = 1;
rowIndices[1] = 0;
printRow(1);

// create and print additional rows
for (j = 2; j < ny; j ++)
   {
   // allocate and initialize row
   rows[j] = (unsigned char *) malloc(j + 1);
   allocated += j + 1;
   // set first column and diagonal
   rows[j][0] = 0;
   rows[j][j] = 0;
   rowIndices[j] = 0;
   
   // set other columns from previous row sequences
   for (i = 1; i < j; i ++)
      {
      // increment and possibly wrap row sequence index
      rowIndices[i] ++;
      if (rowIndices[i] >= i) rowIndices[i] = 0;
      // set element
      rows[j][i] = rows[i][rowIndices[i]];
      }
      
   // print
   printRow(j);
   }

return 0;
}

This program can be used to generate and output the Tableau row data, or just the elapsed time, memory use, and primes.

2: ~/Sites/Tableau/Code/C > cc -O3 -o pt_by_rows pt_by_rows.c
3: ~/Sites/Tableau/Code/C > pt_by_rows 
Usage: pt_by_rows nlines {0 to suppress row data}
4: ~/Sites/Tableau/Code/C > pt_by_rows 33
      1       0.000          397            1
      2       0.000          399        1 - 11
      3       0.000          402        2 - 010
      4       0.000          406        3 - 0110
      5       0.000          411            01010
      6       0.000          417        5 - 011110
      7       0.000          424            0100010
      8       0.000          432        7 - 01111110
      9       0.000          441            010101010
     10       0.000          451            0110110110
     11       0.000          462            01010001010
     12       0.000          474       11 - 011111111110
     13       0.000          487            0100010100010
     14       0.000          501       13 - 01111111111110
     15       0.000          516            010101000101010
     16       0.000          532            0110100110010110
     17       0.000          549            01010101010101010
     18       0.000          567       17 - 011111111111111110
     19       0.000          586            0100010100010100010
     20       0.000          606       19 - 01111111111111111110
     21       0.000          627            010100010101010001010
     22       0.000          649            0110110010110100110110
     23       0.000          672            01010101010001010101010
     24       0.000          696       23 - 011111111111111111111110
     25       0.000          721            0100010100010100010100010
     26       0.000          747            01111011110111101111011110
     27       0.000          774            010101010101000101010101010
     28       0.000          802            0110110110110110110110110110
     29       0.000          831            01010100010101010101000101010
     30       0.000          861       29 - 011111111111111111111111111110
     31       0.000          892            0100000100010100010100010000010
     32       0.000          924       31 - 01111111111111111111111111111110
     33       0.000          957            010101010101010101010101010101010
5: ~/Sites/Tableau/Code/C > pt_by_rows 33 0
      1       0.000          397
      2       0.000          399        1
      3       0.000          402        2
      4       0.000          406        3
      5       0.000          411
      6       0.000          417        5
      7       0.000          424
      8       0.000          432        7
      9       0.000          441
     10       0.000          451
     11       0.000          462
     12       0.000          474       11
     13       0.000          487
     14       0.000          501       13
     15       0.000          516
     16       0.000          532
     17       0.000          549
     18       0.000          567       17
     19       0.000          586
     20       0.000          606       19
     21       0.000          627
     22       0.000          649
     23       0.000          672
     24       0.000          696       23
     25       0.000          721
     26       0.000          747
     27       0.000          774
     28       0.000          802
     29       0.000          831
     30       0.000          861       29
     31       0.000          892
     32       0.000          924       31
     33       0.000          957

I have run this program, minus row output, for 100000 lines in order to see the elapsed time and memory usage. The run took 2 min 10 sec and used 4.66 GB on my MacBook Pro 2 GHz Intel Core i7. The following is an excerpt of the output. (12/14/14: This run takes 1 min 29 sec on my i5-4590 3.3 GHz running Linux.)

      1       0.000      1200001
      2       0.000      1200003        1
      3       0.000      1200006        2
      4       0.000      1200010        3
      5       0.000      1200015
      6       0.000      1200021        5
      7       0.000      1200028
      8       0.000      1200036        7
      9       0.000      1200045
     10       0.000      1200055
...
  99989     130.172   5000150055
  99990     130.176   5000250045    99989
  99991     130.179   5000350036
  99992     130.183   5000450028    99991
  99993     130.186   5000550021
  99994     130.190   5000650015
  99995     130.193   5000750010
  99996     130.197   5000850006
  99997     130.200   5000950003
  99998     130.204   5001050001
  99999     130.207   5001150000
 100000     130.210   5001250000

Plots of time and space are shown below.



If you would like to make your own plots, the data file is here.



©Copyright Sky Coyote, 2013. -- Tableau home