Algorithm to find all possible solutions for x1² + x2² + ... + xn² = 1

Question

Is there any algorithm to find all possible solutions for this equation:

x1² + x2² + ... + xn² = 1

Where xi > 0 and n >= 2

To limit solutions we can fix decimal point of x to 1. For instance:

if n = 2, find all tuples (x1, x2) that satisfies x1² + x2² = 1 The return of this function would be something like (fixing decimal points to 1):

[
    [0.1, 1],
    [0.2, 1],
    [0.3, 0.9],
    [0.4, 0.9],
    [0.5, 0.9],
    [0.6, 0.8],
    [0.7, 0.7],
    [0.8, 0.6],
    [0.9, 0.4],
    [1, 0.1],
    [1, 0.2],
    ...
    [0.4, 0.9]
]

For n=2 it's easy, but what I need is to generalize for n >= 2.

This is a vastly difficult problem afaik. Is it enough to find solutions only in some domain? could define a grid over the domain and iterate Newton's method from each gridpoint, then glob degenerate solutions at the end — kevinkayaks, Jul 18 '19 at 18:10
What about *brute force*, testing each `xi` value in range [0.0, 0.1, 0.2,.... 0.9, 1.0] in combination with other `xj` tuples? — Ripi2, Jul 18 '19 at 18:13
If your question is about the involved math and perhaps algorithms for approximation, math.stackexchange.com is a better place to ask. Putting that into program code is another step then. — Ulrich Eckhardt, Jul 18 '19 at 18:18
@MBo, the correct result is [0.4, 0.916515138991168], but we are fixing decimal point to 1, so rounding we get [0.4, 0.9]. — Pablo Abdelhay, Jul 18 '19 at 18:27
@Ripi2 I think is a solution, but I would like some example on a generic algorithm for that. — Pablo Abdelhay, Jul 18 '19 at 18:27
you have a specify a solution domain for the brute force approach — kevinkayaks, Jul 18 '19 at 18:32
Have a look at the section spherical coordinates of https://en.m.wikipedia.org/wiki/N-sphere — kvantour, Jul 18 '19 at 18:32
If you limit to steps of `0.1`, then it becomes really easy. Just use a `root finding` algorithm to find the roots of `x0**2 + x1**2 - 1`, where `x0` takes values of 0.1, then 0.2, then 0.3, ...., then 1.0, and take note of the output of `x1`. Then, you'll have all combinations of `(x0, x1)` in that domain — rafaelc, Jul 18 '19 at 18:46

OmG · Answer 1 · 2019-07-18T19:24:45.980

First, the equation that you've provided is the general description for a sphere in R^n with radius 1. Hence, the number of all possible points is infinite and uncountable!

If you want all points with 1 decimal precision, you can generalize it easily. Suppose you want an algorithm for n = 3. Fix x_3 to a value between 0 to 1 (0.1, 0.2, ..., 0.9). Then it means you set a plane that intersects a sphere in R^3. Now, you want to find x1 and x2 such that you have a circle with a radius of 1-x^3 in R^2. As you said, you know how to solve it for 2D.

Now you know how to solve the problem for n = 3. Hence, you can solve this recursively and generalize it for n > 3.

I've made this recursive algorithm with brute force. The problem is that it has very high complexity, and became impraticable for n > 8. Any other suggestion? — Pablo Abdelhay, Jul 22 '19 at 19:54

kvantour · Answer 2 · 2019-07-19T16:15:42.803

As indicated by @OmG, your equation resembles the equation of an n-Sphere. Trying to find all possible solutions, is therefore hard as there are an infinite amount of them. A parametrised version of all solutions can be found using a simple parametric equation:

2D: x1=cos(t1)                          t1 in [0,2pi[
    x2=sin(t1)
3D: x1=cos(t1)                          t1 in [0,pi]
    x2=sin(t1) cos(t2)                  t2 in [0,2pi[
    x3=sin(t1) sin(t2)
4D: x1=cos(t1)                          t1 in [0,pi]
    x2=sin(t1) cos(t2)                  t2 in [0,pi]
    x3=sin(t1) sin(t2) cos(t3)          t3 in [0,2pi[
    x4=sin(t1) sin(t2) sin(t3)
...

See https://en.m.wikipedia.org/wiki/N-sphere

If you are just interested in solutions upto a given decimal precision, then you should not work with floating points, but integers. Example, if you are interested in all solutions x₁,x₂,x₃ of the equation x₁² + x₂² + x₃² = 1. Where x_1,2,3 = &pm;a.b with a = 0 or 1 and b is 0,1,2,3,4,5,6,7,8 or 9. Then it is easier to work with integers to avoid numeric errors due to floating point approximation (See Is floating point math broken?). All you need to do is multiply your numbers with 10 (y₁ = 10 · x₁) and solve the equation y₁² + y₂² + y₃² = 100 from an integer point-of-view.

A simple and brute-force algorithm, in this case, would just be:

do i=0,10
  do j=0,i
    if (i*i + j*j > 100) jump out of j-loop
    do k=0,j
      if (i*i+j*j+k*k == 100) print i,j,k
    end do
  end do
end do

The above will print i,j,k. However, all possible permutations and sign-changes valid solutions as well. So the solution (8,6,0) also implies that (-8,6,0), (-6,0,8), (0,8,6), ... are solutions.

So in the end, we reduced the floating-point problem to an integer problem which is easier to check numerically.

Algorithm to find all possible solutions for x1² + x2² + ... + xn² = 1

2 Answers2