tiny bignum c

tiny-bignum-c

cでの小さな複数の精度の整数実装

説明

大量の計算のために、Cの小さな携帯性任意の前提条件の署名されていない整数算術。

各単語のすべてのビットを使用して、基礎となるデータタイプとしてuint8_t 、 uint16_t 、またはuint32_tの配列を使用します。

ナンバーベースは、選択されたワードサイズに応じて0x100、0x10000、または0x100000000です - 明確化については、ヘッダーファイルbn.hを参照してください。

動的メモリ管理は使用されず、 stdio.hはヘックスストリングとの間での対応機能のテストにのみ使用されます。

現在のステータス

基本的な算術（+、 - 、 *、 /、％）およびビットワイズ操作（＆、|、 ^。<<、>>）プラス増分、減少、比較がサポートされています。

設計目標

このライブラリの主な設計目標は、容認できるパフォーマンスと機能の完全性を保持しながら、小さく、正しい、自己閉じ込められ、ほとんどリソースを使用することです。コードの明確さも非常に高く評価されています。

注目すべき機能と省略

• 小型コードとバイナリサイズ：x86の〜500スロック、〜3kbバイナリ。静的＃メモリの使用 /割り当てを定義します。
• 動的メモリ割り当ての使用はありません（つまり、 malloc / freeへの呼び出しはありません）。
• PythonのBig-Integersに対して検証されたランダム化テスト
• 最適なメモリの利用、数値ベースは1 + uint {8,16,32} _maxです。

API

これは使用されるデータ構造であり、DTYPEは#define 'dから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桁以上の数字）。

よくある質問

• Q：このライブラリと他のC Big Integerの実装を区別するものは何ですか？

  A：1つは小さいサイズ。適度な量のRAMのみを使用して、2〜3kbのROMに500行のCコードコンパイルをコンパイルします。通常の選択である10の代わりに、番号ベース2^{8,16,32}を使用して、すべてのビットを使用します。

• Q：なぜ64ビットワードサイズのサポートがないのですか？

  A：すべての計算は、単語サイズよりも大きくする必要がある一時的な変数で行われます（オーバーフローなどを検出するには）。したがって、64ビットワードサイズは、たとえば128ビットの温度varを必要とします。 C99は、最大64ビットまでのポータブル整数のみをサポートしています。

ライセンス

このリポジトリのすべての資料はパブリックドメインにあります。