Manipulação de inteiros grandes

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

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

	
#define NUM_BYTES 16
typedef unsigned char BigInt[NUM_BYTES];

Ou seja, uma variável do tipo BigInt é representada por este array, que deve ser interpretado como um único inteiro de 128 bits, em complemento a dois, seguindo a ordem little-endian. Desta forma, o inteiro 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE (igual a -2) é representado pelo array:

As funções devem seguir os protótipos a seguir:

/* Operacoes basicas */

/* res = a + b */
void bi_sum (BigInt res, BigInt a, BigInt b);

/* res = a - b */
void bi_sub (BigInt res, BigInt a, BigInt b);

/* res = a * b */
void bi_mul (BigInt res, BigInt a, BigInt b);

/* res = a / b */
void bi_div (BigInt res, BigInt a, BigInt b);


/* desloca a de n bits para a direita e grava resultado em res */
void bi_shr (BigInt res, BigInt a, int n);
/* desloca a de n bits para a esquerda e grava resultado em res */
void bi_shl (BigInt res, BigInt a, int n);

O produto deste trabalho deve ser um arquivo em C com nome "bigint.c" contendo apenas a implementação das seis funções acima. Dê um #include no seguinte arquivo bigint.h para as prototipações.

Recomendação: 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!

Avaliação

Para a correção, as funções serão chamadas de uma rotina main de teste, por isto não inclua uma main no seu trabalho.

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.

Prazo: 25/09

Observações

• O trabalho deve ser entregue no dia 25 de setembro por email. O email deve ser mandado para o professor da turma, e a listagem impressa deve ser deixada no escaninho desse professor (Os escaninhos ficam no quarto andar do RDC, próximos à secretaria do DI.).
• Os trabalhos podem ser feitos em grupos de até dois alunos.
• A mensagem enviada deve conter, como anexo, o arquivo "bigint.c", com as funções pedidas.
• Não coloque mais nada na mensagem (.o, .out, etc)
• Coloque no início do arquivo fonte, como comentário, os nomes dos integrantes do grupo.
• Os conteúdos do arquivo enviado e da listagem impressa devem ser rigorosamente iguais (ou serão tirados pontos).
• A pontuação é por função correta. Implemente uma função de cada vez, e teste bem sua  implementação. É melhor entregar um tabalho com apenas algumas funções funcionando corretamente,  do que com todas as funções funcionando incorretamente. Não faça a bobagem de escrever o código de tudo para depois compilar e testar! Tente implementar primeiro a função de soma, certificar-se que ela está funcionando, e só então passar para a próxima!
• 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.
• No início ndo arquivo bigint.c, escreva, como comentário, um mini-relatório, explicando o que está funcionando e, principalmente, o que não está funcionando. (Se o programa tiver bugs, você saber disso é sempre um atenuante.)
• O professor de cada turma poderá chamar alguns alunos para explicarem o código do trabalho entregue.
• O prazo de entrega é dia 25/09, até às 20h. Os trabalhos perderão meio ponto por cada dia de atraso (incluindo dias de final de semana).
• Em caso de dúvidas, não invente. Pergunte!