Арифметика многократной точности

Рассмотрим в качестве примера задачу создания класса, реализующего действия с целыми числами произвольной (или многократной) точности. Наша цель — создать класс, который можно использовать аналогично стандартному типу int, но который не будет ограничен размером машинного слова (например, 264). По аналогии с математическим обозначением моножества целых чисел назовем этот класс ZZ. Реализация будет включать файлы ZZ.h (объявление класса), ZZ.cpp (реализация методов), test.cpp (тестовая программа). Скачать все файлы в одном архиве можно по ссылке внизу странцы.

Сначал рассмотрим возможный вариант использования этого клсса.

#include <iostream>
#include "ZZ.h"
int main() {
  ZZ a = -7, b = 1;
  for(int n=0; n < 50; n++)
    b = b * a;
  std::cout << "a^50 = " << b << std::endl;
  if(a.isPositive())
    std::cout << "Это положительное число!" << std::endl;
} 
Мы хотим иметь возможность инициализировать объекты класса ZZ естественным образом, выполнять арифметичекие операции с числами произвольной точности используя обычные операторы, выполнять специальные операции, распечатывать значения и т.п. Класс определят структуру данных и методы обработки этих данных. Для представления чисел многократной точности можно использовать различные структуры данных. В нашем примере используется представление чисел в виде массива символов, представляющих число в десятичной форме.

#ifndef ZZ_H__
#define ZZ_H__

#include <iostream>

class ZZ {
private:
  // Числа хранятся в десятичном виде в массиве символов.
  // Младший разряд числа хранится в элементе с индексом 0.
  // data_ не содержит \0 и не является C-строкой. Например, число 1024
  // представляется массивом из четырех элементов типа char
  //   data_[0]='4', data_[1]='2', data_[2]='0', data_[3]='1'
  char *data_;
  int ndigits_; // Количество элементов в массиве data_
  bool isPositive_; // Знак числа

  // Скрытый конструктор, который может использоваться только в методах
  // и функциях-друзьях. Выделяет память для arrsize 8-битных разрядов
  // и заполняет ее нулями (выделяется минимум 4 байта).
  // Пример использования: см. реализацию operator* в файле ZZ.cpp
  ZZ(int val, unsigned int arrsize);

  // Возвращает число разрядов (без учета нулей в старших разрядах);
  // Если объект представляет число 0, то возвращается значение 1.
  int realSize() const; // const означает, что функция не изменяет состояние объекта

  // Функция convertIn выделяет память для хранения числа val и заполняет data_. 
  // Если перед вызовом функции ndigits_ > 0, то для data_ выделется ndigits_ байт.
  // Старшие разряды data_, которые не нужны для представления val, заполняются нулями ('0').
  // Если ndigits_ == 0, то размер data_ определяется автоматически по числу десятичных
  // знаков val. 
  void convertIn(int val); 

public:
  ZZ(int val=0); // Конструктор преобразования из "обычных" целых. Этот же конструктор
                 // будет вызываться и в случае, когда аргументы не указаны ("ZZ a;"), 
                 // так как val имеет значение по умолчанию.
  ZZ(const ZZ& z); // Конструктор копирования объектов. 
  ~ZZ(); // Деструктор. Автоматически вызывается при удалении объекта.

  ZZ& operator= (const ZZ& z); // Присвоение
  friend ZZ operator* (const ZZ& z1, const ZZ& z2); // Умножение произвольной точности.

  friend std::ostream& operator <<(std::ostream& os, const ZZ& z); // печать числа

  bool isPositive() const { return isPositive_; } // Проверка знака
  void shrink(); // Отбрасывание старших нулевых разрядов

  static bool doTrace; // Переменная класса, общая для всех объектов.
                       // Присвоить значение такой переменной можно так:
                       //    ZZ::doTrace = false;
                       // Если ZZ::doTrace==true, то конструкторы и деструкторы печатают
                       // на экран текстовые сообщения.
};

#endif

Возможная реализация методов приведена ниже.

#include <cstring>
#include <stdio.h>
#include "ZZ.h"

