Selbst wenn man nur einfache Probleme in Theoretischer Informatik, Zahlentheorie oder Diskreter Mathematik bearbeitet und durch Programme in C zu erschließen versucht, gelangt man schnell an die Grenzen der darstellbaren Wertebereiche für ganze Zahlen. Das Implementieren einer eigenen Bibliothek für große Zahlen ist zwar möglich, mit GMP (GNU Multi Precision Arithmic Library) gibt es aber bereits eine freie und gut gepflegte Implementierung.
Eine einfache, experimentelle Erkundung des Syracuse-Problems könnte so aussehen:
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 | #include <stdio.h> int main() { int a; scanf("%d", &a); while (a != 1) { printf("%d ", a); a = syracuse(a); } printf("1\n"); return 0; } int syracuse(int n) { if (n % 2) { return 3 * n + 1; } else { return n / 2; } } |
Mit der GNU MP Bignum Library wird daraus:
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 | #include <stdio.h> #include <gmp.h> void mpz_syracuse(mpz_t n); int main() { mpz_t a; mpz_init(a); mpz_inp_str (a, NULL, 0); while ( mpz_cmp_si(a,1) ) { mpz_out_str (NULL, 0, a); printf("\n"); mpz_syracuse(a); } printf("1\n"); return 0; } void mpz_syracuse(mpz_t n) { if (mpz_divisible_ui_p(n,2)) { mpz_divexact_ui (n, n, 2); } else { mpz_mul_ui (n, n,3); mpz_add_ui (n, n, 1); } } |
Damit kann man dann auch für sehr große natürliche Zahlen die Zahlenfolge bestimmen, kompiliert wird wie gewohnt, allerdings muss man mit -lgmp linken.
Kommentare