tiny bignum c

Tiny-Bignum-C

Uma pequena implementação inteira de precisão múltipla em C em C

Descrição

Pequena aritmética inteira não assinada por precisão arbitrária portátil em C, para calcular com grandes números.

Usa uma matriz de uint8_t , uint16_t ou uint32_t como tipo de dados subjacente utilizando todos os bits em cada palavra.

A base do número é 0x100, 0x10000 ou 0x100000000, dependendo do tamanho da palavra escolhido-consulte o arquivo de cabeçalho BN.H para esclarecimento.

Nenhum gerenciamento dinâmico de memória é utilizado e stdio.h é usado apenas para testar funções analisando de e para strings hexadecimais.

Status atual

Operações aritméticas básicas (+, -, *, /, %) e bit -butwise (&, |, ^. <<, >>) mais incrementos, decréscimos e comparações são suportados.

Objetivos de design

O principal objetivo do design desta biblioteca é ser pequeno, correto, independente e usar poucos recursos, mantendo o desempenho aceitável e a integridade. A clareza do código também é altamente valorizada.

Recursos e omissões notáveis

• Código pequeno e tamanho binário: ~ 500 sloc, ~ 3kb binário para x86. Estaticamente #Defina o uso / alocação de memória.
• Não há uso de alocação de memória dinâmica (ou seja, sem chamadas para malloc / free ).
• Testes randomizados validados contra os grandes interescedores de Python
• Utilização ideal da memória, a base de números é 1 + uint {8,16,32} _max.

API

Esta é a estrutura de dados usada, onde o dtype é #define 'd para uint8_t , uint16_t ou uint32_t .

 struct bn
{
  DTYPE array [ BN_ARRAY_SIZE ];
};

Esta é a API pública / exportada:

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

Uso

Defina BN_ARRAY_SIZE em bn.h para determinar o tamanho dos números que você deseja usar. A escolha padrão é de 1024 bits. Defina WORD_SIZE como {1,2,4} para usar uint8_t , uint16_t ou uint32_t como estrutura de dados subjacente.

Execute make clean all test os exemplos de uso e para alguns testes aleatórios.

Exemplos

Consulte tests/factorial.c para um exemplo de como calcular o fatorial (100) ou 100! (um número de mais de 150 dígitos).

Perguntas frequentes

• P: O que diferencia esta biblioteca de outras implementações do C Big Integer?

  A: tamanho pequeno para um. ~ 500 linhas de código C compilando para 2-3kb ROM, usando apenas quantidades modestas de RAM. Utilizando todos os bits usando uma base numérica 2^{8,16,32} em vez de 10, que é uma escolha usual.

• P: Por que nenhum suporte para tamanho de palavra de 64 bits?

  R: Todos os cálculos são feitos em uma variável temporária, que precisa ser maior que o tamanho da palavra (para detectar transbordamento etc.). Portanto, o tamanho das palavras de 64 bits precisaria de EG 128 bits temp-Var. O C99 suporta apenas números inteiros portáteis de até 64 bits.

Licença

Todo o material deste repositório é de domínio público.