Primzahlen mit GMP

Primzahlengewinnung mit der GNU MP Bibliothek

Nachdem wir darüber gesprochen haben, hier die Implementierung der Primzahlengewinnung mit Hilfe der GNU MP Bibliothek. Das Programm kann sicherlich weiter optimiert werden - wer will, darf das gerne tun :-)

Das Progrämmchen verwendet ein paar Funktionen, die wir bisher nicht im Einsatz hatten

• eigene Speicherbereiche im sog. heap reservieren

malloc(LEN)	reserviert LEN Bytes Speicher und gibt uns einen Zeiger!! auf diesen Zurück
realloc(PTR,LEN)	kann verwendet werden, um einen solchen Speicherbereich im Nachhinein zu verkleinern bzw. zu vergrößern. Dazu gibt man den von z.B. malloc erhaltenen Zeiger an realloc (Argument PTR) und die neue Wunschlänge als LEN. Als Rückgabewert erhält man die Adresse des neuen Speicherbereichs
free(PTR)	mit free kann (bzw. sollte) man den Speicher wieder an das System zurück geben, sobald dieser nicht mehr benötigt wird

• wenn kein Arbeitsspeicher mehr frei ist, also die Reservierung fehlschlägt, geben realloc und malloc einen sog. Null-Zeiger zurück. Das ist ein Zeiger mit der Adresse 0x00000000.
• das Konstrukt a ? b : c wird in C wie folgt evaluiert
  • ist a wahr (also ungleich 0) wird b zurück gegeben
  • ist a falsch, wir c zurück
  • alloc = alloc ? (alloc << 1) : 1024;
    • ist alloc 0, wird alloc jetzt 1024 zugewiesen
    • ist alloc ungleich 0 (in diesem Fall größer null, da unsigned), wird der Wert von alloc binär um eins nach links verschoben (mit zwei multipliziert) und dann in alloc abgelegt
• die übrigen Funktionsaufrufe sind alle aus der Bibliothek GMP und kümmern sich eben um die Zahlenberechnung. Näheres hierzu findet ihr in den Manpages bzw. Tutorials dieses Projekts ...

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

mpz_t *prim_cache = NULL;
size_t prim_cache_len = 0;
size_t prim_cache_alloc = 0;

int
main(void)
{
  mpz_t prim;

  /* initialize prim to 2 */
  mpz_init(prim);
  mpz_set_ui(prim, 2);

  do {
    mpz_t modulo;
    size_t i = 0;
    int is_prim = 1;

    /* initialize modulo variable, as required by
     * GNU MP library */
    mpz_init(modulo);

    for(; i < prim_cache_len; i ++) {
      /* calculate modulo of prim divided by
       * cached primes */
      mpz_tdiv_r(modulo, prim, prim_cache[i]);

      /* compare modulo to zero,
       * mpz_cmp_ui returns 0 if equal */
      if(mpz_cmp_ui(modulo, 0) == 0) {
        is_prim = 0;
        break;
      }
    }

    if(is_prim) {
      gmp_printf("found prime number: %Zd\n", prim);

      /* add prime to cache */
      if(prim_cache_len >= prim_cache_alloc) {
        prim_cache_alloc = prim_cache_alloc ? (prim_cache_alloc << 1) : 1024;
        /* fprintf(stderr, "cache with %u entries now.\n", prim_cache_alloc); */
        prim_cache = realloc(prim_cache, sizeof(mpz_t) * prim_cache_alloc);

        if(! prim_cache) {
          fprintf(stderr, "no more memory available, sorry.\n");
          return 1;
        }
      }

      mpz_init(prim_cache[prim_cache_len]);
      mpz_set(prim_cache[prim_cache_len], prim);

      prim_cache_len ++;
    }
  } while(mpz_add_ui(prim, prim, 1), 1);
  
  return 0;
}

• obenstehenden Code bitte in prim_gmp.c abspeichern
• gcc -o prim-gmp prim-gmp.c -Wall -W -ggdb -O -lgmp ausführen
• ggf. die GMP Bibliothek installieren und Schritt 2 wiederholen
• ./prim-gmp ausführen
• staunen :-)
• Fragen hier ergänzen