5.3 Пользовательская арифметика

Как видим из описаний предыдущих разделов, стандартные арифметические операции имеют существенные ограничения. В некоторых случаях полезно разра- ботать свое представление числа и соответственно свои арифметические операции. Ниже приведено описание такого подхода.

Целое без знаковое число представляетс в виде нового типа определенно- го с помощью typedef. Структура BigNumberTag с одержит два поля: первое поле описывает количество цифр в поле number. В каждом байте пол number может хранитьс только одна десятична цифра. Причем десятичное сило записывает с права на лево, т.е. самый младший разр д находитс слева. Ниже записана структура числа и некоторые арифметические операции. Здесь представлены алго- ритмы сложения и умножения, основанные на школьной арифметике сложения и умножени столбиком. Кроме того, имеетс функци вычислени с пока алгоритма умножения столбиком и функци вычисления факториала.

Особенность такого представления, учет длины числа. Ниже приводятс: описание структуры и функции. Смотрите пояснение п 5.3 Пояснение представления, учет длины числа.

#define SIZEBIGNUMBERS 200 //размер числа в цифрах
//описание длинного целого без знакового числа
typedef struct BigNumberTag
{
      int size; //количество цифр в числе
      char number[SIZEBIGNUMBERS]; //память под десятичное число
}BigNumber;
//установить значение числа используя строку символов
int SetBigNumber(BigNumber *bn, char *num)
{
      int i,j;
      if((bn->size=strlen(num))>SIZEBIGNUMBERS) return -1;
      // слишком большое число
      for(i=bn->size-1, j=0; i>=0; i--,j++) //храним число в обратном порядке
      bn->number[j]=num[i]-’0’; //храним не коды цифр а сами цифры
}
//печать числа
void PrintBigNumber(BigNumber *bn)
{
      for(int i=bn->size-1; i>=0; i--)
      printf("%c",bn->number[i]+’0’);
      printf("\n");
}
//копировать значение чиcла dst=src
void CopyBigNumber(BigNumber *dst, BigNumber *src)
{
      dst->size=src->size;
      for(int i=0; i<dst->size; i++)
            dst->number[i]=src->number[i];
}
//Сложить bn1 и bn2 результат поместить в bn1
int AddBigNumber(BigNumber *bn1,BigNumber *bn2)
{
      BigNumber res; //здесь храним резудьтат сложения
      int d; //результат сложения двух чисел
      int carry=0; //хранит единицку переноса
      BigNumber *min,*max; //вспомогательные указатели
      if(bn1->size<bn2->size) //определяем длинное число и короткое
      {
            min=bn1; //короткое
            max=bn2; //длинное
      }
      else
      {
            min=bn2;
            max=bn1;
      }
//поскольку цифры храним в обратном порядке, начинаем сложение с левой цифры
      for(int i=0; i<max->size; i++)
      { //если позиция не превысила короткого слова то производим сложение
            if(i<min->size) d=min->number[i]+max->number[i]+carry;
            else d=max->number[i]+carry; //в противном случае учитывается только перенос
            if(d>9)
            { //установливаем перенос в другой разряд
                  res.number[i]=d-10;
                  carry=1;
            }
            else
            { //здесь переноса нет
                  res.number[i]=d;
                  carry=0;
            }
      }//завершение цикла
      if(carry) { //если после цикла еденица переноса установлена, то увеличиваем размер результирующего числа
            if(max->size<SIZEBIGNUMBERS){ //здесь проверяем выход за границу (переполнение)
                  res.number[max->size]=carry; //запомнить перенос
                  res.size=max->size+1; //увеличить размер числа
            }
            else return -1; //выход по переполнению
      }
      else res.size=max->size; //установить размер
      CopyBigNumber(bn1,&res);
      return 1;
}
//функция сдвига вправо (умножение на 10)
//bn - число для сдвига
//count - количество сдвигов
int ShiftRight(BigNumber *bn,int count)
{
      if(bn->size+count<SIZEBIGNUMBERS)
      { //если нет переполнения
            for(int i=bn->size-1; i>=0; i--) { //копировать с конца на count разрадов
                  bn->number[i+count]=bn->number[i];
            }
            bn->size+=count; //изменить длину числа
            for(int i=0; i<count; i++) bn->number[i]=0; //заполнить нулями слева
            return 1; //нормальное завершение
      }
      return -1; //переполнение
}
//функция умножения числа на цифру
int MultDigit(BigNumber *res, BigNumber *bn,int digit)
{
      int d;
      int carry=0;
      if(digit==0)
      { //если цифра равна 0
            res->size=1;
            res->number[0]=0;
      return 1;
      }
      for(int i=0; i<bn->size; i++)
      {
            d=bn->number[i]*digit; //умножаем разряд на цифру
            if(d%10+carry<10) { //если текущий разряд не переполняется
                  res->number[i]=d%10+carry; //вычисляем значение текущего разряда числа
                  carry=d/10; //вычисляем значение переноса в следующий разряд
            }
            else { //переполнение текущего разряда
                  res->number[i]=d%10+carry-10; //определяем значение текущего разряда
                  carry=d/10+1; //вычисляем общий перенос
            }
      }
      if(carry)
      { //если меняется размер слова
            if(bn->size<SIZEBIGNUMBERS){//переполнение ?
                  res->number[bn->size]=carry; //запоминаем перенос
                  res->size=bn->size+1; //увеличиваем размер числа
            }
            else return -1; //выход с переполнением
      }
      else res->size=bn->size; //запоминаем размер
      return 1; //норамальное завершение
}
//функция умноженя больших чисел res=bn1*bn2 ()
int MultBigNumber(BigNumber *res,BigNumber *bn1, BigNumber *bn2)
{
      BigNumber tmp;
      for(int i=0; i<bn2->size; i++)
      {
            MultDigit(&tmp,bn1,bn2->number[i]); //умножаем текущий разряд числа bn2 на число bn1
            if(i==0) CopyBigNumber(res,&tmp); //если первый раз запоминаем результат в res
            else{ //сдвигаем результат на i позиций вправо (умножение на 10*i)
                  ShiftRight(&tmp,i);
                  //PrintBigNumber(&tmp);
                  AddBigNumber(res,&tmp); //и складываем с res
            }
      }
      return 1;
}
//функция умножения больших чисел res=bn1*bn2 и вывод столбиком
int MultBigNumberWithPrint(BigNumber *res,BigNumber *bn1, BigNumber *bn2)
{
      int len;
      BigNumber tmp;
      int row=2;
      clrscr();
      gotoxy(len/2,1);
      cprintf("Multiple from Kru\n");
      len=(bn1->size+bn2->size+2);
      for(int i=0; i<len; i++)
      {
            gotoxy(len-i,row+1);
            if(i<bn1->size) cprintf("%c",bn1->number[i]+’0’);
                  gotoxy(len-i,row+2);
            if(i<bn2->size) cprintf("%c",bn2->number[i]+’0’);
      }
      for(int i=0; i<((bn1->size>bn2->size)?bn1->size:bn2->size);i++)
      {
            gotoxy(len-i,row+3);
            cprintf("-");
      }
      int i;
      for(i=0; i<bn2->size; i++)
      {
            MultDigit(&tmp,bn1,bn2->number[i]);//умножаем текущий разряд числа bn2 на число bn1
            for(int j=0; j<len; j++) {
                  gotoxy(len-j-i,row+4+i);
                  if(j<tmp.size) cprintf("%c",tmp.number[j]+’0’);
            }
            if(i==0) CopyBigNumber(res,&tmp); //если первый раз запоминаем результат в res
            else { //сдвигаем результат на i позиций вправо (умножение на 10*i)
                  ShiftRight(&tmp,i);
                  //PrintBigNumber(&tmp);
                  AddBigNumber(res,&tmp); //и складываем с res
            }
      }
      for(int j=0; j<len; j++) {
            gotoxy(len-j,row+4+i);
            cprintf("-");
      }
      for(int j=0; j<len; j++) {
            gotoxy(len-j,row+5+i);
            if(j<res->size) cprintf("%c",res->number[j]+’0’);
      }
      return 1;
}
//вычиление факторила
void Factorial(BigNumber *res,int n) {
      BigNumber inc, cur, tmp;
      SetBigNumber(&inc,"1"); //запоминаем единицу
      SetBigNumber(&cur,"1"); //текущее значение аргумента
      SetBigNumber(res,"1"); //текущее значение факториала
      for(int i=1; i<=n; i++){//цикл
            MultBigNumber(&tmp,res,&cur); //tmp=cur*res
            //здесь нельзя res=res*cur
            CopyBigNumber(res,&tmp); //res=tmp
            PrintBigNumber(res); //печать промежуточного результат
            AddBigNumber(&cur,&inc); //cur=cur+1
      }
}
int main(int argc, char* argv[])
{
      BigNumber bn, bn2, res;
      SetBigNumber(&bn,"993145678399");
      SetBigNumber(&bn2,"9991");
      //PrintBigNumber(&bn2);
      //AddBigNumber(&bn,&bn2);
      MultBigNumberWithPrint(&res,&bn,&bn2);
      //PrintBigNumber(&bn);
      //PrintBigNumber(&res);
      //Factorial(&res,10);
      getch();
      return 0;
}