tiny bignum c

Tiny-Bignum-C

c

설명

C의 작은 휴대용 임의의-부호없는 정수 산술, 많은 수로 계산.

uint8_t , uint16_t 또는 uint32_t 배열을 각 단어의 모든 비트를 사용하여 기본 데이터 유형으로 사용합니다.

숫자 기반은 선택한 단어 크기에 따라 0x100, 0x10000 또는 0x100000000입니다. 설명은 헤더 파일 BN.H를 참조하십시오.

동적 메모리 관리는 사용되지 않으며 stdio.h 16 진수를 오가는 것만으로 만 사용됩니다.

현재 상태

기본 산술 (+, -, *, /, %) 및 비트 타이 작업 (&, |, ^. <<, >>)+증분, 감소 및 비교가 지원됩니다.

디자인 목표

이 라이브러리의 주요 디자인 목표는 작고 정확하며 자체적으로 포함되어 있으며 수용 가능한 성능과 기능 완전성을 유지하면서 자원이 거의 없습니다. 코드의 명확성도 높이 평가됩니다.

주목할만한 기능 및 누락

• 작은 코드 및 이진 크기 : ~ 500 SLOC, x86 용 ~ 3KB 바이너리. 정적 #정의 메모리 사용 / 할당.
• 동적 메모리 할당을 사용하지 않습니다 (즉, malloc / free 에 대한 호출 없음).
• 무작위 테스트는 Python의 큰 인내에 대해 검증되었습니다
• 최적의 메모리 활용도, 숫자베이스는 1 + uint {8,16,32} _max입니다.

API

이것은 사용 된 데이터 구조이며, 여기서 dtype는 #define 'd 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_ARRAY_SIZE bn.h 로 설정하여 사용하려는 숫자의 크기를 결정하십시오. 기본 선택은 1024 비트 숫자입니다. uint8_t , uint16_t 또는 uint32_t 기본 데이터 구조로 사용하려면 WORD_SIZE {1,2,4}로 설정하십시오.

실행 사용 예와 임의의 테스트를 위해 make clean all test .

예

Factorial (100) 또는 100을 계산하는 방법의 예는 tests/factorial.c 참조하십시오! (150 개 이상의 숫자).

FAQ

• Q :이 라이브러리를 다른 C 대형 정수 구현과 구별하는 것은 무엇입니까?

  A : 하나의 작은 크기. ~ 500 줄의 C 코드 라인 2-3KB ROM으로, 겸손한 양의 RAM 만 사용합니다. 10 대가 아닌 숫자 base 2^{8,16,32}를 사용하여 모든 비트를 사용합니다. 이는 일반적인 선택입니다.

• Q : 64 비트 단어 크기를 지원하지 않는 이유는 무엇입니까?

  A : 모든 계산은 임시 변수로 수행되며, 이는 단어 크기보다 커야합니다 (오버플로 등을 감지하기 위해). 따라서 64 비트 단어 크기는 예를 들어 128 비트 템프 바르가 필요합니다. C99는 최대 64 비트의 휴대용 정수 만 지원합니다.

특허

이 저장소의 모든 재료는 공개 도메인에 있습니다.