Recently in the Coursera course "Algorithms: Design and Analysis, Part I" I come across to an interesting introduction of the divide and conquer technique using the multiplication between big integers as an example. My hands started to itch immediately. I would have to try to write an implementation!

**The Problem**

Given two integers x and y of any size return the product of them.

**The Idea**

The simplest algorithm is what we are all used to do, writing down all the products and then add them together. This is know as the "Long Multiplication" algorithm.

Using a simple calculus is easy to understand that the problem can be solved using a recursive approach.

It is always possible to write x and y in the following way:

So the product can be calculated as:

This means that we can calculate the product xy calculating 4 small products (ac, ad, bc, bd) in a recursive way.

More info:

**The Implementation**

For simplicity, I decided to represent a number using a string encapsulated in a class called MyBigInteger.

This is the implementation of the multiplication algorithm in C#:

In order to implement the algorithm I also had to implement the sum between two big numbers using the classic mathematical way:

The full code is available in my personal repository (BigIntegerMultiplication).

**Tests**

**Improvements**

In this example, we have a recursive tree with 4 branches. In reality it is possible to have only 3 branches using a simple trick (Karatsuba multiplication).

Instead of calculating ac and bd directly it is possible to calculate first:

and then calculate (ad + bc) using a subtraction:

In order to implement this slightly improved version of the algorithm is necessary to implement the subtraction of two big integers. I didn't wanted to do it, so I don't have an implementation to share.

**Conclusion**

The purpose of the exercise was to prove to myself that I was able to build the algorithm based on the original idea presented in the course. I would like to let the reader aware that the .NET framework already implement a comprehensive class that implement the operations on big integers in a quick way: BigInteger.

## No comments:

## Post a Comment

What you think about this post? I really appreciate your constructive feedback (positive and negative) and I am looking forward to start a discussion with you on this topic.