Re: [ANN][GAP] Gapcoin - Prime Gap Search - New Math Algo - CPU / GPU - Zero Premine
It would be really fantastic to see the upper bound limits removed someday, perhaps.
We simply need moar primespersec (network has power) i.e. more folks mining and/or better miners / ASICs etc.,
We simply need moar primespersec (network has power) i.e. more folks mining and/or better miners / ASICs etc.,
I don't believe that the upper bound on shift value is a blocking issue. Back in Dec 2017, YomKi articulated why:
There are a few different methods being used for current gap finding efforts:
- Exhaustive search. This is looking for true record gaps, which means it started at 2 and went up from there. It's intensely computationally expensive. Tomás Oliveira e Silva ran a distributed project from 2005 to 2012 that got to 4e18 using years of work on hundreds of cores. Interestingly, the computational result was used in Helfgott's 2013 proof of the Odd Goldbach Conjecture. Recently the PGS team at mersenneforum have used a different method to extend this and after about 9 months have brought this to 10e18. The number of records per computational effort is very small, however these are true Minimal Gaps -- once found the record is permanent, as no earlier gaps of that size exist.
- Gapcoin. For relatively small P1 values (84-347 digits), choose a random small range, sieve out small multiples, then run Fermat tests to find gaps. While each step is efficient and fast, it's rather inefficient at finding record gaps. It's basically rapidly throwing darts while blindfolded and being spun around -- the only way to get more darts in the target is to throw faster.
- Primorial methods. Gaps are far more common at multiples of primorials without some small divisors, e.g. numbers of the form N * p# / k with k a small square free number. So if one looks at increasing values of N * 191#/30, for instance, using efficient methods for finding the previous and next primes around that point, one can find record gaps many times times faster than the gapcoin method. That is the method used by most other searchers and is what holds all but 3 of the highest merits (those three being from the exhaustive search). There are some minor variations -- Hans Rosenthal in 2017 did searches with a fixed large N and instead varied k. Using the dart analogy from before, this is throwing darts while aiming at the target. The darts are thrown a lot slower, but since they're all thrown in the direction of the target rather than randomly around the room, more of them result in high results.
I find it worth bearing in mind that the Gapcoin code is performing not one but two functions - the discovery of prime gaps with record merit is a designed side-effect of using prime gap search as as a proof-of-work mechanism for a cryptocurrency and that dual functioning requirement necessarily restricts the range of P1 values that can be selected. As I noted, the higher the shift, the larger the primes being sieved and so the lower the hash rate. More efficient primorial-based methods for finding gaps are an ill fit with the requirement to act as a proof-of-work mechanism. The Prime Gap Search group of the mersenne forum has an open source primorial-based gap search implementation but, given its functional focus is on searching gaps, it's not a good solution for a proof-of-work implementation.
The fact that the Gapcoin prime gap record search implementation isn't as efficient as a dedicated approach is an inevitable trade-off arising from its use as a proof-of-work mechanism. Baisically, it's a balance and emphasising one aspect of this dual-functioning comes at the expense of the other.
...snip...
Indeed. I'm just keen to see what additional Prime Gaps Gapcoin might spin-up as the hash rate hopefully increases.
No forks required in the mean tine of course (an intentional pun).
P.S. Looks good Graham. I will PM you back ASAP. I guess we are going to have to co-ordinate a lot more on this one from now on then.
@Graham
- https://github.com/gapcoin/Gapcoin-PoWCore
"Additional notes:
startindex can be hash ∗ 2^shift + [0, 2^shift)
max sieve size depends on start index, and is limited by (hash + 2^shift) - startindex.
shift can theoretically be in range [14, 2^16) but nodes can choose to only accept shifts till a given amount (e.g. 512) "
Without objection from any of the original developers of Gapcoin I'm contacting Squares - Cryptocurrency Open Patent Alliance (COPA) ...
- https://open-patent.org/
With regards to the possibility of them helping the Gapcoin project to protect the original Gapcoin-PoWCore from any 'bad' actors.
...
Another disclaimer is also being added to the https://gapcoin.club website ...
"Disclaimer (Warning): Gapcoin (GAP) is NOT associated with the pi network project."
Onward.