Алгоритм Аль-Каші

Під час проведення розрахунків у давнину користувалися різними "правилами", які спрощували ці розрахунки. Вони і були першими алгоритмами. Один з них – це алгоритм Аль-Каші. Цей алгоритм був запропонований на початку 15 століття, хоча схожі процедури зустрічалися і в індійському математичному трактаті "Чанда-сутра", і в роботах єгипетських математиків під час розгляду множення.

Алгоритм аль-Каші обчислення значення хⁿ, де n – позитивне число.

Крок 1. Вводимо три величини - N = n; y = 1; z = x.

У цей момент справедливе співвідношення хⁿ=y*zⁿ.

Крок 2. Ділимо N на 2, одночасно визначаємо, чи було до того N парним. Якщо N було парним, переходимо до кроку 5.

Крок 3. Примножуємо y на z.

Крок 4. Якщо N дорівнює нулю, відповідь дорівнює y.

Крок 5. Примножуємо z на себе, Z= z*z.

Повертаємось до кроку 2.

Можна розглянути алгоритм Аль-Каші також по-іншому:

Крок 1. Вводимо три величини N = n; y = 0; z = x.

Крок 2. Ділимо N на 2; одночасно визначаємо, чи було N до того парним. Якщо N було парним, переходимо до кроку 5.

Крок 3. Збільшуємо y на z.

Крок 4. Якщо N дорівнює нулю, відповідь дорівнює y.

Крок 5. Складаємо з собою, Z = z + z.

Повертаємось до кроку 2.

У цьому варіанті алгоритму Аль-Каші в кроках 3 і 5 множення замінено додаванням, і в кроці 1 y прирівнюється не одиниці, а нулю. Внаслідок виконання такого модифікованого алгоритму Аль-Каші отримуємо добуток двох чисел n і х: y = n*x.

Алгоритм Аль-Каші зручний для практичних обчислень способів множення, який зводиться до більш простих операцій подвоєння, розподілу навпіл та додавання. Саме такий прийом застосовувався при обчисленнях на рахівницях.