Почему время Python, необходимое для умножения двух n-значных чисел, увеличивается только тогда, когда n увеличивается за 10 с?

Question

Я подсчитываю время, затраченное на моем компьютере, чтобы вычислить произведение двух n-значных чисел.

Я использую этот код для этого:

import timeit
for i in range(50):
    avg=0
    for j in range(30):
        avg+=timeit.timeit('a*b','a='+str(10**i)+';b='+str(10**i))
    print(avg/30)

Возвращает результатына этом графике:

Где ось X - это n, а ось Y - это время в секундах.Как видите, время увеличивается примерно на n, когда оно кратно 10, и не постоянно увеличивается.

Я не понимаю, почему время меняется так:

Answer 1

Интервал Python int сохраняется как последовательность 30-битных блоков (или иногда 15-битных блоков, но это реже в наши дни).Увеличение числа до десяти десятичных цифр занимает около 30 бит, а время, необходимое для умножения двух чисел, зависит в основном от того, сколько 30-битных блоков занимает каждое число, поэтому время увеличивается с шагом примерно в 9 десятичных цифр.