Working with values that greatly exceed the long (64 bit)

How large numbers are represented and stored will depend on your programming language. In languages like C and Java , the most they offer you are libraries that implement giant numbers. In languages like Python3 and Haskell , you do not have to worry about "popping" a variable because the number is too large. Usage examples:

In C , using the gmp library:

# include <stdio.h>
# include <gmp.h>

int main(int argc, char *argv[]) {
    mpz_t a, b;
    mpz_init_set_str (a, "987654321987654321000000000", 10);
    mpz_init_set_str (b, "987654321987654321000000000", 10);
    mpz_mul (a, a, b); // a = a * b

    printf("%s\n", mpz_get_str (NULL, 10, a));
    return 0;
}

Result: 975461059740893157555403139789971041000000000000000000 .

Note: The .c file must be compiled with the following command to include the gmp library: gcc ARQUIVO.c -lgmp -lm .

In Java , using the BigInteger :

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger b1 = new BigInteger("987654321987654321000000000");
        BigInteger b2 = new BigInteger("987654321987654321000000000");

        BigInteger produto = b1.multiply(b2);

        System.out.println(produto);
    }
}

Result: 975461059740893157555403139789971041000000000000000000 .

Haskell , with native support:

Prelude> 987654321987654321000000000 * 987654321987654321000000000
975461059740893157555403139789971041000000000000000000

In Python3 , also with native support:

>>> 987654321987654321000000000 * 987654321987654321000000000
975461059740893157555403139789971041000000000000000000

In Java, use the class BigInteger . It has arbitrary size.

In C you will either have to choose a non-standard library or deploy it on your own. GMPLib has a known implementation.

Multiplying is done by the multiply() :

BigInteger x = new BigInteger("12345678901234567890");
BigInteger y = new BigInteger("9876543210");
x.multiply(y);

See running on ideone .

There are several ways to store and perform calculations with arbitrary precision numbers.

I believe the simplest example is to store the digits that make up the number in a string and do the calculations "practically" the same way we do the account manually, however, this simple form does not provide very good performance.

Here is a practical, commented, and very simple example in C of how to make a sum with arbitrary numbers:

#include <stdio.h>
#include <string.h>

// Tamanho do buffer
#define TAMANHO_MAXIMO  100000

// Retorna o máximo de 2 números
#define MAX(x, y)   ((x) > (y) ? (x) : (y))

int soma(const char *num1, const char *num2, char resultado[], int max)
{
    int d1, d2, i1, i2, r, soma;
    int vai_um = 0;
    int res;

    // Índices dos números. Começa a soma a partir da unidade
    i1 = strlen(num1);
    i2 = strlen(num2);

    // Retorna o tamanho do resultado a ser impresso
    res = max - (MAX(i1, i2) + 1);

    // Índice do resultado
    r = max - 2;

    d1 = d2 = soma = 0;

    // Efetua a soma dígito a dígito
    for (;;) {
        // Se terminou finaliza o looping
        if (i1 <= 0 && i2 <= 0)
            break;

        // Obtém os dois dígitos
        d1 = i1-- <= 0 ? 0 : num1[i1] - 48;
        d2 = i2-- <= 0 ? 0 : num2[i2] - 48;

        // Soma os dígitos e o "vai um" se houver
        soma = d1 + d2 + vai_um;

        // Se a soma for maior que o dígito nove, "guarda" o "vai um"
        if (soma > 9) {
            vai_um = 1;
            soma = soma - 10;
        } else {
            // se for menor que 9, o "vai um" é zero
            vai_um = 0;
        }

        // Armazena dígito calculado
        resultado[r--] = soma + 48;
    };
    // retorna o tamanho a ser impresso
    return res;
}


int main()
{
    // Números
    char *n1 = "77843828938721973129372914798658749876459670949872346284631267542726289473294723948102389208120398347289347239472912345673414723947328947329472394810238920812039834728934723947298309563680458650468804968450685604586065486450684508654068059482309128301238019238120334332984732947492384772394723947329473294793248012983012318";
    char *n2 = "289473294723948102389208120398347289347239472912345673414723947328262894732947239481023892081203983472893947329472394810238920812039834728934723947298309563680458650468804968450685604586065486450684508654068059482309128301238019238120334332984732947492384772394723947329473294793248012983012318";

    // Resultado
    char resultado[TAMANHO_MAXIMO];
    // Tamanho do resulltado
    size_t r;

    // Preenche o resultado com 0
    memset(resultado, 0, TAMANHO_MAXIMO);

    // Coloca NULL no final da string
    resultado[TAMANHO_MAXIMO - 1] = NULL;
    printf("SOMA=%s\n + %s\n = \n\n", n1, n2);

    // Chama a função soma e informa o tamanho máximo do buffer
    r = soma(n1, n2, &resultado[0], TAMANHO_MAXIMO);

    printf("%s\n", &resultado[r]);
    getchar();
    return 0;
}

After execution, the output is:

SOMA=778438289387219731293729147986587498764596709498723462846312675427262894732
94723948102389208120398347289347239472912345673414723947328947329472394810238920
81203983472893472394729830956368045865046880496845068560458606548645068450865406
80594823091283012380192381203343329847329474923847723947239473294732947932480129
83012318
 + 28947329472394810238920812039834728934723947291234567341472394732826289473294
72394810238920812039834728939473294723948102389208120398347289347239472983095636
80458650468804968450685604586065486450684508654068059482309128301238019238120334
332984732947492384772394723947329473294793248012983012318
 =

77843828938721973129372914798948223171183619052261554405029614832073528946207069
62151711315544866124202229447895393623775461870742022289465894478962047784162407
96694578694478945966191273609173009376099369013712091721309729013690173081361189
64618256602476038476240668665969465894984769544789447894658946589586496025966024
636

In the example above, the buffer size is limited to TAMANHO_MAXIMO however, in a real library, it can be dynamically allocated.

The other operations (subtraction, multiplication, division) are done in a similar way.

There are several techniques to optimize this type of operation, for example:

• change the base of the number to a larger base (eg base 16, 64 or 256), because each digit occupies a smaller memory space

• save the "go one" operation on a vector and apply it in just one loop at the end of the operation (used mainly in multiplication)

For more information on operations with arbitrary numbers and optimization:

The Art of Computer Programming - Vol 2

Numerical Recipes Home Page

Multiplication can be done in parts. You divide the number into smaller bits, multiply these bits between them (with rules) and finally add all the products with rules.

For example, to multiply 1234567 by 321 you can divide the numbers into 2-digit pieces (base 100). Now multiply the pieces of each number

1 * 3 = 3 (base ^ 4)
1 * 21 = 21 (base ^ 3)
23 * 3 = 69 (base ^ 3)
23 * 21 = 483 (base ^ 2)
45 * 3 = 135 (base ^ 2)
45 * 21 = 945 (base ^ 1)
67 * 3 = 201 (base ^ 1)
67 * 21 = 1407 (base ^ 0)

And now, if you add up these products while keeping a close eye on the bases, obtens

3, 21+69, 483+135, 945+201, 1407
3, 90, 618, 1146, 1407
3, 90+6, 18+11, 46+14, 07
3, 96, 29, 60, 07
396296007                          = 1234567 * 321

With computers this is easy to do on a 256 basis, for example.

Basically this is the way I learned in school :-)