Why is python's built in multiplication so fast
algorithm, python
Solution
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.
Problem
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 ?