Twin Primes Segmented Sieve of Zakiya (SSoZ) Explained

Salih Dincer salihdb at hotmail.com
Sat Jun 18 20:21:17 UTC 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 at 79


More information about the Digitalmars-d mailing list