digitalmars.D - Twin Primes Segmented Sieve of Zakiya (SSoZ) Explained
- Jabari Zakiya (17/17) Jun 17 2022 I just released this new paper which presents D versions and
- Sergey (2/5) Jun 18 2022 Does it run comparably performant to Nim and Rust realisation?
- max haughton (3/6) Jun 18 2022 A PGO build will probably squeeze out a bit more performance if
- Salih Dincer (21/28) Jun 18 2022 Some adjustments should be made to highlight D's abilities and
- Salih Dincer (44/44) Jun 18 2022 Hi,
- kdevel (71/74) Jun 18 2022 On Saturday, 18 June 2022 at 20:21:17 UTC, Salih Dincer wrote:
- Salih Dincer (7/11) Jun 18 2022 Yes I did. Could the error be because you didn't copy the
- kdevel (10/17) Jun 19 2022 For enhanced readability I suggest not to use UFCS in
- Jabari Zakiya (5/22) Jun 29 2022 I just updated my paper (Revised June 28, 2022), and all the
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
Sergey <kornburn yandex.ru> 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
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
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_ExplainedCongratulations, 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/ae93bfa03dbc8b25ccc7f97ff8ad0f61Some 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
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
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
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
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: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) ```- 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()`.
Jun 19 2022
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