Multiply Big Numbers

4 minutes read
Algorithm • Programming
Algorithm • C++ • Golang • Math • Programming

Multiply Strings

I answered this LeetCode question many years ago and got a successful submission with a not too bad score.

Some code like this, I tried to make it easy to understand, well it might sacrifice some performance. The code takes less than 1s to calculate 10,000! on a MBP 2017 and nearly 100s to calculate 100,000!. Bravo!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

std::string multiply(std::string a, std::string b)
{
    size_t size_a = a.size();
    size_t size_b = b.size();
    size_t size_p = size_a + size_b;

    std::vector<int> va(size_a), vb(size_b), vp(size_p, 0);
    std::transform(a.rbegin(), a.rend(), va.begin(), [](char c) { return c - '0'; });
    std::transform(b.rbegin(), b.rend(), vb.begin(), [](char c) { return c - '0'; });

    // Multiply
    for (size_t j = 0; j < size_b; j++)
    {
        for (size_t i = 0; i < size_a; i++)
        {
            vp[i + j] += va[i] * vb[j];
        }
    }

    // Process carry
    size_p--;
    for (size_t i = 0; i < size_p; i++)
    {
        vp[i + 1] += vp[i] / 10;
        vp[i] %= 10;
    }

    // Remove unwanted prefix zeros
    while (vp.size() > 1 && *vp.crbegin() == 0)
    {
        vp.pop_back();
    }

    // Convert to string
    std::string p(vp.size(), '0');
    std::transform(vp.rbegin(), vp.rend(), p.begin(), [](int i) { return i + '0'; });

    return p;
}

Golang Package math/big

I thought there won’t be much to optimize until I tried Golang package math/big recently. I was surprised at it’s performance, it takes less than 1s to calculate 100,000! and around 62s to calculate 1,000,000!.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

package main

import (
	"fmt"
	"math/big"
	"os"
)

func main() {
	if len(os.Args) != 2 {
		fmt.Println("Usage:\n\tfactorial number")
		return
	}

	var f = new(big.Int)
	if _, ok := f.SetString(os.Args[1], 10); !ok {
		fmt.Printf("Warning: \"%s\" is not a number.\n", os.Args[1])
		return
	}

	if !f.IsInt64() {
		fmt.Printf("Warning: \"%s\" exceeds the 64-bit integer limit.\n", os.Args[1])
		return
	}

	if f.Int64() >= 1 {
		fmt.Println(f.MulRange(1, f.Int64()))
	} else {
		fmt.Println("0")
	}
}

GNU Multiple Precision Arithmetic Library

A GMP using C++ binding has even better performance. It calculates 10,000,000! in 20s.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <gmpxx.h>
#include <iostream>
#include <string>

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        std::cout << "Usage:\n\tfactorial number" << std::endl;
        return 0;
    }

    long l;
    try
    {
        l = std::stol(argv[1]);
    }
    catch (std::invalid_argument const &e)
    {
        std::cout << "Warning: \"" << argv[1] << "\" is not a number." << std::endl;
        return 1;
    }
    catch (std::out_of_range const &e)
    {
        std::cout << "Warning: \"" << argv[1] << "\" exceeds the long integer limit." << std::endl;
        return 1;
    }

    if (l < 1)
    {
        std::cout << "0" << std::endl;
        return 0;
    }

    std::cout << mpz_class::factorial(l) << std::endl;

    return 0;
}

Compile

1

g++ -Wall -O3 -lgmpxx -lgmp -o factorial factorial.cpp

Why?

It does not take Google much time to find out GMP Multiplication. It is using several different algorithms, for example.

NxN limb multiplications and squares are done using one of seven algorithms, as the size N increases.

Algorithm Threshold
Basecase (none)
Karatsuba MUL_TOOM22_THRESHOLD
Toom-3 MUL_TOOM33_THRESHOLD
Toom-4 MUL_TOOM44_THRESHOLD
Toom-6.5 MUL_TOOM6H_THRESHOLD
Toom-8.5 MUL_TOOM8H_THRESHOLD
FFT MUL_FFT_THRESHOLD

Further reading on Wikipedia.

Summarize

It is always fun to implement some algorithms by ourselves. For big numbers, however, we should really directly use the well-optimized and well-tested GMP or other similar libraries.