tiny bignum c

Tiny-bignum-C

Implementasi integer multi-presisi kecil di C

Keterangan

Portabel kecil presisi arbitrer Aritmatika integer unsigned dalam C, untuk menghitung dengan jumlah besar.

Menggunakan array uint8_t , uint16_t atau uint32_t sebagai tipe data yang mendasari menggunakan semua bit dalam setiap kata.

Basis angka adalah 0x100, 0x10000 atau 0x100000000 tergantung pada ukuran kata yang dipilih-lihat file header bn.h untuk klarifikasi.

Tidak ada manajemen memori dinamis yang digunakan, dan stdio.h hanya digunakan untuk fungsi pengujian yang dikurangi ke dan dari string hex.

Status saat ini

Aritmatika dasar (+, -, *, /, %) dan operasi bitwise (&, |, ^. <<, >>) plus kenaikan, penurunan dan perbandingan didukung.

Tujuan desain

Tujuan desain utama dari perpustakaan ini adalah menjadi kecil, benar, mandiri dan menggunakan sedikit sumber daya sambil mempertahankan kinerja yang dapat diterima dan kelengkapan fitur. Kejelasan kode juga sangat dihargai.

Fitur dan kelalaian yang terkenal

• Kode Kecil dan Ukuran Biner: ~ 500 Sloc, ~ Biner 3KB untuk X86. Secara statis #define'd memori penggunaan / alokasi.
• Tidak menggunakan alokasi memori dinamis (yaitu tidak ada panggilan ke malloc / free ).
• Pengujian acak divalidasi terhadap Integer Besar Python
• Pemanfaatan memori yang optimal, basis angka adalah 1 + uint {8,16,32} _max.

API

Ini adalah struktur data yang digunakan, di mana dType adalah #define 'd ke uint8_t , uint16_t atau uint32_t .

 struct bn
{
  DTYPE array [ BN_ARRAY_SIZE ];
};

Ini adalah API publik / diekspor:

 /* 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 */

Penggunaan

Atur BN_ARRAY_SIZE di bn.h untuk menentukan ukuran angka yang ingin Anda gunakan. Pilihan default adalah 1024 bit nomor. Atur WORD_SIZE ke {1,2,4} untuk menggunakan uint8_t , uint16_t atau uint32_t sebagai struktur data yang mendasarinya.

Jalankan make clean all test untuk Contoh Penggunaan dan untuk beberapa pengujian acak.

Contoh

Lihat tests/factorial.c untuk contoh cara menghitung faktorial (100) atau 100! (nomor 150+ digit).

FAQ

• T: Apa yang membedakan perpustakaan ini dari implementasi C Big Integer lainnya?

  A: Ukuran kecil untuk satu. ~ 500 baris C-code yang dikompilasi ke ROM 2-3KB, hanya menggunakan RAM dalam jumlah sederhana. Memanfaatkan semua bit dengan menggunakan basis angka 2^{8,16,32} bukan 10 yang merupakan pilihan biasa.

• T: Mengapa tidak ada dukungan untuk ukuran kata 64-bit?

  A: Semua perhitungan dilakukan dalam variabel sementara, yang perlu lebih besar dari ukuran kata (untuk mendeteksi overflow dll.). Jadi ukuran kata 64-bit akan membutuhkan EG 128-bit Temp-Var. C99 hanya mendukung bilangan bulat portabel hingga 64-bit.

Lisensi

Semua materi dalam repositori ini ada di domain publik.