Bitcoin Forum
May 22, 2018, 08:21:53 PM *
News: Latest stable version of Bitcoin Core: 0.16.0  [Torrent]. (New!)
 
  Home Help Search Donate Login Register  
  Show Posts
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 [51] 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 »
1001  Alternate cryptocurrencies / Altcoin Discussion / Re: [Bounty][OLD: New Bounty Made!] CUDA or OpenCL Primcoin Miner! on: July 18, 2013, 01:02:48 AM
I will toss some coins to the bounty but not for CUDA  Tongue

Hey, make your own thread! xD

If you want to contribute to a OpenCL miner, you would probably have the best luck making your own thread though. Smiley
1002  Alternate cryptocurrencies / Altcoin Discussion / Re: [Bounty] CUDA or OpenCL Primcoin Miner! Current: 400XPC on: July 18, 2013, 12:39:38 AM
Oh, forgot about this thread. I raised the bounty to 6BTC on another thread. I'll edit OP. Smiley
1003  Alternate cryptocurrencies / Altcoin Discussion / Re: [New Bounty] 6BTC for PrimeCoin CUDA miner! on: July 17, 2013, 02:05:29 PM
I vote for OpenCL, beacause I don't have nor going to buy NVidia, will put another 5BTC to bounty if it's designed for ATI Raedon GPUs.

For now, this thread is only for a CUDA-based miner, however I recommend if you would like to see an OCL one that you put that bounty in its own thread, I might contribute a Bitcoin to that one as well. Smiley
1004  Alternate cryptocurrencies / Altcoin Discussion / Re: [New Bounty] 6BTC for PrimeCoin CUDA miner! on: July 17, 2013, 01:34:19 PM
I think I have a pretty good understanding of the algorithm from a mathematics standpoint.  I don't know CUDA (or OpenCL, which I would suggest--it runs on both NVidia and AMD with reasonably comparable performance) and I don't know the getwork protocol, but I can give some insight into the mathematics, at least.

The first thing to understand is that if the block hash is H then H, 2H, 3H, 4H, etc are all valid origins, and that H-1, 2H-1, 4H-1, 8H-1, etc. makes a valid Cunningham chain (if all of those numbers are prime and the chain is long enough; this is for a Cunningham chain of the first kind.  For the second kind replace the "-" with "+".  Most of the math here will assume Cunningham chains of the First kind, but it is identicle for chains of the Second kind.  If H 1, 2H 1, ... are all prime (i.e. a chain of the first and second) then the chain is a bi-twin chain).  That means that when you are eliminating composite origins you are also eliminating numbers that could appear later in the chain.  This will become useful later.

Another thing to notice is that H, 2H, 3H, 4H, etc. are very unlikely to be prime.  If you look at the probability that a random number on the order of 2^256 is prime then it is about 1 in 177; that makes the probability that 8 randomly chosen numbers are all primes about 1 in 1 quintillion--impractically low.  That probability is greatly improved by using a "primorial" number--the product of many small primes.  If you take pRimorial= R = H * 2 * 3 * 5 * 7 * .... * 47 (the first 15 prime numbers; quick tests on my own code suggest that this is about ideal, although some tweaking and testing is in order) then you increase the size of the number you are testing, but you also make the numbers much more likely to be prime.  Thus if you look at R-1, 2R -1, etc then you know that each of those numbers is not divisible by 2, 3, 5, ... , 47 because they are 1 less than (or greater than, if you are looking for Cunningham chains of the Second kind) a multiple of each of those numbers.  This means that the smallest factor NR 1 can have is 53, where N is any integer.

From here you execute the Sieve.  The standard Sieve of Eratosthenes is very straightforward, but it is designed to be executed starting at 1 and then continuing over the small, consecutive integers, such as is shown on the GIF on the Wikipedia page.  We are not interested in consecutive numbers, and they are far from small, so a change must be adopted.  This change requires knowledge of modular arithmetic.  To execute the sieve we first take a small prime number (starting with 53 if our primorial ended with 47) and take R (mod 53).  If (and only if) R ≡ 0 (mod 53) then R is divisible by 53, and all future R will be divisible by 53.  In that case, no NR-1 will be divisible by 53 and none should be eliminated.

