Auf Grund der Portabilität wird die Programmiersprache C gewählt, und die einzelnen Funktionen werden in einem separaten Quellcode realisiert, so daß sie später leicht wiederverwendet werden können.
Um eine möglichst hohe Geschwindigkeit zu realisieren, wird eine möglichst kleine Datenstruktur verwendet, so daß auch bei großen Zahlen der Verwaltungsaufwand nicht all zu groß wird.
Es ist zwar nur die Implementierung von positiven Zahlen erwünscht, aber aus Gründen der Erweiterbarkeit wird auch die Berechnung mit negativen Zahlen realisiert.
Es wird folgende interne Darstellung für die Zahlen gewählt:
struct big_struct
{
int sign;
unsigned long dgs_alloc;
unsigned long dgs_used;
unsigned int * dp;
}
Die einzelnen Komponenten innerhalb der Struktur haben folgende Bedeutung:
| Member | Bedeutung |
|---|---|
| int sign | Vorzeichen der Zahl |
| unsigned long dgs_alloc | Anzahl reservierter Stellen |
| unsigned long dgs_used | Anzahl benutzter Stellen |
| unsigned int * dp | Puffer für die einzelnen Stellen der Zahl |
Es wird bei der Erzeugung jeder Zahl Speicherplatz reserviert, der gegebenenfalls vergrößert werden kann.
Dies hat den Vorteil, daß praktisch beliebig lange Zahlen verwendet werden können.
Diese Datenstruktur muß zu Programmbeginn mit der Funktion: big_init_pkg() initialisiert werden, und bei Programmende muß der reservierte Speicherplatz durch Aufruf der Funktion: big_release_pkg() wieder freigegeben werden.
Es werden außerdem einige Funktionen benötigt, welche die Konvertierung von bekannten Datentypen in die beliebig langen Integer-Zahlen (bignum) ermöglichen:
Vor Aufruf dieser Funktionen muß jedoch immer erst Speicher für die Datenstruktur bignum mit der Funktion big_create(bignum * a) reserviert werden.
| Funktion | Bedeutung |
|---|---|
| big_init_pkg() | Initialisierung der globalen Datenstrukturen |
| zu Anfang des Programms | |
| big_release_pkg() | Freigabe der globalen Datenstrukturen zu Ende des Programms |
| big_create(a) | Initialisiert Datenstruktur für große Ganzzahl a |
| bignum * a | zu initialisierende Zahl |
| big_set_ulong (value, a) | Initialisiert eine lange Zahl (bignum) mit dem Wert |
| einer unsigned long Variablen | |
| unsigned long value | Wert der Variablen, mit dem initialisiert werden soll |
| bignum * a | Eine zu initialisierende Variable vom Typ bignum |
| big_set_string (string, base, a) | Initialisiert eine lange Zahl (bignum) mit dem Wert, |
| der durch den String repräsentiert wird | |
| char * string | String, der die Zahl darstellt (z.B. 1234567890), |
| die in bignum gespeichert werden soll | |
| int base | Zahlenbasis z.B. 10, 2, 16, ... |
| bignum * a | bignum, die mit dem Wert aus dem String belegt wird |
| big_add(a, b, c) | Addiert die beiden langen Zahlen a und b |
| und legt das Ergebnis in c ab | |
| bignum * a | 1. Operand der Addition |
| bignum * b | 2. Operand der Addition |
| bignum * c | Ergebnis der Addition von a und b |
| big_sub (a, b, c) | Subtrahiert die beiden langen Zahlen a und b |
| und legt das Ergebnis in c ab | |
| bignum * a | 1. Operand der Subtraktion |
| bignum * b | 2. Operand der Subtraktion |
| bignum * c | Ergebnis der Subtraktion von a und b |
| big_mul (a, b, c) | Multipliziert die beiden langen Zahlen a und b |
| und legt das Ergebnis in c ab | |
| bignum * a | 1. Operand der Multiplikation |
| bignum * b | 2. Operand der Multiplikation |
| bignum * c | Ergebnis der Multiplikation von a und b |
enthält die internen Datenstrukturen für die Berechnungen.
#ifndef _BIGNUM_INTERNAL_H_
#define _BIGNUM_INTERNAL_H_
#define BIGNUM_DIGIT unsigned short /* Datentyp für eine Stelle der Zahl */
#define BIGNUM_TWO_DIGITS unsigned long /* Datentyp für 2 Stellen der Zahl */
#define BIG_CHARBITS 8 /* sizeof char */
#define BIGNUM_DIGIT_BITS 16 /* sizeof int */
#define BIGNUM_TWO_DIGITS_BITS 32 /* sizeof long */
struct big_struct /* Die eigentliche Datenstruktur */
{
int sign; /* Vorzeichen der Zahl */
unsigned long dgs_alloc; /* Wieviele Stellen sind reserviert */
unsigned long dgs_used; /* Wieviele Stellen sind frei */
BIGNUM_DIGIT *dp; /* Speicherplatz fuer die
/* einzelnen Stellen */
};
#endif
enthält alle wichtigen Marcos, Definitionen, und Funktionsprototypen:
#ifndef _BIGNUM_H_
#define _BIGNUM_H_
#include "internal.h"
typedef struct big_struct bignum; /* Weniger Schreibarbeit */
#define BIG_SIGN_0 0 /* Die möglichen Vorzeichen */
#define BIG_SIGN_PLUS 1
#define BIG_SIGN_MINUS -1
/* Fehlerkonstanten */
#define BIG_OK 0 /* Alles o.k. */
#define BIG_MEMERR 1 /* Zu wenig Speicher vorhanden */
#define BIG_DIV_ZERO 2 /* Division durch 0 */
#define BIG_ARGERR 3 /* Falsche Zahlenbasis */
/* Externen Variablen zur Fehlerbehandlung */
typedef int bigerr_t; /* Fehler-Variable */
extern int big_errno; /* Welcher Fehler ist aufgetreten */
extern char *big_end_string; /* Text der Fehlermeldung */
/* Prototypen der Funktionen */
/* Beschreibung : siehe im C - Source - File */
extern bigerr_t big_init_pkg();
extern void big_release_pkg();
extern bigerr_t big_create();
extern void big_destroy();
extern bigerr_t big_set_big();
extern void big_set_long();
extern void big_set_ulong();
extern bigerr_t big_set_string();
extern int big_long();
extern int big_ulong();
extern char *big_string();
extern bigerr_t big_negate();
extern int big_compare();
extern bigerr_t big_add();
extern bigerr_t big_sub();
extern bigerr_t big_mul();
#endif /* _BIGNUM_H_ */
#include "bignum.h"
#define DIGIT BIGNUM_DIGIT
#define DIGIT2 BIGNUM_TWO_DIGITS
#define TRUE (1 == 1)
#define FALSE (1 != 1)
/* minimalen Speicherplatz fuer eine Stelle bestimmen */
#define MIN_ALLOC ((sizeof(long) / sizeof(DIGIT)) << 1)
/* Bestimmen einer einzelnen Stelle in der Zahl */
/* steht nur eine 0 in der Zahl */
#define zerop(BIG) ((*(BIG)->dp == 0) && ((BIG)->dgs_used == 1))
/* Steht nur eine 1 in der Zahl */
#define uonep(BIG) ((*(BIG)->dp == 1) && ((BIG)->dgs_used == 1))
/* Vorzeichen wechseln */
#define NEGATE_SIGN(SGN) (-(SGN))
#define DIGIT_BITS BIGNUM_DIGIT_BITS
#define DIGIT2_BITS BIGNUM_TWO_DIGITS_BITS
/* Bestimmt die Wertigkeit einer Stelle */
#define DIGIT_PART(N) ((DIGIT)((N) & ((((DIGIT2)1) << DIGIT_BITS) - 1)))
/* betimmt das Vorzeichen einer Zahl */
#define RESULT_MINUSP(RES) (((RES) & ((DIGIT2)1 << (DIGIT2_BITS - 1))) != 0)
/* verschiebt Stelle nach recht ---> Division durch 2 */
#define SHIFT_DIGIT_DOWN(N) (DIGIT_PART((N) >> DIGIT_BITS))
/* verschiebt Stelle nach rechts ---> Multiplikation mit 2 */
#define SHIFT_DIGIT_UP(N) ((DIGIT2)((N) << DIGIT_BITS))
/* Betimmt min Wertigkeit in einer Zahl */
#define DIGIT_BASE (((DIGIT2)1) << DIGIT_BITS)
/* bestimmt max. Wertigkeit in einer Zahl */
#define MAX_DIGIT ((((DIGIT2)1) << DIGIT_BITS) - 1)
#define uint unsigned int
#define ulong unsigned long
extern char *malloc ();
extern int free ();
char *last_string, *big_end_string;
ulong length_last_string;
/* Array zur Kontrolle, ob aktuelle Stelle innerhalb
* der Zahl im Zahlensystem gültig ist */
char big_base_digits[] =
"00112233445566778899AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz";
/* Eigene Fehlermeldungen */
char error_string[] = "(big_errno != 0, Es ist ein Fehler Aufgetreten !)";
bignum big_one; /* Die Zahl 1 als bignum */
bignumtmp_string, /* Temporäre Variablen */
tmp_add,
tmp_mul,
tmp_q,
tmp_r;
DIGIT *tmp_digits;
ulong tmp_ulong;
/* Globale Fehlervariable, gibt Auskunft ob Rechenschritt erfolgreich war */
int big_errno = BIG_OK;
/* Wird fuer verschiedene Berechnung benötigt,
* enthält Potenzen der einzelnen Zahlen */
struct digit_blocks
{
int digCnt;
DIGIT dig_base;
}
big_block[37];
/* ---------------------------------------------------------------------- */
/* Start der Funktiondef. */
/* ---------------------------------------------------------------------- */
static char *
strchr (char *str_ptr, char ch)
/*
Sucht nach dem ersten Vorkommen von Zeichen ch im String str_ptr
gibt Pointer auf gefundenes Zeichen zurück, bzw. Wenn Zeichen nicht
gefunden wurde einen NULL Pointer.
*/
{
do
{
if (*str_ptr == ch)
{
return str_ptr;
}
}
while (*str_ptr++ != '\0');
return NULL;
}
static void
init_digit_blocks ()
/* Belegt die Datenstruktur mit den
* Umrechnungsfaktoren der einzelnen
* Zahlensysteme
*/
{
uint digcnt, base;
DIGIT maxdigit, curdigit, tmp;
for (base = 2; base <= 36; base++)
{
tmp = ((1 << (DIGIT_BITS - 1)) / base);
maxdigit = tmp * 2;
curdigit = 1;
digcnt = 0;
while (curdigit < maxdigit)
{
digcnt++;
curdigit *= base;
}
big_block[base].digCnt = digcnt;
big_block[base].dig_base = curdigit;
}
}
#define free_digits(DP, CNT) free ((char *)DP)
/* Gibt reservierten Speicherplatz
* wieder frei
*/
static DIGIT *
allocate_digits (ulong alloclen)
/* reserviert einen freien Speicherblock mit der
* Größe alloclen auf dem Heap
* Parameter:
* alloclen:Groesse des zu reservierenden Speichers
* Rueckgabe:
* Pointer auf den Speicherbereich
*/
{
DIGIT *digit_ptr;
if (big_errno != BIG_OK)
{
return NULL;
}
digit_ptr = (DIGIT *) malloc (alloclen * sizeof (DIGIT));
/* reserviert Speicher fuer alloclen * Größe einer Stelle
* --> fuer alloclen Stellen */
if (digit_ptr == NULL)
{
big_errno = BIG_MEMERR;
return NULL;
}
return digit_ptr;
}
static bigerr_t
newsize (DIGIT ** dp_p, ulong * cursize_p, ulong minsz, ulong newsz)
/* verändert die Größe
* eines Speicherblockes
* Parameter:
* dp_p:Adresse des zu aendernden Blocks
* cursize_p:Variable mit Groesse des alten Blocks
* minsz:Min. Groesse des neunen Blocks
* newsz:Gewuenschte Groesse des Neuen Blocks
*/
{
if (*cursize_p >= minsz)
{
return big_errno;
}
free_digits (*dp_p, *cursize_p); /* Gibt alten Speicherblock frei */
if (newsz < MIN_ALLOC)
{
newsz = MIN_ALLOC;
}
if ((*dp_p = allocate_digits (newsz)) == NULL)
{
return big_errno;
}
*cursize_p = newsz;
return big_errno;
}
static void
digits_cpy (DIGIT * dst, DIGIT * src, ulong count)
/* Kopiert einzelne Stellen
* von src nach dst
* Parameter:
* dst:Ziel-Variable
* src:Quell-Variable
* count:Anzahl der zu kopierenden Stellen
*/
{
while (count-- > 0)
{
*dst++ = *src++;
}
}
static DIGIT *
copy_digits (DIGIT * src, ulong cp_count, ulong alloclen)
/* Kopiert cp_count einzelne Stellen
* in einen neuen Speicherblock,
* der dynamisch allokiert wird
* Parameter:
* src:Quell-Variable
* cp_count:Anzahl zu kopierender Stellen
* alloclen:Groesse des Zielbereiches
* Rueckgabe:
* Pointer auf Zielbreich
*/
{
DIGIT *dst;
if (big_errno != BIG_OK)
{
return NULL;
}
if ((dst = allocate_digits (alloclen)) == NULL)
{
return NULL;
}
digits_cpy (dst, src, cp_count);
return dst;
}
static void
add_digit (bignum * a, DIGIT d)
/* hängt eine best Zahl Stellen d
* an eine bignum a an
* Parameter:
* a:Pointer auf Variable, an die angehaengt wird
* d:Anzuhaengende Stellen
*/
{
DIGIT2 res = d;
DIGIT *last_digit, *digit_ptr = a->dp, *digvect;
last_digit = digit_ptr + a->dgs_used; /* letzte Benutzte Stelle */
while (digit_ptr < last_digit) /* niederwertigste Stelle Suchen */
{
res = *digit_ptr + res;
*digit_ptr = DIGIT_PART (res);
res = SHIFT_DIGIT_DOWN (res);
digit_ptr++;
if (res == 0)
{
break;
}
}
if (res != 0)
{
if (a->dgs_used < a->dgs_alloc)
{
*digit_ptr = DIGIT_PART (res);
}
else
{
if ((digvect = copy_digits (a->dp, a->dgs_used,
a->dgs_used + 4)) == NULL)
{ /* vorige Zahl in neuen Bereich kopieren */
return; /* Es ist nicht genug Platz vorhanden */
}
digvect[a->dgs_used] = DIGIT_PART (res);
free_digits (a->dp, a->dgs_alloc); /* alten Bereich freigeben */
a->dgs_alloc = a->dgs_used + 4;
a->dp = digvect;
}
a->dgs_used++;
}
}
static int
ucompare_digits (bignum * a, bignum * b)
/* Ermittelt größere von 2 bignums
* Parameter:
* a:erste Zahl
* b:zweite Zahl
* Rueckgabe:
* 0:( a == b)
* 1:(a > b)
* -1:(a < b)
*/
{
DIGIT *a_ptr, *b_ptr;
if (a->dgs_used == b->dgs_used) /* Biede Zahlen haben gleich vier Stellen */
{
a_ptr = a->dp + a->dgs_used - 1;
b_ptr = b->dp + b->dgs_used - 1;
while ((*a_ptr == *b_ptr) && (a_ptr >= a->dp))
{
a_ptr--;
b_ptr--;
}
if (a_ptr < a->dp) /* beide Zahlen sind gleich */
{
return 0;
}
else
{ /* 1 wenn a > b sonst -1 */
return (*a_ptr > *b_ptr) ? 1 : -1;
}
}
return (a->dgs_used > b->dgs_used) ? 1 : -1; /* 1 a hat mehr Stellen als b */
}
static void
uadd_digits (bignum * a, bignum * b, bignum * c)
/* Macht die eigentliche Addition
* Algorithmus:
* a und b werden Stellemwiese addiert,
* und Ergebnis wird in c abgelegt
* Parameter:
* a:Erster bignum Summand
* b:Zweiter bignum Summand
* c:bignum in der Ergebnis Abgelegt werden soll
*/
{
DIGIT *dp_x, *dp_y, *dp_z, *res_dp, *end_x, *end_y;
ulong len_x, len_y;
DIGIT2 res = 0;
if (a->dgs_used > b->dgs_used) /* Falls a länger als b */
{
dp_x = a->dp; /* a entscheidet ueber länge von ergebnis */
len_x = a->dgs_used;
dp_y = b->dp;
len_y = b->dgs_used;
}
else
{
dp_x = b->dp; /* b entscheidet ueber Grösse von Ergebnis */
len_x = b->dgs_used;
dp_y = a->dp;
len_y = a->dgs_used;
}
end_x = dp_x + len_x;
end_y = dp_y + len_y;
if (c->dgs_alloc >= len_x)
{
dp_z = c->dp; /* es ist bereits genügend Platz in c resierviert */
}
else
{ /* erst noch genügend Platz in c reservieren */
if (newsize (& tmp_add.dp, &tmp_add.dgs_alloc,
len_x, len_x + 4) != BIG_OK)
{
return;
}
dp_z = tmp_add.dp;
}
res_dp = dp_z;
while (dp_y < end_y) /* Stellenweise Addition */
{
res += ((DIGIT2) * dp_x++) + *dp_y++;
*res_dp++ = DIGIT_PART (res);
res = SHIFT_DIGIT_DOWN (res);
}
while (dp_x < end_x)
{
res += *dp_x++;
*res_dp++ = DIGIT_PART (res);
res = SHIFT_DIGIT_DOWN (res);
}
if (res != 0)
{
*res_dp++ = DIGIT_PART (res);
}
if (dp_z != c->dp) /* falls Ergebnis in a oder b angelegt werden soll */
{
tmp_digits = c->dp;
c->dp = tmp_add.dp;
tmp_add.dp = tmp_digits;
tmp_ulong = c->dgs_alloc;
c->dgs_alloc = tmp_add.dgs_alloc;
tmp_add.dgs_alloc = tmp_ulong;
}
c->dgs_used = res_dp - c->dp;
}
static void
usub_digits (bignum * a, bignum * b, bignum * c)
/* Macht die eigentliche Subtraktion
* Algorithmus:
* a und b werden Stellemwiese sutrahiert,
* und Ergebnis wird in c abgelegt
* Parameter:
* a:Erste bignum Zahl
* b:Zweite bignum Zahl
* c:bignum in der Ergebnis Abgelegt werden soll
*/
{
DIGIT *dp_x, *dp_y, *dp_z, *res_dp, *end_x, *end_y;
ulong len_x, len_y;
DIGIT2 res = 0;
dp_x = a->dp;
len_x = a->dgs_used;
dp_y = b->dp;
len_y = b->dgs_used;
end_x = dp_x + len_x;
/lange der Ergbnisses bestimmen * /
end_y = dp_y + len_y;
if (c->dgs_alloc >= len_x)
{
dp_z = c->dp; /* Platz reicht aus */
}
else
{ /* zusatzlichen Paltz reservieren */
if (newsize (&tmp_add.dp, &tmp_add.dgs_alloc,
len_x, len_x + 2) != BIG_OK)
{
return;
}
dp_z = tmp_add.dp;
}
res_dp = dp_z;
while (dp_y < end_y) /* Sellenweise subtraktion */
{
res = ((DIGIT2) * dp_x++) - *dp_y++ - RESULT_MINUSP (res);
*res_dp++ = DIGIT_PART (res);
}
while (dp_x < end_x)
{
res = *dp_x++ - RESULT_MINUSP (res);
*res_dp++ = DIGIT_PART (res);
}
while ((*--res_dp == 0) && (res_dp > dp_z))
{
/* Erste von 0 versch. Zahl */
}
if (dp_z != c->dp) /* Ergebnis ablegen */
{
tmp_digits = c->dp;
c->dp = tmp_add.dp;
tmp_add.dp = tmp_digits;
tmp_ulong = tmp_add.dgs_alloc;
tmp_add.dgs_alloc = c->dgs_alloc;
c->dgs_alloc = tmp_ulong;
}
c->dgs_used = res_dp - dp_z + 1;
}
/* ---------------------------------------------------------------------- */
/* Init und Exit Funktionen */
bigerr_t
big_init_pkg ()
/*
* Init - Funktion der ganzen Funktionen,
* muss bei Prg-Start aufgerufen werden,
* um alle internen Datenstrukturen zu initialisieren
*/
{
init_digit_blocks (); /* Unsetzungstabelle berechnen */
big_create (&tmp_string); /* Temporäre Var fuer Berechnungen */
big_create (&tmp_add);
big_create (&tmp_mul);
big_create (&tmp_q);
big_create (&tmp_r);
big_set_long ((long) 1, &big_one); /* bignum mit Wert 1 erzeugen */
length_last_string = 10;
if ((last_string = malloc (length_last_string)) == NULL)
{
big_errno = BIG_MEMERR;
}
return big_errno;
}
void
big_release_pkg ()
/* Diese Funktion muss VOR
* PRG-Ende aufgerufen werden,
* damit alle resiervierten Speicherbereiche
* wieder freigegeben werden.
*/
{
big_destroy (&tmp_string);
big_destroy (&tmp_add);
big_destroy (&tmp_mul);
big_destroy (&tmp_q);
big_destroy (&tmp_r);
big_destroy (&big_one);
free (last_string);
}
bigerr_t
big_create (bignum * a)
/* reserviert Speicher fuer eine bignum,
* muss vor der benutzung der einzelenen
* Zahl aufgerufen werden.
* Parameter:
* a:Adresse der zu initialisierenden Zahl
*/
{
if (big_errno != BIG_OK)
{
return big_errno;
}
a->sign = BIG_SIGN_0; /* Zahl wird mit 0 initalisiert */
a->dgs_used = 1;
if ((a->dp = allocate_digits ((long) sizeof (long))) == NULL)
{
return big_errno;
}
a->dgs_alloc = sizeof (long); /* Platz fuer 1 Stellige Zhal reserviert */
*a->dp = 0;
return big_errno;
}
void
big_destroy (bignum * a)
/* gibt von bignum belegten Speicher
* wieder frei
* Parameter:
* a:Adresse der freizugebenden Variable
*/
{
free_digits (a->dp, a->dgs_alloc);
}
bigerr_t
big_set_big (bignum * a, bignum * b)
/* ermöglicht die Zuweisung von
* 2 bignum Zahlen (b = a)
* Parameter:
* a:Zahl, die zugewiesen werden soll
* b:Zahl, die a zugewiesen bekommt
*/
{
if ((big_errno != BIG_OK) || (a == b))
{
return big_errno;
}
if (newsize (&b->dp, &b->dgs_alloc, a->dgs_used, a->dgs_used) != BIG_OK)
{ /* reserviert evtl zusätzlichen Speicher im linken operanden */
return big_errno;
}
b->dgs_used = a->dgs_used;
b->sign = a->sign;
digits_cpy (b->dp, a->dp, a->dgs_used); /* zahl b wird nach a kopiert */
return big_errno;
}
void
big_set_ulong (ulong n, bignum * a)
/* bignum wird mit dem wert von n vorbelegt
* Parameter:
* a:bignum, die mit wert belegt wird
* n:ganze Zhal, die nach bignum konvertiert wird
*/
{
int i;
if (big_errno != BIG_OK)
{
return;
}
if (n == 0) /* Falls wert = ist --> bignum mit 0 belegen */
{
*a->dp = 0;
a->dgs_used = 1;
a->sign = BIG_SIGN_0;
}
else
/* Bignum mit wert belegen */
{
a->dgs_used = 0;
for (i = 0; i < sizeof (long) / sizeof (DIGIT); i++)
{
a->dgs_used++;
a->dp[i] = DIGIT_PART (n);
n = SHIFT_DIGIT_DOWN (n);
}
a->sign = BIG_SIGN_PLUS;
}
}
bigerr_t
big_set_string (char *numstr, int base, bignum * a)
/* Belegt den Wert einer bignum mit den Wert,
* der durch einen String dargestellt wird
*
* Als Basis sind alle möglichen Zahlensysteme erlaubt
* Parameter:
* numstr:Zeichenkette, die den Zahlenwert darstellt
* base:Zahlenbasis, z.B. 10, 2, 16, 3, ...
* a:bignum-Variable, die entspeched belegt wird
*/
{
char *src = numstr, *maxdigit, *chrptr;
DIGIT dig_base, dig_sum, last_base;
int cnt, maxcnt;
if (big_errno != BIG_OK)
{
return big_errno;
}
big_end_string = numstr;
if ((base < 2) || (base > 36))
{ /* illegales Zhalensystem wurde angegeben */
big_errno = BIG_ARGERR;
return big_errno;
}
maxdigit = big_base_digits + (base << 1);
/* groestmoegliche Zahl im Zahlensystem bestimmen */
maxcnt = big_block[base].digCnt;
dig_base = big_block[base].dig_base;
a->dgs_used = 1; /* bignum initialisieren mit 1 stelliger zahl */
*a->dp = 0;
a->sign = BIG_SIGN_PLUS;
while (strchr (" \t\n\r", *src) != NULL) /* Whitespaces ueberlesen */
{
src++;
}
if ((*src == '-') || (*src == '+')) /* mögliches Vz beachten */
{
a->sign = (*src == '-') ? BIG_SIGN_MINUS : BIG_SIGN_PLUS;
src++;
}
chrptr = strchr (big_base_digits, *src);
/* ist aktuelles Zeichen im Zahlensystem erlaubt */
if ((chrptr == NULL) || (chrptr >= maxdigit))
{
big_end_string = src;
big_errno = BIG_ARGERR;
return big_errno;
}
while (*src == '0') /* führende '0' überlesen */
{
src++;
}
chrptr = strchr (big_base_digits, *src);
/* ist aktuelles Zeichen im Zahlensystem erlaubt */
if ((chrptr == NULL) || (chrptr >= maxdigit))
{ /* folgendes Zeichen ist ungültig */
big_end_string = src;
a->sign = BIG_SIGN_0; /* es wird nur eine '0' angelegt */
return big_errno;
}
dig_sum = 0;
cnt = 0;
while ((chrptr = strchr (big_base_digits, *src)),
(chrptr != NULL) && (chrptr < maxdigit))
/* die folgenden Stellen werden entspechend ihrer Wertigkeit
entsprechned aufaddiert und das Ergebnis wird als bignum
abgelegt */
{
dig_sum = dig_sum * base + ((chrptr - big_base_digits) >> 1);
if (++cnt >= maxcnt)
{
umul_digit (a, dig_base);
add_digit (a, dig_sum);
dig_sum = 0;
cnt = 0;
}
src++;
}
if (cnt > 0)
{ /* Es gab einen Uebertrag */
last_base = base;
while (--cnt > 0)
{
last_base *= base;
}
umul_digit (a, last_base);
add_digit (a, dig_sum);
}
big_end_string = src;
return big_errno;
}
int
big_ulong (bignum * a, ulong * n)
/* die Zahl bignum wird in eine
* unsigned long Varaible konvertieren
* Parameter:
* a:Umzuwandelnde bignum Zahl
* n:Zielvariable
* Achtung:wenn bignum nich mit Zahlenbreich von
* Zielvariable darstellbar ist, so erfolgt
*KEINE konvertierung !!!
*/
{
ulong old_n;
DIGIT *dp;
if (big_errno != BIG_OK)
{
return FALSE;
}
if (a->dgs_used > sizeof (ulong) / sizeof (DIGIT))
{
return FALSE; /* die bignum ist zu groß fuer ulong Varialbe */
}
dp = a->dp + a->dgs_used - 1;
old_n = *n = *dp--;
while ((dp >= a->dp) && (old_n < *n))
{ /* Wert von Bignum stellenmäßig berechnen
* und in ulang var ablegen */
old_n = *n;
*n = SHIFT_DIGIT_UP (*n) + *dp--;
}
if (old_n >= *n)
{
return FALSE;
}
return FALSE;
}
bigerr_t
big_negate (bignum * a, bignum * b)
/* Kehrt VZ einer bignum Zahl um
* und speichert Ergebnis in neuer
* bignum Zahl ab (a = -b)
* Parameter:
* b:zu negierende Zahl
* a:bekommt b zugewiesen
*/
{
big_set_big (a, b);
b->sign = NEGATE_SIGN (a->sign);
return big_errno;
}
int
big_compare (bignum * a, bignum * b)
/* vergeicht 2 bignum Zahlen
* und liefert Ergebnis der Vergleiches
* Parameter:
* a:erste bignum-Zahl
* b:zweite bignum-Zahl
* Rueckgabe:
* 0:die zahlen sind gleich (a == b)
* 1:bignum a ist groesser (a > b)
* -1:bignum b ist groesser (a < b)
*/
{
if (a->sign == b->sign)
{
if (a->sign == 0) /* Die Zahlen sind gleich */
{
return 0;
}
return
(a->sign == BIG_SIGN_MINUS)
? -ucompare_digits (a, b) /* a < b */
: ucompare_digits (a, b); /* a > b */
}
return b->sign - a->sign;
}
bigerr_t
big_add (bignum * a, bignum * b, bignum * c)
/* Hilfsfunktion:
* addiert a und b und
* legt Ergebnis in c ab ( c = a + b)
* Parameter:
* a:erste bignum Zahl
* b:zweite bignum Zahl
* c:bignum, wo Ergebnis abgelegt wird
*/
{
int cmp;
if (big_errno != BIG_OK)
{
return big_errno;
}
if (a->sign == b->sign) /* Gleiches VZ --> Addition */
{
uadd_digits (a, b, c);
c->sign = a->sign;
}
else
/* Verschiedene VZ --> Subtraktion */
{
cmp = ucompare_digits (a, b);
if (cmp < 0)
{
usub_digits (b, a, c);
if (zerop (c))
{
c->sign = BIG_SIGN_0;
}
else
{
c->sign = b->sign;
}
}
else if (cmp > 0)
{
usub_digits (a, b, c);
if (zerop (c))
{
c->sign = BIG_SIGN_0;
}
else
{
c->sign = a->sign;
}
}
else
{
c->dgs_used = 1;
*c->dp = 0;
c->sign = BIG_SIGN_0;
}
}
return big_errno;
}
bigerr_t
big_sub (bignum * a, bignum * b, bignum * c)
/* Hilfsfunktion:
* subtrahiert a und b und
* legt Ergebnis in c ab ( c = a - b)
* Parameter:
* a:erste bignum Zahl
* b:zweite bignum Zahl
* c:bignum, wo Ergebnis abgelegt wird
*/
{
int cmp;
if (big_errno != BIG_OK)
{
return big_errno;
}
if (a->sign == BIG_SIGN_0) /* a ist 0 */
{
big_set_big (b, c);
big_negate (c, c);
return big_errno;
}
if (b->sign == BIG_SIGN_0) /* b ist 0 */
{
big_set_big (a, c);
return big_errno;
}
cmp = ucompare_digits (a, b);
if (cmp <= 0)
{
if (a->sign != b->sign)
{
uadd_digits (a, b, c);
c->sign = a->sign;
}
else
{
usub_digits (b, a, c);
c->sign = (zerop (c) ? BIG_SIGN_0 : NEGATE_SIGN (a->sign));
}
}
else if (cmp > 0)
{
if (a->sign != b->sign)
{
uadd_digits (a, b, c);
c->sign = a->sign;
}
else
{
usub_digits (a, b, c);
c->sign = (zerop (c) ? BIG_SIGN_0 : b->sign);
}
}
else
{
c->dgs_used = 1;
*c->dp = 0;
c->sign = BIG_SIGN_0;
}
return big_errno;
}
bigerr_t
big_mul (bignum * a, bignum * b, bignum * c)
/* Hilfsfunktion:
* multipliziert a und b und
* legt Ergebnis in c ab ( c = a * b)
* Parameter:
* a:erste bignum Zahl
* b:zweite bignum Zahl
* c:bignum, wo Ergebnis abgelegt wird
*/
{
DIGIT *dp_x, *dp_xstart, *dp_xend;
DIGIT *dp_y, *dp_ystart, *dp_yend;
DIGIT *dp_z, *dp_zstart, *dp_zend, *dp_zsumstart;
ulong len_x, len_y, len_z;
DIGIT2 res;
DIGIT tmp_res;
if (big_errno != BIG_OK)
{
return big_errno;
}
if (zerop (a) || zerop (b))
{
c->sign = BIG_SIGN_0;
c->dgs_used = 1;
*c->dp = 0;
return big_errno;
}
if (uonep (a))
{
big_set_big (b, c);
c->sign = (a->sign == b->sign) ? BIG_SIGN_PLUS : BIG_SIGN_MINUS;
return big_errno;
}
if (uonep (b))
{
big_set_big (a, c);
c->sign = (a->sign == b->sign) ? BIG_SIGN_PLUS : BIG_SIGN_MINUS;
return big_errno;
}
if (a->dgs_used < b->dgs_used)
{
dp_xstart = a->dp;
len_x = a->dgs_used;
dp_ystart = b->dp;
len_y = b->dgs_used;
}
else
{
dp_xstart = b->dp;
len_x = b->dgs_used;
dp_ystart = a->dp;
len_y = a->dgs_used;
}
if ((c == a) || (c == b))
{
if (newsize (&tmp_mul.dp, &tmp_mul.dgs_alloc,
len_x + len_y, len_x + len_y + 2) != BIG_OK)
{
return big_errno;
}
dp_zsumstart = tmp_mul.dp;
len_z = tmp_mul.dgs_alloc;
}
else
{
if (newsize (&c->dp, &c->dgs_alloc,
len_x + len_y, len_x + len_y + 2) != BIG_OK)
{
return big_errno;
}
dp_zsumstart = c->dp;
len_z = c->dgs_alloc;
}
dp_xend = dp_xstart + len_x;
dp_yend = dp_ystart + len_y;
dp_zend = dp_zsumstart + len_y;
for (dp_z = dp_zsumstart; dp_z < dp_zend; dp_z++)
{
*dp_z = 0; /* Zero out rightmost digits */
}
dp_zstart = dp_zsumstart;
for (dp_x = dp_xstart; dp_x < dp_xend; dp_x++)
{
dp_z = dp_zstart;
tmp_res = 0;
for (dp_y = dp_ystart; dp_y < dp_yend; dp_y++)
{
res = (DIGIT2) (*dp_x) * (*dp_y) + (*dp_z) + tmp_res;
*dp_z++ = DIGIT_PART (res);
tmp_res = SHIFT_DIGIT_DOWN (res);
}
*dp_z = tmp_res;
dp_zstart++;
}
if (dp_zsumstart != c->dp)
{
tmp_digits = c->dp;
c->dp = tmp_mul.dp;
tmp_mul.dp = tmp_digits;
tmp_ulong = c->dgs_alloc;
c->dgs_alloc = tmp_mul.dgs_alloc;
tmp_mul.dgs_alloc = tmp_ulong;
}
if (*dp_z == 0)
{
dp_z--;
}
c->dgs_used = dp_z - dp_zsumstart + 1;
c->sign = a->sign * b->sign;
return big_errno;
}
testet alle wichtigen Funktionen (verwendet nur geringe Stellenzahl)
#include <stdio.h>
#include "bignum.h"
main ()
{
ulong value1, value 2;
ulong ergebnis;
bignum a, b, c;
value1 = 12345;
value2 = 54321;
big_init_pkg (); /* Alle Variablen initialisieren */
/* Platz für bignums reservieren */
big_create (&a); /* Operand 1 */
big_create (&b); /* Operand 2 */
big_create (&c); /* Ergebnis */
/* bignums mit Werten belegen */
big_set_ulong (value1, &a); /* 1. Operand */
big_set_ulong (value2, &b); /* 2. Operand */
/* Addition durchführen */
big_add (&a, &b, &c);
/* Ergebnis zurück konvertieren */
big_long (&c, &ergebnis);
/* Ergebnis ausgeben */
printf ("Ergebnis: %ul\n", ergebnis);
/* Reservierten Speicher freigeben */
big_destroy (&Zahl1); /* Operand 1 */
big_destroy (&Zahl2); /* Operand 2 */
big_destroy (&Ergebnis); /* Ergebnis */
big_release_pkg (); /* Globale Datenstrukturen freigeben */
}
testet weitere Funktionen (verwendet sehr große Stellenzahl)
Es werden hier die beiden folgenden Zahlen Zahl1 und Zahl2 multipliziert, und das Ergebnis wird ausgegeben.
Zahl1 mit 105 Stellen:
16311784525650292068755854365669702024741136446212
03858931609458045532501874726047433264764355226803
78897
Zahl2 mit 75 Stellen:
78853915247995992358347387072972515879664753888371
8863262181413347391236469
Ergebnis = (Zahl1 * Zahl2), 180 Stellen:
12862480745292006410890272858478665047052244641713
57804194346814698101043793016009864587782936724194
24400367611751818467130949025218486854306250248762
104794478806532579114244394693
Bei diesem Beispiel kann festgestellt werden, da ß das Ergebnis unter LINUX praktisch genau so schnell wie das des vorigen Beispiels berechnet werden kann.
Unter DOS jedoch ergibt sich eine Vervielfachung der Berechnungsdauer, was jedoch vermutlich daran liegt, da ß hier nur 16 bit Berechnungen durchgeführt werden, und nicht wie unter LINUX 32 bit.
#include<stdio.h>
#include "bignum.h"
main ()
{
bignum Zahl1, Zahl2, Ergebnis;
big_init_pkg (); /* Alle Variablen initialisieren */
/* Platz für bignums reservieren */
big_create (&Zahl1); /* Operand 1 */
big_create (&Zahl2); /* Operand 2 */
big_create (&Ergebnis); /* Ergebnis */
/* bignums mit Werten belegen */
/* 1. Operand */
big_set_string ("16311784525650292068755854365669702024741136446212"
"03858931609458045532501874726047433264764355226803"
"78897", 10, &Zahl1);
/* 2. Operand */
big_set_string ("78853915247995992358347387072972515879664753888371"
"8863262181413347391236469", 10, &Zahl2);
/* Multiplikation durchführen */
big_mul (&Zahl1, &Zahl2, &Ergebnis);
/* Ergebnis zurück konvertieren */
puts (big_string (&Ergebnis, 10);
/* Reservierten Speicher freigeben */
big_destroy (&Zahl1); /* Operand 1 */
big_destroy (&Zahl2); /* Operand 2 */
big_destroy (&Ergebnis); /* Ergebnis */
big_release_pkg (); /* Globale Datenstrukturen freigeben */
}