Vfrdtyky

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 ?

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.

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.

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.

Usually, functional programming involving many computations is best made to take less time using memoization -- the basic idea is that if you feed a true function (something that always evaluates the same result for a given argument) the same thing twice or more, you're wasting time, time that could easily be saved by identifying common calls and storing whatever they evaluate down to into a hash table or other quickly-accessible object. See https://en.wikipedia.org/wiki/Memoization for basic theory. It is well-implemented in Common Lisp.