In every other case, R ≡ r (mod 53), where 0 < r < 53.  If you have found that r = 1 then that shows that R-1 ≡ 0 (mod 53) and is therefore not prime (and cannot be a member of a Cunningham Chain of the first kind).  If r = 52 then R+1 ≡ 0 (mod 53) and is therefore not prime.  If r is any other number then you have to search.  Since r is relatively prime to 53 (i.e. gcd(r,53) = 1) it can be shown that N * r (mod 53) will cycle through every number less than 53.  Thanks to modular arithmetic, N * r ≡ N * R (mod 53), so you can search for the N for which N1 * r ≡ 1 (mod 53) and for which N2 * r ≡ 52 (mod 53).  You can eliminate N1R - 1 as a candidate for chains of the first kind, and you can eliminate N2R + 1 as a candidate for chains of the second kind.

The power of finding this N is that you then know that if N * r ≡ 1 (mod 53) then (53 + N) * r ≡ 1 (mod 53) since N * r is cyclic with a period of 53.  Thus, you can quickly go through, just like in the classic form of the sieve of Eratosthenes, and eliminate every 53rd N.  You would then repeat this process for subsequent prime numbers (59, 61, 67, ...), until sieving against another prime number is not worth it--it takes too long and removes too few numbers.

The next thing you can do to eliminate candidates is to look for clusters (you can actually do this while sieving if you want, but I have separated it since it is a separate topic).  Since the goal is to find chains of (currently) 8 primes it makes no sense to waste time performing a long primality test on a chain of numbers that have passed the sieve that is 7 or fewer long.  Thus, you can look through the sieve for chains in the form N-1, 2N-1, 4N-1, ... 128N-1 where all of those numbers have no small factors (which would have been found in the sieve).  When you find these, they are passed to the formal (probable) primality tests.

The main test used in this step is the Fermat Primality Test, based on Fermat's Little Theorem.  It states that aP-1 ≡ 1 (mod P) for all prime P.  (It does not state that if that identity holds true then P is prime, but in practice prime numbers are far more likely than "Fermat liars").  For the reference client "a" is chosen to be 2, since 1 is trivially a Fermat Liar for every composite P and since a larger "a" would take more time for no benefit.  To perform the operation it is best to use "fast modular exponentiation," which is shown in pseudocode in the Modular Exponentiation Wikipedia page.

The second test used is the Euler Lagrange Lifchitz test (a brief reading of the code suggests that it is not actually used, but it is implemented.  You can skip this paragraph and not lose much).  It states that if P is prime and P ≡ 1 (mod 4) then 2P + 1 is prime if and only if 2P + 1 ≡ 0 (mod 2P + 1).  There are other forms as well:  if P ≡ 3 (mod 4) then 2P + 1 is prime if and only if 2P - 1 ≡ 0 (mod 2P +1).  There are forms for 2P-1 as well; if P ≡ 1 (mod 4) then you use 2P-1 - 1 ≡ 0 (mod 2P - 1); otherwise it's 2P-1 + 1 ≡ 0 (mod 2P -1).  These are not much, if any, faster than just using the Fermat primality test--they all rely on a single modular exponentiation, and in all cases the base is 2, and both the exponent and the modulus are on the order of P.  Lifchitz mentions a way to look for Cunningham chains of the second kind "in cluster" by taking 2ni-1-1-1 ≡ 0 (mod n * n1 * n2 * ... * ni) where ni = 2ni-1-1.  This test only looks for one kind of chain, though, and requires that n ≡ 1 (mod 4).  Also, it is a much more expensive modular exponentiation since the modulus is the product of 8 or more large numbers.

When a prime chain is found that is at least as long as floor(difficulty) (e.g. at least 8 when the difficulty is 8.9) it is necessary to calculate the fractional difficulty.  I haven't verified this in the source code, but in the design paper he takes r = (2P-1 (mod P) ) as the Fermat remainder, then defines the fractional length as (P - r) / P.  P, in all of this, is the number that would have been next in the chain.  I'm not sure which half of a bi-twin chain has to be used (note that a bi-twin chain can have an odd length if the two Cunningham chains it is made up of differ in length by 1).  If the integer chain length plus the fractional length is greater than the difficulty, it is a valid share.

