4 ms·

Generally yes, but actually porting this is probably a fun pet project that could be done in a few weeks for fun to find the secret number for 42 :). It's too b

Generally yes, but actually porting this is probably a fun pet project that could be done in a few weeks for fun to find the secret number for 42 :). It's too bad the paper doesn't have a GitHub link.

dragontamer 8y ago
Oh yeah, that's why I'm interested in that algorithm :-) Honestly, the more and more I look into this, it seems like GPUs are the ideal computational platform for this problem. We're talking about a simple equation, with numbers that fit inside the 64-bit integer space (less than 10^19). GPUs can calculate that somewhat easily (The compiler probably turns 64-bit multiplies into 4x32-bit multiplies + adds, but that's still low in memory usage...) I'm not sure if one GPU would be enough to compute everything. But we're talking about 512-cpu cores at 1-month of computing. A GPU probably can solve it within 6 months. I'm talking about replicating the work done on "33" by the way, not on 42. If 10^19 is sufficient for a search space, then 64-bit ints can be used. ------------ It won't be an easy port btw. The three variables are written as x^2 - 2xy + y^2 == (33 - z^3) / d, where d = (x+y). The Numberphile video said that "d" is brute-force searched, because there are very few values of "z" that would satisfy the above formula. So every shader probably can brute-force d on its own in a GPU. Overall, seems pretty efficient to run this on a GPU. Very little memory, everything probably fits in GPU-register space.
- xiphias2 8y ago
  X^2 doesn't fit in 64 bits, but after a little bit of search I found the __mul64hi PTX instruction that makes it easy :)
- qlk1123 8y ago
  What you are talking about is to exploit the mass parallelism of GPU, but I suspect that there are huge differences between each of the calculation/evaluation, which is not a good pattern for GPU threads. As GPU threads work together in bundles, or warp, the cost on sync'ing each thread may be high. But still, worth a try if you have one, and don't forget SHOW HN once you have luck ;)
  - dragontamer 8y ago
    > but I suspect that there are huge differences between each of the calculation/evaluation Its a (nearly) linear brute-force search. Every thread is going to run "guess d", and then calculate "(33 - z^3) / d = x^2 -2xy + y^2". All values must be integer, so (33 - z^3) / d must be an integer value. Which means the selected value "d" must be a factor of (33 - z^3). So "z" is going to be a small search space. I would expect that similar "d" values would have similar amounts of "z" values that satisfy this solution, so thread divergence doesn't seem to be a major issue. That's about as uniform as it gets. Its a guess-and-check search, very much akin to cryptocoin mining. It seems like the GPU is the best architecture to the algorithm.
    - qlk1123 8y ago
      What about the RHS of the equation? x^2-xy+y^2 are three big-number multiplications and two big-number adds, where digit number do matters.
      - dragontamer 8y ago
        Not as "big number" as you might think. The x, y, and z terms were: (8,866,128,975,287,528)³ + (–8,778,405,442,862,239)³ + (–2,736,111,468,807,040)³ = 33. The biggest number will fit inside of 53 bits, 54 if you include the sign bit. Which means all of the values fit inside of 64-bits (including the sign bit). The cubes will fit within 192-bits. If this truly were a "big number" problem, then brute-force wouldn't be a valid methodology!
        qlk1123 8y ago
        I got your point. It seems that we are just not on the same page. As the product of any cube can turn out to be 192-bit, it should be impossible to fit into a GPU instruction or even a single CUDA C statement. That's why I call it big-number calculation: manual carry/overflow handling, larger-than-register size operands, tedious indexing/bug prone if coding from scratch, ... but of course you can still argue that it is not "big." Or maybe now GPGPUs have big integer support? The last time I did actual GPU computing was CUDA 7 I guess, using cublas in daily basis so never ever been familiar with integer computation in GPU.

dragontamer 8y ago

Oh yeah, that's why I'm interested in that algorithm :-) Honestly, the more and more I look into this, it seems like GPUs are the ideal computational platform for this problem. We're talking about a simple equation, with numbers that fit inside the 64-bit integer space (less than 10^19). GPUs can calculate that somewhat easily (The compiler probably turns 64-bit multiplies into 4x32-bit multiplies + adds, but that's still low in memory usage...) I'm not sure if one GPU would be enough to compute everything. But we're talking about 512-cpu cores at 1-month of computing. A GPU probably can solve it within 6 months. I'm talking about replicating the work done on "33" by the way, not on 42. If 10^19 is sufficient for a search space, then 64-bit ints can be used. ------------ It won't be an easy port btw. The three variables are written as x^2 - 2xy + y^2 == (33 - z^3) / d, where d = (x+y). The Numberphile video said that "d" is brute-force searched, because there are very few values of "z" that would satisfy the above formula. So every shader probably can brute-force d on its own in a GPU. Overall, seems pretty efficient to run this on a GPU. Very little memory, everything probably fits in GPU-register space.

xiphias2 8y ago
X^2 doesn't fit in 64 bits, but after a little bit of search I found the __mul64hi PTX instruction that makes it easy :)
qlk1123 8y ago
What you are talking about is to exploit the mass parallelism of GPU, but I suspect that there are huge differences between each of the calculation/evaluation, which is not a good pattern for GPU threads. As GPU threads work together in bundles, or warp, the cost on sync'ing each thread may be high. But still, worth a try if you have one, and don't forget SHOW HN once you have luck ;)
- dragontamer 8y ago
  > but I suspect that there are huge differences between each of the calculation/evaluation Its a (nearly) linear brute-force search. Every thread is going to run "guess d", and then calculate "(33 - z^3) / d = x^2 -2xy + y^2". All values must be integer, so (33 - z^3) / d must be an integer value. Which means the selected value "d" must be a factor of (33 - z^3). So "z" is going to be a small search space. I would expect that similar "d" values would have similar amounts of "z" values that satisfy this solution, so thread divergence doesn't seem to be a major issue. That's about as uniform as it gets. Its a guess-and-check search, very much akin to cryptocoin mining. It seems like the GPU is the best architecture to the algorithm.
  - qlk1123 8y ago
    What about the RHS of the equation? x^2-xy+y^2 are three big-number multiplications and two big-number adds, where digit number do matters.
    - dragontamer 8y ago
      Not as "big number" as you might think. The x, y, and z terms were: (8,866,128,975,287,528)³ + (–8,778,405,442,862,239)³ + (–2,736,111,468,807,040)³ = 33. The biggest number will fit inside of 53 bits, 54 if you include the sign bit. Which means all of the values fit inside of 64-bits (including the sign bit). The cubes will fit within 192-bits. If this truly were a "big number" problem, then brute-force wouldn't be a valid methodology!
      - qlk1123 8y ago
        I got your point. It seems that we are just not on the same page. As the product of any cube can turn out to be 192-bit, it should be impossible to fit into a GPU instruction or even a single CUDA C statement. That's why I call it big-number calculation: manual carry/overflow handling, larger-than-register size operands, tedious indexing/bug prone if coding from scratch, ... but of course you can still argue that it is not "big." Or maybe now GPGPUs have big integer support? The last time I did actual GPU computing was CUDA 7 I guess, using cublas in daily basis so never ever been familiar with integer computation in GPU.