Эффективно вычисляя все пифагорейские тройки, зная гипотенузу
Учитывая гипотенузы (c в типичном уравнении a*a + b*b = c*c), что является эффективным способом для вычисления всех возможных целочисленных значений a а также bтакой, что a < b?
Примечание: я видел c быть больше чем 1e12таким образом c*c больше, чем long.MaxValueиз того, что я могу сказать, c*c вписывается в decimal, хоть.
5 ответов
Существует математическое решение, которое быстро находит a и b даже для больших значений c. К сожалению, не все так просто. Я пытаюсь дать краткое объяснение алгоритма. Надеюсь, это не слишком запутанно.
Так как дано c, и вы ищете a и b, вы в основном хотите решить диофантовы уравнения вида
n=x^2+y^2,
где п дается. Не сильно помогает то, что n = c * c - квадрат, и поэтому я описываю решение для любого n. Если бы n было простым числом, то вы могли бы использовать теорему Ферма, чтобы решить, разрешимо ли ваше уравнение, и использовать, как указал Морон, алгоритм Эрмита-Серре, чтобы найти решения, если они есть.
Чтобы решить случай, когда n не является простым, хорошей идеей будет использование гауссовых целых чисел. (Гауссовы целые числа - это просто комплексные числа с целыми коэффициентами). В частности, следует отметить, что норма х + у
N(x+yi) = x^2+y^2.
Следовательно, нужно найти гауссовы целые числа x+yi, норма которых равна n. Поскольку норма является мультипликативной, достаточно решить это уравнение для факторов n, а затем умножить гауссовы целые числа индивидуальных уравнений. Позвольте мне привести пример. Мы хотим решить
65 = x^2 + y^2.
Это эквивалентно нахождению x,y такого, что
N(x+yi) = 65
над гауссовыми целыми числами. Фактор 65 = 5 * 13, затем мы используем Ферма, чтобы отметить, что и 5, и 13 могут быть представлены как сумма двух квадратов. Наконец, мы находим либо с помощью грубой силы с помощью алгоритма Эрмита-Серре
N(2+i) = N(1+2i) = ... = 5
N(2+3i) = N(3+2i) = ... = 13
Обратите внимание, я пропустил целые числа Гаусса 2-i, -2+i и т. Д. С отрицательными коэффициентами. Это, конечно, тоже решения.
Следовательно, теперь мы можем умножить эти решения вместе, чтобы получить
65 = 5*13 = N(2+i) * N(2+3i) = N((2+i) * (2+3i)) = N(1 + 8i)
а также
65 = 5 * 13 = N(2+i) * N(3+2i) = N((2+i) * (3+2i)) = N(4 + 7i).
Следовательно, каждый получает два решения
1*1 + 8*8 = 65
4*4 + 7*7 = 65
Другие комбинации, например, с отрицательными коэффициентами должны быть проверены тоже. Они не дают новых решений, кроме перестановок и измененных знаков.
Чтобы вычислить все решения, можно также добавить, что нет необходимости когда-либо вычислять c * c. Поиск факторов с - это все, что необходимо. Кроме того, так как a и b оба меньше, чем c, не произойдет, что произведения гауссовых целых чисел не будут представлены с 64-битными целочисленными коэффициентами. Следовательно, если вы будете осторожны, 64-битное целое число будет достаточно точным, чтобы решить проблему. Конечно, всегда проще использовать такой язык, как Python, который не имеет таких проблем переполнения.
Все пифагорейские тройки (a,b,c) удовлетворяют свойству, что для некоторых целых чисел k, m и n
a=k(m^2-n^2), b=2kmn, c=k(m^2 + n^2)
Итак, начните с факторинга c. Затем для каждого отдельного множителя k из c (т.е. для каждого отдельного подмножества множителей, умноженных вместе), найдите все m и n, которые удовлетворяют c/k = (m^2 + n^2). Выполнение последнего займет значительно меньше времени, чем метод грубой силы, предложенный другими (вам нужно только найти квадраты, которые суммируют с / к, а не с ^ 2), но идентифицируют все тройки (а, б, в), Вам также не нужно использовать bignums, потому что все промежуточные результаты вписываются в long.
Я также предлагаю вам посетить веб-страницу http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Pythag/pythag.html под заголовком "Более общий пифагорейский тройной калькулятор", который содержит встроенный калькулятор, написанный на javascript, который делает именно то, что вы хотите.
Начните со значения 1 для a и значения c для b.
сравнить c*c - b*b в a*a, Если они равны, у вас есть совпадение.
Изменяйте a и b по отношению друг к другу в зависимости от того, какая сторона больше, пока они не станут одинаковыми.
Можно и пойти за библиотекой BigNum.
Что касается эффективного способа нахождения а и б:
Для каждого значения b (начиная с c-1 и опускаясь до b * b
Учитывая AC:
Поскольку b > a, если a минимально (a = 1), b = sqrt(c*c - 1).
Поэтому b ДОЛЖЕН быть между этим значением и c -1.
Кроме того, поскольку b должно быть целым числом, вам нужно найти первое значение, для которого это целое число.
Now, a property of squares:
The squares are: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ...
The differences: -, 3, 5, 07, 09, 11, 13, 15, 17, 019, 021, ...
That means a square can be written as a summation of ODD numbers:
1 + 3 + 5 + 7 + n+...
where n = number the summation is a square of.
Таким образом, есть ровно c квадратных чисел, меньших чем c*c, и вы можете идентифицировать их с помощью простого вычитания
Возвращаясь к началу, беря b = sqrt (cc - 1), округляя вниз и беря b b, получаем квадрат b, который должен быть выше, и aa = 1. Найдите c c - (aa + b b). Это должно дать вам число, которое должно быть добавлено для достижения c*c.
Так как вы можете добавить 3 + 5 + 7 + ... к, и b+2 + b+4 + b+6 + ... для б, вы просто должны найти правильный термин на основе суммы, а не сам квадрат:)