I hope this has been easy enough to follow, while still being informative.  If anyone has questions I'll try to answer them.  Note that my understanding is based partially on looking at the code but also largely on my own insights; I've likely missed something major, but there is a slim chance that I've offered an improvement on what's already being done simply from coming at it from a different persepctive.  If you feel this satisfies part of your bounty for money, I can receive donations at 1FbWVR3LpGoWp5rc4SJc3cHo42ALrYhcxC.  Not really doing this for the bounty, though.  I just want to be as much help as possible towards making GPU mining a reality, to help neutralize the botnet and massive VPS farm threats.  

Awesome explanation, sending 0.25BTC over. I think I have a good enough explanation of the math to go forward, however (and this is a really dumb question), the block that has to be a factor of the origin of the prime, we just convert the hex of the previous block (so say we are trying to mine block 54320, we would convert the hex of block 54319 to decimal, correct?)

Oh, and another dumb question... What does '≡' mean? Smiley
1005  Alternate cryptocurrencies / Altcoin Discussion / Re: [New Bounty] 6BTC for PrimeCoin CUDA miner! on: July 17, 2013, 03:00:50 AM
-What purpose the sieve serves

In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.

The multiples of a given prime are generated starting from that prime, as a sequence of numbers with the same difference, equal to that prime, between consecutive numbers. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so)

awesome bounty btw i hope someone gets it

Yeah, during my short digging I did find the sieve of Eratosthenes, though your explanation was better than what I found. My main question with the sieve is, since we are finding very huge primes, what purpose this 'table of primes' serves the finding of large prime chains?
the sieve works by getting increasing more likely 'primes' by altering a value to be more likely prime, and the table is used as seeds for that 'winnowing' process.
You want to have a big table because the more you have, the more likely one of them will work for a given block.

This is really interesting! Mathematically, how does the sieve table work? Is one of the primes multiplied by a certain value and then changed in order to obtain a true prime? Also, what address do you want your 0.25 BTC to? Smiley
the prime chain is linked to the block header hash by requiring that its origin be divisible by the block header hash.
pk/r is used to measure the difficulty of the chain. r is the Fermat test remainder of the next number in chain pk
d = k + (pk- r)/pk  

k is the prime chain length. d = difficulty if pk passes probable primality tests then it should be considered as a chain of higher integral length.

my BTC addy is 13YGmE2CCAxWpAhqQSm5NVz9pU7Q4B22jm
thanks Smiley

Stellar, sent your 0.25 BTC Smiley Cheers!!
1006  Alternate cryptocurrencies / Altcoin Discussion / Re: [Bounty] Primecoin Standalone CPU Miner! Current: 2.5BTC on: July 17, 2013, 01:41:48 AM
Hello! I'm offering up 2.5BTC of my own money to the first person who releases a standalone CPU miner for primecoin that performs as well if not better than the primecoin implementation already in the client.

[...]



i dont know if it performs same or better..

Another valid point Smiley
1007  Alternate cryptocurrencies / Altcoin Discussion / Re: [New Bounty] 6BTC for PrimeCoin CUDA miner! on: July 17, 2013, 01:39:21 AM

If you provide a great explanation of all of the following (and are the first to do so), I will give you one BTC:
-What purpose the sieve serves
-What relation the block hash has to the potential block-solving primes
-Process of obtaining all mining data from primecoind
-process of submitting prime chain to mining data

1) I think you got the purpose of the sieve.

2) None.

3) primecoind getblocktemplate

4) primecoind submitblock

Looks like you know what's up, so I'm gonna grill you for some more information, and if you can provide it you'll be the new owner of a shiny Bitcoin. Smiley

2.) I thought that the block hash was used as some factor of either start of chain +1 or start of chain -1 (or in a bi-twin chain, the average between the two first values?). Was this something else that served the purpose of not allowing the same prime chain to be used multiple times?

