bignum.c

#include <stdio.h>
#include <stdlib.h>
#include "bignum.h"
#include "list.h"
#include <ctype.h>

bignum newbignum(list l){
  bignum n = malloc(sizeof(struct bignumber));
  n -> num = l;
  n -> size = length(l);
  return n;
}

int getSize(bignum n){
  return n->size;
}

int getElem(bignum n,int x){
  list l = n->num;
  return elem(x,l);
}

bignum intToBignum(int x){
  char temp[256];
  sprintf(temp,"%d\n",x);
  stringToBignum(temp);
}

bignum stringToBignum(char* x){
  list l = NULL;
  for(   ; (*x)!='\n'; x++){
    if(isdigit(*x)==0){
      printf("Erro: Número incorreto. Carateres não permetidos\n");
      exit(1);
    }
    int value = (*x) - '0';
    l = newlist(value,l);
  }
  bignum n = newbignum(l);
  return n;
}

void printBignum(bignum n){
  //unfill(n);
  list nova = reverse(n->num);
  printlist(nova);
}

int isBigger(bignum n1,bignum n2){
  int compare = getSize(n1) - getSize(n2);
  if(compare>0)
    fill(n2,getSize(n1));
  if(compare<0)
    fill(n1,getSize(n2));
  list l1 = reverse(n1->num);
  list l2 = reverse(n2->num);
  while(l1!=NULL){
    if(head(l1)>head(l2))
      return 1;
    if(head(l1)<head(l2))
      return -1;
    l1 = tail(l1);
    l2 = tail(l2);
  }
  return 1;
}
  
    


bignum add2(bignum n1,bignum n2){
  int compare = getSize(n1) - getSize(n2);
  if(compare>0)
    fill(n2,getSize(n1));
  if(compare<0)
    fill(n1,getSize(n2));
  list l = NULL;
  int carry=0;
  list l1 = n1->num;
  list l2 = n2->num;
  while(l1!=NULL){
    int val_1 = head(l1);
    int val_2 = head(l2);
    int soma = val_1 + val_2;
    if(carry!=0)
      soma++;
    if(soma>9){
      soma = soma%10;
      carry = 1;
    }
    else
      carry = 0;
    l = newlist(soma,l);
    l1 = tail(l1);
    l2 = tail(l2);
  }
  if(carry!=0)
    l = newlist(carry,l);
  bignum n = newbignum(reverse(l));
  return n;
}
    

bignum dif(bignum n1,bignum n2){
  list l = NULL;
  int carry=0;
  if(isBigger(n1,n2)==-1){
    printf("Erro: O primeiro Bignumber necessita de ser maior do que o segundo Bignumber.\n");
    exit(1);
  }
  list l1 = n1->num;
  list l2 = n2->num;
  while(l1!=NULL){
    int sub;
    int val_1 = head(l1);
    int val_2 = head(l2);
    if(carry!=0)
      val_2++;
    if(val_1 >= val_2){
      sub = val_1 - val_2;
      carry =0;
    }
    else{
      val_1 = val_1+10;
      sub = val_1-val_2;
      carry = 1;
    }
    l = newlist(sub,l);
    l1 = tail(l1);
    l2 = tail(l2);
  }
  while(head(l)==0 && tail(l)!=NULL){
    l = tail(l);
  }
  bignum n = newbignum(reverse(l));
  return n;
}
  
    

bignum mult(bignum n1,bignum n2){
  bignum big_array[getSize(n2)];
  int i=0;
  list l2 = n2->num;
  while(l2!=NULL){
    int carry=0;
    int val_2 = head(l2);
    list l = NULL;
    list l1 = n1->num;
    while(l1!=NULL){
      int val_1 = head(l1);
      int mult_val = val_1*val_2;
      if(carry!=0)
	mult_val = mult_val + carry;
      if(mult_val>9){
	carry = mult_val/10;
	mult_val = mult_val%10; 
      }
      else
	carry = 0;
      l = newlist(mult_val,l);
      l1 = tail(l1);
    }
    if(carry!=0)
      l = newlist(carry,l);
    int aux = i;
    while(aux>0){
      l = append(l,newlist(0,NULL));
      aux--;
    }
    big_array[i] = newbignum(reverse(l));
    i++;
    l2 = tail(l2);
  }
  bignum result = big_array[0];
  for(i=1;i<getSize(n2);i++)
    result = add2(result,big_array[i]);
  return result;
}

bignum div1(bignum N1,bignum N2){
  bignum result = intToBignum(0), um = intToBignum(1), n1 = N1, n2 = N2;
  if(isBigger(N1,N2)==-1){
    printf("Erro: O primeiro Bignumber necessita de ser maior do que o segundo Bignumber.\n");
    exit(1);
  }
  if(head(N2->num)==0 && getSize(N2)==1){
    printf("Erro: Impossível dividir por 0\n");
    exit(1);
  }
  while(isBigger(n1,n2)!=-1){
    result = add2(result,um);
    n1 = dif(n1,n2);
  }
  return result;
}

void fill(bignum n1,int x){
  list l = n1->num;
  while(getSize(n1)<x){
    l = append(l,newlist(0,NULL));
    n1->size++;
  }
}

void unfill(bignum n1){
  list l = reverse(n1->num);
  while(head(l)==0){
    l = tail(l);
    n1->size--;
  }
  n1->num = reverse(l);
}