Fast solutions for $x^2+y^2+z^2=d^2$ for large $d>1000$

Question

I need a fast algorithm to calculate solutions to $x^2+y^2+z^2=d^2$ for $d>1000$.

I tried Pythagorean quadruple (Alternate parametrization approach) for $d<400$ and it isn't that fast.

UPDATE

def EfficientDivisors(n):
    factors = []
    i = 2
    while (i < sqrt(n)):
        if (n%i == 0):
            factors.append(i)
            if (i != (n/i)):
                factors.append(n//i)
        i += 1
    return factors
#alternative parameterization: a and b are both even
def fncTest4(d):
    c = 0
    nSolutionNumber = 0
    for a in range(2, d, 2):
        l = a//2
        for b in range(2, d, 2):
            m = b//2
            nTemp1 = l ** 2 + m ** 2
            factors = EfficientDivisors(nTemp1)
            for n in factors:
                if n ** 2 < nTemp1:
                    nTemp2 = (nTemp1 + n ** 2) // n
                    if d == nTemp2:
                        c = d - 2 * n
                        nSolutionNumber += 1
                        print(nSolutionNumber, ":", a, b, c, d)
                        break

fncTest4(2000) # 4 minutes

Answer 1

Here’s the outline.

WLOG, $a>=b>=c$.

Then $a$ has a maximum value of $d-1$ and a minimum value of $\sqrt{\frac{d^2}{3}}$, rounded down.

For each $a$, calculate $u=d^2-a^2$

Then maximum $b$ is $\sqrt{u}$ rounded up, but also $<=a$ and minimum $b$ is $\sqrt{\frac{u}{2}}$, rounded down.

For each $b$, calculate $v=u-b^2$

When $v$ is a square, $c=\sqrt{v}$ and we have a solution.

Good luck with your project. Please let me know if you need any more details.

I’ll add the VB6 code, if I ever find out how to do it.

Some test results, $(c,b,a,d)$

$$(20,28,29,45)$$ $$(15,30,30,45)$$ $$(6,30,33,45)$$ $$(20,20,35,45)$$ $$(4,28,35,45)$$ $$(16,20,37,45)$$ $$(13,16,40,45)$$ $$(8,19,40,45)$$ $$(5,20,40,45)$$ $$(6,15,42,45)$$ $$(5,8,44,45)$$ $$(22,31,34,51)$$ $$(17,34,34,51)$$ $$(24,27,36,51)$$ $$(3,36,36,51)$$ $$(14,31,38,51)$$ $$(1,34,38,51)$$ $$(14,17,46,51)$$ $$(1,22,46,51)$$ $$(14,14,47,51)$$ $$(10,10,49,51)$$ $$(2,14,49,51)$$ $$(1,10,50,51)$$ $$(480,600,640,1000)$$ $$(192,640,744,1000)$$ $$(424,480,768,1000)$$ $$(280,576,768,1000)$$ $$(224,600,768,1000)$$ $$(24,640,768,1000)$$ $$(360,480,800,1000)$$ $$(168,576,800,1000)$$ $$(192,480,856,1000)$$ $$(352,360,864,1000)$$ $$(152,480,864,1000)$$ $$(96,480,872,1000)$$ $$(96,360,928,1000)$$ $$(168,224,960,1000)$$ $$(960,1200,1280,2000)$$ $$(384,1280,1488,2000)$$ $$(848,960,1536,2000)$$ $$(560,1152,1536,2000)$$ $$(448,1200,1536,2000)$$ $$(48,1280,1536,2000)$$ $$(720,960,1600,2000)$$ $$(336,1152,1600,2000)$$ $$(384,960,1712,2000)$$ $$(704,720,1728,2000)$$ $$(304,960,1728,2000)$$ $$(192,960,1744,2000)$$ $$(192,720,1856,2000)$$ $$(336,448,1920,2000)$$