On Sunday, 2 February 2025 at 03:22:00 UTC, Jabari Zakiya wrote:
The D version is way slower, because of the array operations.
For an input of 1000000 (1M): D: 12+ secs; Crystal: 0.036 secs.
First of fall make sure you are using LDC or GDC compiler. Second
step is to add proper flags for optimizations (-O3).
Your initial version showed on my M1 laptop:
```bash
[1000000, 5402]
[17, 999983]
[499943, 500057]
19 secs, 367 ms, 923 μs, and 9 hnsecs
```
Then I propose some small changes:
1) You can initialize lhr with 1 row in similar logic as in
Ruby/Crystal
```d
uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;
```
2) The logic with shift and duplicated array could be simplified
in D with simple index processing and slising (you even don't
need to create duplicated array)
```d
foreach(i, r; lhr)
{
auto ri_max = rhi / r; // ri can't multiply r with
values > this
if (lhr[i+1] > ri_max)
break; // exit if product of
consecutive r’s > n-2
foreach(ri; lhr[i+1..$]) // for each residue in
reduced list
{
if (ri > ri_max)
break; // exit for r if cross-product
with ri > n-2
lhr_mults ~= r * ri; // store value if < n-2
}
} // check cross-products of next
lhr member
```
But these 2 updates don't make a lot of improvements in terms of
performance.
In Ruby|Crystal you can just do: lhr -= lhr_mult
to remove elements of one array from another, and not one at a
time.
I assume there's a D equivalent?!?
In D we have `setDifference`, so the code instead of filter +
canFind (which will be very costly in terms of big-O notation)
will become
```d
lhr_del.sort!("a < b"); // to use setDifference we need to have
sorted arrays
lhr = setDifference(lhr, lhr_del).array;
```
So after those updates the time improved
```bash
[1000000, 5402]
[17, 999983]
[499943, 500057]
81 ms, 144 μs, and 7 hnsecs
```
