Длинная арифметика в С++ своими руками

Примерно месяц назад(в качестве лабораторной работы) было необходимо написать калькулятор больших чисел. Конечно же, самое интересное не «найти шаблоничоков» во всемирной паутине, а немного разобраться самому.



Итак. Цель – написание логики программы, основанное на системе счисления кратной 10, поддерживающее работу с бесконечно большими числами, которые могут быть как целые. Так и десятичные.
Для начала определим «числа» которые понадобятся нам для работы
//наибольшая с\\с для unsigned (long) (int)
#define Notation 1000000000
//наибольшее кол-во разрядов для unsigned (long) (int)
#define lengthOfNotation 9
//Для простоты обращения
#define THIS (*this)

This code was highlighted with code.xnim.ru


Здесь можно встретить «странный» на первый взгляд define THIS. Для чего он понадобится?
Ответим, приведя структуру переменных в классе:

  1. class NQInt
  2. {
  3. //число
  4. int* value;
  5. //десятичное число
  6. int* underValue;
  7. //метка позитивного настроения числа
  8. bool Positive;
  9. //длина числа
  10. int valueLeng;
  11. //длина десятичного числа
  12. int underValueLeng;
  13. //размeр погрешности
  14. int errSize;
  15. //Последующий код класса

This code was highlighted with code.xnim.ru

( в моем рассматриваемом решении будем работать с с/с с основанием 1 000 000 000. Если есть необходимость изменить с/с это легко сделать сменив соответствующие defines
Как видно из кода, я решил разделить работу целых чисел и десятичных. В некоторых случаях это может быть неудобно (сложение, умножение т.д.) так как необходимо представлять число как «единое целое». Данную проблему решить можно очень просто. Давайте разберем представление числа как «такового»:
Дано: 123456789.12345
Данное число будет представлено в логике программы как –
  1. value = 123456789 ;
  2. underValue = 12345 ;
  3. Positive = true;
  4. valueLeng = 1 ; //C/c вмещает 9 цифр
  5. underValueLeng = 1 ;

This code was highlighted with code.xnim.ru


Соответственно, если число будет представлено как 10123456789, то value будет равно {123456789}(нуль индекс),{10}(первый индекс)

Теперь вопрос. Как осуществить адресацию внутри двух переменных? Моим решением было перегрузить оператор[].

Идея перегрузки – если число больше нуля, то возвращаем соответствующее значение value, иначе возвращаем модуль индекса – 1
пример реализации

  1.   if (i<0)
  2. {
  3.    return(underValue[abs(i)-1]);
  4. }
  5. return (value[i]);

This code was highlighted with code.xnim.ru


Логику работу со структурой класса мы разобрали. Теперь непосредственно к операциям +,-,*,/

Плюс, равно как и минус могут гордиться своей простотой реализации для любых чисел.
Основное, что программист не должен забыть ни в коем случае – числа положительное плюс отрицательно все-таки лучше отнимать, а не складывать. Разбирать это не будем, ввиду полной ясности этих проверок.

Остановимся непосредственно на вопросах реализации алгоритма. Складывать будем как, некогда делали в школе – столбиком.
Идея реализации – выбираем самое минимальное значение(min) (если есть числа после запятой, то это обязательно отрицательное значение, иначе оно равно 0) и выбираем максимальное значение(max) – длина самого большого положительного числа.

И затем в цикле от min до max складываем значения. Причем, если сумма двух значений больше, чем Notation, то в результат кладем только остаток от деления на Notation, а все, что больше, чем Notation добавляем к следующей части числа.
Пример реализации цикла (используется NQList – списко поддурживающий добавление вначало, вконец, удаление по номеру и адресацию через [])

  1. //Пример сложения двух чисел THIS и A
  2. NQList <int > Resulted;// здесь накапливаем число
  3. int incr = 0 ;//инкремент к следующему числу
  4. for (int i =-min; i <max; i++)//собственно цикл
  5. {//собственно слагание
  6.    long long Value = 0 ;
  7.    if (i >= -underValueLeng && i < valueLeng)
  8.    {
  9.     Value += THIS[i];
  10.    }
  11.    if (i >= -A.underValueLeng && i < A.valueLeng)
  12.    {
  13.     Value += A[i];
  14.    }
  15.    Value+=incr;
  16.    incr = Value / Notation;
  17.    Resulted.addLast(Value % Notation);
  18. }

This code was highlighted with code.xnim.ru


Данный цикл прекрасно сложит все числа, однако в случае, если мы складываем такие числа, как 999 999 999 + 1, то данный цикл заполнит только 000 000 000, поэтому, целесообразно добавить -
  if (incr) Resulted.addLast(incr);
This code was highlighted with code.xnim.ru


В конечно итоге мы получили число, количество знаков после запятой у которого равно min, а элементы числа хранятся в Resulted.

Операция «минус» аналогична сложению. Предлагаю разобрать ее самостоятельно.

Теперь перейдем к операции умножения.
Умножение можно определить как большое количество сложений, но данный способ очень ресурсоемкий процесс. Поэтому умножать будем также – в столбик. Это уменьшит количество времени работы программы.

Как это сделать.

Данную операцию можно провести легко, используя два вложенных цикла.
Один по одному числу, другой по другому.
На каждой итерации алгоритма – умножим соответствующие числа и запишем в новый элемент. Причем не будем забывать, что каждый элемент должен быть меньше Notation, поэтому введем так же, как и в «+» инкремент для следующего числа.
Полученный код:

  1. NQList <int > Resulted;
  2. int incr = 0 ;
  3. for (int i = -underValueLeng; i < valueLeng; i++)
  4.    for (int j = -A.underValueLeng; j < A.valueLeng; j++)
  5.    {//идем с двух сторон
  6.     unsigned long long Value;
  7.      Value =((unsigned long long)THIS[i])*(unsigned long long)A[j] +(unsigned long long)incr;
  8.      //берется произведение, высчитывается инкремент следующих разрядов
  9.      incr = Value / Notation;
  10.      Value -= ((unsigned long long)incr)*((unsigned long long)Notation);//Сокращение длины
  11.     
  12.      if (i+j + underValueLeng + A.underValueLeng >= Resulted.Count()) Resulted.addLast(Value);//добавление нового если необходимо
  13.      else
  14.      {//морока с разрядами =)
  15.        unsigned long long Val = (unsigned long long)Resulted[i+j+underValueLeng+A.underValueLeng] + Value;
  16.        int Dincr = Val / Notation;
  17.        Val -= ((unsigned long long)Dincr)*((unsigned long long)Notation);
  18.        Resulted[i+j+underValueLeng+A.underValueLeng] = Val;
  19.        incr += Dincr;    
  20.      }
  21.      if (incr)
  22.      if (i+j + underValueLeng + A.underValueLeng+1  >= Resulted.Count()) Resulted.addLast(incr);
  23.      else
  24.      {//перевод разрядов
  25.         Resulted[i+j+underValueLeng+A.underValueLeng + 1 ] += incr;
  26.      }
  27.      incr = 0 ;
  28.      for (int k = i+j+underValueLeng+A.underValueLeng; k < Resulted.Count()-1 && Resulted[k] >= Notation; k++)
  29.      {
  30.        int D = Resulted[k] / Notation;
  31.        Resulted[k] -= D*Notation;
  32.        Resulted[k+1 ] += D;
  33.      }
  34.    }

This code was highlighted with code.xnim.ru



Легко заметить, что при работе с разрядами числа «обновляются», не отходя от «кассы». При использовании с/с меньших 1 000 000 000 данная задача не является «критической». Это обуславливается необходимостью вмещать весьма большие значения такие как 99999998000000001

Теперь подходим к самой важной части работы, а именно – к делению.


Для этой операции, равно как и для умножения, деления существуют различные алгоритмы, которые ускоряют данный процесс.
Воспользуемся простейшим делением «в столбик» с его оптимизацией – бинарный поиск.

Суть работы алгоритма – из исходного числа последовательно выбирается следующее (от старшего) число и происходит «попытка» деления выбранного числа.

В случае с десятичными числами, думаю, проще привести число в целый вид (умножением на 10, либо написанием функции, добавляющий разряд к целой части, и забирающей у десятичной части).

Общий вид алгоритма

1. Перевод числа к целому виду
2. Цикл по числу
2.2. Поиск следующего числа частного (перебор, бин поиск)
2.3. Запись найденного числа
2.4. Уменьшение делимого

Примерный код:

  1. if(A.underValueLeng)
  2. {
  3.    while (A.underValueLeng > 0 )
  4.    {// делитель приводим к целому виду, попутно увеличивая делимое
  5.     TempThis.setNextDigit();
  6.     A.setNextDigit();
  7.     
  8.    }
  9.   
  10.    TempThis.deleteNullsItems();
  11.    A.deleteNullsItems();//методы, убирающие ведущие нули и конечные (в случае с символами после запятой)
  12. }
  13. //накопление точности
  14. //errSize - пользователь вводит точность вычисления.
  15. int underPointLength = 0 , PointIncrement = TempThis.valueLeng;
  16. if (PointIncrement == 1 && TempThis.valueLeng == 1 && TempThis.value[0] == 0 ) PointIncrement = 0 ;
  17. for (int i = 0 ; i < errSize; i++)
  18.    TempThis.setNextDigit();//создаем чило требуемой точности
  19. TempThis.deleteNullsItems();
  20. //наколпление "неточности"
  21. while (TempThis.underValueLeng > 0 )
  22. {//если основное число еще имеет десятичную часть
  23.    TempThis.setNextDigit();
  24. }
  25. TempThis.deleteNullsItems();
  26. int CurrentENDPos = TempThis.valueLeng - A.valueLeng;
  27. PointIncrement -= A.valueLeng;
  28. PointIncrement++;
  29. NQList <int > RES;
  30. for (;CurrentENDPos >= 0 ; CurrentENDPos--)
  31. {//главный цикл вырывает по очередному значения (первое подсчитывает заранее размер) и затем бинарит его
  32.   
  33.    if (!NQInt(0).Compare(TempThis))
  34.    { for (;CurrentENDPos >= 0 ;CurrentENDPos--)
  35.     {//так некрасиво, но если нет смысла делить, то можно
  36.        RES.addFirst(0);
  37.        PointIncrement--;
  38.        if (PointIncrement < 0 ) underPointLength++;
  39.     }
  40.    continue;
  41.    }
  42.    if (TempThis.valueLeng - CurrentENDPos <=0)
  43.    {//если числа нет, а делить надо
  44.     PointIncrement--;
  45.     if (PointIncrement < 0 ) underPointLength++;
  46.     RES.addFirst(0);
  47.     continue;
  48.    }
  49.    PointIncrement--;// приближение запятой
  50.    NQInt *LocalD = new NQInt(TempThis,TempThis.valueLeng-1,TempThis.valueLeng - CurrentENDPos);
  51.    unsigned int min = 0 ;
  52.    unsigned int max = Notation;
  53.    int Result;
  54.    NQList <int > Resulted;
  55.    while (min <= max)
  56.    {//бинарим и ищем
  57.     int Middle = (min+max) > >1;
  58.     NQInt Current = A * NQInt(Middle);
  59.     if (Current.Compare(*LocalD) != 1 )
  60.     {
  61.      Result = Middle;
  62.      min = Middle + 1 ;
  63.     }
  64.     else
  65.     {
  66.      max = Middle - 1 ;
  67.     }
  68.    }
  69.    RES.addFirst(Result);//добавляем значение
  70.    if (PointIncrement < 0 ) underPointLength++;//запятая
  71.    NQInt Subtractor = A*NQInt(Result);
  72.    for (int i = 0 ; i <CurrentENDPos; i++)
  73.     Subtractor.setNextDigit();//ищем остаточную разницу
  74.    TempThis = TempThis - Subtractor;
  75.    TempThis.deleteNullsItems();
  76. }

This code was highlighted with code.xnim.ru



В переменной RES хранится конечный результат.

Однако при делении чисел вида 1000000000 на 10 будет «долгое» деление, так как будет происходить деление 0 на 10, 00 на 10 и т.д. Введем «дополнительную» оптимизацию к данному коду. А также приведем код, который приводит числа к представлению без десятичной части

  1. int CurrentENDPos = TempThis.valueLeng – A.valueLeng;
  2. PointIncrement -= NextDLen;
  3. PointIncrement++;
  4. NQList <int > RES;
  5. for (;CurrentENDPos >= 0 ; CurrentENDPos--)
  6. {//главный цикл вырывает по очередному значения (первое подсчитывает заранее размер) и затем бинарит его
  7.   
  8.    if (!NQInt(0).Compare(TempThis))
  9.    { for (;CurrentENDPos >= 0 ;CurrentENDPos--)
  10.     {//так некрасиво, но если нет смысла делить, то можно
  11.        RES.addFirst(0);
  12.        PointIncrement--;
  13.        if (PointIncrement < 0 ) underPointLength++;
  14.     }
  15.    continue;
  16.    }
  17.    if (TempThis.valueLeng - CurrentENDPos <=0)
  18.    {//если числа нет, а делить надо
  19.     PointIncrement--;
  20.     if (PointIncrement < 0 ) underPointLength++;
  21.     RES.addFirst(0);
  22.     continue;
  23.    }
  24.    PointIncrement--;// приближение запятой
  25.    NQInt *LocalD = new NQInt(TempThis,TempThis.valueLeng-1,TempThis.valueLeng - CurrentENDPos);
  26.    unsigned int min = 0 ;
  27.    unsigned int max = Notation;
  28.    int Result;
  29.    NQList <int > Resulted;
  30.    while (min <= max)
  31.    {//бинарим и ищем
  32.     int Middle = (min+max) > >1;
  33.     NQInt Current = A * NQInt(Middle);
  34.     if (Current.Compare(*LocalD) != 1 )
  35.     {
  36.      Result = Middle;
  37.      min = Middle + 1 ;
  38.     }
  39.     else
  40.     {
  41.      max = Middle - 1 ;
  42.     }
  43.    }
  44.    RES.addFirst(Result);//добавляем значение
  45.    if (PointIncrement < 0 ) underPointLength++;//запятая
  46.    NQInt Subtractor = A*NQInt(Result);
  47.    for (int i = 0 ; i <CurrentENDPos; i++)
  48.     Subtractor.setNextDigit();//ищем остаточную разницу
  49.    TempThis = TempThis - Subtractor;
  50.    TempThis.deleteNullsItems();
  51. }

This code was highlighted with code.xnim.ru





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

Описанные здесь способы только одни из многих.

Автор Мостовой Никита.
2012-03-15