www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Twin Primes Segmented Sieve of Zakiya (SSoZ) Explained

reply Jabari Zakiya <jzakiya gmail.com> writes:
I just released this new paper which presents D versions and 
benchmarks for this agorithm.

Twin Primes Segmented Sieve of Zakiya (SSoZ) Explained
https://www.academia.edu/81206391/Twin_Primes_Segmented_Sieve_of_Zakiya_SSoZ_Explained

Over the past few years I’ve gotten help in developing the code 
from the Forum and thought
I’d share the results of the refined code’s comparative 
performance to some other languages

I haven't substantially changed the code in over 3, and am hoping 
people can make it faster.

Here are the D sources for the code in the paper.

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

cousinprimes_ssoz
https://gist.github.com/jzakiya/147747d391b5b0432c7967dd17dae124



I would love to see what times people get on different hardware, 
like an M1, ARMs, et al.
Jun 17 2022
next sibling parent Sergey <kornburn yandex.ru> writes:
On Friday, 17 June 2022 at 20:52:11 UTC, Jabari Zakiya wrote:
 I just released this new paper which presents D versions and 
 benchmarks for this agorithm.

 [...]
Does it run comparably performant to Nim and Rust realisation?
Jun 18 2022
prev sibling next sibling parent max haughton <maxhaton gmail.com> writes:
On Friday, 17 June 2022 at 20:52:11 UTC, Jabari Zakiya wrote:
 I just released this new paper which presents D versions and 
 benchmarks for this agorithm.

 [...]
A PGO build will probably squeeze out a bit more performance if desired. Similarly using the full native instruction set.
Jun 18 2022
prev sibling next sibling parent reply Salih Dincer <salihdb hotmail.com> writes:
On Friday, 17 June 2022 at 20:52:11 UTC, Jabari Zakiya wrote:
 I just released this new paper which presents D versions and 
 benchmarks for this agorithm.

 Twin Primes Segmented Sieve of Zakiya (SSoZ) Explained
 https://www.academia.edu/81206391/Twin_Primes_Segmented_Sieve_of_Zakiya_SSoZ_Explained
Congratulations, all 25 pages are very clearly written...
 Here are the D sources for the code in the paper.

 twinprimes_ssoz
 https://gist.github.com/jzakiya/ae93bfa03dbc8b25ccc7f97ff8ad0f61
Some adjustments should be made to highlight D's abilities and reduce the number of lines. ```d int main(string[] args) { if(args.length > 1) { import std.conv; end_num = args[1].to!uint.max(3); start_num = args[2].to!uint.max(3); twinPrimesSsoz(); } else { import std.stdio : err = stderr; err.writefln("Please input:\n %s 3 7919", args[0]); return 1; } return 0; } ``` Line number increased though, sorry... SDB 79
Jun 18 2022
parent reply Salih Dincer <salihdb hotmail.com> writes:
Hi,

It's not a trivial detail, though, and it's not a highlight of D 
abilities. But if you're using integer `sqrt()` you can use the 
following proven algorithm (up to 100 million!):

```d
auto sqrt(T)(T i)
{
   T x = i;
   T y = (x + 1) >> 1;

   while (y < x)
   {
     x = y;
     y = (x + i / x) >> 1;
   }
   return x;
}
```

In fact, `realSqrt()` will give incorrect results when it 
approaches 100 million. Because there are losses in type 
conversions.

**Test codes:**

```d
import std.algorithm;
import std.math : realSqrt = sqrt;
import std.range;
import std.stdio;

void main() {
   alias testType = ulong;
   testType count;
   2.iota!testType(100_000_002)
    .each!((end_num) {
      const double test = end_num * end_num;

      const testType root1 = cast(testType) realSqrt(test);
      const testType root2 = sqrt!testType(end_num * end_num);

      if(root2 != end_num) {
        writefln("%s: %s == %s", end_num, root1, root2);
      }
      assert(root2 == end_num);
      count++;
    });
    count.writeln;
}
```

SDB 79
Jun 18 2022
parent reply kdevel <kdevel vogtner.de> writes:
On Saturday, 18 June 2022 at 20:21:17 UTC, Salih Dincer wrote:

- Have you tried to compile your code with dmd/gdc before pasting?
- I can't read the 2.iota-stuff. Are you trying to avoid writing 
a raw for-loop?

