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 deslocamento de bits.

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:

Implementação

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


/* Operacoes de deslocamento */

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

/* desloca a de n bits para a esquerda e guarda 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 arquivo bigint.h para as prototipações.

Testando as funções

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.

Prazo: 19/04 (até a meia noite)

Entrega

• Deve ser entregue um único arquivo, bigint.c, contendo a implementação das funções pedidas (e eventualmente, funções auxiliares). Esse arquivo * 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 o arquivo "bigint.c".
• Coloque no início do arquivo fonte, como comentário, os nomes dos integrantes do grupo da seguinte forma:

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

• Coloque também como comentário no arquivo um pequeno relatório explicando o que esta funcionando e, principalmente, o que não está funcionando. (Se o seu trabalho tem bugs você saber disso e relatar conta a seu favor...)

Observações

• O trabalho pode ser feito em grupo de dois alunos.
• Implemente uma função de cada vez, e teste bem sua  implementação. É melhor entregar um trabalho com apenas algumas funções funcionando corretamente,  do que com todas as funções funcionando incorretamente.
• Não faça a bobagem de escrever todo o código para depois compilar e testar! Tente implementar primeiro a função de soma, certifique-se que ela está funcionando, e só então passe 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.
• 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!