tiny bignum c
1.0.0
Kleine tragbare willkürliche, vorzeichenlose Ganzzahlarithmetik in C zur Berechnung mit großen Zahlen.
Verwendet ein Array von uint8_t , uint16_t oder uint32_t als zugrunde liegende Datentyp, wobei alle Bits in jedem Wort verwendet werden.
Die Zahlenbasis beträgt 0x100, 0x10000 oder 0x100000000, abhängig von der ausgewählten Wortgröße-siehe Header-Datei Bn.H zur Klärung.
Es wird kein dynamisches Speichermanagement verwendet, und stdio.h wird nur zum Testen von Funktionen verwendet, die an und von Hex-Sace analysieren.
Basisarithmetische (+, -, *, /, %) und bitweise Operationen (&, |, ^. <<, >>) Plus Inkremente werden Dekremente und Vergleiche unterstützt.
Das Hauptziel dieser Bibliothek ist es, kleine, korrekte, selbsthaltige und nur wenige Ressourcen zu verwenden und gleichzeitig akzeptable Leistung und Vollständigkeit beizubehalten. Die Klarheit des Codes ist ebenfalls hoch geschätzt.
malloc / free ). Dies ist die verwendete Datenstruktur, wobei DTYPE #define 'd bis uint8_t , uint16_t oder uint32_t ist.
struct bn
{
DTYPE array [ BN_ARRAY_SIZE ];
};Dies ist die öffentliche / exportierte API:
/* Initialization functions: */
void bignum_init ( struct bn * n ); /* n gets zero-initialized */
void bignum_from_int ( struct bn * n , DTYPE_TMP i );
int bignum_to_int ( struct bn * n );
/* NOTE: The functions below are meant for testing mainly and expects input in hex-format and of a certain length */
/* See the implementation for details or the test-files for examples of how to use them. */
void bignum_from_string ( struct bn * n , char * str , int nbytes );
void bignum_to_string ( struct bn * n , char * str , int maxsize );
/* Basic arithmetic operations: */
void bignum_add ( struct bn * a , struct bn * b , struct bn * c ); /* c = a + b */
void bignum_sub ( struct bn * a , struct bn * b , struct bn * c ); /* c = a - b */
void bignum_mul ( struct bn * a , struct bn * b , struct bn * c ); /* c = a * b */
void bignum_div ( struct bn * a , struct bn * b , struct bn * c ); /* c = a / b */
void bignum_mod ( struct bn * a , struct bn * b , struct bn * c ); /* c = a % b */
void bignum_divmod ( struct bn * a , struct bn * b , struct bn * c , struct bn * d ); /* c = a/b, d = a%b */
/* Bitwise operations: */
void bignum_and ( struct bn * a , struct bn * b , struct bn * c ); /* c = a & b */
void bignum_or ( struct bn * a , struct bn * b , struct bn * c ); /* c = a | b */
void bignum_xor ( struct bn * a , struct bn * b , struct bn * c ); /* c = a ^ b */
void bignum_lshift ( struct bn * a , struct bn * b , int nbits ); /* b = a << nbits */
void bignum_rshift ( struct bn * a , struct bn * b , int nbits ); /* b = a >> nbits */
/* Special operators and comparison */
int bignum_cmp ( struct bn * a , struct bn * b ); /* Compare: returns LARGER, EQUAL or SMALLER */
int bignum_is_zero ( struct bn * n ); /* For comparison with zero */
void bignum_inc ( struct bn * n ); /* Increment: add one to n */
void bignum_dec ( struct bn * n ); /* Decrement: subtract one from n */
void bignum_pow ( struct bn * a , struct bn * b , struct bn * c ); /* Calculate a^b -- e.g. 2^10 => 1024 */
void bignum_isqrt ( struct bn * a , struct bn * b ); /* Integer square root -- e.g. isqrt(5) => 2 */
void bignum_assign ( struct bn * dst , struct bn * src ); /* Copy src into dst -- dst := src */ Setzen Sie BN_ARRAY_SIZE in bn.h um die Größe der Zahlen zu bestimmen, die Sie verwenden möchten. Die Standardauswahl beträgt 1024 Bitnummern. Setzen Sie WORD_SIZE auf {1,2,4}, um uint8_t , uint16_t oder uint32_t als zugrunde liegende Datenstruktur zu verwenden.
Run make clean all test für Beispiele für die Nutzung und einige zufällige Tests.
Siehe tests/factorial.c für ein Beispiel für die Berechnung der Faktoren (100) oder 100! (eine über 150 -stellige Ziffernzahl).
F: Was unterscheidet diese Bibliothek von anderen Cig Integer -Implementierungen von C big?
A: Kleine Größe für einen. ~ 500 Zeilen C-Code-Kompilieren zu 2-3 KB ROM mit nur bescheidenen Mengen RAM. Verwendung aller Bits unter Verwendung einer Zahlenbasis 2^{8,16,32} anstelle von 10, was eine übliche Wahl ist.
F: Warum keine Unterstützung für 64-Bit-Wortgröße?
A: Alle Berechnungen werden in einer vorübergehenden Variablen durchgeführt, die größer sein muss als die Wortgröße (um Überlauf usw. zu erkennen). Daher müsste 64-Bit-Wortgröße z. B. 128-Bit-Temp-Var erforderlich. C99 unterstützt nur tragbare ganze Zahlen bis zu 64 Bit.
Das gesamte Material in diesem Repository ist gemeinfrei.
