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

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

Алгоритм

Обозначение

Пусть 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 у ^ {п} + г = х}$${\ Displaystyle (у + 1) ^ {п}> х}$${\ 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 х '= В ^ {п} х + \ альфа}$${\ displaystyle y '= по + \ beta}$${\ displaystyle r '= x'-y' ^ {n}}$${\ displaystyle \ beta}$

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

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

Обратите внимание на это , поэтому условие ${\ Displaystyle х = у ^ {п} + г}$

${\ Displaystyle (по + \ бета) ^ {п} \ Leq B ^ {п} х + \ альфа}$

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

${\ 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 г = ху ^ {п}}$${\ Displaystyle х <(у + 1) ^ {п}}$${\ displaystyle r <(y + 1) ^ {n} -y ^ {n}}$${\ Displaystyle г <ну ^ {п-1} + О (у ^ {п-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 (по + \ бета) ^ {п}}$${\ displaystyle y}$${\ Displaystyle у ^ {п-1}}$${\ Displaystyle у ^ {п}}$

Резюме

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 '= по + \ 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 у ^ {п} <хВ ^ {к}}$${\ Displaystyle у ^ {п} + г = хВ ^ {к}}$${\ 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)×12     +13
     —
     2 000
     1 744                    = 3(10×1)2×4     +3(10×1)×42     +43
     —————
       256 000
       241 984                = 3(10×14)2×4    +3(10×14)×42    +43
       ———————
        14 016 000
        12 458 888            = 3(10×144)2×2   +3(10×144)×22   +23
        ——————————
         1 557 112 000
         1 247 791 448        = 3(10×1442)2×2  +3(10×1442)×22  +23
         —————————————
           309 320 552 000
           249 599 823 424    = 3(10×14422)2×4 +3(10×14422)×42 +43
           ———————————————
            59 720 728 576

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

Спектакль

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

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

Обратите внимание, что увеличение базы увеличивает время, необходимое для выбора , в раз , но уменьшает количество цифр, необходимых для достижения заданной точности, в тот же раз, и поскольку алгоритм является кубическим по количеству цифр, увеличение базы дает общее ускорение . Когда основание больше, чем подкоренное выражение, алгоритм вырождается в двоичный поиск , поэтому следует, что этот алгоритм бесполезен для вычисления корней с помощью компьютера, так как он всегда уступает гораздо более простому двоичному поиску и имеет такую ​​же сложность памяти. ${\ displaystyle \ beta}$${\ Displaystyle О (\ журнал (B))}$${\ Displaystyle О (\ журнал ^ {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 remainder

Корень квадратный из 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 x 2)
          -----
           1 76 00
                 0 = 20×1732×0+0^2 (34640 x 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
     3 913 = 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 443 829 = 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 ++.