3.) "getblocktemplate" provides this, which parts are relevant, and how are they relevant, to mining?
{
    "version" : 2,
    "previousblockhash" : "7072f0272b3e38536e072c94e340b7c7824a71989f6e9f3112ce30d6be5ae525",
    "transactions" : [
    ],
    "coinbaseaux" : {
        "flags" : "062f503253482f"
    },
    "coinbasevalue" : 1249000000,
    "target" : "0000000000000000000000000000000000000000000000007118620000000000",
    "mintime" : 1374023934,
    "mutable" : [
        "time",
        "transactions",
        "prevblock"
    ],
    "noncerange" : "00000000ffffffff",
    "sigoplimit" : 20000,
    "sizelimit" : 1000000,
    "curtime" : 1374024884,
    "bits" : "08f11862",
    "height" : 55422
}
1008  Alternate cryptocurrencies / Altcoin Discussion / Re: [New Bounty] 6BTC for PrimeCoin CUDA miner! on: July 17, 2013, 01:33:10 AM
I'm confused, why wouldn't you write it as OpenCL? This provides at least some level of portability.

EDIT: That being said, it's a generous offer!

Mainly because from what I understand CUDA is more fit to this purpose, as well as it serving as a nice way to get the NVidia players into cryptos as well. Cheesy
1009  Alternate cryptocurrencies / Altcoin Discussion / Re: [New Bounty] 6BTC for PrimeCoin CUDA miner! on: July 17, 2013, 01:32:19 AM
-What purpose the sieve serves

In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.

The multiples of a given prime are generated starting from that prime, as a sequence of numbers with the same difference, equal to that prime, between consecutive numbers. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so)

awesome bounty btw i hope someone gets it

Yeah, during my short digging I did find the sieve of Eratosthenes, though your explanation was better than what I found. My main question with the sieve is, since we are finding very huge primes, what purpose this 'table of primes' serves the finding of large prime chains?
the sieve works by getting increasing more likely 'primes' by altering a value to be more likely prime, and the table is used as seeds for that 'winnowing' process.
You want to have a big table because the more you have, the more likely one of them will work for a given block.

This is really interesting! Mathematically, how does the sieve table work? Is one of the primes multiplied by a certain value and then changed in order to obtain a true prime? Also, what address do you want your 0.25 BTC to? Smiley
1010  Alternate cryptocurrencies / Altcoin Discussion / Re: [Bounty] Primecoin Standalone CPU Miner! Current: 2.5BTC on: July 17, 2013, 01:30:20 AM
Forgot about this thread, xD!

Anyhow, ypool, from what I understand, does have a stand-alone miner. However, since their code won't work as-is on linux, and many people are doubting their authenticity, I am holding the coinage for now. However, this is a community bounty, so if the majority of people want me to send the coins to ypool, I'm cool with that. Smiley
1011  Alternate cryptocurrencies / Altcoin Discussion / Re: [New Bounty] 6BTC for PrimeCoin CUDA miner! on: July 17, 2013, 01:20:40 AM
Why not Opencl?

From what I understand, CUDA is more apt to this type of work. As well, I think variety is a cool thing, and getting both groups of major video card fanboys in on cryptocoins couldn't hurt. Tongue

While I would love OCL (I have 10 7950s and 3 7970s), I think NVidia would be a nice change.
1012  Alternate cryptocurrencies / Altcoin Discussion / Re: [XPM] Mining Explanation Bounty: 1BTC :) on: July 17, 2013, 12:33:36 AM

Unfortunately since you only answered one, you are not eligible. However, if you answer the 2nd question I put in the other thread (a further question on the sieve), I'll take that question out of the bounty, and give you 0.25 BTC for your efforts. Cheers! Smiley
1013  Alternate cryptocurrencies / Altcoin Discussion / Re: [New Bounty] 6BTC for PrimeCoin CUDA miner! on: July 17, 2013, 12:27:21 AM
-What purpose the sieve serves

In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.

The multiples of a given prime are generated starting from that prime, as a sequence of numbers with the same difference, equal to that prime, between consecutive numbers. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so)

