Алгоритм аль-Каши
При проведении расчетов в древности пользовались различными "правилами", которые упрощали эти расчеты. Они и были первыми алгоритмами. Один из них – это алгоритм Аль-Каши. Этот алгоритм был предложен в самом начале 15 века, хотя похожие процедуры встречались и в индийском математическом трактате "Чанда-сутра", и в работах египетских математиков при рассмотрении умножения.
Алгоритм аль-Каши вычисления значения хn, где n – положительное число.
Шаг 1. Вводим три величины – N = n; y =1; z = х.
В этот момент справедливо соотношение хn = y*zn.
Шаг 2. Делим N на 2, одновременно определяем, было ли до того N чётным. Если N было чётным, то переходим к шагу 5.
Шаг 3. Умножаем y на z.
Шаг 4. Если N равно нулю, то ответ равен y.
Шаг 5. Умножаем z на себя, Z= z*z.
Возвращаемся к шагу 2.
Можно рассмотреть алгоритм Аль-Каши и по-другому:
Шаг 1. Вводим три величины N = n; y = 0; z = х.
Шаг 2. Делим N на 2; одновременно определяем, было ли N до того чётным. Если N было чётным, то переходим к шагу 5.
Шаг 3. Увеличиваем y на z.
Шаг 4. Если N равно нулю, то ответ равен y.
Шаг 5. Складываем z с собой, Z = z + z.
Возвращаемся к шагу 2.
В этом варианте алгоритма Аль-Каши в шагах 3 и 5 умножение заменено сложением, и в шаге 1 y приравнивается не единице, а нулю. В результате выполнения такого модифицированного алгоритма Аль-Каши получаем произведение двух чисел n и х: y = n*x.
Алгоритма Аль-Каши удобный для практических вычислений способ умножения, который сводится к более простым операциям удвоения, деления пополам и сложения. Именно такой приём применяется при вычислениях на счётах – в Европе он традиционно носит название не алгоритма Аль-Каши, а "русский крестьянский метод".
