Why is python's built in multiplication so fast [closed]

Question

So the other day I was trying something in python, I was trying to write a custom multiplication function in python

def multi(x, y):
    z = 0
    while y > 0:
        z = z + x
        y = y - 1
    return z

However, when I ran it with extremely large numbers like (1 << 90) and (1 << 45) which is (2 ^ 90) * (2 ^ 45). It took forever to compute. So I tried looking into different types of multiplication, like the russian peasant multiplication technique, implemented down there, which was extremely fast but not as readable as multi(x, y)

def russian_peasant(x, y):
    z = 0
    while y > 0:
        if y % 2 == 1: z = z + x
        x = x << 1
        y = y >> 1
    return z 

What I want you to answer is how do programming languages like python multiply numbers ?

Answer 1

The basic answer to your question is this, multiplication using * is handled through C code. In essence if you write something in pure python its going to be slower than the C implementation, let me give you an example.

The operator.mul function is implemented in C, but a lambda is implemented in Python, we're going to try to find the product of all the numbers in an array using functools.reduce and we are going to use two cases, one using operator.mul and another using a lambda which both do the same thing (on the surface):

from timeit import timeit
setup = """
from functools import reduce
from operator import mul
"""

print(timeit('reduce(mul, range(1, 10))', setup=setup))
print(timeit('reduce(lambda x, y: x * y, range(1, 10))', setup=setup))

Output:

1.48362842561
2.67425475375

operator.mul takes less time, as you can see.

Answer 2

Your multi version runs in O(N) whereas russian_peasant version runs in O(logN), which is far better than O(N).

To realize how fast your russian_peasant version is, check this out

from math import log
print round(log(100000000, 2))   # 27.0

So, the loop has to be executed just 27 times, but your multi version's while loop has to be executed 100000000 times, when y is 100000000.

To answer your other question,

What I want you to answer is how do programming languages like python multiply numbers ?

Python uses O(N^2) grade school multiplication algorithm for small numbers, but for big numbers it uses Karatsuba algorithm.

Basically multiplication is handled in C code, which can be compiled to machine code and executed faster.

Answer 3

Programming languages like Python use the multiplication instruction provided by your computer's CPU.

In addition, you have to remember that Python is a very high-level programming language, which runs on a virtual machine which itself runs on your computer. As such, it is, inherently, a few order of magnitudes slower than native code. Translating your algorithm to assembly (or even to C) would result in a massive speedup -- although it'd still be slower than the CPU's multiplication operation.

On the plus side, unlike naive assembly/C, Python auto-promotes integers to bignums instead of overflowing when your numbers are bigger than 2**32.