Всё крайне просто.
Потому что, начиная с рационального числа и проводя четыре арифметических действия, +−×: , мы будем оставаться в поле рациональных чисел. А корень в большинстве случаев иррациональный.
Мы можем получить лишь рациональное число, достаточно близкое к нашему корню.
И все «нормальные» методы вычисления корня работают так: если ещё немного повычислять, можно получить более точный корень. То есть итерационные.
Пример НЕитерационного метода предложили Ын, Уолш и Таролли, но более он известен по игре Quake III: придумать приближение логарифма, разделить на 2 и обратить это самое приближение. Но этот метод не масштабируем: если точности не хватает, придётся брать в руки какой-нибудь метод Ньютона и дотягивать точность. Ну или придумывать более точное приближение логарифма — исходное было всего лишь прочтением компьютерного дробного как целого числа. То есть придётся рубить его на мантиссу и порядок, порядок брать как есть, а мантиссу преобразовывать каким-то многочленом (если читать дробное как целое, то наш многочлен — банальная линейная функция, log₂(1+x)≈x).
А лучше порядок превратить в несмещённый, поделить надвое, вернуть опять к смещённому, и остаётся только найти приближение — многочленом или таблицей — для x∈[1,4).
Другой НЕитерационный алгоритм — банальная таблица. Каким-то раком предвычислить таблицу, а то, что в таблицу не попадает, приблизить любым доступным методом, да хоть линейной интерполяцией или многочленами Эрмита.
Простой
