A Friendly Challenge for D

[Jabari Zakiya]

On Wednesday, 10 October 2018 at 20:43:01 UTC, Kagamin wrote:
> On Wednesday, 10 October 2018 at 16:15:56 UTC, Jabari Zakiya 
> wrote:
>> https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e
>
> As i understand, main thread preallocates global memory and 
> tracks it, and other threads don't track it?

Here's an abreviated elementary explanation of the algorithm and 
implementation.
You will need to read (download) my paper "The Segmented Sieve of 
Zakiya (SSoZ)"
because I will make reference to things in it, to keep this as 
short as possible.

https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ

To really understand the math and theory of the algorithm 
requires primarily
just understanding Table 3 on page 3 of the paper, as it 
encapsulates everything.
You can read the paper to understand the language of the 
algorithm used in the code.

Twinprimes are 2 (odd) primes that differ by only 2 eg. 3-5, 5-7, 
11-13, 29-31.

Table 3 shows all the residues values (prime candidates|pcs) and 
residues groups
(resgroups|columns) to find all the primes upto 541 using P5 
(modpg = 30, rescnt = 8).

For a given value N, it will be represented with a PG table of 
some number of
resgroups, with max size I call Kmax (the regroups value N 
residues in).

Using P5, I only need to sieve primes along the residue tracks 
(restracks) that can
produce twinprimes, here 11-13, 17-19, 29-31. Thus I create 3 
byte arrays, one for each twinpair, and use the lower 2 bits to 
represent the upper and lower twinprime restracks.

Then for each twinpair (here 3) I run 3 thread which perform the 
SSoZ on the entire Kmax length of resgroups in parallel. At the 
end I accumulate the results and print them out. This, in a 
nutshell, is what the algorithm does. The paper gives you enough 
to understand the fundamental nature of the algorithm, though 
I've learned so much more than in 2014. :)

The larger the PG the more twinpair restracks (see page 14) there 
are to use. For larger numbers you want to use the largest PG 
possible that 'fits' into the hardware cpu. All my 
development|testing was done on laptops using Intel I5|I7 cpus 
with 4 or 8 threads. I'm really interested how it performs on 
other platforms (ARM, AMD, PowerPC, etc).


The main proc "twinprimes_ssoz" manages program flow and set as 
follows:

1) accepts the input number (an integer) in "val" from the cli

2) sets "num" to be first odd number < "val" if "val" even

3) calls "selectPG" with "num" to select optimum Prime Generator 
(PG) parameters

4) compute various working parameters per selected PG and number 
value (see refs)

5) compute global values for number of primes, and their values, 
<= sqrt(num) for
selected PG with proc "sozpg"

6) Set initial twinprime count for selected PG

7) Then with proc "segsieve" allocate one thread to perform SSoZ 
(segmented sieve of zakiya)
on each twinprime pair residues (determined by selected PG), and 
count number of twinprmes
computed in each thread.

8) Then determine true total twinprime count and last twinprime 
<= "num"

It also is timing different intervals and prints out diagnostics 
and final output.


The proc "twins_sieve" is the primary function that manages and 
performs the SSoZ for
a given twinprim pair parameters in each thread. The more threads 
the faster the process goes.

I'll provide more info later. I have to run now. I wanted to get 
this out now while I
was at my laptop, and online.