time complexity of int

[casevh]

Python does use an improved algorithm for squaring large numbers. The improvement just decreases the constant so the time complexity doesn't change. The improvement is measurable.

a is 1232 bits long.

$ py38 -m timeit -s "a=3**777 + 7**123; b=a+11**7" "a*b"
200000 loops, best of 5: 1.49 usec per loop
$ py38 -m timeit -s "a=3**777 + 7**123; b=a+11**7" "a*a"
200000 loops, best of 5: 1.09 usec per loop

Now a is 123274 bit long.

$ py38 -m timeit -s "a=3**77777 + 7**12345; b=a+11**7" "a*a"
100 loops, best of 5: 2.58 msec per loop
$ py38 -m timeit -s "a=3**77777 + 7**12345; b=a+11**7" "a*b"
100 loops, best of 5: 2.98 msec per loop