Алгоритм швидкого зведення в натуральну ступінь

Сьогодні мова зайде про зведення числа в ступінь, яку саме? Відповідь для різних алгоритмів буде різнитися. Однак, давайте домовимося - ми будемо розглядати виключно безліч раціональних чисел, таким чином про комплексні числа ми в цій статті говорити не будемо.

Найчастіше звести число до степеня досить просто, для цього буде потрібно функція power. яка люб'язно все зробить за вас. Але що робити, якщо такої функції у вас немає? А раптом швидкість стандартної функції power вас не влаштовує? Давайте самостійно спробуємо написати функцію, яка б зводила числа в довільну ступінь.

"Математичний" алгоритм

Зазвичай, якщо ви запитаєте пересічного вчителя інформатики про зведення в ступінь, то швидше за все отримаєте у відповідь стандартну, можна сказати чергову, "відписку": використовуйте властивість логарифма. Так ось, давайте розглянемо саме цей метод.

Математичне обгрунтування. Давайте займемося математикою, а саме спробуємо перетворити вираз a в ступеня b. Для цього ми зробимо на вигляд непримітну операцію, скористаємося тотожністю x = exp (ln (x)). Таким чином ми отримаємо a ^ b = exp (ln (a ^ b)). Тепер по властивості логарифма винесемо показник ступеня (у нас це b), отримаємо a ^ b = exp (b * ln (a)).

"Швидкий" алгоритм

Однак, існує альтернативний алгоритм зведення числа в натуральну ступінь.

трасування

Для доказу обгрунтовано алгоритму порівняємо його з звичайним алгоритмом (циклічним) за кількістю операцій. Дані для "швидкого" зведення були отримані експериментально.

Графік залежності кількості операцій від показника ступеня. Швидке зведення. циклічне зведення. На осі OX зазначається розмір масиву, на осі OY кількість операцій для отримання значення.

порівняння "циклічного" "швидкого" піднесення до степеня

Той же графік, але вісь OY взята логарифмічною (log plot).