+- Python Forum (https://python-forum.io)
+-- Forum: General (https://python-forum.io/forum-1.html)
+--- Forum: News and Discussions (https://python-forum.io/forum-31.html)
+--- Thread: time complexity of int (/thread-28079.html)
time complexity of int - Skaperen - Jul-03-2020
what is the big O formula time complexity for various operators with type int?
RE: time complexity of int - casevh - Jul-04-2020
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
RE: time complexity of int - Skaperen - Jul-05-2020
is comparison of two ints also O(n)?
RE: time complexity of int - casevh - Jul-05-2020
Yes, comparison is also O(n).
RE: time complexity of int - Skaperen - Jul-05-2020
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.
RE: time complexity of int - casevh - Jul-05-2020
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 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
RE: time complexity of int - Skaperen - Jul-05-2020
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.