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位的便携式整数。

执照

该存储库中的所有材料都在公共领域。