Fastest Prime Sieve, in D

Jabari Zakiya jzakiya at gmail.com
Fri Jun 28 19:32:41 UTC 2019


This is a continuation of a previous thread on the Segmented 
Sieve of Zakiya (SSoZ):

https://forum.dlang.org/post/ozwapetxgcxkbzjjslqe@forum.dlang.org

to present the D version of the current state-of-art of the work.

The D version source code also performs the Fastest Primes Sieve 
for Twin Primes.

https://gist.github.com/jzakiya/ae93bfa03dbc8b25ccc7f97ff8ad0f61

It's a direct translation of the (original) Nim 
(www.nim-lang.org) version.

https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e

For those interested, here are two places to get my current paper 
on it.
I need to update it (again) to incorporate this new algorithm, 
and results.

https://www.academia.edu/37952623/The_Use_of_Prime_Generators_to_Implement_Fast_Twin_Primes_Sieve_of_Zakiya_SoZ_Applications_to_Number_Theory_and_Implications_for_the_Riemann_Hypotheses

https://www.scribd.com/document/395415391/The-Use-of-Prime-Generators-to-Implement-Fast-Twin-Primes-Sieve-Of-Zakiya-SoZ-Applications-to-Number-Theory-and-Implications-for-the-Riemann-Hypoth

I compiled the D source using the latest LDC 1.16.0. When 
comparing times to Nim it's comparable but becomes slower as 
inputs sizes increase. Here are some times for the Nim version 
compared to `primesieve` -- 
https://github.com/kimwalisch/primesieve

```
➜  ~ inxi -SCM
System:    Host: localhost.localdomain Kernel: 5.1.11-pclos1 
x86_64 bits: 64 Desktop: KDE Plasma 5.16.1 Distro: PCLinuxOS 2019
Machine:   Type: Laptop System: System76 product: Gazelle v: 
gaze10 serial: <root required>
            Mobo: System76 model: Gazelle v: gaze10 serial: <root 
required> UEFI [Legacy]: American Megatrends v: 1.05.08
            date: 03/31/2016
CPU:       Topology: Quad Core model: Intel Core i7-6700HQ bits: 
64 type: MT MCP L2 cache: 6144 KiB
            Speed: 1185 MHz min/max: 800/3500 MHz Core speeds 
(MHz): 1: 800 2: 800 3: 800 4: 800 5: 800 6: 800 7: 800 8: 800
```

```
             N          | twinprimes_ssoz |   primesieve  | Ratio |
     -------------------|-----------------|---------------|-------|
        100_000_000_000 |       4.628     |      5.837    |  1.26 |
        500_000_000_000 |      23.308     |     32.765    |  1.41 |
      1_000_000_000_000 |      47.966     |     69.705    |  1.45 |
      5_000_000_000_000 |     265.746     |    388.233    |  1.46 |
     10_000_000_000_000 |     572.803     |    821.755    |  1.43 |
     50_000_000_000_000 |    3004.487     |   4620.525    |  1.54 |
    100_000_000_000_000 |    6307.521     |   9724.568    |  1.54 |
    200_000_000_000_000 |   13603.531     |  20279.547    |  1.49 |
```
I'm hoping people can help improve it and make it faster than it 
currently is.

Thanks.

Jabari


More information about the Digitalmars-d mailing list