awesome bounty btw i hope someone gets it

Yeah, during my short digging I did find the sieve of Eratosthenes, though your explanation was better than what I found. My main question with the sieve is, since we are finding very huge primes, what purpose this 'table of primes' serves the finding of large prime chains?
1014  Alternate cryptocurrencies / Altcoin Discussion / [XPM] Mining Explanation Bounty: 1BTC :) on: July 17, 2013, 12:23:41 AM
If you provide a great explanation of all of the following (and are the first to do so), I will give you one BTC:
-What purpose the sieve serves
-What relation the block hash has to the potential block-solving primes
-Process of obtaining all mining data from primecoind
-process of submitting prime chain to mining data
1015  Alternate cryptocurrencies / Altcoin Discussion / [Removed Bounty] PrimeCoin CUDA miner on: July 17, 2013, 12:21:06 AM
As a result of extensive development of OpenCL miners for Primecoin with impressive performance, this bounty is now removed. GPU mining of Primecoin is going to soon be saturated. If you were currently developing something for this bounty (unlikely as all development seems to be Opencl and it has been months) PM me.


Note: mtrlt is making a OpenCL-miner. That doesn't qualify for this bounty.

New rule: CUDA miner has to somewhat-significantly outperform mtrlt miner on equivalently-priced hardware (aka CUDA miner that gets 800 coins/day on a $400 NVidia GPU on testnet will get this bounty if mtrlt's miner will get 500 coins/day on a $400 AMD GPU).

The first person who makes a CUDA miner that outperforms a CPU of equivalent value by more than 2x ($330 NVidia GPU, like a 670, should give more than 2x the blocks of an i7-3770 on testnet over the same period of time) will get 6 Bitcoins! If anyone else wants to add to the bounty, just post a message with your 'pledge'.  

Requirements: compiled windows binary, source code provided.
Optional: compiled linux binaries.

Current bounty chip-ins:
Vorksholk: 6BTC

Alternately, if someone wants to dig through the primecoin code and give me a nice concise summary of exactly how the mining process works (purpose that the sieve serves, relation of block hash to potential primes, process of getting data from primecoind, process of submitting data to primecoind) I will either write my own, or attempt to hire someone with the USD equivalent.

If you provide a great explanation of all of the following (and are the first to do so), I will give you one BTC:
-What purpose the sieve serves
-What relation the block hash has to the potential block-solving primes
-Process of obtaining all mining data from primecoind
-process of submitting prime chain to mining data

Also, at heart, I love NVidia, I'm a NVidia fanboy. Smiley
1016  Alternate cryptocurrencies / Altcoin Discussion / Re: [XPM] GetWork API? on: July 16, 2013, 10:56:49 PM
Bump again.
1017  Alternate cryptocurrencies / Altcoin Discussion / Re: [XPM] GetWork API? on: July 16, 2013, 02:48:12 PM
Bump.
1018  Alternate cryptocurrencies / Altcoin Discussion / [XPM] GetWork API? on: July 16, 2013, 01:22:50 AM
Hey! I think it was 2 days ago that Sunny King mentioned that he would implement a form of API for getwork for external miners.

1.) How's this going?

2.) What do you plan to include in the API output? That way, we can start building external miners.

From what I understand, the main things that an external miner needs are the block hash and the difficulty. Am I right in saying that the block hash, when converted to decimal, needs to be a factor of the average of the first number in the prime chain? Then the mining program could just return the first prime, and the client would derive the chain from there?
1019  Alternate cryptocurrencies / Announcements (Altcoins) / Re: [XPM] [ANN] Primecoin High Performance on: July 15, 2013, 02:13:56 PM
I'm a bit confused.

The primes we are finding are huge, what purpose does the up-to-2,000,000 or so prime sieve serve?
1020  Alternate cryptocurrencies / Altcoin Discussion / Re: Primecoin GPU miner implementation brainstorming thread on: July 15, 2013, 01:48:54 PM
I haven't really delved into the code much yet, but basically the prime chain has to have it's smallest element's average (1 less than, or one more than) a multiple of the block hash? Right?
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 [51] 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 »
Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!