Возведение в степень

dbdb

geg

# Импортируем функцию timeit из модуля timeit для измерения времени выполнения кода
from timeit import timeit

# Напишем функцию возведения числа a в степень n, где n целое число
a = 2
n = 1000


def power(a, n):
    if n == 0:
        return 1
    return power(a, n-1) * a


print('{} ** {} = '.format(a, n), power(a, n))

print('\nRun 100000 tests...')    # Выводим сообщение о начале тестов.

# Вызываем функцию timeit 100000 раз для точного измерения времени выполнения функции power
print(timeit(globals=globals(), stmt='power(a, n)', number=100000) * 10,
      'мkс на одно выполнение функции при n = {}'.format(n))

Лист. 1. Алгоритм возведения в степень.

2 ** 1000 =  10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Run 100000 tests...
163.4900032600035 мkс на одно выполнение функции при n = 1000

Лист. 2. Результат работы программы листинг 1.

# Импортируем функцию timeit из модуля timeit для измерения времени выполнения кода
from timeit import timeit

# Напишем функцию возведения числа a в степень n, где n целое число
a = 2
n = 1000


def power(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return power(a * a, n // 2)
    return power(a, n-1) * a 

print('{} ** {} = '.format(a, n), power(a, n))

print('\nRun 1000000 tests...')    # Выводим сообщение о начале тестов.

# Вызываем функцию timeit 1000000 раз для точного измерения времени выполнения функции power
print(timeit(globals=globals(), stmt='power(a, n)', number=1000000),
      'мkс на одно выполнение функции при n = {}'.format(n))

Лист. 3. Алгоритм возведения в степень.

2 ** 1000 =  10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Run 1000000 tests...
1.6686957189995155 мkс на одно выполнение функции при n = 1000

Лист. 4. Результат работы программы листинг 3.

# Импортируем функцию timeit из модуля timeit для измерения времени выполнения кода
from timeit import timeit

# Напишем функцию возведения числа a в степень n, где n целое число
a = 2
n = 1000


def power(a, n):
    if n == 0:
        return 1
    if n % 5 == 0:
        return power(a * a * a * a * a, n // 5)
    return power(a, n-1) * a 

print('{} ** {} = '.format(a, n), power(a, n))

print('\nRun 1000000 tests...')    # Выводим сообщение о начале тестов.

# Вызываем функцию timeit 1000000 раз для точного измерения времени выполнения функции power
print(timeit(globals=globals(), stmt='power(a, n)', number=1000000),
      'мkс на одно выполнение функции при n = {}'.format(n))

Лист. 5. Алгоритм возведения в степень.

2 ** 1000 =  10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Run 1000000 tests...
1.4251287910001338 мkс на одно выполнение функции при n = 1000

Лист. 6. Результат работы программы листинг 5.

# Импортируем функцию timeit из модуля timeit для измерения времени выполнения кода
from timeit import timeit

# Напишем функцию возведения числа a в степень n, где n целое число
a = 2
n = 1000


def power(a, n):
    if n == 0:
        return 1
    if n % 5 == 0:
        return power(a * a * a * a * a, n // 5)
    if n % 2 == 0:
        return power(a * a, n // 2)
    return power(a, n-1) * a 

print('{} ** {} = '.format(a, n), power(a, n))

print('\nRun 1000000 tests...')    # Выводим сообщение о начале тестов.

# Вызываем функцию timeit 1000000 раз для точного измерения времени выполнения функции power
print(timeit(globals=globals(), stmt='power(a, n)', number=1000000),
      'мkс на одно выполнение функции при n = {}'.format(n))

Лист. 7. Алгоритм возведения в степень.

2 ** 1000 =  10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Run 1000000 tests...
1.0515102979998119 мkс на одно выполнение функции при n = 1000

Лист. 8. Результат работы программы листинг 5.

опо

Тимофей Хирьянов, МФТИ, Информатика. Алгоритмы и структуры данных на Python 3. Лекция 7. Возведение в степень (в конце лекции).

Источники:

Тимофей Хирьянов, Решето Эратосфена

Llama3, модель AI

Python