Алгоритм сдвига n- го корня

В этой статье не процитировать какие - либо источники . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален . Поиск источников:  «Алгоритм изменения корня n-й степени»  -  новости  · газеты  · книги  · ученый  · JSTOR ( май 2010 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

Алгоритм [ править ]

Обозначение [ править ]

Пусть B будет основанием используемой вами системы счисления, а n будет степенью извлекаемого корня. Пусть будет подкоренное выражение, обработанное на данный момент, будет корнем, извлеченным на данный момент, и быть остатком. Позвольте быть следующей цифрой подкоренного выражения и будет следующей цифрой корня. Пусть будет новым значением для следующей итерации, будет новым значением для следующей итерации и будет новым значением для следующей итерации. Все это целые числа .${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle r}$${\ displaystyle \ alpha}$${\ displaystyle n}$${\ displaystyle \ beta}$${\displaystyle x'}$${\displaystyle x}$${\displaystyle y'}$${\displaystyle y}$${\displaystyle r'}$${\displaystyle r}$

Инварианты [ править ]

На каждой итерации инвариант сохраняется. Инвариант останется в силе. Таким образом, является наибольшим целым числом, меньшим или равным корню n- й степени , и является остатком.${\displaystyle y^{n}+r=x}$${\displaystyle (y+1)^{n}>x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle r}$

Инициализация [ править ]

Начальные значения и должны быть 0. Значение для первой итерации должно быть наиболее значимым выровненным блоком цифр подкоренного выражения. Выровненный блок цифр означает блок цифр, выровненный так, чтобы десятичная точка попадала между блоками. Например, в 123.4 наиболее значимым выровненным блоком из двух цифр является 01, следующим по значимости является 23, а третьим по значимости - 40.${\displaystyle x,y}$${\displaystyle r}$${\displaystyle \alpha }$${\displaystyle n}$${\displaystyle n}$

Основной цикл [ править ]

На каждой итерации мы сдвигаем цифры подкоренного выражения, так что у нас есть и мы производим одну цифру корня, так что у нас есть . Это следует из первого инварианта . Мы хотим выбрать так, чтобы выполнялись описанные выше инварианты. Оказывается, что всегда есть ровно один такой выбор, как будет показано ниже.${\displaystyle n}$${\displaystyle x'=B^{n}x+\alpha }$${\displaystyle y'=By+\beta }$${\displaystyle r'=x'-y'^{n}}$${\displaystyle \beta }$

Доказательство существования и уникальности${\displaystyle \beta }$  -

По определению цифры, и по определению блока цифр,${\displaystyle 0\leq \beta <B}$${\displaystyle 0\leq \alpha <B^{n}}$

Первый инвариант говорит, что:

${\displaystyle x'=y'^{n}+r'}$

или же

${\displaystyle B^{n}x+\alpha =(By+\beta )^{n}+r'.}$

Итак, выберите наибольшее целое число, такое, чтобы${\displaystyle \beta }$

${\displaystyle (By+\beta )^{n}\leq B^{n}x+\alpha }$

Такой всегда существует, с и если тогда , но с тех пор , это всегда верно для . Таким образом, всегда будет a , удовлетворяющий первому инварианту${\displaystyle \beta }$${\displaystyle 0\leq \beta <B}$${\displaystyle \beta =0}$${\displaystyle B^{n}y^{n}\leq B^{n}x+\alpha }$${\displaystyle y^{n}\leq x}$${\displaystyle \beta =0}$${\displaystyle \beta }$

Теперь рассмотрим второй инвариант. Он говорит:

${\displaystyle (y'+1)^{n}>x'\,}$

или же

${\displaystyle (By+\beta +1)^{n}>B^{n}x+\alpha \,}$

Теперь, если не является наибольшим допустимым для первого инварианта, как описано выше, то также допустимо, и мы имеем${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle \beta +1}$

${\displaystyle (By+\beta +1)^{n}\leq B^{n}x+\alpha \,}$

Это нарушает второй инвариант, поэтому, чтобы удовлетворить обоим инвариантам, мы должны выбрать наибольшее значение, разрешенное первым инвариантом. Таким образом, мы доказали существование и уникальность .${\displaystyle \beta }$${\displaystyle \beta }$

Подводя итог, на каждой итерации:

1. Позвольте быть следующим выровненным блоком цифр от подкоренного выражения${\displaystyle \alpha }$
2. Позволять ${\displaystyle x'=B^{n}x+\alpha }$
3. Позвольте быть наибольшим таким, что${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle (By+\beta )^{n}\leq B^{n}x+\alpha }$
4. Позволять ${\displaystyle y'=By+\beta }$
5. Позволять ${\displaystyle r'=x'-y'^{n}}$

Обратите внимание на это , поэтому условие${\displaystyle x=y^{n}+r}$

${\displaystyle (By+\beta )^{n}\leq B^{n}x+\alpha }$

эквивалентно

${\displaystyle (By+\beta )^{n}-B^{n}y^{n}\leq B^{n}r+\alpha }$

и

${\displaystyle r'=x'-y'^{n}=B^{n}x+\alpha -(By+\beta )^{n}}$

эквивалентно

${\displaystyle r'=B^{n}r+\alpha -((By+\beta )^{n}-B^{n}y^{n})}$

Таким образом, нам на самом деле не нужно , и поскольку and , or , or , so, используя вместо, мы экономим время и пространство в 1 / . Кроме того, мы вычитаем в новом тесте отменяет единицу in , поэтому теперь самая высокая степень, которую мы должны оценить, - это, а не .${\displaystyle x}$${\displaystyle r=x-y^{n}}$${\displaystyle x<(y+1)^{n}}$${\displaystyle r<(y+1)^{n}-y^{n}}$${\displaystyle r<ny^{n-1}+O(y^{n-2})}$${\displaystyle r<nx^{{n-1} \over n}+O(x^{{n-2} \over n})}$${\displaystyle r}$${\displaystyle x}$${\displaystyle n}$${\displaystyle B^{n}y^{n}}$${\displaystyle (By+\beta )^{n}}$${\displaystyle y}$${\displaystyle y^{n-1}}$${\displaystyle y^{n}}$

Резюме [ править ]

1. Инициализировать и установить на 0.${\displaystyle r}$${\displaystyle y}$
2. Повторяйте, пока не получите желаемую точность :
   1. Позвольте быть следующим выровненным блоком цифр от подкоренного выражения.${\displaystyle \alpha }$
   2. Позвольте быть наибольшим таким, что${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle (By+\beta )^{n}-B^{n}y^{n}\leq B^{n}r+\alpha .}$
   3. Пусть .${\displaystyle y'=By+\beta }$
   4. Позволять ${\displaystyle r'=B^{n}r+\alpha -((By+\beta )^{n}-B^{n}y^{n}).}$
   5. Назначьте и${\displaystyle y\leftarrow y'}$${\displaystyle r\leftarrow r'.}$
3. ${\displaystyle y}$- наибольшее целое число, такое, что , и , где - количество использованных цифр подкоренного выражения после десятичной точки (отрицательное число, если алгоритм еще не достиг десятичной точки).${\displaystyle y^{n}<xB^{k}}$${\displaystyle y^{n}+r=xB^{k}}$${\displaystyle k}$

Бумага и карандаш n- е корни [ править ]

Как отмечалось выше, этот алгоритм похож на деление в столбик и имеет ту же нотацию:

 1 . 4  4  2  2  4 ——————————————————————_ 3 / 3. 000  000  000  000  000 \ / 1 = 3 (10 × 0 ) 2 × 1 + 3 (10 × 0 ) × 1 2 + 1 3 - 2 000 1 744 = 3 (10 × 1 ) 2 × 4 + 3 (10 × 1 ) × 4 2 + 4 3 ————— 256 000 241 984 = 3 (10 × 1 4 ) 2 × 4 + 3 (10 × 1 4 ) × 4 2 + 4 3 ——————— 14 016 000 12 458 888 = 3 (10 × 1 4 4 ) 2 × 2 + 3 (10 × 1 4 4 ) × 2 2 + 2 3 —————————— 1 557 112 000 1 247 791 448 = 3 (10 × 1 4 4 2 ) 2 × 2 + 3 (10 × 1 4 4 2 ) × 2 2 + 2 3 ————————————— 309 320 552 000 249 599 823 424 = 3 (10 × 1 4 4 2 2 ) 2 × 4 + 3 (10 × 1 4 4 2 2 ) × 4 2 + 4 3 ——————————————— 59 720 728 576

Обратите внимание, что после первой или двух итераций ведущий член преобладает над , поэтому мы можем получить часто правильное первое предположение , разделив на .${\displaystyle (By+\beta )^{n}-B^{n}y^{n}}$${\displaystyle \beta }$${\displaystyle B^{n}r+\alpha }$${\displaystyle nB^{n-1}y^{n-1}}$

Производительность [ править ]

На каждой итерации наиболее трудоемкой задачей является выбор . Мы знаем, что существуют возможные значения, поэтому можем найти их, используя сравнения. Каждое сравнение потребует оценки . На k- й итерации имеет цифры, и многочлен может быть вычислен с помощью умножения до цифр и сложения до цифр, если мы знаем степени и до конца для и для . имеет ограниченный диапазон, поэтому мы можем получить степени за постоянное время. Мы можем получить степени с умножением до${\displaystyle \beta }$${\displaystyle B}$${\displaystyle \beta }$${\displaystyle O(\log(B))}$${\displaystyle (By+\beta )^{n}-B^{n}y^{n}}$${\displaystyle y}$${\displaystyle k}$${\displaystyle 2n-4}$${\displaystyle k(n-1)}$${\displaystyle n-2}$${\displaystyle k(n-1)}$${\displaystyle y}$${\displaystyle \beta }$${\displaystyle n-1}$${\displaystyle y}$${\displaystyle n}$${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle y}$${\displaystyle n-2}$${\displaystyle k(n-1)}$цифры. Предполагая, что умножение цифр требует времени, а сложение требует времени , мы берем время для каждого сравнения или время, чтобы выбрать . Остальная часть алгоритма - это сложение и вычитание, что требует времени , поэтому требуется каждая итерация . Для всех цифр нам нужно время .${\displaystyle n}$${\displaystyle O(n^{2})}$${\displaystyle O(n)}$${\displaystyle O(k^{2}n^{2})}$${\displaystyle O(k^{2}n^{2}\log(B))}$${\displaystyle \beta }$${\displaystyle O(k)}$${\displaystyle O(k^{2}n^{2}\log(B))}$${\displaystyle k}$${\displaystyle O(k^{3}n^{2}\log(B))}$

Единственное необходимое внутреннее хранилище - это цифры на k- й итерации. Тот факт, что этот алгоритм не имеет ограниченного использования памяти, устанавливает верхнюю границу количества цифр, которые могут быть вычислены мысленно, в отличие от более элементарных алгоритмов арифметики. К сожалению, любой конечный автомат с ограниченной памятью и периодическими входами может производить только периодические выходные данные, поэтому нет таких алгоритмов, которые могут вычислять иррациональные числа из рациональных, и, следовательно, нет алгоритмов извлечения корня с ограниченной памятью.${\displaystyle r}$${\displaystyle O(k)}$

Обратите внимание, что увеличение базы увеличивает время, необходимое для выбора , в раз , но уменьшает количество цифр, необходимых для достижения заданной точности, в тот же коэффициент, и поскольку алгоритм является кубическим по количеству цифр, увеличение базы дает общее ускорение . Когда основание больше, чем подкоренное выражение, алгоритм вырождается в двоичный поиск , поэтому следует, что этот алгоритм бесполезен для вычисления корней с помощью компьютера, поскольку он всегда уступает гораздо более простому двоичному поиску и имеет ту же сложность памяти.${\displaystyle \beta }$${\displaystyle O(\log(B))}$${\displaystyle O(\log ^{2}(B))}$

Примеры [ править ]

Квадратный корень из 2 в двоичном формате [ править ]

 1. 0 1 1 0 1 ------------------_ / 10.00 00 00 00 00 1 \ / 1 + 1 ----- ---- 1 00 100 0 + 0 -------- ----- 1 00 00 1001 10 01 + 1 ----------- ------ 1 11 00 10101 1 01 01 + 1 ---------- ------- 1 11 00 101100 0 + 0 ---------- -------- 1 11 00 00 1011001 1 01 10 01 1 ---------- 1 01 11 остаток

Квадратный корень из 3 [ править ]

 1. 7 3 2 0 5 ----------------------_ / 3.00 00 00 00 00 \ / 1 = 20 × 0 × 1 + 1 ^ 2 - 2 00 1 89 = 20 × 1 × 7 + 7 ^ 2 (27 x 7) ---- 11 00 10 29 = 20 × 17 × 3 + 3 ^ 2 (343 x 3) ----- 71 00 69 24 = 20 × 173 × 2 + 2 ^ 2 (3462 х 2) ----- 1 76 00 0 = 20 × 1732 × 0 + 0 ^ 2 (34640 х 0) ------- 1 76 00 00 1 73 20 25 = 20 × 17320 × 5 + 5 ^ 2 (346405 x 5) ---------- 2 79 75

Кубический корень из 5 [ править ]

 1. 7 0 9 9 7 ----------------------_ 3 / 5. 000 000 000 000 000 \ / 1 = 300 × (0 ^ 2) × 1 + 30 × 0 × (1 ^ 2) + 1 ^ 3 - 4 000 3913 = 300 × (1 ^ 2) × 7 + 30 × 1 × (7 ^ 2) + 7 ^ 3 ----- 87 000 0 = 300 × (17 ^ 2 × 0 + 30 × 17 × (0 ^ 2) + 0 ^ 3 ------- 87 000 000 78 443829 = 300 × (170 ^ 2) × 9 + 30 × 170 × (9 ^ 2) + 9 ^ 3 ---------- 8 556 171 000 7 889 992 299 = 300 × (1709 ^ 2) × 9 + 30 × 1709 × (9 ^ 2) + 9 ^ 3 ------------- 666 178 701 000 614 014 317 973 = 300 × (17099 ^ 2) × 7 + 30 × 17099 × (7 ^ 2) + 7 ^ 3 --------------- 52 164 383 027

Корень четвертой степени из 7 [ править ]

 1. 6 2 6 5 7 ---------------------------_ 4 / 7.0000 0000 0000 0000 0000 \ / 1 = 4000 × (0 ^ 3) × 1 + 600 × (0 ^ 2) × (1 ^ 2) + 40 × 0 × (1 ^ 3) + 1 ^ 4 - 6 0000 5 5536 = 4000 × (1 ^ 3) × 6 + 600 × (1 ^ 2) × (6 ^ 2) + 40 × 1 × (6 ^ 3) + 6 ^ 4 ------ 4464 0000 3338 7536 = 4000 × (16 ^ 3) × 2 + 600 × (16 ^ 2) × (2 ^ 2) + 40 × 16 × (2 ^ 3) + 2 ^ 4 --------- 1125 2464 0000 1026 0494 3376 = 4000 × (162 ^ 3) × 6 + 600 × (162 ^ 2) × (6 ^ 2) + 40 × 162 × (6 ^ 3) + 6 ^ 4 -------------- 99 1969 6624 0000 86 0185 1379 0625 = 4000 × (1626 ^ 3) × 5 + 600 × (1626 ^ 2) × (5 ^ 2) + ----------------- 40 × 1626 × (5 ^ 3) + 5 ^ 4 13 1784 5244 9375 0000 12 0489 2414 6927 3201 = 4000 × (16265 ^ 3) × 7 + 600 × (16265 ^ 2) × (7 ^ 2) + ---------------------- 40 × 16265 × (7 ^ 3) + 7 ^ 4 1 1295 2830 2447 6799

См. Также [ править ]

• Методы вычисления квадратных корней
• n- й корневой алгоритм

Внешние ссылки [ править ]

• Почему работает алгоритм извлечения квадратного корня «Домашняя школьная математика». Также на связанных страницах приведены примеры метода квадратного корня с использованием карандаша и бумаги с делением в длину.
• Размышления о квадратном корне из двух «средних». На примере реализации на C ++.