News for hackers. Stuff that matters.
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.