tiny bignum c

微小bignum-c

C中的小型多精度整數實現

描述

C中的小型便攜式定義無符號整數算術，用於大量計算。

使用每個單詞中的所有位，使用uint8_t ， uint16_t或uint32_t的數組作為基礎數據類型。

數字基為0x100、0x10000或0x100000000，具體取決於所選的單詞大小 - 請參閱標題文件bn.h以進行澄清。

沒有使用動態內存管理，而stdio.h僅用於測試與十六進制的解析功能。

當前狀態

支持基本算術（+， - ， *， /，％）和位操作（＆，|， ^。<<，>>）加上增量，減少和比較。

設計目標

該庫的主要設計目標是小，正確，自我包含，並使用很少的資源，同時保留可接受的性能和功能完整性。代碼的清晰度也很高。

著名的功能和遺漏

• 小型代碼和二進制尺寸：〜500 sloc，〜3kb二進制X86。靜態＃定義內存使用 /分配。
• 無需使用動態內存分配（即無需撥打malloc / free ）。
• 對Python的大智能者的隨機測試
• 最佳內存利用率，數字庫為1 + UINT {8,16,32} _max。

API

這是使用的數據結構，其中dtype是#define to uint8_t ， uint16_t或uint32_t 。

 struct bn
{
  DTYPE array [ BN_ARRAY_SIZE ];
};

這是公共 /導出的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 */

用法

在bn.h中設置BN_ARRAY_SIZE ，以確定要使用的數字的大小。默認選擇是1024位數字。將WORD_SIZE設置為{1,2,4}以使用uint8_t ， uint16_t或uint32_t作為基礎數據結構。

運行make clean all test以獲取使用示例和一些隨機測試。

例子

有關如何計算階乘（100）或100的示例，請參見tests/factorial.c 。 （150多位數字）。

常問問題

• 問：該庫與其他C大整數實現區別是什麼？

  答：一個小尺寸。 〜500行的C代碼將僅使用適度的RAM編譯為2-3KB ROM。利用所有位，使用數字鹼基2^{8,16,32}而不是10，這是通常的選擇。

• 問：為什麼不支持64位單詞大小？

  答：所有計算均以臨時變量進行，該變量需要大於單詞大小（以檢測溢出等）。因此，64位單詞大小將需要128位的溫度var。 C99僅支持高達64位的便攜式整數。

執照

該存儲庫中的所有材料都在公共領域。