time complexity of int

[Skaperen]

what is the big O formula time complexity for various operators with type int?

[casevh]

Assume n is length of the number in bits and let's use ^ for exponentiation.

Addition and subtraction are O(n).

Multiplication uses the Karatsuba algorithm that is O(n^1.585) instead of the classical algorithm which is O(n^2). The details are at https://bugs.python.org/issue560379 More improvements to multiplication are discussed at https://bugs.python.org/issue3944

Division is O(n^2).

There are some enhancement to exponentiation. The details are at https://bugs.python.org/issue936813

[Skaperen]

is comparison of two ints also O(n)?

[casevh]

Yes, comparison is also O(n).

[Skaperen]

i wonder if there are any algorithms that can improve on squaring a large int (multiply by itself) as opposed to multiplying two random ints that are different. maybe that same parts are the same on both sides can skip some work in places and lower the exponential some more.

[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

[Skaperen]

there is a formula to do multiply based on squaring. but it has to do 2 squares so it won't help unless the exponent is improved or the constant change is more than half lower.

many years ago i wrote some mainframe machine code to do 16-bit multiply by doing squaring with lookup tables. my code ran in 0.75 of the time needed by the machine instruction that does 16-bit multiply. i vaguely recall a way to improve division, too, but it only gains on really big numbers.