This will likely be my final post about the GC60 project. After four years of research, I believe I have reached the goal I set out to achieve.
The program that reached this milestone is called GC60_M60x16_LRLN. I would like to briefly clarify the naming convention I use: these are not simple code optimizations, but different structures that share the core idea of the main project. For this reason, they have different names depending on the logic applied. In this case, M60x16 indicates processing across 16 columns mod 60, while M30x8 indicates processing across 8 columns mod 30.
To give you a quick example of the results (which you can verify directly in the repository):
Julia (Magnitude 10^19 with W = 100,000:
x8 version: ~0.905 s
x16 version: ~0.495 s
C++ (same Magnitude and same window):
x16.cpp version: ~0.276 s
The programs are released under the MIT-0 license: any of you who wish to implement them further, optimize them, or integrate them into your own projects are completely free to do so.
Thank you all for your attention and for giving me the opportunity to share my project!
Update: Iβve also made the repository available on GitHub, as Codeberg occasionally has server availability issues.
Please benchmark your algorithm on a size where sieves actually make sense. All you are seeing here is that a method that works less like a sieve performs better than a method that tracks the data necessary to sieve information. To demonstrate, this code is 10x slower than a basic primality checker (BPSW with extra miller rabbin iterations) running on a single thread.
julia> using Primes
julia> function badsieve(start, width)
n = 0
for i in start:start+width
isprime(i) && (n+=1)
end
return n
end
badsieve (generic function with 1 method)
julia> @benchmark badsieve(UInt128(10)^19, 100000)
BenchmarkTools.Trial: 351 samples with 1 evaluation per sample.
Range (min β¦ max): 9.617 ms β¦ 187.168 ms β GC (min β¦ max): 0.00% β¦ 67.02%
Time (median): 10.318 ms β GC (median): 0.00%
Time (mean Β± Ο): 14.271 ms Β± 23.337 ms β GC (mean Β± Ο): 18.61% Β± 10.44%
β
βββββββββββββββββββββββββββββββββββββββββββββ βββββββββββββββ β
9.62 ms Histogram: log(frequency) by time 159 ms <
Memory estimate: 7.99 MiB, allocs estimate: 319442.
In order for your benchmark to be at all meaningful, you need W~sqrt(Magnitude)/100 or bigger (roughly 3*10^7).
If I understood correctly, you believe that for benchmarks to be meaningful, the search window (W) should be proportional to the magnitude being analyzed.
I have included several benchmarks of this kind in the repository, but here is a practical example based on GC60_M60x16_LRLN.cpp using a window size of W = 10,000,000:
Radice max (Limite Setaccio B): 3.162.277.660
Cicli totali per colonna : 202
Generazione divisori di base in corsoβ¦
Divisori di base pronti: 5.795 primi
[Tempo bootstrap: 0 min. 0 sec. 9 ms]
Avvio setacciamento verticale a 16 colonne con filtro LRLNβ¦
Divisori geometrici stabili isolati: 2.584.535
[Tempo Fase B (Setaccio + LRLN): 0 min. 0 sec. 397 ms]
Fase C: spogliatura della finestra passiva a 10.000.000.000.000.000.000β¦
Primi reali trovati nella finestra: 229.305
[Tempo Fase C: 0 min. 0 sec. 52 ms]
TEMPO REALE TOTALE DI ESECUZIONE: 0 min. 0 sec. 459 ms
I also ran primesieve on the exact same range (10^19 with a window of 10,000,000), yielding the identical count of 229,305 primes in 1.638 seconds.
I invite you to run this test on your own setup to verify the comparison firsthand. If youβd like to share your results, I would be very glad to read them!
Just to clarify, βGCβ simply stands for my initials (Govi Claudio) and the numbers are references to the project iterations and the modulus 60 structure, rather than a sequence of 59 previous methods!
In short, the GC-60 model is a divisor-centric approach to prime number exploration. Instead of scanning a search window directly or using traditional sieves, it translates known prime divisors based on the mathematical structure of modulus 60 (M60).
The search window acts as a passive container: only the divisors that carry relevant structural information project onto it, filtering out non-primes. This isolates candidate primes efficiently without the need to track unnecessary data across the entire window.
Feel free to check out the details and source code in the repository!