Jun 17 2012

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:
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).

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.

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.

Permanent link to this article: https://www.productivecsharp.com/2012/06/biginteger-multiplication-a-recursive-approach/