BigInteger multiplication - A recursive approach

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:

http://en.wikipedia.org/wiki/Multiplication_algorithm

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.