```
$ pr.d(10): Error: none of the overloads of template 
`pr.main.each!((end_num)
{
const double test = end_num * end_num;
const testType root1 = cast(testType)realSqrt(test);
const testType root2 = sqrt!testType(end_num * end_num);
if (root2 != end_num)
{
writefln("%s: %s == %s", end_num, root1, root2);
}
assert(root2 == end_num);
count++;
}
).each` are callable using argument types `!()(Result)`
[...]/linux/bin64/../../src/phobos/std/algorithm/iteration.d(908):       
Candidates are: `each(Range)(Range r)`
   with `Range = Result`
   must satisfy one of the following constraints:
`       isRangeIterable!Range
        __traits(compiles, typeof(r.front).length)`
[...]/linux/bin64/../../src/phobos/std/algorithm/iteration.d(969):             
          `each(Iterable)(auto ref Iterable r)`
   with `Iterable = Result`
   must satisfy one of the following constraints:
`       isForeachIterable!Iterable
        __traits(compiles, Parameters!(Parameters!(r.opApply)))`
```

 In fact, realSqrt() will give incorrect results when it 
 approaches 100 million. Because there are losses in type 
 conversions.
Do you mean this: ``` const double test = end_num * end_num; ``` The loss of precision is due to the integer overflow before the assignment to test. It has nothing to do with the double precision variable test which has a mantissa of 53 bits. ```hm.d import std.stdio; import std.conv; import std.math; import std.exception; void radix (uint i) { double d = i; d *= i; // writefln!"d = %f" (d); double root = sqrt (d); // writefln!"root = %f" (root); uint rdx = cast (uint) root; enforce (rdx == i); } void main (string [] args) { enforce (args.length == 3); uint first = args [1].to!uint; enforce (first >= 0); uint last = args [2].to!uint; enforce (last >= 1); enforce (last < last.max); enforce (last > first); for (uint i = first; i <= last; ++i) radix (i); writeln ("success"); } ``` No problem when approaching 100_000_000: ``` $ ./hm 9000 10000 success ```
Jun 18 2022
parent reply Salih Dincer <salihdb hotmail.com> writes:
On Saturday, 18 June 2022 at 21:01:04 UTC, kdevel wrote:
 - Have you tried to compile your code with dmd/gdc before 
 pasting?
Yes I did. Could the error be because you didn't copy the `sqrt()` function? On Saturday, 18 June 2022 at 21:01:04 UTC, kdevel wrote:
 - I can't read the 2.iota-stuff. Are you trying to avoid 
 writing a raw for-loop?
`iota()` and `each()` are essential. But it needs some experience to find the error in `each()`. SDB 79
Jun 18 2022
parent kdevel <kdevel vogtner.de> writes:
On Saturday, 18 June 2022 at 23:44:27 UTC, Salih Dincer wrote:
 Yes I did.  Could the error be because you didn't copy the 
 `sqrt()` function?
Oops. Yes.
 On Saturday, 18 June 2022 at 21:01:04 UTC, kdevel wrote:
 - I can't read the 2.iota-stuff. Are you trying to avoid 
 writing a raw for-loop?
`iota()` and `each()` are essential. But it needs some experience to find the error in `each()`.
For enhanced readability I suggest not to use UFCS in ``` 2.iota!testType(100_000_002) ``` but group begin/end together: ``` iota!testType(2, 100_000_002) ```
Jun 19 2022
prev sibling parent Jabari Zakiya <jzakiya gmail.com> writes:
On Friday, 17 June 2022 at 20:52:11 UTC, Jabari Zakiya wrote:
 I just released this new paper which presents D versions and 
 benchmarks for this agorithm.

 Twin Primes Segmented Sieve of Zakiya (SSoZ) Explained
 https://www.academia.edu/81206391/Twin_Primes_Segmented_Sieve_of_Zakiya_SSoZ_Explained

 Over the past few years I’ve gotten help in developing the code 
 from the Forum and thought
 I’d share the results of the refined code’s comparative 
 performance to some other languages

 I haven't substantially changed the code in over 3, and am 
 hoping people can make it faster.

 Here are the D sources for the code in the paper.

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

 cousinprimes_ssoz
 https://gist.github.com/jzakiya/147747d391b5b0432c7967dd17dae124



 I would love to see what times people get on different 
 hardware, like an M1, ARMs, et al.
I just updated my paper (Revised June 28, 2022), and all the coded versions, to reflect their changes to avoid arithmetic overflows in 2 places. You can access them at the previously provided links.
Jun 29 2022