News for hackers. Stuff that matters.
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by jhncls on Tuesday March 26, 2019 @11:43AM (#19492843)
The Numberphile video, mentioned elsewhere, explains how a search of O(n^3) is reduced to a linear search via some clever tricks. From there, the linear search is quite brute force. Several numbers are searched at the same time, indicating that no solution for 42 could be found under 10^16. Some supercomputer infrastructure seems to be necessary ("don't try this at home").
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by SilasX on Tuesday March 26, 2019 @12:28PM (#19493296)
Wow, linear? I had recognized this as a variant of the interview problem where you try to find a triple that sums to zero in a list, but that only shrinks it to quadratic.

https://www.geeksforgeeks.org/find-triplets-array-whose-sum-...

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by ConceptJunkie on Tuesday March 26, 2019 @12:29PM (#19493322)
The paper ends with "The total computation used approximately 23 core-years over one month of real time.", so yes, I think running this on your 8-core desktop is not going to cut it.
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by dragontamer on Tuesday March 26, 2019 @02:44PM (#19494817)
But what about a $400 GPU with 4096 shaders?

I haven't looked at the algorithm, but a linear search probably can be GPGPU computed in parallel. A Vega64 is around $400 and runs 16384 threads on 4096 physical shaders at roughly 1.2GHz.

The main issue is if whatever data-structures used for this search will actually fit inside the microscopic amount of memory that is available to each shader.

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by Jweb_Guru on Tuesday March 26, 2019 @03:44PM (#19495348)
You should probably assume that people using supercomputers have thought about "just using a GPU."
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by xiphias2 on Tuesday March 26, 2019 @05:12PM (#19496073)
Don't assume anything.

They are not using GPUs and from the paper it looks like they haven't thought about it. I think a GPU cluster would be a speedup, but big number multiplication is relatively slow on GPUs, so maybe not as big speedup as with other algorithms.

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by Jweb_Guru on Tuesday March 26, 2019 @05:17PM (#19496110)
A GPU cluster, sure. But the discussion was about running the algorithm on a single GPU on your desktop.
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by xiphias2 on Tuesday March 26, 2019 @07:41PM (#19496948)
Sure, you're right I was comparing cost of the 2 systems, with 1 GPU it's an interesting question, but as the author had CPU cluster available, it was the logical choice for him.
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by dragontamer on Tuesday March 26, 2019 @06:10PM (#19496479)
Why? GPU Programmers cost a lot more than a month-worth of supercomputer time.

Its probably cheaper and easier to just port your code to Amazon cloud or Google Cloud for a month, rather than to port your code to a GPU.

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by xiphias2 on Tuesday March 26, 2019 @07:39PM (#19496941)
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.
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by dragontamer on Tuesday March 26, 2019 @07:51PM (#19496994)
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.

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by qlk1123 on Tuesday March 26, 2019 @10:28PM (#19497730)
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 ;)

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by dragontamer on Wednesday March 27, 2019 @04:46PM (#19505845)
> 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.

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by qlk1123 on Wednesday March 27, 2019 @09:43PM (#19508332)
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.
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by dragontamer on Wednesday March 27, 2019 @10:52PM (#19508764)
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!

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by qlk1123 on Thursday March 28, 2019 @04:56AM (#19510449)
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.

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by dragontamer on Thursday March 28, 2019 @09:06AM (#19511768)
> 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."

Its not a general big-integer implementation which can be arbitrarily sized. Since you know all results fit inside of 192 bits, and that all operands are less than 64-bits, you can easily code for this special case.

192-bit x 64-bit is way easier to debug and test than 192-bit x 192-bit. Its probably the bulk of your work, but I don't foresee any major complication here. Its just grade-school arithmetic.

    struct cube{
        long long val[3];
    }

    cube multiply(cube x, long long y){
        cube toReturn;
        toReturn.val[0] = x.val[0] * y;
        toReturn.val[1] = x.val[1] * y + __umul64hi(x.val[0] * y);
        toReturn.val[2] = x.val[2] * y + __umul64hi(x.val[1] * y);
        return toReturn;
    }
This is grade-school arithmetic level. This isn't very difficult at all. The only thing you needed to know is that CUDA has an intrinsic to take the top 64-bits of a 128-bit multiplication.

Without any if-statements, the GPU can calculate the above across different threads without any divergence. You can likely optimize this further with MAD instructions, but the above would be a good "first step" towards this problem.

As I said earlier: this wouldn't be an "easy" port, but it would be possible, and it would likely be very efficient. I'm not going to think through all the edge cases, but the bulk of the algorithm seems very easy to do efficiently on the GPU architecture to me.

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by dragontamer on Thursday March 28, 2019 @11:27AM (#19513128)
And of course, code I type up in less than 5 minutes has a variety of bugs (compiler errors AND logic bugs). Despite the mistakes, I stand by my reasoning that the above code is relatively simple.

And again, I'm not saying GPU-porting is easy. I'm just saying its possible, and likely is the most cost-effective use of hardware. Whether or not it is worth the programmer time is a separate question of course. But I don't see anything that's stopping a GPU from efficiently computing THIS problem, especially if its restricted to 192-bit as the biggest number in the whole algorithm (worst-case 64-bit cubed).

I've tried to port other algorithms to the GPU and it didn't work. But THIS sum-of-three cubes problem looks like an easier job than most algorithms to me.

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by qlk1123 on Thursday March 28, 2019 @06:17PM (#19517190)
> But I don't see anything that's stopping a GPU from efficiently computing THIS problem, especially if its restricted to 192-bit as the biggest number in the whole algorithm (worst-case 64-bit cubed).

Fair enough. Also thanks for the demonstration, it updates my understanding.

But still at some moment in the future, we may need a general big-number algorithms for calculation due to the inevitable expansion of search space. There is no guarantee that unsolved k's, says 100 < k < 200, can be found in min(|x|,|y|,|z|) <= 192 bit.

> But THIS sum-of-three cubes problem looks like an easier job than most algorithms to me.

Good luck and I'm looking forwards to any updates.

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by xiphias2 on Tuesday March 26, 2019 @08:42PM (#19497270)
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 :)
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by ars on Tuesday March 26, 2019 @03:19PM (#19495133)
> I haven't looked at the algorithm

You can see it here: https://youtu.be/ASoz_NuIvP0?t=393

Rewind a couple of minutes if you want the explanation.

Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by dragontamer on Tuesday March 26, 2019 @09:54PM (#19497575)
That's actually really simple and clever. That definitely makes the search space much smaller and brute-force is now possible.
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by Rychard on Tuesday March 26, 2019 @02:29PM (#19494674)

    1 core year = 12 core months
    23 core years = 276 core months
    
So, 276 cores running for one month? Is this right?
Re:Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 by waynecochran on Tuesday March 26, 2019 @03:15PM (#19495095)
Yes, but I am left hanging on the specific details. He factors to yield

    (x + y)(x^2 - xy + x^2) = 42 - z^3
He brute force searches over values d and finds a value z such that d divides 42 - z^3 (evidently these are rare and easy to find) and then solves the following two equations for x and y (which is easy):

    d = x + y
    x^2 - xy + x^2 = (42 - z^3)/d
The part I don't get is how to find the z's given d. Does anyone know where to find these details?