Ermin Hodžić

In this text, we are going to be dealing with what we call big numbers. Such numbers far exceed the maximum value supported by fundamental single-variable data types in programming languages, such as the 64-bit integer, or the double type. Within a 64-bit integer variable, we are able to store numbers of up to 19 decimal digits. However, what do we do when that is no longer enough? If we, for whatever purpose, need to store numbers that have potentially hundreds or even thousands of digits, we can no longer rely on the basic built-in data types provided by programming languages, as there are no machine instructions that operate on such big numbers. Thus, we have to resort to writing our own code that implements such big numbers and the appropriate basic operations, such as addition and multiplication.

Before going into the technical details of implementing addition and multiplication on such numbers, we are going to talk about how dealing with big numbers actually reduces to dealing with polynomials. We do this because polynomials provide us with more flexibility, as they are not as restricted in their structure as numbers themselves are. Afterwards, we will go through a number of increasingly faster algorithms used to multiply polynomials, ultimately describing the Fast Fourier Transform algorithm to the tiniest detail.

Please refer to the PDF LaTeX document for the description.