C++. Сборник рецептов - Д. Стефенс

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

Рецепт 11.20.

11.20. Представление больших чисел фиксированного размера

Требуется выполнить операции с числами, размер которых превышает размер типа long int.

Шаблон BigInt в примере 11.38 использует bitset из заголовочного файла <bitset> для того, чтобы можно было представить целые числа без знака в виде набора бит фиксированного размера, причем количество бит определяется параметром шаблона.

Пример 11.38. big_int.hpp

#ifndef BIG_INT_HPP

#define BIG_INT_HPP

#include <bitset>

#include "bitset_arithmetic.hpp" // Рецепт 11.20

template<unsigned int N>

class BigInt {

 typedef BigInt self;

public:

 BigInt() : bits() {}

 BigInt(const self& x) : bits(x.bits) {}

 BigInt(unsigned long x) {

  int n = 0;

  while (x) {

   bits[n++] = x & 0x1;

   x >>= 1;

  }

 }

 explicit BigInt(const std::bitset<N>& x) bits(x) {}

 // открытые функции

 bool operator[](int n) const { return bits[n]; }

 unsigned long toUlong() const { return bits.to_ulong(); }

 // операторы

 self& operator<<=(unsigned int n) {

  bits <<= n;

  return *this;

 }

 self& operator>>=(unsigned int n) {

  bits >>= n;

  return *this;

 }

 self operator++(int) {

  self i = *this;

  operator++();

  return i;

 }

 self operator--(int) {

  self i = *this;

  operator--();

  return i;

 }

 self& operator++() {

  bool carry = false;

  bits[0] = fullAdder(bits[0], 1, carry);

  for (int i = 1; i < N; i++) {

   bits[i] = fullAdder(bits[i], 0, carry);

  }

  return *this;

 }

 self& operator--() {

  bool borrow = false;

  bits[0] = fullSubtractor(bits[0], 1, borrow);

  for (int i = 1; i < N; i++) {

   bits[i] = fullSubtractor(bits[i], 0, borrow);

  }

  return *this;

 }

 self& operator+=(const self& x) {

  bitsetAdd(bits, x.bits);

  return *this;

 }

 self& operator-=(const self& x) {

  bitsetSubtract(bits, x.bits);

  return *this;

 }

 self& operator*=(const self& x) {

  bitsetMultiply(bits, x.bits);

  return *this;

 }

 self& operator/=(const self& x) {

  std::bitset<N> tmp;

  bitsetDivide(bits, x.bits, bits, tmp);

  return *this;

 }

 self& operator%=(const self& x) {

  std::bitset<N> tmp;

  bitsetDivide(bits, x.bits, tmp, bits);

  return *this;

 }

 self operator~() const { return ~bits; }

 self& operator&=(self x) { bits x.bits; return *this; }

 self& operator|=(self x) { bits x.bits; return *this; }

 self& operator~=(self x) { bits ~= x.bits; return *this; }

 // дружественные функции

 friend self operator<<(self x, unsigned int n) { return x <<= n; }

 friend self operator>>(self x, unsigned int n) { return x >>= n; }

 friend self operator+(self x, const self& y) { return x += y; }

 friend self operator-(self x, const self& y) { return x -= y; }

 friend self operator*(self x, const self& y) { return x *= y; }

 friend self operator/(self x, const self& y) { return x /= y; }

 friend self operator%(self x, const self& y) { return x %= y; }

 friend self operator^(self x, const self& y) { return x ^= y; }

 friend self operator&(self x, const self& y) { return x &= y; }

 friend self operator|(self x, const self& y) { return x |= y; }

 // операторы сравнения

 friend bool operator==(const self& x, const self& y) {

  return x.bits == y.bits;

 }

 friend bool operator!=(const self& x, const self& y) {

  return x.bits ! = y.bits;

 }

 friend bool operator>(const self& x, const self& y) {

  return bitsetGt(x.bits, y.bits);

 }

 friend bool operator<(const self& x, const self& y) {

  return bitsetLt(x.bits, y.bits);

 }

