It seems your post got buried by all the other noise. Thanks for the spirit and sharing of your code! My immediate question is: have you compared your code's efficiency to original RCKangaroo, maybe not only for puzzle #80? Is there any significant advantage with your own setup (single GPU, decent RAM size)?
Hi Cricktor, thanks for taking the time to look at it I appreciate the question.
Short answer on benchmarks: I don't have a proper apples-to-apples wall-clock comparison yet on the same puzzle. I validated correctness by solving Puzzle #80 (79-bit range), but didn't run the original RCKangaroo side-by-side on the same hardware. That's a fair gap I should do it and publish numbers. I'll prioritize that.
What I can describe are the algorithmic changes in the GPU kernel, since that's where performance actually matters:
1. Endomorphism 6x canonical form (GPU-side)Before the DP check, each X coordinate is reduced to its canonical form the smallest of three equivalent values:
canonical = min(x, β·x, β²·x) mod p
This is done branchless inside the CUDA kernel. Three equivalent points now map to the same Distinguished Point, effectively multiplying useful DP coverage by up to √3. No CPU involvement.
2. Cheap Second PointWhen computing P + J (the kangaroo hop), the modular inverse is already available from batch inversion, so P − J comes almost for free:
Cost: 1 Add + 1 Mul + 1 Sqr + 2 Sub (per group)
This doesn't alter the kangaroo's trajectory but generates a second DP candidate per hop, roughly doubling the DP output rate.
3. XDP (Extended Distinguished Points)Instead of the standard single-pattern DP check:
Original: (x >> shift) == 0 → accepts 1 pattern
PSC: (x >> shift) < XDP_MULT → accepts N patterns (default N=8)
The DP rate increases 8x. More DPs per hop means faster collision detection, at the cost of more CPU-side processing which is where the abundant RAM and multi-threaded CPU come in.
These three compound inside the kernel every hop produces significantly more useful DP candidates than the original, without modifying the hop arithmetic itself.
Architecture changes (motivated by single GPU + 128 GB RAM):
ALL-TAME mode: During TRAP phase, 100% of GPU kangaroos are TAME, filling all available RAM exclusively with TAME entries. During HUNT, all kangaroos switch to WILD and check against the stored TAMEs. No WILD storage needed just streaming collision checks. This maximizes the TAME table size compared to the original's split TAME/WILD1/WILD2 allocation.
Ultra-compact 16-byte entries (vs 25 bytes in the original): distance is truncated by 32 bits to save space, giving +56% capacity in the same RAM. The lost precision is recovered on collision via a precomputed Baby-Step Giant-Step table (~400ms per resolution).
Async BSGS resolution on dedicated CPU threads while the GPU keeps hopping. The GPU never stalls waiting for collision verification.
Honest summary: raw hop speed per GPU cycle is essentially the same I didn't modify RetiredCoder's core EC arithmetic, which is already SOTA. The advantage comes from (a) extracting more useful work per hop via endomorphism + cheap point + XDP, and (b) an architecture that lets a single GPU with abundant RAM build and exploit a much larger TAME table than the original design allows.
Whether that translates into a meaningful wall-clock advantage on a specific puzzle I owe you actual numbers. I'll run a controlled comparison and report back.
Code:
github.com/pscamillo/PSCKangaroo the kernel diff against the original
RCGpuCore.cu should make the changes easy to inspect.
