04: Discussing Efficiency - Peasant Multiplication Test

04: Discussing Efficiency - Peasant Multiplication Test#

This notebook demonstrates the Peasant Multiplication algorithm, an ancient method for multiplying two numbers using only addition, halving, and doubling. It is also known as Russian Peasant Multiplication. The algorithm is efficient and illustrates how complex operations can be broken down into simpler steps.

Trivia:
The name “Peasant Multiplication” comes from the idea that the method could be performed by peasants who might not know the full multiplication table, but could easily double, halve, and add numbers. The algorithm is also called “Russian Peasant Multiplication” because it was widely used in Russia, but similar techniques have been found in ancient Egyptian mathematics as well.

What is Peasant Multiplication?#

Peasant Multiplication works by repeatedly halving one number and doubling the other, adding the doubled number to the result whenever the halved number is odd. This process continues until the halved number reaches zero.

Start with two numbers, x and y.
Initialize the product to 0.
Repeat the following steps until x becomes 0:
- If x is odd, add y to the product.
- Halve x (discard any remainder, i.e., use floor division).
- Double y.
The final product is the result of the multiplication.

This method leverages the binary representation of numbers: each time x is odd, it corresponds to a ‘1’ in its binary form, and the corresponding y is added to the product.

Example#

Let’s multiply 13 by 12:

Step	x (halved)	y (doubled)	x odd?	Add y to product?	Product
1	13	12	Yes	Yes	12
2	6	24	No	No	12
3	3	48	Yes	Yes	12+48=60
4	1	96	Yes	Yes	60+96=156
5	0	192	-	-	156

Final result: 13 × 12 = 156

Truth Table for Odd/Even Check#

x	x % 2 == 1 (Odd?)
13	True
6	False
3	True
1	True
0	False

Pseudocode#

Pseudocode is a way to describe algorithms using a mixture of natural language and programming-like structure. It is not written in any specific programming language and cannot be executed by a computer. Instead, it focuses on the logic and steps of the algorithm, making it easy for humans to read and understand.

Unlike regular code, pseudocode does not follow strict syntax rules and ignores language-specific details such as variable declarations, data types, or exact function names. This abstraction allows programmers and non-programmers alike to discuss and design algorithms without worrying about implementation details.

Pseudocode is used to:

Plan and communicate algorithms before coding.
Make the logic clear and language-agnostic.
Help identify errors or improvements in the algorithm’s structure.
Serve as a blueprint for translating the logic into actual code in any programming language.

function peasant_multiply(x, y)
    set product to 0
    while x is greater than 0
        if x is odd
            add y to product
        halve x (discard remainder)
        double y
    return product

This notebook will walk through the implementation and execution of this algorithm step by step.

# Import numpy to use
import numpy as np

## Write the peasant multiplication algorithm
## Run it for x = 123, y = 456

## First, set x and y:
x = 123
y = 456

## Start the algorithm
## Set the product equal to 0:
prod = 0
## while x > 0 , do some stuff:
while x > 0:
    ## If x is odd, add to the product:
    if np.mod(x,2) != 0:
        ## add y to the product
        prod = prod + y
        ## print screen:
        print('x is odd, product is', str(prod))
    ## Either way (x is odd or even), change x and y:
    x = np.floor(x/2)
    y = y+y
    print('x is ', str(x), ' y is ', str(y))
## Return the product
print('Final product is ', str(prod))

x is odd, product is 456
x is  61.0  y is  912
x is odd, product is 1368
x is  30.0  y is  1824
x is  15.0  y is  3648
x is odd, product is 5016
x is  7.0  y is  7296
x is odd, product is 12312
x is  3.0  y is  14592
x is odd, product is 26904
x is  1.0  y is  29184
x is odd, product is 56088
x is  0.0  y is  58368
Final product is  56088

import time

# Reset x and y for timing
x = 123
y = 456
prod = 0

start_time = time.time()

while x > 0:
    if np.mod(x, 2) != 0:
        prod = prod + y
    x = np.floor(x / 2)
    y = y + y

end_time = time.time()
elapsed_time = end_time - start_time

print('Final product is', prod)
print('Elapsed time: {:.2f} microseconds'.format(elapsed_time * 1e6))

Final product is 56088
Elapsed time: 61.99 microseconds

# Reset x and y for timing
x = 123
y = 456

start_time = time.time()

result = x * y

end_time = time.time()
elapsed_time = end_time - start_time

print('Result using * operator:', result)
print('Elapsed time: {:.2f} microseconds'.format(elapsed_time * 1e6))

Result using * operator: 56088
Elapsed time: 17.17 microseconds

Performance: Peasant Multiplication vs. Regular Multiplication#

The regular multiplication operator (*) in Python (and most programming languages) is highly optimized at the hardware and software level. Modern CPUs can multiply integers in a single instruction, making this operation extremely fast.

In contrast, the Peasant Multiplication algorithm breaks multiplication into a series of additions, halvings, and doublings, performed repeatedly in a loop. This involves more instructions and conditional checks, making it significantly slower than the built-in multiplication operator.

Why is Regular Multiplication Faster?#

Hardware Optimization: CPUs have dedicated circuits for multiplication, allowing them to perform this operation in a single clock cycle.
Algorithmic Complexity: Peasant Multiplication requires multiple iterations, each involving division, addition, and conditional logic, which increases execution time.
Interpreter Overhead: Each step in the algorithm is interpreted and executed separately, adding further overhead compared to a single operator.

Importance of Timing in Scientific Computing#

In scientific computing, algorithms often process large datasets or perform complex calculations repeatedly. Even small inefficiencies can add up to significant delays when scaled up. Measuring and optimizing the execution time of code is crucial for:

Efficiency: Faster code means results are obtained sooner, which is essential for research and real-time applications.
Resource Utilization: Efficient code uses less CPU time and memory, allowing more computations to be performed on the same hardware.
Scalability: Optimized algorithms can handle larger problems and datasets.

In summary: While Peasant Multiplication is an interesting historical algorithm, the built-in multiplication operator is much faster and preferred for practical use, especially when performance matters. Timing considerations help ensure that scientific code runs efficiently and scales to meet the demands of modern research.