07 Dec 2019

C und die GNU MP Bignum Library

Zur Berechnung von Fakultät, Fibonacci, Ackermann: Der Endboss mit der GNU MP Bignum Library

Zu diesem Beitrag Haskell versus C reiche ich jetzt noch eine Version in C mit der Bignum-Library nach. Ich weise darauf hin, dass die Implementierung so natürlich total ungünstig ist, und es für die einelnen Fälle viel schlauere Ideen gibt. Es ging mir aber einfach darum, mal was mit Bignum zu machen. Ausserdem kann man so schön testen, wie gut der Rechner ist.

Vielen Dank beim gesamten Internet, z. B. cubbi.org für Tipps, sonst hätte ich noch länger gebraucht.

Der Kandidat

gmp_a.c

/****
 * big numbers test for fun by chrissie 12/2019
 *
 * gcc -lgmp gmp_a.c -o gmp_a 
 */

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

/* big numbers Fibonacci recursive */
mpz_t* my_mpz_fib(unsigned long n)
{
    mpz_t *r = malloc(sizeof(mpz_t));
    if(n < 2) {
        mpz_init_set_ui(*r, n);      // 0 or 1
    } else {
        mpz_init(*r);
        mpz_t* f1 = my_mpz_fib(n - 1);
        mpz_t* f2 = my_mpz_fib(n - 2);
        mpz_add(*r, *f1, *f2);
        mpz_clear(*f1); free(f1);
        mpz_clear(*f2); free(f2);
    }
    return r;
}

/* big numbers Faculty */
void my_mpz_fac(mpz_t fac, unsigned long n)
{
    unsigned long i; 
    for (i = 2; i <= n; ++i) {
        mpz_mul_ui(fac, fac,  i);
    }
}
/* big numbers Ackermann */
mpz_t* my_mpz_ackermann(unsigned long m, mpz_t *n)
{
        mpz_t *r = malloc(sizeof(mpz_t));
        mpz_init(*r);
        if (m == 0)  {                          // if m == 0
            mpz_add_ui(*r, *n, 1);
            return r;
        } 
        else if (0 == mpz_cmp_ui(*n, 0)) {
            mpz_t *f1 = malloc(sizeof(mpz_t));  // if n == 0
            mpz_init_set_ui(*f1, 1);
            r = my_mpz_ackermann (m - 1, f1);
            mpz_clear(*f1); free(f1);
            return r;
        } else {
            mpz_t *f1 = malloc(sizeof(mpz_t));
            mpz_init(*f1);
            mpz_sub_ui(*f1, *n, 1);             // calc n - 1
            mpz_t *f2 = malloc(sizeof(mpz_t));
            f2 = my_mpz_ackermann (m, f1);
            mpz_t *r  = my_mpz_ackermann (m-1, f2);
            mpz_clear (*f1); free (f1);
            mpz_clear (*f2); free (f2);
            return r;
        }
}

int main()
{
    unsigned long fa = 42;
    mpz_t result;
    mpz_init (result);
    mpz_set_ui (result, 1);
    my_mpz_fac (result, fa);
    printf("faculty of %lu is ",fa);
    mpz_out_str(stdout, 10, result);
    printf("\n");

    unsigned long fi = 42;
    mpz_t *f_res = my_mpz_fib (fi);
    char* s_res = mpz_get_str(NULL, 10, *f_res);
    printf("fibonacci of %lu is %s\n",fi, s_res);
    free (f_res); free(s_res);

    unsigned long f1 = 3;
    unsigned long f2 = 16;
    mpz_t *m_f2 = malloc(sizeof(mpz_t));
    mpz_init_set_ui(*m_f2, f2);
    f_res = my_mpz_ackermann (f1, m_f2);
    s_res = mpz_get_str(NULL, 10, *f_res);
    printf("ackermann of: %lu, %lu is %s\n",f1, f2, s_res);
    free(f_res); free(s_res);free(m_f2);
    return 0;
}

Alle Listings mit makefile kann man hier herunterladen: gmp_a.c

Ausführen

kompilieren und ausführen

$ gcc -lgmp gmp_a.c -o gmp_a
$ ./gmp_a 
faculty of 42 is 1405006117752879898543142606244511569936384000000000
fibonacci of 42 is 267914296
ackermann of: 3, 16 is 524285

Sehr großer Ackermann wie ack(5,15) lässt sich wohl kaum berechnen, der Rechner ist dann am Ende, selbst Wolfram Alpha steigt dann mit Result too large to represent aus. Schade!

Wenn ich Lust habe, baue ich noch eine OpenMP-Version. Die bringt aber nix beim Ackermann, wie der geneigte Leser spätestens jetzt schon weiss.