Jul-05-2020, 03:03 PM
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.
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 loopNow 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