Это нерешенная проблема из моего прошлого присваивания рациональных чисел произвольной точности в C ++.
Для расчета я использовал это выражение из Википедии ( a - первоначальное предположение, r - его остаток):
Я закончил, просто догадавшись из экспериментирует с таким подходом:
- Используйте целочисленный квадрат root функцию в числителе / знаменателе, используйте это как предположение
- Итерируйте непрерывную дробь до двоичной длины числа знаменатель был как минимум целевой точностью
Это сработало достаточно хорошо, чтобы пройти официальные тесты, однако, по результатам моего тестирования, точность была слишком высокой (иногда почти вдвое) - т.е. код был неэффективным - и у меня не было доказательств он работал на любом вводе (и, следовательно, не доверял коду).
Упрощенный отрывок из кода (natural / rational хранить числа произвольной длины, задница Например, все операции возвращают дроби в их простейшем виде):
rational sqrt(rational input, int precision) {
rational guess(isqrt(input.numerator), isqrt(input.denominator)); // a
rational remainder = input - power(guess, 2); // r
rational result = guess;
rational expansion;
while (result.denominator.size() <= precision) {
expansion = remainder / (2 * guess + expansion);
result = guess + expansion;
// Handle rational results
if (power(root, 2) == input) {
break;
}
}
return result;
}
Можно ли сделать лучше? Если да, то как?