Measuring Big O of multiplication in Python

Question

As I understand it, the Order of Complexity for multiplication is quadratic so if a multiply two 1-digit numbers together there will be 1 operation, two 2-digit numbers together there will be 4 operations, two 3-digit numbers 9 operations and so on.

I wanted to see this complexity by timing the execution of a program that simply multiplied two numbers together. Unexpectedly, regardless of the size of the numbers, the execution time is the same.

import time

num1 = 135
num2 = 342

start = time.time()
total = num1 * num2
finish = time.time()
elapsed = finish - start

print elapsed

So the result is 9.53674316406e-07 if I multiply two 3-digit numbers or two 30-digit numbers.

What is it that I'm misunderstanding?

*"As I understand it, the Order of Complexity for multiplication is quadratic"* - what makes you think that? Counting the digits in decimal makes no sense, for one thing, as the computer will process the number's binary representation. — jonrsharpe, Jun 30 '15 at 13:29
As per this explanation @jonrsharpe http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o — tommyd456, Jun 30 '15 at 13:30
For large numbers it should. I think he's confused for small numbers though. — CrazyCasta, Jun 30 '15 at 13:30
Note that the answer there refers to **how a person would multiply two numbers**, not (necessarily) how a computer would do it. See e.g. http://stackoverflow.com/q/3060064/3001761, there are various algorithms for multiplication. — jonrsharpe, Jun 30 '15 at 13:32
Quadratic in terms of the number of bits in each number not the numbers themselves. But if you have any sense, you will see that this is still slow even with bits, so that is why there exists linearithmic or even faster multiplication algorithms and I'm quite sure Guido has implemented something similar. And if he hasn't, he should give me a call — smac89, Jun 30 '15 at 13:34
Python uses the Karatsuba multiplication algorithm for big integer multiplication, which multiplies numbers in O(n^1.585), not O(n^2). — interjay, Jun 30 '15 at 13:34

score 5 · Accepted Answer · answered Jun 30 '15 at 13:30

Your numbers are far too small to exhibit any difference in the time taken to multiply them. Try some proper sized numbers of the order of 10^10⁶.

For example:

import time

for k in range(10):
    num = 10**(10**k)

    start = time.time()
    total = num * num
    finish = time.time()
    elapsed = finish - start

    print k, elapsed

On my machine this outputs:

0 2.86102294922e-06
1 5.00679016113e-06
2 2.14576721191e-06
3 7.86781311035e-06
4 0.000285148620605
5 0.010409116745
6 0.391373157501
7 15.7926459312

(I'm still waiting for 8).

CrazyCasta · Answer 2 · 2015-06-30T13:47:41.297

You are correct that for large numbers multiplication is quadratic (or even with better algorithms at least >O(n)). As long as they fit in a 64-bit number you probably won't see any change. There's two problems you're running into 64-bit numbers will hold up to 9.223372e+18 (an 19 digit number) and your 30 digit numbers are just going to be two 64-bit numbers. Try something with several 64-bit numbers (say 10000, which would be an 180000 digit number):

import time
import random

for i in range(0, 190000, 10000):
    a = random.randint(10**i, 10**(i+1)-1)
    b = random.randint(10**i, 10**(i+1)-1)

    start = time.time()
    c = a*b
    end = time.time()

    print i, str(c)[0], end-start # str(c)[0] just in case optimization on c (unlikely)

Results:

0 1 0.0
10000 3 0.000855922698975
20000 5 0.00253701210022
30000 1 0.00445008277893
40000 4 0.00767087936401
50000 3 0.00982689857483
60000 1 0.0133669376373
70000 9 0.0174329280853
80000 4 0.0230648517609
90000 3 0.0251250267029
100000 4 0.0296058654785
110000 4 0.0344429016113
120000 3 0.0401389598846
130000 1 0.0457019805908
140000 2 0.0524950027466
150000 1 0.0619490146637
160000 5 0.0693421363831
170000 2 0.068922996521
180000 2 0.0755639076233

Conclusion based on 90000 and 180000 it's >O(n) but

Measuring Big O of multiplication in Python

2 Answers2