Was ist der einfachste Weg, bigint in C zu implementieren?

Ich versuche, 100 zu berechnen! (d. h. die Fakultät von 100).

Ich suche nach dem einfachsten Weg, dies mit C zu erreichen. Ich habe herumgelesen, aber keine konkrete Antwort gefunden.

Falls Sie es wissen müssen, ich programmiere in Xcode unter Mac OS X.

Wenn Sie nach einer einfachen Bibliothek suchen, ist libtommath (von libtomcrypt) wahrscheinlich das, was Sie wollen.

Wenn Sie selbst eine einfache Implementierung schreiben möchten (entweder als Lernübung oder weil Sie nur eine sehr begrenzte Teilmenge der Bigint-Funktionalität benötigen und nicht auf eine Abhängigkeit von einer großen Bibliothek, Namespace-Verschmutzung usw. , dann könnte ich für dein Problem folgendes vorschlagen:

Da können Sie die Größe des Ergebnisses basierend auf einschränken nweisen Sie einfach ein Array von vor uint32_t der erforderlichen Größe, um das Ergebnis zu halten. Ich vermute, du wirst es wollen drucken das Ergebnis, daher ist es sinnvoll, eine Basis zu verwenden, die eine Potenz von 10 ist (dh Basis 1000000000) und nicht eine Potenz von 2. Das heißt, jedes Element Ihres Arrays darf einen Wert zwischen 0 und 999999999 enthalten.

Um diese Zahl mit einer (normalen, nicht großen) ganzen Zahl zu multiplizieren nmach sowas wie:

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp % 1000000000;
    carry = tmp / 1000000000;
}
if (carry) big[len++] = carry;

Wenn Sie wissen n niemals größer als 100 (oder eine andere kleine Zahl) sein und vermeiden möchten, in den 64-Bit-Bereich zu gehen (oder wenn Sie auf einer 64-Bit-Plattform sind und verwenden möchten uint64_t für Ihr Bigint-Array), dann machen Sie die Basis zu einer kleineren Potenz von 10, damit das Multiplikationsergebnis immer in den Typ passt.

Jetzt ist das Drucken des Ergebnisses nur so etwas wie:

printf("%lu", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.9lu", (long)big[i-1]);
putchar('\n');

Wenn Sie anstelle einer Zehnerpotenz eine Zweierpotenz als Basis verwenden möchten, wird die Multiplikation viel schneller:

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp;
    carry = tmp >> 32;
}
if (carry) big[len++] = carry;

Das Ergebnis dezimal auszugeben wird jedoch nicht so angenehm sein… 🙂 Natürlich, wenn Sie das Ergebnis in hexadezimaler Form wollen, dann ist es einfach:

printf("%lx", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.8lx", (long)big[i-1]);
putchar('\n');

Hoffe das hilft! Ich überlasse die Implementierung anderer Dinge (wie Addition, Multiplikation von 2 Bigints usw.) als Übung für Sie. Denken Sie einfach daran zurück, wie Sie in der Grundschule Addition, Multiplikation, Division usw. zur Basis 10 gelernt haben, und bringen Sie dem Computer bei, wie das geht (aber stattdessen in Basis 10^9 oder Basis 2^32), und Sie sollten es tun habe kein Problem.

Wenn Sie bereit sind, eine Bibliotheksimplementierung zu verwenden, scheint die Standardimplementierung zu sein GMP

mpz_t out;
mpz_init(out);
mpz_fac_ui(out,100);
mpz_out_str(stdout,10,out);

sollte 100 rechnen! vom Blick in die Dokumente.

Du hast nach dem gefragt einfachste Weg, dies zu tun. Also, los geht’s:

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

int main(int argc, char** argv) {
    mpz_t mynum;
    mpz_init(mynum);
    mpz_add_ui(mynum, 100);
    int i;
    for (i = 99; i > 1; i--) {
        mpz_mul_si(mynum, mynum, (long)i);
    }
    mpz_out_str(stdout, 10, mynum);
    return 0;
}

Ich habe diesen Code getestet und er gibt die richtige Antwort.

Sie können auch verwenden OpenSSL Mrd; Es ist bereits in Mac OS X installiert.

Sie können Fakultät 1000 in C mit nur 30 Codezeilen drucken, <stdio.h> und verkohlen Typ :

#include <stdio.h>
#define B_SIZE 3000 // number of buffered digits

struct buffer {
    size_t index;
    char data[B_SIZE];
};

void init_buffer(struct buffer *buffer, int n) {
    for (buffer->index = B_SIZE; n; buffer->data[--buffer->index] = (char) (n % 10), n /= 10);
}

void print_buffer(const struct buffer *buffer) {
    for (size_t i = buffer->index; i < B_SIZE; ++i) putchar('0' + buffer->data[i]);
}

void natural_mul_buffer(struct buffer *buffer, const int n) {
    int a, b = 0;
    for (size_t i = (B_SIZE - 1); i >= buffer->index; --i) {
        a = n * buffer->data[i] + b;
        buffer->data[i] = (char) (a % 10);
        b = a / 10;
    }
    for (; b; buffer->data[--buffer->index] = (char) (b % 10), b /= 10);
}

int main() {
    struct buffer number_1 = {0};
    init_buffer(&number_1, 1);
    for (int i = 2; i <= 100; ++i)
        natural_mul_buffer(&number_1, i);
    print_buffer(&number_1);
}

Schneller findet man aber die „Kleinen“ factorial(10000) wird hier ≈ sofort berechnet.

Sie können es in a setzen fact.c Datei dann kompilieren + ausführen:

gcc -O3 -std=c99 -Wall -pedantic fact.c ; ./a.out ;

Wenn Sie eine Basiskonvertierung durchführen möchten, gibt es eine Lösung, siehe auch Fibonacci(10000), Danke.