digitalmars.D.learn - help with prime pairs code
- Jabari Zakiya (129/129) Jan 31 I'm converting Ruby code to D and am running into issues.
- user1234 (102/107) Jan 31 A first draft of the translation, not very idiomatic D code:
- Jabari Zakiya (11/18) Feb 01 Thank you very much!
- user1234 (3/25) Feb 01 yeah Crystal is in my scope. Whyle I'm usualy not into dynamic
- user1234 (4/27) Feb 01 [Gradual
- Jabari Zakiya (86/114) Feb 01 Here's the Crystal version of the Ruby code.
- Sergey (55/61) Feb 02 First of fall make sure you are using LDC or GDC compiler. Second
- Jabari Zakiya (85/92) Feb 02 Here's the D code with the suggested changes, and other updates.
- Jabari Zakiya (36/131) Feb 02 I am really impressed!
- Sergey (7/15) Feb 02 Nice. Maybe create a github repo with results from different
- Jabari Zakiya (27/42) Feb 02 Good idea. I'll see if I'm up to it.
- monkyyy (3/6) Feb 02 translated code isnt going to be idiomatic ever; just state what
- Jabari Zakiya (11/15) Feb 04 FYI.
- Jabari Zakiya (137/155) Feb 05 I updated the code to make entering data easier.
- Jabari Zakiya (58/156) Feb 08 I've updated the code to make it shorter|simpler.
- Jabari Zakiya (305/314) Feb 18 I'm bringing attention to this issue as it might improve D.
- monkyyy (3/4) Feb 18 Known issue with upstream, try one of mine data structures
- Salih Dincer (17/24) Feb 18 Many parts of the core code can be optimized. Since I don't have
- Sergey (3/6) Feb 19 It is giving different result
- Salih Dincer (113/116) Feb 19 First of all, I see that you don't use reserve() at all in
- Salih Dincer (133/137) Feb 21 I removed 1 line in your code (note if (r <= rMax) ) and added
I'm converting Ruby code to D and am running into issues.
Would appreciate what needs to be done to get it to compile/run
correctly.
Here's the Ruby code:
```
RubyVM::YJIT.enable if RUBY_ENGINE == "ruby" and
RUBY_VERSION.to_f >= 3.3
def prime_pairs_lohi(n)
return puts "Input not even n > 2" unless n.even? && n > 2
return (pp [n, 1]; pp [n/2, n/2]; pp [n/2, n/2]) if n <= 6
lhr = 3.step(n/2, 2).select { |r| r if r.gcd(n) == 1 }
residue limit
pcp
others are too
end
end
list
list r w/others
values > this
consecutive r’s > n-2
list
with ri > n-2
lhr member
end
vals
lhr_del = lhr_mults.map { |r_del| (r_del > ndiv2 ? n - r_del :
r_del) }
count
n
n
end
execution
last output
```
Here's my D code.
```
module prime_pairs;
import std;
//import std.datetime.stopwatch : StopWatch;
//import std.stdio : readf, write, writeln, readln;
//import std.numeric : gcd;
void prime_pairs_lohi(uint n) {
if ((n|1) == 1 || n < 4) return writeln("Input not even n > 2");
//if (n <= 6) return { writel([n, 1]); writeln([n/2, n/2]);
writeln([n/2, n/2])}
// generate the low-half-residues (lhr) r < n/2
lhr = [];
auto ndiv2 = n/2;
auto rhi = n-2;
auto r = 3;
while (r < ndiv2) {
if (gcd(r,n) == 1) lhr ~= r;
r += 2;
}
lhr_mults = []; // for lhr values not part of
a pcp
// store all the powers of the lhr members < n-2
foreach(r; lhr) { // step thru the lhr members
r_pwr = r; // set to first power of r
if (r > rhi/r_pwr) break; // exit if r^2 > n-2, as all
others are too
while (r < rhi/r_pwr) { // while r^e < n-2
lhr_mults ~=(r_pwr *= r); // store its current power of r
} }
// store all the cross-products of the lhr members < n-2
lhr_dup = lhr.dup; // make copy of the lhr
members list
while ((r = lhr_dup.shift) && lhr_dup.length != 0) {
ri_max = rhi / r; // ri can't multiply r with
values > this
if (lhr_dup[0] > ri_max) break; // exit if product of
consecutive r’s > n-2
foreach(ri; lhr_dup) { // 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
// convert lhr_mults vals > n/2 to their lhr complements n-r,
// store them, those < n/2, in lhr_del; it now holds non-pcp
lhr vals
lhr_del = lhr_mults.map { |r_del| (r_del > ndiv2 ? n - r_del :
r_del) }
lhr -= lhr_del;
writeln("[", n,", ", lhr.length,"]"); // show n and pcp
prime pairs count
writeln("[", lhr[0], ", ", n-lhr[0], "]"); // show first pcp
prime pair of n
writeln("[", lhr[$-1],", ",n-lhr[$-1],"]"); // show last pcp
prime pair of n
}
void main() {
ulong[] x;
foreach (_; 0 .. 1) { ulong a; readf!" %d"(a); x ~= a; }
n = x[0];
auto stopWatchExecution = StopWatch();
stopWatchExecution.start();
prime_pairs_lohi(n);
stopWatchExecution.stop();
writeln(stopWatchExecution.peek());
```
Jan 31
On Friday, 31 January 2025 at 20:05:54 UTC, Jabari Zakiya wrote:I'm converting Ruby code to D and am running into issues. Would appreciate what needs to be done to get it to compile/run correctly. Here's the Ruby code: [...]A first draft of the translation, not very idiomatic D code: ```d module prime_pairs; import std; void prime_pairs_lohi(uint n) { if ((n|1) == 1 || n < 4) { return writeln("Input not even n > 2"); } if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; } // generate the low-half-residues (lhr) r < n/2 int[] lhr; auto ndiv2 = n/2; auto rhi = n-2; { auto r = 3; while (r < ndiv2) { if (gcd(r,n) == 1) lhr ~= r; r += 2; } } int[] lhr_mults; // for lhr values not part of a pcp // store all the powers of the lhr members < n-2 foreach(r; lhr) // step thru the lhr members { auto r_pwr = r; // set to first power of r if (r > rhi/r_pwr) break; // exit if r^2 > n-2, as all others are too while (r < rhi/r_pwr) // while r^e < n-2 lhr_mults ~=(r_pwr *= r);// store its current power of r } // store all the cross-products of the lhr members < n-2 auto lhr_dup = lhr.dup; // make copy of the lhr members list { auto shift(T)(ref T[] a) { if (!a.length) return -1; auto r = a[0]; a = a[1..$]; return r; } int r; while ((r = shift(lhr_dup)) != -1 && lhr_dup.length != 0) { auto ri_max = rhi / r; // ri can't multiply r with values > this if (lhr_dup[0] > ri_max) break; // exit if product of consecutive r’s > n-2 foreach(ri; lhr_dup) // 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 } // convert lhr_mults vals > n/2 to their lhr complements n-r, // store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del); lhr = lhr.filter!(a => !lhr_del.canFind(a)).array; writeln("[", n,", ", lhr.length,"]"); // show n and pcp prime pairs count writeln("[", lhr[0], ", ", n-lhr[0], "]"); // show first pcp prime pair of n writeln("[", lhr[$-1],", ",n-lhr[$-1],"]"); // show last pcp prime pair of n } void main() { prime_pairs_lohi(16); } ``` Results seems to match to what I see in TryRubyPlayGround. Summary of the problems I've seen in you attempt - problem of scoping (e.g loop variables) - missing storage class to declare variables - some missing 1:1 equivalent of Ruby functs `.shift` and the `-` operator on array. - lambda syntax not mastered (lhr_del mapping) A bit of learning required but should be to overcome. Now I wait for the person who will post a beautiful version with UFCS chains...
Jan 31
On Saturday, 1 February 2025 at 00:21:22 UTC, user1234 wrote:On Friday, 31 January 2025 at 20:05:54 UTC, Jabari Zakiya wrote:Thank you very much! As you can see, D is not my primary language, but I respect its speed and readability. I also have a faster Crystal version, almost identical (96%) to the Rudy code. I'm implementing it in different languages, partly as a way to learn them with a real task. I'll study the D code thoroughly to conceptually understand the idioms used int it. I, like you, also wait to see a "beautiful" version done.[...]A first draft of the translation, not very idiomatic D code: ```d module prime_pairs; import std; [...]
Feb 01
On Saturday, 1 February 2025 at 21:56:23 UTC, Jabari Zakiya wrote:On Saturday, 1 February 2025 at 00:21:22 UTC, user1234 wrote:yeah Crystal is in my scope. Whyle I'm usualy not into dynamic typed langs, there's something I like in the Crystal lang.On Friday, 31 January 2025 at 20:05:54 UTC, Jabari Zakiya wrote:Thank you very much! As you can see, D is not my primary language, but I respect its speed and readability. I also have a faster Crystal version, almost identical (96%) to the Rudy code.[...]A first draft of the translation, not very idiomatic D code: ```d module prime_pairs; import std; [...]I'm implementing it in different languages, partly as a way to learn them with a real task. I'll study the D code thoroughly to conceptually understand the idioms used int it. I, like you, also wait to see a "beautiful" version done.
Feb 01
On Sunday, 2 February 2025 at 01:12:59 UTC, user1234 wrote:On Saturday, 1 February 2025 at 21:56:23 UTC, Jabari Zakiya wrote:[Gradual typing](https://en.wikipedia.org/wiki/Gradual_typing#:~:text=Gradual%20typing%20allows%20software%20developers,static%20typing%20to%20be%20used.) That's the shit I like with Crystal.On Saturday, 1 February 2025 at 00:21:22 UTC, user1234 wrote:yeah Crystal is in my scope. Whyle I'm usualy not into dynamic typed langs, there's something I like in the Crystal lang.On Friday, 31 January 2025 at 20:05:54 UTC, Jabari Zakiya wrote:Thank you very much! As you can see, D is not my primary language, but I respect its speed and readability. I also have a faster Crystal version, almost identical (96%) to the Rudy code.[...]A first draft of the translation, not very idiomatic D code: ```d module prime_pairs; import std; [...]
Feb 01
On Sunday, 2 February 2025 at 01:39:34 UTC, user1234 wrote:On Sunday, 2 February 2025 at 01:12:59 UTC, user1234 wrote:Here's the Crystal version of the Ruby code. ``` prime_pairs_lohi.cr def prime_pairs_lohi(n) return puts "Input not even n > 2" unless n.even? && n > 2 return (pp [n, 1]; pp [n//2, n//2]; pp [n//2, n//2]) if n <= 6 lhr = 3u64.step(to: n//2, by: 2).select { |r| r if r.gcd(n) == 1 }.to_a residue limit of a pcp all others are too of r end end members list 1st list r w/others values > this consecutive r’s > n-2 reduced list cross-product with ri > n-2 next lhr member end complements first lhr -= lhr_mults.map { |r_del| r_del > ndiv2 ? n - r_del : r_del } pairs count pair of n pair of n end code execution def gen_pcp terminal runtime as last output end gen_pcp ``` Add this to the D code to take terminal input and to time execution. I don't know if this is most idiomatic, but it works. import std.datetime.stopwatch : StopWatch; void main() { int n; readf("%s", &n); auto stopWatchExecution = StopWatch(); stopWatchExecution.start(); prime_pairs_lohi(n); stopWatchExecution.stop(); writeln(stopWatchExecution.peek()); } The D version is way slower, because of the array operations. For an input of 1000000 (1M): D: 12+ secs; Crystal: 0.036 secs. 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?!? As n increases so do those arrays, and the times become much longer.On Saturday, 1 February 2025 at 21:56:23 UTC, Jabari Zakiya wrote:[Gradual typing](https://en.wikipedia.org/wiki/Gradual_typing#:~:text=Gradual%20typing%20allows%20software%20developers,static%20typing%20to%20be%20used.) That's the shit I like with Crystal.On Saturday, 1 February 2025 at 00:21:22 UTC, user1234 wrote:yeah Crystal is in my scope. Whyle I'm usualy not into dynamic typed langs, there's something I like in the Crystal lang.On Friday, 31 January 2025 at 20:05:54 UTC, Jabari Zakiya wrote:Thank you very much! As you can see, D is not my primary language, but I respect its speed and readability. I also have a faster Crystal version, almost identical (96%) to the Rudy code.[...]A first draft of the translation, not very idiomatic D code: ```d module prime_pairs; import std; [...]
Feb 01
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 ```
Feb 02
On Sunday, 2 February 2025 at 10:26:56 UTC, Sergey wrote:So after those updates the time improved ```bash [1000000, 5402] [17, 999983] [499943, 500057] 81 ms, 144 μs, and 7 hnsecs ```Here's the D code with the suggested changes, and other updates. Note, I make the source code look like Ruby|Crystal for my esthetics. ``` // Compile with ldc2: $ ldc2 --release -O3 -mcpu native prime_pairs_lohi.d // Run as: echo 100000 | ./prime_pairs_lohi // Update: 2025/02/02 module prime_pairs; import std; import std.datetime.stopwatch : StopWatch; void prime_pairs_lohi(uint n) { if ((n&1) == 1 || n < 4) { return writeln("Input not even n > 2"); } if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; } // generate the low-half-residues (lhr) r < n/2 auto ndiv2 = n/2; // llr:hhr midpoint auto rhi = n-2; // max residue limit uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array; // store all the powers of the lhr members < n-2 int[] lhr_mults; // for lhr values not part of a pcp foreach(r; lhr) { // step thru the lhr members auto r_pwr = r; // set to first power of r if (r > rhi/r_pwr) break; // exit if r^2 > n-2, as all others are too while (r < rhi/r_pwr) // while r^e < n-2 lhr_mults ~=(r_pwr *= r); // store its current power of r } // store all the cross-products of the lhr members < n-2 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 } } // convert lhr_mults vals > n/2 to their lhr complements n-r, // store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array; lhr_del.sort!("a < b"); lhr = setDifference(lhr, lhr_del).array; writeln([n, lhr.length]); // show n and pcp prime pairs count writeln([lhr[0], n-lhr[0]]); // show first pcp prime pair of n writeln([lhr[$-1],n-lhr[$-1]]); // show last pcp prime pair of n } void main() { int n; readf("%s", &n); // get input to n from terminal auto timer = StopWatch(); // create execution timer timer.start(); // start it prime_pairs_lohi(n); // run routine writeln(timer.peek()); // show timer results } ``` The D version is now faster than Crystal. ``` D (LDC2 2.40) ➜ ~ echo 100000000 |./prime_pairs_lohi [100000000, 291400] [11, 99999989] [49999757, 50000243] 7 secs, 422 ms, 641 μs, and 9 hnsecs Crystal (1.15) ➜ ~ ./prime_pairs_lohi 100_000_000 [100000000, 291400] [11, 99999989] [49999757, 50000243] 00:00:10.454055301 ``` I'll eventually do a Rust version, maybe C++, et al. I want to think everybody for the help. If you find more performance improvements please post them.
Feb 02
On Sunday, 2 February 2025 at 21:17:39 UTC, Jabari Zakiya wrote:On Sunday, 2 February 2025 at 10:26:56 UTC, Sergey wrote:I am really impressed! D is phenomenally memory efficient with this code. I just ran the D code for some really large n values. On my older Lenovo Legion 5, using Linux (June 2024) w/16GB I was able to go up to n = 1,000,000,0000 and it took up ~14.4GB max, out of ~14.9GB usable. I got a new, fast TUXEDO Gen 3, w/64GB (Jan 2025), so I'm going to how high I can go on it. Here are some results on the Lenovo Legion 5. ``` ➜ ~ echo 500000000 |./prime_pairs_lohi3 [500000000, 1219610] [7, 499999993] [249999877, 250000123] 43 secs, 402 ms, 950 μs, and 3 hnsecs ➜ ~ ➜ ~ echo 900000000 |./prime_pairs_lohi3 [900000000, 4132595] [37, 899999963] [449999993, 450000007] 36 secs, 135 ms, 163 μs, and 6 hnsecs ➜ ~ ➜ ~ echo 1000000000 |./prime_pairs_lohi3 [1000000000, 2274205] [71, 999999929] [499999931, 500000069] 1 minute, 32 secs, 87 ms, 624 μs, and 8 hnsecs ➜ ~ ➜ ~ echo 1500000000 |./prime_pairs_lohi3 [1500000000, 6543613] [43, 1499999957] [749999927, 750000073] 1 minute, 6 secs, 205 ms, 381 μs, and 5 hnsecs ➜ ~ ```So after those updates the time improved ```bash [1000000, 5402] [17, 999983] [499943, 500057] 81 ms, 144 μs, and 7 hnsecs ```Here's the D code with the suggested changes, and other updates. Note, I make the source code look like Ruby|Crystal for my esthetics. ``` // Compile with ldc2: $ ldc2 --release -O3 -mcpu native prime_pairs_lohi.d // Run as: echo 100000 | ./prime_pairs_lohi // Update: 2025/02/02 module prime_pairs; import std; import std.datetime.stopwatch : StopWatch; void prime_pairs_lohi(uint n) { if ((n&1) == 1 || n < 4) { return writeln("Input not even n > 2"); } if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; } // generate the low-half-residues (lhr) r < n/2 auto ndiv2 = n/2; // llr:hhr midpoint auto rhi = n-2; // max residue limit uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array; // store all the powers of the lhr members < n-2 int[] lhr_mults; // for lhr values not part of a pcp foreach(r; lhr) { // step thru the lhr members auto r_pwr = r; // set to first power of r if (r > rhi/r_pwr) break; // exit if r^2 > n-2, as all others are too while (r < rhi/r_pwr) // while r^e < n-2 lhr_mults ~=(r_pwr *= r); // store its current power of r } // store all the cross-products of the lhr members < n-2 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 } } // convert lhr_mults vals > n/2 to their lhr complements n-r, // store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array; lhr_del.sort!("a < b"); lhr = setDifference(lhr, lhr_del).array; writeln([n, lhr.length]); // show n and pcp prime pairs count writeln([lhr[0], n-lhr[0]]); // show first pcp prime pair of n writeln([lhr[$-1],n-lhr[$-1]]); // show last pcp prime pair of n } void main() { int n; readf("%s", &n); // get input to n from terminal auto timer = StopWatch(); // create execution timer timer.start(); // start it prime_pairs_lohi(n); // run routine writeln(timer.peek()); // show timer results } ``` The D version is now faster than Crystal. ``` D (LDC2 2.40) ➜ ~ echo 100000000 |./prime_pairs_lohi [100000000, 291400] [11, 99999989] [49999757, 50000243] 7 secs, 422 ms, 641 μs, and 9 hnsecs Crystal (1.15) ➜ ~ ./prime_pairs_lohi 100_000_000 [100000000, 291400] [11, 99999989] [49999757, 50000243] 00:00:10.454055301 ``` I'll eventually do a Rust version, maybe C++, et al. I want to think everybody for the help. If you find more performance improvements please post them.
Feb 02
On Sunday, 2 February 2025 at 22:40:41 UTC, Jabari Zakiya wrote:I am really impressed! D is phenomenally memory efficient with this code. I just ran the D code for some really large n values. On my older Lenovo Legion 5, using Linux (June 2024) w/16GB I was able to go up to n = 1,000,000,0000 and it took up ~14.4GB max, out of ~14.9GB usable. I got a new, fast TUXEDO Gen 3, w/64GB (Jan 2025), so I'm going to how high I can go on it.Nice. Maybe create a github repo with results from different languages. It will be interesting to see the comparison. I haven't checked other parts of the code - maybe it is possible to improve the performance a bit more (to reduce some allocations, use `appender` instead of `~=` operator) But will see what other will produce first :)
Feb 02
On Monday, 3 February 2025 at 00:04:17 UTC, Sergey wrote:On Sunday, 2 February 2025 at 22:40:41 UTC, Jabari Zakiya wrote:Good idea. I'll see if I'm up to it. Another code opt for you. I translated this Ruby code: lhr_del = lhr_mults.map { |r_del| (r_del > ndiv2 ? n - r_del : r_del) } lhr_rmax high bound lhr <= lhr_rmax prime residues prime residues <= lhr_rmax To this D code. It works, seems fast, can it be done shorter, faster, more idiomatic? auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array; lhr_del.sort!("a < b"); auto lhr_rmax = 2 + cast(uint) sqrt(cast(double) n-2); auto lhr_rmax_cnt = 0; foreach(r; lhr) { if (r > lhr_rmax) break; lhr_rmax_cnt += 1;} lhr = setDifference(lhr, lhr_del).array; uint[] pcp_rmax; foreach(pcp; lhr) { if (pcp > lhr_rmax) break; pcp_rmax ~= pcp; }I am really impressed! D is phenomenally memory efficient with this code. I just ran the D code for some really large n values. On my older Lenovo Legion 5, using Linux (June 2024) w/16GB I was able to go up to n = 1,000,000,0000 and it took up ~14.4GB max, out of ~14.9GB usable. I got a new, fast TUXEDO Gen 3, w/64GB (Jan 2025), so I'm going to how high I can go on it.Nice. Maybe create a github repo with results from different languages. It will be interesting to see the comparison. I haven't checked other parts of the code - maybe it is possible to improve the performance a bit more (to reduce some allocations, use `appender` instead of `~=` operator) But will see what other will produce first :)
Feb 02
On Monday, 3 February 2025 at 04:15:09 UTC, Jabari Zakiya wrote:I translated this Ruby code: To this D code. It works, seems fast, can it be done shorter, faster, more idiomatic?translated code isnt going to be idiomatic ever; just state what you want done
Feb 02
On Monday, 3 February 2025 at 04:59:43 UTC, monkyyy wrote:On Monday, 3 February 2025 at 04:15:09 UTC, Jabari Zakiya wrote:FYI. This code finds all the prime pairs that sum to n for all even integers n > 2. It (Ruby code) is included in a paper I just released (Feb 2, 2025) on Goldbach's Conjecture (1742) and Bertrand's Postulate (1845). For those interested in Prime|Number Theory check it out. A lot of new, good, stuff is in it! **Proof of Goldbach's Conjecture and Bertrand's Postulate Using Prime Generator Theory (PGT)** https://www.academia.edu/127404211/Proof_of_Goldbachs_Conjecture_and_Bertrands_Postulate_Using_Prime_Generator_Theory_PGT_I translated this Ruby code:
Feb 04
On Tuesday, 4 February 2025 at 17:17:42 UTC, Jabari Zakiya wrote:On Monday, 3 February 2025 at 04:59:43 UTC, monkyyy wrote:I updated the code to make entering data easier. It now mimics the Ruby|Crystal code and takes "humanized" data strings. You can now run the code as: `$ ./primes_pair_lohi_u32 123_456_780` I also created two versions, one for u32 input values, and one for u64. Unless you have lots of memmory, the u32 version is best to use. Here's the u32 input size version. // Compile with ldc2: $ ldc2 --release -O3 -mcpu native prime_pairs_lohi_u32.d // Run as: $ ./prime_pairs_lohi_u32 123_456_780 module prime_pairs; import std; import std.datetime.stopwatch : StopWatch; void prime_pairs_lohi(uint n) { // inputs can be of size u32 if ((n&1) == 1 || n < 4) { return writeln("Input not even nOn Monday, 3 February 2025 at 04:15:09 UTC, Jabari Zakiya wrote:FYI. This code finds all the prime pairs that sum to n for all even integers n > 2. It (Ruby code) is included in a paper I just released (Feb 2, 2025) on Goldbach's Conjecture (1742) and Bertrand's Postulate (1845). For those interested in Prime|Number Theory check it out. A lot of new, good, stuff is in it! **Proof of Goldbach's Conjecture and Bertrand's Postulate Using Prime Generator Theory (PGT)** https://www.academia.edu/127404211/Proof_of_Goldbachs_Conjecture_and_Bertrands_Postulate_Using_Prime_Generator_Theory_PGT_I translated this Ruby code:2"); }if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; } // generate the low-half-residues (lhr) r < n/2 auto ndiv2 = n/2; // llr:hhr midpoint auto rhi = n-2; // max residue limit uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array; // store all the powers of the lhr members < n-2 uint[] lhr_mults; // for lhr values not part of a pcp foreach(r; lhr) { // step thru the lhr members auto r_pwr = r; // set to first power of r if (r > rhi/r_pwr) break; // exit if r^2 > n-2, as all others are too while (r < rhi/r_pwr) // while r^e < n-2 lhr_mults ~=(r_pwr *= r); // store its current power of rA } // store all the cross-products of the lhr members < n-2 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 } } // convert lhr_mults vals > n/2 to their lhr complements n-r, // store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array; lhr_del.sort!("a < b"); lhr = setDifference(lhr, lhr_del).array; writeln([n, lhr.length]); // show n and pcp prime pairs count writeln([lhr[0], n-lhr[0]]); // show first pcp prime pair of n writeln([lhr[$-1],n-lhr[$-1]]); // show last pcp prime pair of n } void main(string[] args) { // directly recieve input from terminal string[] inputs = args[1..$]; // can include '_': 123_456 auto nums = inputs.map!(i => i.filter!(n => n != '_')); auto n = nums.map!(f => f.to!uint())[0]; auto timer = StopWatch(); // create execution timer timer.start(); // start it prime_pairs_lohi(n); // run routine writeln(timer.peek()); // show timer results } Here's the u64 version. // Compile with ldc2: $ ldc2 --release -O3 -mcpu native prime_pairs_lohi_u64.d // Run as: $ ./prime_pairs_lohi_u64 123_456_780 module prime_pairs; import std; import std.datetime.stopwatch : StopWatch; void prime_pairs_lohi(ulong n) { // inputs can be of size u64 if ((n&1) == 1 || n < 4) { return writeln("Input not even n2"); }if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; } // generate the low-half-residues (lhr) r < n/2 auto ndiv2 = n/2; // llr:hhr midpoint auto rhi = n-2; // max residue limit ulong[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array; // store all the powers of the lhr members < n-2 ulong[] lhr_mults; // for lhr values not part of a pcp foreach(r; lhr) { // step thru the lhr members auto r_pwr = r; // set to first power of r if (r > rhi/r_pwr) break; // exit if r^2 > n-2, as all others are too while (r < rhi/r_pwr) // while r^e < n-2 lhr_mults ~=(r_pwr *= r); // store its current power of rA } // store all the cross-products of the lhr members < n-2 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 } } // convert lhr_mults vals > n/2 to their lhr complements n-r, // store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array; lhr_del.sort!("a < b"); lhr = setDifference(lhr, lhr_del).array; writeln([n, lhr.length]); // show n and pcp prime pairs count writeln([lhr[0], n-lhr[0]]); // show first pcp prime pair of n writeln([lhr[$-1],n-lhr[$-1]]); // show last pcp prime pair of n } void main(string[] args) { // directly recieve input from terminal string[] inputs = args[1..$]; // can include '_': 123_456 auto nums = inputs.map!(i => i.filter!(n => n != '_')); auto n = nums.map!(f => f.to!ulong())[0]; auto timer = StopWatch(); // create execution timer timer.start(); // start it prime_pairs_lohi(n); // run routine writeln(timer.peek()); // show timer results }
Feb 05
On Wednesday, 5 February 2025 at 21:24:51 UTC, Jabari Zakiya wrote:On Tuesday, 4 February 2025 at 17:17:42 UTC, Jabari Zakiya wrote:I've updated the code to make it shorter|simpler. ``` module prime_pairs; import std; import std.datetime.stopwatch : StopWatch; void prime_pairs_lohi(uint n) { // inputs can be of size u32 if ((n&1) == 1 || n < 4) { return writeln("Input not even n > 2"); } if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; } // generate the low-half-residues (lhr) r < n/2 auto ndiv2 = n/2; // llr:hhr midpoint auto rhi = n-2; // max residue limit uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array; // store all powers and cross-products of the lhr members < n-2 uint[] lhr_mults; // lhr multiples, not part of a pcp foreach(i, r; lhr) { auto rmax = rhi / r; // ri can't multiply r with values > this if (r < rmax) lhr_mults ~= r*r; // for r^2 multiples if (lhr[i+1] > rmax) break ; // exit if product of consecutive r’s > n-2 foreach(ri; lhr[i+1..$]) { // for each residue in reduced list if (ri > rmax) break; // exit for r if cross-product with ri > n-2 lhr_mults ~= r * ri; // store value if < n-2 } } // convert lhr_mults vals > n/2 to their lhr complements n-r, // store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array; lhr_del.sort!("a < b"); lhr = setDifference(lhr, lhr_del).array; // lhr now contains just pcp primes writeln([n, lhr.length]); // show n and pcp prime pairs count writeln([lhr[0], n-lhr[0]]); // show first pcp prime pair of n writeln([lhr[$-1],n-lhr[$-1]]); // show last pcp prime pair of n } void main(string[] args) { // directly recieve input from terminal string[] inputs = args[1..$]; // can include '_': 123_456 auto nums = inputs.map!(i => i.filter!(n => n != '_')); auto n = nums.map!(f => f.to!uint())[0]; auto timer = StopWatch(); // create execution timer timer.start(); // start it prime_pairs_lohi(n); // run routine writeln(timer.peek()); // show timer results } ```On Monday, 3 February 2025 at 04:59:43 UTC, monkyyy wrote:I updated the code to make entering data easier. It now mimics the Ruby|Crystal code and takes "humanized" data strings. You can now run the code as: `$ ./primes_pair_lohi_u32 123_456_780` I also created two versions, one for u32 input values, and one for u64. Unless you have lots of memmory, the u32 version is best to use. Here's the u32 input size version. // Compile with ldc2: $ ldc2 --release -O3 -mcpu native prime_pairs_lohi_u32.d // Run as: $ ./prime_pairs_lohi_u32 123_456_780 module prime_pairs; import std; import std.datetime.stopwatch : StopWatch; void prime_pairs_lohi(uint n) { // inputs can be of size u32 if ((n&1) == 1 || n < 4) { return writeln("Input not even n > 2"); } if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; } // generate the low-half-residues (lhr) r < n/2 auto ndiv2 = n/2; // llr:hhr midpoint auto rhi = n-2; // max residue limit uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array; // store all the powers of the lhr members < n-2 uint[] lhr_mults; // for lhr values not part of a pcp foreach(r; lhr) { // step thru the lhr members auto r_pwr = r; // set to first power of r if (r > rhi/r_pwr) break; // exit if r^2 > n-2, as all others are too while (r < rhi/r_pwr) // while r^e < n-2 lhr_mults ~=(r_pwr *= r); // store its current power of rA } // store all the cross-products of the lhr members < n-2 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 } } // convert lhr_mults vals > n/2 to their lhr complements n-r, // store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array; lhr_del.sort!("a < b"); lhr = setDifference(lhr, lhr_del).array; writeln([n, lhr.length]); // show n and pcp prime pairs count writeln([lhr[0], n-lhr[0]]); // show first pcp prime pair of n writeln([lhr[$-1],n-lhr[$-1]]); // show last pcp prime pair of n } void main(string[] args) { // directly recieve input from terminal string[] inputs = args[1..$]; // can include '_': 123_456 auto nums = inputs.map!(i => i.filter!(n => n != '_')); auto n = nums.map!(f => f.to!uint())[0]; auto timer = StopWatch(); // create execution timer timer.start(); // start it prime_pairs_lohi(n); // run routine writeln(timer.peek()); // show timer results }On Monday, 3 February 2025 at 04:15:09 UTC, Jabari Zakiya wrote:FYI. This code finds all the prime pairs that sum to n for all even integers n > 2. It (Ruby code) is included in a paper I just released (Feb 2, 2025) on Goldbach's Conjecture (1742) and Bertrand's Postulate (1845). For those interested in Prime|Number Theory check it out. A lot of new, good, stuff is in it! **Proof of Goldbach's Conjecture and Bertrand's Postulate Using Prime Generator Theory (PGT)** https://www.academia.edu/127404211/Proof_of_Goldbachs_Conjecture_and_Bertrands_Postulate_Using_Prime_Generator_Theory_PGT_I translated this Ruby code:
Feb 08
I'm bringing attention to this issue as it might improve D. It has to do with the fastest way to remove elements in one array|list from another. It concerns the code in this thread to generate the prime pairs of n. In the code I have two arrays, `lhr` and `lhr_del`, and want to remove|delete the elements in `lhr_del` from `lhr`. In D it's: `lhr_del.sort!("a < b");` `lhr = setDifference(lhr, lhr_del).array;` In the original Rust version it was done as: `lhr.retain(|&m| !lhr_del.contains(&m));` This is conceptually keeping the members in `lhr` not in `lhr_del`. This is slow in Rust, and was greatly improved doing: `lhr_del.sort_unstable();` `lhr.retain(|&m| !lhr_del.binary_search(&m).is_ok());` Then Someone did a Rust equivalent of `D`'s `setDifference` allowing it to be coded as: `lhr_del.sort_unstable();` `let lhr: Vec<u32> = SetDiff::new(&lhr, &lhr_del).collect();` This is even faster. Here's the Rust code implementation for the `u32` version. Change the `u32` references to `usize` for `u64` size numbers (which use more memory). ``` struct SetDiff<'a> { r1: &'a [u32], r2: &'a [u32], } impl<'a> SetDiff<'a> { fn adjust_pos(&mut self) { while !self.r1.is_empty() { if self.r2.is_empty() || self.r1[0] < self.r2[0] { break; } else if self.r2[0] < self.r1 [0] { self.r2 = &self.r2[1..]; } else { self.r1 = &self.r1[1..]; self.r2 = &self.r2[1..]; } } } fn new(r1: &'a [u32], r2: &'a [u32]) -> Self { let mut s = SetDiff{ r1, r2 }; s.adjust_pos(); s } } impl<'a> Iterator for SetDiff<'a> { type Item = u32; fn next(&mut self) -> Option<Self::Item> { let val = self.r1.get(0).copied(); if val.is_some() { self.r1 = &self.r1[1..]; } self.adjust_pos(); return val } } ``` Here are `u32` time comparisons for the last two Rust versions and D. ``` ------------------------------------------ n | b-srch | setdif | D | ------------_-|--------|--------|--------| 100,000,000 | 3.35 | 2.96 | 7.21 | --------------|--------|------- |--------| 200,000,000 | 7.77 | 6.19 | 15.86 | ------- ------|--------|--------|--------| 300,000,000 | 6.40 | 5.73 | 10.89 | --------------|--------|--------|--------| 400,000,000 | 14.44 | 12.80 | 33.13 | ---- ---------|--------|--------|--------| 500,000,000 | 18.44 | 16.32 | 42.58 | --------------|--------|--------|--------| 600,000,000 | 13.47 | 12.05 | 22.22 | ---- ---------|--------|--------|--------| 700,000,000 | 21.72 | 19.51 | 46.19 | --------------|--------|--------|--------| 800,000,000 | 30.97 | 27.51 | 71.44 | ---- ---------|--------|--------|--------| 900,000,000 | 22.95 | 18.30 | 35.66 | --------------|--------|--------|--------| 1,000,000,000 | 38.99 | 34.81 | 88.74 | ``` The only substantive difference between the versions seems to be how each does its `SetDif`. At least that's the only thing I can think of that causes this much performance difference. I thought I'd let you know. Here are the source files, and compiling settings. ``` /* D LDC2 1.40 Compile with ldc2: $ ldc2 --release -O3 -mcpu native prime_pairs_lohi.d Run as: $ ./prime_pairs_lohi_u32 123_456 */ module prime_pairs; import std; import std.datetime.stopwatch : StopWatch; void prime_pairs_lohi(uint n) { // inputs can be of size u32 if ((n&1) == 1 || n < 4) { return writeln("Input not even n > 2"); } if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; } // generate the low-half-residues (lhr) r < n/2 auto ndiv2 = n/2; // llr:hhr midpoint auto rhi = n-2; // max residue limit uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array; // identify and store all powers and cross-products of the lhr members < n-2 uint[] lhr_del; // lhr multiples, not part of a pcp foreach(i, r; lhr) { // iterate thru lhr to find prime multiples auto rmax = rhi / r; // ri can't multiply r with values > this if (r < rmax) lhr_del ~= (r*r < ndiv2) ? r*r : n - r*r; // for r^2 multiples if (lhr[i+1] > rmax) break ; // exit if product of consecutive r’s > n-2 foreach(ri; lhr[i+1..$]) { // for each residue in reduced list if (ri > rmax) break; // exit for r if cross-product with ri > n-2 lhr_del ~= (r*ri < ndiv2) ? r*ri : n - r*ri; // store value if < n-2 } } // remove from lhr its lhr mulitples, the pcp remain lhr_del.sort!("a < b"); lhr = setDifference(lhr, lhr_del).array; writeln([n, lhr.length]); // show n and pcp prime pairs count writeln([lhr[0], n-lhr[0]]); // show first pcp prime pair of n writeln([lhr[$-1],n-lhr[$-1]]); // show last pcp prime pair of n } void main(string[] args) { // directly recieve input from terminal string[] inputs = args[1..$]; // can include '_': 123_456 auto nums = inputs.map!(i => i.filter!(n => n != '_')); auto n = nums.map!(f => f.to!uint())[0]; auto timer = StopWatch(); // create execution timer timer.start(); // start it prime_pairs_lohi(n); // run routine writeln(timer.peek()); // show timer results } ------------------------------------------------------------------------------------ /* Rust 1.84.1 Can compile as: $ cargo build --release or: $ RUSTFLAGS="-C opt-level=3 -C debuginfo=0 -C target-cpu=native" cargo build --release Run as: $ ./prime_pairs_lohi 123_456 */ use std::time::Instant; fn coprime(mut m: u32, mut n: u32) -> bool { while m|1 != 1 { let t = m; m = n % m; n = t } m > 0 } fn prime_pairs_lohi(n : u32) { // for u32 input values if n&1 == 1 || n < 4 { return println!("Input not even n > 2"); } if n <= 6 { return println!("[{}, {}]\n[{}, {}]\n[{}, {}]",n,1,n/2,n/2,n/2,n/2); }; // generate the low-half-residues (lhr) r < n/2 let (ndiv2, rhi) = (n/2, n-2); // lhr:hhr midpoint, max residue limit let mut lhr: Vec<u32> = (3..ndiv2).step_by(2).filter(|&r| coprime(r, n)).collect(); // identify and store all powers and cross-products of the lhr members < n-2 let mut lhr_del = Vec::with_capacity(lhr.len() as usize); for i in 1..lhr.len()-1 { // iterate thru lhr to find prime multiples let (mut j, r) = (i, lhr[i-1]); // for current residue let rmax = rhi / r; // ri can't multiply r with values > this if r < rmax { lhr_del.push(if r*r < ndiv2 {r*r} else {n - r*r} ); } if lhr[i] > rmax { break } // exit if product of consecutive r’s > n-2 while lhr[j] <= rmax { // stop for r if product with ri > n-2 lhr_del.push(if r*lhr[j] < ndiv2 {r*lhr[j]} else {n - r*lhr[j]}); j += 1; // get next lhr value } } lhr_del.sort_unstable(); // remove from lhr its lhr mults lhr.retain(|&m| !lhr_del.binary_search(&m).is_ok()); let lcnt = lhr.len(); // number of pcp prime pairs println!("[{}, {}]", n, lcnt); // show n and pcp prime pairs count println!("[{}, {}]", lhr[0],n-lhr[0]); // show first pcp prime pair of n println!("[{}, {}]", lhr[lcnt-1], n-lhr[lcnt-1]); // show last pcp prime pair of n } fn main() { let n: u32 = std::env::args() .nth(1).expect("missing count argument") .replace('_', "").parse().expect("one input"); let start = Instant::now(); prime_pairs_lohi(n); println!("{:?}", start.elapsed()); } --------------------------------------------------------------------------------------------- /* Rust 1.84.1 Can compile as: $ cargo build --release or: $ RUSTFLAGS="-C opt-level=3 -C debuginfo=0 -C target-cpu=native" cargo build --release Run as: $ ./prime_pairs_lohi 123_456 */ use std::time::Instant; struct SetDiff<'a> { r1: &'a [u32], r2: &'a [u32], } impl<'a> SetDiff<'a> { fn adjust_pos(&mut self) { while !self.r1.is_empty() { if self.r2.is_empty() || self.r1[0] < self.r2[0] { break; } else if self.r2[0] < self.r1 [0] { self.r2 = &self.r2[1..]; } else { self.r1 = &self.r1[1..]; self.r2 = &self.r2[1..]; } } } fn new(r1: &'a [u32], r2: &'a [u32]) -> Self { let mut s = SetDiff{ r1, r2 }; s.adjust_pos(); s } } impl<'a> Iterator for SetDiff<'a> { type Item = u32; fn next(&mut self) -> Option<Self::Item> { let val = self.r1.get(0).copied(); if val.is_some() { self.r1 = &self.r1[1..]; } self.adjust_pos(); return val } } fn coprime(mut m: u32, mut n: u32) -> bool { while m|1 != 1 { let t = m; m = n % m; n = t } m > 0 } fn prime_pairs_lohi(n : u32) { // for u32 input values if n&1 == 1 || n < 4 { return println!("Input not even n > 2"); } if n <= 6 { return println!("[{}, {}]\n[{}, {}]\n[{}, {}]",n,1,n/2,n/2,n/2,n/2); }; // generate the low-half-residues (lhr) r < n/2 let (ndiv2, rhi) = (n/2, n-2); // lhr:hhr midpoint, max residue limit let mut lhr: Vec<u32> = (3..ndiv2).step_by(2).filter(|&r| coprime(r, n)).collect(); // identify and store all powers and cross-products of the lhr members < n-2 let mut lhr_del = Vec::with_capacity(lhr.len() as usize); for i in 1..lhr.len()-1 { // iterate thru lhr to find prime multiples let (mut j, r) = (i, lhr[i-1]); // for current residue let rmax = rhi / r; // ri can't multiply r with values > this if r < rmax { lhr_del.push(if r*r < ndiv2 {r*r} else {n - r*r} ); } if lhr[i] > rmax { break } // exit if product of consecutive r’s > n-2 while lhr[j] <= rmax { // stop for r if product with ri > n-2 lhr_del.push(if r*lhr[j] < ndiv2 {r*lhr[j]} else {n - r*lhr[j]}); j += 1; // get next lhr value } } lhr_del.sort_unstable(); // remove from lhr its lhr mults let lhr: Vec<u32> = SetDiff::new(&lhr, &lhr_del).collect(); let lcnt = lhr.len(); // number of pcp prime pairs println!("[{}, {}]", n, lcnt); // show n and pcp prime pairs count println!("[{}, {}]", lhr[0],n-lhr[0]); // show first pcp prime pair of n println!("[{}, {}]", lhr[lcnt-1], n-lhr[lcnt-1]); // show last pcp prime pair of n } fn main() { let n: u32 = std::env::args() .nth(1).expect("missing count argument") .replace('_', "").parse().expect("one input"); let start = Instant::now(); prime_pairs_lohi(n); println!("{:?}", start.elapsed()); } ```// convert lhr_mults vals > n/2 to their lhr complements n-r, // store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n - r_del : r_del).array; lhr_del.sort!("a < b"); lhr = setDifference(lhr, lhr_del).array;
Feb 18
monkyyy <crazymonkyyy gmail.com> On Tuesday, 18 February 2025 at 22:45:39 UTC, Jabari Zakiya wrote:I'm bringing attention to this issue as it might improve D.Known issue with upstream, try one of mine data structures https://github.com/opendlang/d/blob/main/source/odc/datastructures.d
Feb 18
On Tuesday, 18 February 2025 at 22:45:39 UTC, Jabari Zakiya wrote:I'm bringing attention to this issue as it might improve D. It has to do with the fastest way to remove elements in one array|list from another. It concerns the code in this thread to generate the prime pairs of n. In the code I have two arrays, `lhr` and `lhr_del`, and want to remove|delete the elements in `lhr_del` from `lhr`.Many parts of the core code can be optimized. Since I don't have much time right now, I only saw 1 improvement. Below the GCD filter will give the same list (lhr[]). ```d uint[] lhr;// = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;/* lhr.reserve(cast(ulong)log(cast(double)n)/2); for (uint i = 3; i < ndiv2; i += 2) { if (i % 3 != 0 && i % 5 != 0) { lhr ~= i; } }//*/ ``` SDB 79
Feb 18
On Wednesday, 19 February 2025 at 02:25:03 UTC, Salih Dincer wrote:have much time right now, I only saw 1 improvement. Below the GCD filter will give the same list (lhr[]). SDB 79It is giving different result
Feb 19
On Friday, 31 January 2025 at 20:05:54 UTC, Jabari Zakiya wrote:I'm converting Ruby code to D and am running into issues. Would appreciate what needs to be done to get it to compile/run correctly.First of all, I see that you don't use reserve() at all in arrays. Since I work on a mobile platform (by Dcoder from India), I have limited opportunities. So would you try the code below; does it work quickly, safely and with accurate results. ```d import std.stdio, std.conv, std.range, std.algorithm; import std.datetime.stopwatch : StopWatch; void main(string[] args) { alias T = uint; auto inputs = ["5_005_446", "65_537"]; auto nums = inputs.map!(i => i.filter!(n => n != '_')); auto n = nums.map!(f => f.to!T())[0]; auto timer = StopWatch(); timer.start(); n.prime_pairs_lohi(); timer.peek.writeln(); } void prime_pairs_lohi(T)(T n) { if (n & 1 || n < 4) { return writeln("Input not even n > 2"); } if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; } T ndiv2 = n / 2; T rhi = n - 2; T[] lhr;// = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;/* lhr.reserve(n / 4); // SDB 79 added! auto factors = n.getFactors!100; for (T i = 3; i < ndiv2; i += 2) { bool coprime = true; foreach (p; factors) { if (i % p == 0) { coprime = false; break; } } if (coprime) lhr ~= i; }//*/ // identify and store all powers and cross-products of the lhr members < n-2 T[] lhr_del; // lhr multiples, not part of a pcp lhr_del.reserve(n / 2); // SDB 79 added! foreach(i, r; lhr) { // iterate thru lhr to find prime multiples auto rmax = rhi / r; // ri can't multiply r with values > this if (r < rmax) lhr_del ~= (r*r < ndiv2) ? r*r : n - r*r; // for r^2 multiples if (lhr[i+1] > rmax) break; // exit if product of consecutive r’s > n-2 foreach(ri; lhr[i+1..$]) { // for each residue in reduced list if (ri > rmax) break; // exit for r if cross-product with ri > n-2 lhr_del ~= (r*ri < ndiv2) ? r*ri : n - r*ri; // store value if < n-2 } } // remove from lhr its lhr multiples, the pcp remain lhr_del.sort!"a < b"; lhr = setDifference(lhr, lhr_del).array; writeln([n, lhr.length]); // show n and pcp prime pairs count writeln([lhr[0], n-lhr[0]]); // show first pcp prime pair of n writeln([lhr[$-1],n-lhr[$-1]]); // show last pcp prime pair of n } auto getFactors(int limit, T)(T n) { T[] factors; T f = 3; T x = n;/* T x = n; while (x % 2 == 0) { factors ~= 2; x /= 2; }//*/ while (f < limit && f * f <= x) { if (x % f == 0) { if (!factors.canFind(f)) { factors ~= f; } x /= f; } else { f += 2; } } //if (x > 1) factors ~= x; return factors; } auto gcd(T)(T a, T b) { while (b != 0) { auto temp = b; //while (a >= b) a -= b;/* a %= b; //*/ b = a; a = temp; } return cast(T)a; } ``` SDB 79
Feb 19
On Wednesday, 19 February 2025 at 23:58:09 UTC, Salih Dincer wrote:On Friday, 31 January 2025 at 20:05:54 UTC, Jabari Zakiya wrote:I removed 1 line in your code (note if (r <= rMax) ) and added values greater than 0 to the 2nd array (lhr_del[]). setDifference() did not cause any problems. Can you check? ```d import std.stdio, std.conv, std.range, std.algorithm; import std.datetime.stopwatch : StopWatch; void main(string[] args) { alias T = uint; auto inputs = ["500_005_446", "65_537"]; auto nums = inputs.map!(i => i.filter!(n => n != '_')); auto n = nums.map!(f => f.to!T())[0]; auto timer = StopWatch(); timer.start(); n.prime_pairs_lohi(); timer.peek.writeln(); } /* [500005446, 1854807] [7, 500005439] [250002523, 250002923] [250001387, 250004059] [249999649, 250005797] [249998743, 250006703] 1 minute, 44 secs, 656 ms, 912 μs, and 8 hnsecs */ void prime_pairs_lohi(T)(T n) { if (n & 1 || n < 4) { return writeln("Input not even n > 2"); } if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]); writeln([n/2, n/2]); return; } T ndiv2 = n / 2; T rhi = n - 2; T[] lhr;// = iota(3, ndiv2, 2).filter!(e => gcd(e, n) == 1).array;/* lhr.reserve(n / 4); // SDB 79 added! auto factors = n.getFactors!100; for (T i = 3; i < ndiv2; i += 2) { bool coprime = true; foreach (p; factors) { if (i % p == 0) { coprime = false; break; } } if (coprime) lhr ~= i; }//*/ // identify and store all powers and cross-products of the lhr members < n-2 T[] lhr_del; // lhr multiples, not part of a pcp foreach(i, r; lhr) // iterate thru lhr to find prime multiples { auto rMax = rhi / r; if (r <= rMax) // ri can't multiply r with values >= this { T r2 = r * r; // for r^2 multiples if (auto value = (r2 < ndiv2) ? r2 : n - r2) { // SDB 79 added! lhr_del ~= value; } } // SDB 79 removed! // if (lhr[i+1] > rmax) break; // exit if product of consecutive r’s > n-2 foreach(ri; lhr[i+1..$]) { // for each residue in reduced list if (ri > rMax) break; // exit for r if cross-product with ri > n-2 if (auto value = (r*ri < ndiv2) ? r*ri : n - r*ri) // store value if < n-2 { // SDB 79 added! lhr_del ~= value; } } } // remove from lhr its lhr multiples, the pcp remain lhr = lhr.setDifference(lhr_del.sort!"a < b").array; writeln([n, lhr.length]); // show n and pcp prime pairs count writeln([lhr[0], n-lhr[0]]); // show first pcp prime pair of n writeln([lhr[$-1], n - lhr[$-1]]); // show last pcp writeln([lhr[$-10], n-lhr[$-10]]); // show last pcp prime pair of n writeln([lhr[$-20], n-lhr[$-20]]); // show last pcp prime pair of n writeln([lhr[$-30], n-lhr[$-30]]); // show last pcp prime pair of n } auto getFactors(int limit, T)(T n) { T[] factors; T f = 3; T x = n;/* T x = n; while (x % 2 == 0) { factors ~= 2; x /= 2; }//*/ while (f < limit && f * f <= x) { if (x % f == 0) { if (!factors.canFind(f)) { factors ~= f; } x /= f; } else { f += 2; } } //if (x > 1) factors ~= x; return factors; } auto gcd(T)(T a, T b) { while (b != 0) { auto temp = b; //while (a >= b) a -= b;/* a %= b; //*/ b = a; a = temp; } return cast(T)a; } ``` SDB 79I'm converting Ruby code to D and am running into issues. Would appreciate what needs to be done to get it to compile/run correctly.
Feb 21