Manipulação de inteiros grandes

O objetivo deste trabalho é construir uma biblioteca para manipulação de inteiros grandes. A biblioteca deverá prover algumas operações aritméticas básicas (somar, subtrair, multiplicar) e operações de deslocamento de bits.

A biblioteca deve ser implementada em C, usando a seguinte definição para o tipo do inteiro grande:

	
typedef unsigned char *BigInt;

Uma variável do tipo BigInt é representada por um array de bytes que deve ser interpretado como um único inteiro de N bits, em complemento a dois, seguindo a ordem little-endian. O valor de N será fornecido na inicialização da biblioteca (ver abaixo). Desta forma, o array:

Especificação da Biblioteca

/* Inicialização da biblioteca */

/* nbits sempre maior que 0 e múltiplo de 8 */
void bi_init (int nbits);

/* Criação e destruição */

/* cria novo BigInt com valor inicial val */
BigInt bi_new (int val);

/* destroi BigInt */
void bi_destroy (BigInt a);

/* Operacoes basicas */

/* a + b */
BigInt bi_sum (BigInt a, BigInt b);

/* -a */
BigInt bi_minus (BigInt a);

/* a - b */
BigInt bi_sub (BigInt a, BigInt b);

/* a * b */
BigInt bi_mul (BigInt a, BigInt b);

/* Operacoes de deslocamento */

/* desloca a de n bits para a direita */
BigInt bi_shr (BigInt a, int n);

/* desloca a de n bits para a esquerda */
BigInt bi_shl (BigInt a, int n);

O produto deste trabalho deve ser um arquivo em C com nome "bigint.c" contendo apenas a implementação das funções acima. O arquivo bigint.c deverá conter a linha

#include bigint.h

Testando as funções

   #include "bigint.h"

Crie seu programa executável teste com a linha:

   gcc -Wall -o teste bigint.c teste.c

Recomendações:

• Construa suas funções uma a uma e vá testando-as aos poucos, em vez de escrever o código todo de uma vez sem testar as funções individualmente. É receita de desgraça certa deixar para testar tudo no final!
• Não se esqueça de testar bem seu programa antes de entregá-lo!
• Algumas das operações possuem uma implementação evidente, enquanto que outras requerem um pouco mais de investigação. Por este motivo, os trabalhos também serão julgados pela sua eficiência (atenção na implementação da multiplicação!!!).

Prazo: 24/09 (até a meia noite)

Entrega

• Devem ser entregues dois únicos arquivos, bigint.c, contendo a implementação das funções pedidas (e eventualmente, funções auxiliares) e um arquivo rel.txt, contendo um relatório em texto (ver abaixo).
• O arquivo bigint.c *não* deve conter uma função main.
• O trabalho deve ser enviado por email para o professor da turma, com subject/assunto "Trabalho 1 - Software Basico". Indique claramente os integrantes do grupo no corpo do email e inclua, como anexo *apenas* os arquivos bigint.c e rel.txt.
• O arquivo rel.txt deve conter um pequeno relatório explicando o que está funcionando e também (muito importante!) o que não está funcionando. Se seu programa tem bugs, você saber disso é um atenuante...
• Coloque no início dos dois arquivos, como comentário, os nomes dos integrantes do grupo da seguinte forma:

  /* Nome_do_Aluno1 Matricula */
  /* Nome_do_Aluno2 Matricula */
  

Observações

• O trabalho pode ser feito em grupo de dois alunos.
• Se você não implementar alguma das funções, crie uma dummy com o nome da função que faltou e corpo '{ return; }', para que o programa teste a ser usado para correção do trabalho possa ser gerado sem problemas.
• Teste seu programa com casos variados antes de entregá-lo!!
• Na avaliação do trabalho os alunos deverão explicar ao professor, no laboratório, o código do trabalho entregue. Será marcada uma data específica para essa avaliação.
• Em caso de dúvidas, não invente. Pergunte!