bool ZZ::doTrace=true; // Инициализируем переменную класса

void ZZ::convertIn(int val) {
  char temp[12]; // 32-битный int содержит не более 11 десятичных разрядов + конец строки
  sprintf(temp, "%d", val); // sprintf работает как printf, только записывает 
                            // результат в строку (temp), а не в файл или на экран.
  int len = strlen(temp); // В C++ переменные можно объявлять где угодно
  if(ndigits_ == 0) {
    ndigits_ = len;
  }

  // Выделяем память для ndigits_ байт.
  data_ = new char[ndigits_]; // new - это C++-ный аналог malloc. См. деструктор
  if(len > ndigits_) { throw "ZZ::convertIn: len > ndigits_"; } // Сообщаем об ошибке

  // копируем данные в массив data_; Если ndigits_ больше, чем нужно, то
  // старшие разряды содержат символ '0'
  for(int i=0; i<ndigits_; i++) { // переменная i доступна только внутри цикла
    data_[i] = (i < len ? temp[len - i - 1] : '0');
  }
}

ZZ::ZZ(int val) : data_(NULL), ndigits_(0), isPositive_(false) {
  // Синтаксис в предыдущей строке эквивалентен операторам data_=NULL; и т.д.

  if(ZZ::doTrace) {
    std::cout << "Constructor" << std::endl;
  }

  convertIn(val);
}


ZZ::ZZ(int val, unsigned int arrsize) : data_(NULL), isPositive_(false) {
  ndigits_ = arrsize;
  convertIn(val);
}


ZZ::ZZ(const ZZ& z) {
  delete data_;
  data_ = new char[z.ndigits_];
  memcpy(data_, z.data_, z.ndigits_);
  ndigits_ = z.ndigits_;
  isPositive_ = z.isPositive_;
}


ZZ::~ZZ() {
  if(ZZ::doTrace) {
    std::cout << "Destructor" << std::endl;
  }
  delete[] data_;
  // Если память выделялась с помощью new, то ее надо освобождать delete. Например,
  //   ZZ *p = new ZZ; delete p;
  // Если выделялся массив (стандартного типа или класса):
  //     ZZ *p = new ZZ[10];
  // то удалять его надо с помощью
  //     delete[] p;
  // В этом случае деструктор (в данном случае ZZ::~ZZ) будет вызван для
  // каждого элемента массива. При создании массива будет 10 раз вызван
  // конструктор ZZ::ZZ().
}


ZZ operator* (const ZZ& z1, const ZZ& z2) {
  // Умножение столбиком
  int z1rs = z1.realSize(),
      z2rs = z2.realSize();
  ZZ res(0, z1rs+z2rs+1);
  for(int i=0; i < z1rs; i++) {
    for(int j=0; j < z2rs; j++) {
      unsigned int prod = (unsigned int)(z1.data_[i]-'0')*(unsigned int)(z2.data_[j]-'0');

      // записываем результат умножения i-й и j-й цифр и выполняем цикл переноса
      for(int k=i+j; k < i+z2rs+1 && prod > 0; k++) {
        unsigned int sum = (prod % 10) + (unsigned)(res.data_[k]-'0');
        res.data_[k] = '0' + (sum % 10);
        prod = (sum/10 + prod/10);
      }
    }
  }

  res.isPositive_ = !(z1.isPositive_ ^ z2.isPositive_);
  return res;
}


ZZ& ZZ::operator= (const ZZ& z) {
  delete data_;
  data_ = new char[ndigits_ = z.ndigits_];
  memcpy(data_, z.data_, z.ndigits_);
  isPositive_ = z.isPositive_;
  return *this;
}

std::ostream& operator <<(std::ostream& os, const ZZ& z) {
  for(int i = z.realSize()-1; i>=0; i--) {
    os << z.data_[i];
    //if(i>0) os << " ";
  }
  return os;
}


int ZZ::realSize() const {
  for(int i=ndigits_-1; i>0; --i)
    if(data_[i] != 0 && data_[i] != '0') return i+1;
  return 1;
}

Скачать архив »