How to work with values that far exceed the long (64 bit) limit value

Question

How is stored and performed operations with numbers that exceed the limit values of type long and double? How the four primary operations are done with these numbers (sum, subtraction, multiplication and division)?

Context

It is common for most programming languages to support types long and double (both use a 64-bit word) however in Super computers (such as those that do atomic bomb calculations and processing meteorological and astronomical data) that have thousands of processing cores and memory Tbs working concurrently should probably work with values that exceed and much the values supported long and double.

Example of values exceeding and exceeding the supported values long and double.

• googol
• googolplex
• mol (chemical unit)
• Long.MAX_VALUE * Long.MAX_VALUE * Long.MAX_VALUE (JAVA)
• googolplex * googolplex

What solutions would be possible in C (much performance) and Java (well-known)

Answer 1

How large numbers are represented and stored will depend on your programming language. In languages such as C and Java, the most they offer you are libraries that implement giant numbers. Already in languages like Python3 and Haskell, you don’t have to worry about "popping" a variable because the number is too big. Examples of use:

---

In C, using the library gmp:

# 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;
}

Upshot: 975461059740893157555403139789971041000000000000000000.

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

---

In Java, using the class 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);
    }
}

Upshot: 975461059740893157555403139789971041000000000000000000.

---

In Haskell, native-backed:

Prelude> 987654321987654321000000000 * 987654321987654321000000000
975461059740893157555403139789971041000000000000000000

---

In Python3, also with native support:

>>> 987654321987654321000000000 * 987654321987654321000000000
975461059740893157555403139789971041000000000000000000

Answer 2

In Java use the class BigInteger. She has arbitrary size.

In C you will have to choose a non-standard library or implement on your own. A Gmplib has a known implementation.

Multiplication occurs by the method multiply():

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

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

Answer 3

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" in the same way we do the account manually, however, this simple form does not offer a very good performance.

Follow a practical example, commented and very simple in C how to make a summing up 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

Ne example above, buffer size is limited to constant 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 (ex: base 16, 64 or 256), as each digit occupies a smaller memory space

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

---

For more information on arbitrary numbers and optimization operations (in English):

The Art of Computer Programming - Vol 2

Numerical Recipes Home Page

Answer 4

Multiplication can be done by parts. You divide the number into smaller pieces, you multiply those bits (with rules) and finally you add all the products, with rules.

For example, to multiply 1234567 by 321 you can divide the numbers into 2-digit pedals (base 100). Now you 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 these products while keeping the basis in mind, you get

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 256 basis, for example.

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