Вычислить квадратный корень, используя целочисленную арифметику

Question

Я хочу вычислить квадратный корень некоторого целого числа без использования арифметики с плавающей запятой. Однако подвох заключается в том, что я не хочу отказываться от точности вывода. То есть я не хочу, чтобы в результате округлялось целое число, я хотел бы также получить значение десятичной точки, по крайней мере, до двух значащих цифр. В качестве примера:

sqrt(9) = 3
sqrt(10) = 3.16
sqrt(999999) = 999.99

Я думал об этом, но я не особо придумывал решения, и поиск не очень помог, так как большинство подобных вопросов - только это, только похоже.

Вывод допустим в любой форме, которая не является числом с плавающей запятой и точно представляет данные. Предпочтительно, чтобы у меня было два целых числа, одно для части перед десятичной дробью и одно для части после десятичной.

Я в порядке только с псевдокодом / объясненным алгоритмом, если кодирование C будет лучшим. Спасибо

Answer 1

Вы можете вычислить целочисленный числитель и целочисленный знаменатель так, чтобы при делении чисел с плавающей точкой на знаменатель получался квадратный корень из входного числа.

Обратите внимание, однако, что метод квадратного корня не существует, так что результат на 100% точен для каждого натурального числа, так как квадратный корень такого числа может быть иррациональным числом.

---

Вот алгоритм:

Function (input number, input num_of_iterations, output root):
    Set root.numerator   = number
    Set root.denominator = 1
    Run num_of_iterations:
        Set root = root-(root^2-number)/(root*2)

Эта реализация C++ может оказаться полезной (она также включает преобразование числителя, разделенного знаменателем, в числовую строку с предопределенной точностью с плавающей запятой).

---

Обратите внимание, что никаких операций с плавающей запятой не требуется (как показано по данной ссылке).