Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
time complexity of int
#1
what is the big O formula time complexity for various operators with type int?
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply
#2
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
Reply
#3
is comparison of two ints also O(n)?
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply
#4
Yes, comparison is also O(n).
Reply
#5
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.
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply
#6
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
Reply
#7
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.
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Time complexity different between operating systems. Why? Mekire 2 4,232 Jan-18-2017, 09:29 PM
Last Post: casevh

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020