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.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Маленький стек фиксированного размера

Из книги автора

Маленький стек фиксированного размера Пользовательские программы могут "отдохнуть" вместе со своими тоннами статически выделяемых переменных в стеке, включая структуры большого размера и многоэлементные массивы. Такое поведение является законным в режиме задачи, так


Текст фиксированного формата

Из книги автора

Текст фиксированного формата Аппетит приходит во время еды. Мы еще не успели доделать свою первую Web- страницу, а уже хотим сделать еще одну. Давайте же ее сделаем. Дадим аппетиту разгуляться!Новая Web-страница (листинг 2.10) будет посвящена тегу <TITLE>. Листинг 2.10 <!DOCTYPE


Закон больших чисел

Из книги автора

Закон больших чисел В оценке заложена ошибка. Собственно, поэтому они и называются оценками. Один из способов контроля ошибок основан на законе больших чисел.[48] В частности, из этого закона следует, что при разбиении большой задачи на несколько меньших и независимой их


Не ждите больших новостей

Из книги автора

Не ждите больших новостей Метки: блогословие, темы блога, PR, СМИМаркетологи из информационно открытых компаний уже поняли, что по отношению к СМИ являются не просителями, а ньюсмейкерами. Они могут управлять информацией как ценным ресурсом – с пользой для своей


Текст фиксированного формата

Из книги автора

Текст фиксированного формата Аппетит приходит во время еды. Мы еще не успели доделать свою первую Web- страницу, а уже хотим сделать еще одну. Давайте же ее сделаем. Дадим аппетиту разгуляться!Новая Web-страница (листинг 2.10) будет посвящена тегу <TITLE>. Листинг 2.10 <!DOCTYPE


Наполнение больших каталогов

Из книги автора

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


3. Представление чисел в ЭВМ

Из книги автора

3. Представление чисел в ЭВМ 32-разрядные процессоры могут работать с оперативной памятью емкостью до 232-1, а адреса могут записываться в диапазоне 00000000 – FFFFFFFF. Однако в реальном режиме процессор работает с памятью до 220-1, а адреса попадают в диапазон 00000 – FFFFF. Байты памяти


Глава 18 Создание больших публикаций

Из книги автора

Глава 18 Создание больших публикаций При верстке многостраничных публикаций нам потребуются дополнительные знания и техники работы. Собственно говоря, некоторые из этих приемов могут и будут использоваться и при верстке одностраничных документов (например, при


3.1.1. Аппаратное представление целых чисел

Из книги автора

3.1.1. Аппаратное представление целых чисел Delphi относится к языкам, в которых целые типы данных максимально приближены к аппаратной реализации целых чисел процессором. Это позволяет выполнять операции с целочисленными данными максимально быстро, но заставляет


5.1. Представление чисел в языке Ruby

Из книги автора

5.1. Представление чисел в языке Ruby Если вы знакомы с любым другим языком программирования, то представление чисел в Ruby не вызовет у вас никакого удивления. Объект класса Fixnum может представлять число со знаком или без знака:237  # Число без знака (положительное).+237 # То же, что


11.9. Представление числового вектора фиксированного размера

Из книги автора

11.9. Представление числового вектора фиксированного размера ПроблемаТребуется иметь эффективное представление числовых векторов фиксированного размера.РешениеВ программном обеспечении обычного типа часто более эффектный результат по сравнению с valarray дает


Пример 22-6. Сравнение двух больших целых чисел

Из книги автора

Пример 22-6. Сравнение двух больших целых чисел #!/bin/bash# max2.sh: Наибольшее из двух БОЛЬШИХ целых чисел.# Это модификация предыдущего примера "max.sh",# которая позволяет выполнять сравнение больших целых чисел.EQUAL=0 # Если числа равны.MAXRETVAL=255 # Максимально возможное


2.3. Представление чисел в компьютере

Из книги автора

2.3. Представление чисел в компьютере Числовые данные обрабатываются в компьютере в двоичной системе счисления. Числа хранятся в памяти компьютера в двоичном коде, т. е. в виде последовательности нулей и единиц, и могут быть представлены в формате с фиксированной или


Создание подстановки из фиксированного набора значений

Из книги автора

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


2. Представление чисел в ЭВМ. Формализованное понятие алгоритма

Из книги автора

2. Представление чисел в ЭВМ. Формализованное понятие алгоритма 32-разрядные процессоры могут работать с оперативной памятью емкостью до 232-1, а адреса могут записываться в диапазоне 00000000 – FFFFFFFF. Однако в реальном режиме процессор работает с памятью до 220-1, а адреса