Введение
Алгоритм последовательного извлечения n-го корня — это алгоритм для вычисления n-го корня положительного действительного числа, который итеративно выполняется путем добавления по n цифр подкоренного числа, начиная со старших разрядов, и на каждой итерации выдает одну цифру корня, аналогично алгоритму деления в столбик.
Обозначение
Пусть *b* будет основанием системы счисления, которую вы используете, а *n* — степенью извлекаемого корня. Пусть *r* — подкоренное выражение, обработанное на данный момент, *q* — корень, извлеченный на данный момент, а *rem* — остаток. Пусть *d* — следующие *k* цифр подкоренного выражения, а *digit* — следующая цифра корня. Пусть *r'* — новое значение *r* для следующей итерации, *q'* — новое значение *q* для следующей итерации, а *rem'* — новое значение *rem* для следующей итерации. Все эти значения — целые числа.
Инварианты
При каждой итерации инвариант будет выполняться. Инвариант будет выполняться. Таким образом, является наибольшим целым числом, не превосходящим корень степени n из , а является остатком.
Инициализация
Начальные значения , и должны быть равны 0. Значение для первой итерации должно быть наиболее значимым выровненным блоком цифр подкоренного числа. Выровненный блок цифр означает блок цифр, расположенных так, чтобы десятичная точка находилась между блоками. Например, в числе 123.4 наиболее значимый выровненный блок из двух цифр — 01, следующий по значимости — 23, а третий по значимости — 40.
Выступление
На каждой итерации самая трудоемкая задача – выбрать. Мы знаем, что существует возможных значений, поэтому мы можем найти их с помощью сравнений. Каждое сравнение потребует вычисления. В k-й итерации, имеет цифр, и полином может быть вычислен с помощью умножений до цифр и сложений до цифр, как только мы знаем степени и вплоть до для и для. Имеет ограниченный диапазон, поэтому мы можем получить степени в постоянное время. Мы можем получить степени с помощью умножений до цифр. Предполагая, что умножение цифр занимает время , а сложение занимает время , мы тратим время на каждое сравнение, или время, чтобы выбрать. Остальная часть алгоритма – сложение и вычитание, что занимает время, поэтому каждая итерация занимает время. Для всех цифр нам требуется время. Единственное необходимое внутреннее хранилище – это , что составляет цифр на k-й итерации. Тот факт, что этот алгоритм не имеет ограниченного использования памяти, накладывает верхнюю границу на количество цифр, которые могут быть вычислены вручную, в отличие от более элементарных алгоритмов арифметики. К сожалению, любая машина с ограниченной памятью с периодическими входными данными может производить только периодические выходные данные, поэтому не существует алгоритмов, которые могут вычислять иррациональные числа из рациональных, и, следовательно, не существует алгоритмов извлечения корня с ограниченной памятью. Обратите внимание, что увеличение основания увеличивает время, необходимое для выбора, в разы, но уменьшает количество цифр, необходимое для достижения заданной точности, на тот же фактор, и поскольку алгоритм имеет кубическую сложность по количеству цифр, увеличение основания дает общее ускорение. Когда основание больше, чем подкоренное число, алгоритм вырождается в двоичный поиск, поэтому следует, что этот алгоритм не полезен для вычисления корней на компьютере, поскольку он всегда уступает гораздо более простому двоичному поиску и имеет ту же сложность по памяти.
for each comparison, or time to pick The remainder of the algorithm is addition and subtraction that takes time , so each iteration takes For all digits, we need time
The only internal storage needed is , which is digits on the kth iteration. That this algorithm does not have bounded memory usage puts an upper bound on the number of digits which can be computed mentally, unlike the more elementary algorithms of arithmetic. Unfortunately, any bounded memory state machine with periodic inputs can only produce periodic outputs, so there are no such algorithms which can compute irrational numbers from rational ones, and thus no bounded memory root extraction algorithms. Note that increasing the base increases the time needed to pick by a factor of , but decreases the number of digits needed to achieve a given precision by the same factor, and since the algorithm is cubic time in the number of digits, increasing the base gives an overall speedup of When the base is larger than the radicand, the algorithm degenerates to binary search, so it follows that this algorithm is not useful for computing roots with a computer, as it is always outperformed by much simpler binary search, and has the same memory complexity.