 friend bool operator>=(const self& x, const self& y) {

  return bitsetGtEq(x.bits, y.bits);

 }

 friend bool operator<=(const self& x, const self& y) {

  return bitsetLtEq(x bits, y.bits);

 }

private:

 std::bitset<N> bits;

};

#endif

Шаблонный класс BigInt можно использовать для вычисления факториалов, как показано в примере 11.39.

Пример 11.39. Применение класса big_int

#include "big_int.hpp"

#include <iostream>

#include <vector>

#include <iterator>

#include <algorithm>

using namespace std;

void outputBigInt(BigInt<1024> x) {

 vector<int> v;

 if (x == 0) {

  cout << 0;

  return;

 }

 while (x > 0) {

  v.push_back((x % 10).to_ulong());

  x /= 10;

 }

 copy(v.rbegin(), v.rend(), ostream_iterator<int>(cout, ""));

 cout << endl;

}

int main() {

 BigInt<1024> n(1); // вычислить факториал числа 32

 for (int 1=1; i <= 32; ++i) {

  n *= i;

 }

 outputBigInt(n);

}

Программа примера 11.39 выдает следующий результат.

263130836933693530167218012160000000

Большие целые числа часто встречаются во многих приложениях. Например, в криптографии нередки числа, которые представляются 1000 и более битами. Однако современный стандарт C++ позволяет работать как максимум с типом long int.

Число бит типа long int зависит от реализации, но оно не может быть меньше 32. И едва ли это число будет больше 1000. Следует помнить, что один из этих битов используется в качестве знака.

Ожидается, что новая версия стандарта (C++0x) последует за стандартом C99 и предусмотрит тип long long, размер которого будет, по крайней мере, не меньше размера long int, а возможно, и больше. Несмотря на это, всегда будут случаи, когда требуется наличие целочисленного типа, размер которого превышает размер самого большого встроенного типа.

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

Рецепт 11.19.

11.21. Реализация чисел с фиксированной точкой

Требуется обеспечить выполнение вычислений с вещественными числами, используя тип с фиксированной, а не с плавающей точкой.

В примере 11.40 представлена реализация вещественного числа с фиксированной точкой, когда количество двоичных позиций справа от точки задается параметром шаблона. Например, тип basic_fixed_real<10> имеет 10 двоичных цифр справа от двоичной точки, что позволяет представлять числа с точностью до 1/1024.

Пример 11.40. Представление вещественных чисел, используя формат с фиксированной точкой

#include <iostream>

using namespace std;

template<int E>

struct BasicFixedReal {

 typedef BasicFixedReal self;

 static const int factor = 1 << (E - 1);

 BasicFixedReal() : m(0) {}

 BasicFixedReal(double d) : m(static_cast<int>(d * factor)) {}

 self& operator+=(const self& x) { m += x.m; return *this; }

 self& operator-=(const self& x) { m -= x.m; return *this; }

 self& operator*=(const self& x) { m *= x.m; m >>=E; return *this; }

 self& operator/=(const self& x) { m /= x.m; m *= factor; return *this; }

 self& operator*=(int x) { m *= x; return *this; }

 self& operator/=(int x) { m /= x; return *this; }

 self operator-() { return self(-m); }

 double toDouble() const { return double(m) / factor; }

 // дружественные функции

 friend self operator+(self x, const self& v) { return x += y; }

 friend self operator-(self x, const self& y) { return x -= y; }

 friend self operator-(self x, const self& y) { return x *= y; }

 friend self operator/(self x, const self& y) { return x /= y; }

 // операторы сравнения

 friend bool operator==(const self& x, const self& y) { return x.m == y.m; }

 friend bool operator!=(const self& x, const self& y) { return x.m != y.m; }

 friend bool operator>(const self& x, const self& y) { return x.m > y.m; }

 friend bool operator<(const self& x, const self& y) { return x.m < y.m; }

 friend bool operator>=(const self& x, const self& y) { return x.m >= y.m; }

 friend bool operator<=(const self& x, const self& y) { return x.m <= y.m; }

private: