Генерация пифагорейских четверок с одним фиксированным значением?

Question

Если бы я хотел генерировать уникальные (без учета негативов) пифагорейские четверки (в форме a ^ 2 + b ^ 2 + c ^ 2 = d ^ 2) с фиксированным d (в данном случае 2 ^ 15 - 1), есть ли лучший, чем O (n ^ 3) способ сделать это?

Прямо сейчас я довольно грубо заставляю это:

int r = (1 << 15) - 1;

for(int i = 0; i < r; i++)
 for(int j = i; j < r; j++)
  for(int k = j; k < r; k++)
   if( i * i + j * j + k * k == r * r )
    //add to list

Что такое O (n ^ 3), есть ли более быстрый способ? Я нашел несколько фрагментов, которые могли бы генерировать четверки, но все они сказали, что могут пропустить некоторые. Я видел уравнения для них, и я подумал, что может быть какая-то линейная система уравнений?

Answer 1

Это все равно будет O (n ^ 3), но вы могли бы немного ускорить его, не ища слишком большие числа:

...
for(int i = 0; i < r; i++)
  for(int j = i; j < sqrt(r^2 - i^2); j++)
     for(int k = j; k < sqrt(r^2 - i^2 - j^2); k++)
...

Answer 2

Вторая параметризация на ранее упомянутой странице Википедии говорит

Все пифагорейские четверки ... могут быть сгенерированы из двух натуральных чисел a, нечетного и b, четного... Пусть p - любой фактор из a ^ 2 + b ^ 2, такой что p ^ 2

, который представляется простым методом O (n ^ 2) для генерации всех пифагорейских квадов, но без очевидного способа извлечь выгоду из фиксированного d.

Вот еще один метод O (n ^ 2), который не требует математического понимания, только некоторые базовые возможности структур данных:

   for(k=0; k<r; ++k)
     insert r^2 - k^2 into BST [*]

   for(i=0; i<r; ++i)
     for(j=i; j<r; ++j)
       if i^2 + j^2 is in BST report i,j,k [**]

[*] Может использоваться любая структура данных высокоскоростного словаря;деревья бинарного поиска не обязательны.Тем не менее, AA-деревья быстрые и легко кодируемые.

[**] Вычисляет k из k ^ 2 = r ^ 2 - i ^ 2 - j ^ 2.

Answer 3

Попробуйте с параметризацией, Страница Википедии упоминает 2 из них.