Diggins PDP #3 : arbitrary precision integers

christopher diggins

// big_int.hpp
// The Diggins PDP (Public Domain Post) #3
// Public Domain code by Christopher Diggins, May 22, 2005
//
// Description:
// A naively implemented unsigned integer type for arbitrarily large
// values. Implemented using vector<bool>

#ifndef BIG_INT_HPP
#define BIG_INT_HPP

#include <limits>
#include <vector>
#include <algorithm>
#include <functional>
#include <stdexcept>
#include <cassert>
#include <iostream>
#include "binary_arithme tic.hpp" // Diggins PDP #1.2

#include <cassert>

namespace cdiggins
{
class big_int_impl
{
typedef big_int_impl self;
public:
self() {
}
self(const big_int_impl& x) : bits(x.bits) {
}
self(const std::vector<boo l>& x) : bits(x) {
bits = x;
}
self(int x) {
while (x) {
bits.push_back( x & 0x1);
x >>= 1;
}
}
self& operator=(const std::vector<boo l>& x) {
bits = x;
return *this;
}
self& operator<<=(int n) {
if (n == 0) return *this;
resize(size() + n);
for (int i=size() - 1; i >= n; i--) {
bits[i] = bits[i - n];
}
for (int i=n-1; i >= 0; i--) {
bits[i] = false;
}
truncate_leadin g_zeros();
return *this;
}
self& operator>>=(int n) {
if (n == 0) return *this;
if (n >= size()) return *this = 0;
for (int i=0; i < size() - n; i++) {
bits[i] = bits[i + n];
}
resize(size() - n);
return *this;
}
self operator++(int) {
self i = *this;
operator+=(1);
return i;
}
self operator--(int) {
self i = *this;
operator-=(1);
return i;
}
self& operator++() {
operator+=(1);
return *this;
}
self& operator--() {
operator-=(1);
return *this;
}
self& operator+=(cons t self& x) {
bool carry = false;
if (x.size() > size()) resize(x.size() );
for (int i = 0; i < size(); i++) {
bits[i] = full_adder(bits[i], x[i], carry);
}
if (carry) {
resize(size() + 1);
bits[size() - 1] = 1;
}
truncate_leadin g_zeros();
return *this;
}
self& operator-=(const self& x) {
assert(x <= *this);
if (x == 0) return *this;
bool borrow = false;
for (int i = 0; i < size(); i++) {
bits[i] = full_subtractor (bits[i], x[i], borrow);
}
assert(!borrow) ; // should be no borrowing
truncate_leadin g_zeros();
return *this;
}
self& operator*=(self x) {
std::vector<boo l> v = bits;
*this = 0;
for (int i=0; i < static_cast<int >(v.size()); i++)
{
if (v[i]) {
*this += x;
}
x <<= 1;
}
return *this;
}
self& operator/=(const self& x) {
return *this = divide_quotient (*this, x);
}
self& operator%=(cons t self& x) {
return *this = divide_remainde r(*this, x);
}
self operator~() const {
std::vector<boo l> v = bits;
for (int i=0; i<static_cast<i nt>(v.size()); i++) {
v[i] = !v[i];
}
return v;
}
self& operator&=(self x) {
if (x.size() > size()) {
resize(x.size() );
}
if (x.size() < size()) {
x.resize(size() );
}
std::transform( bits.begin(), bits.end(), x.bits.begin(), bits.begin(),
std::logical_an d<bool>());
truncate_leadin g_zeros();
return *this;
}
self& operator|=(self x) {
if (x.size() > size()) {
resize(x.size() );
}
if (x.size() < size()) {
x.resize(size() );
}
std::transform( bits.begin(), bits.end(), x.bits.begin(), bits.begin(),
std::logical_or <bool>());
truncate_leadin g_zeros();
return *this;
}
self& operator^=(self x) {
if (x.size() > size()) {
resize(x.size() );
}
if (x.size() < size()) {
x.resize(size() );
}
std::transform( bits.begin(), bits.end(), x.bits.begin(), bits.begin(),
&logical_xor<bo ol>);
truncate_leadin g_zeros();
return *this;
}
bool operator[](int n) const {
if (n >= size()) return false;
return bits[n];
}
int size() const {
return static_cast<int >(bits.size() );
}
unsigned long to_ulong() {
int digits = std::numeric_li mits<unsigned long>::digits;
if (size() >= digits) {
throw std::domain_err or("out of range for unsigned long");
}
unsigned long ret = 0;
unsigned long tmp = 1;
for (int i=0; i < digits; i++) {
if (operator[](i)) {
ret |= tmp;
}
tmp <<= 1;
}
return ret;
}
// friend functions
friend self operator<<(cons t self& x, unsigned int n) {
return self(x) <<= n;
}
friend self operator>>(cons t self& x, unsigned int n) {
return self(x) >>= n;
}
friend self operator+(const self& x, const self& y) {
return self(x) += y;
}
friend self operator-(const self& x, const self& y) {
return self(x) -= y;
}
friend self operator*(const self& x, const self& y) {
return self(x) *= y;
}
friend self operator/(const self& x, const self& y) {
return self(x) /= y;
}
friend self operator%(const self& x, const self& y) {
return self(x) %= y;
}
friend self operator^(const self& x, const self& y) {
return self(x) ^= y;
}
friend self operator&(const self& x, const self& y) {
return self(x) &= y;
}
friend self operator|(const self& x, const self& y) {
return self(x) |= y;
}
// comparison operators
friend bool operator==(cons t self& x, const self& y) {
if (x.size() != y.size()) return false;
for (int i=0; i < x.size(); i++) {
if (x[i] != y[i]) {
return false;
}
}
return true;
}
friend bool operator!=(cons t self& x, const self& y) {
return !(x == y);
}
friend bool operator>(const self& x, const self& y) {
int i = x.size();
if (i > y.size()) return true;
if (i < y.size()) return false;
while (i--) {
if (x[i] > y[i]) return true;
if (x[i] < y[i]) return false;
}
return false;
}
friend bool operator<(const self& x, const self& y) {
int i = x.size();
if (i > y.size()) return false;
if (i < y.size()) return true;
while (i--) {
if (x[i] > y[i]) return false;
if (x[i] < y[i]) return true;
}
return false;
}
friend bool operator>=(cons t self& x, const self& y) {
return (x > y) || (x == y);
}
friend bool operator<=(cons t self& x, const self& y) {
return (x < y) || (x == y);
}
private:
void resize(int n) {
int old = size();
bits.resize(n);
for (int i=old; i < n; i++) {
bits[i] = false;
}
}
void truncate_leadin g_zeros() {
int sig_digit = -1;
for (int i=0; i<size(); i++) {
if (bits[i]) {
sig_digit = static_cast<int >(i);
}
}
resize(sig_digi t + 1);
}
std::vector<boo l> bits;
};

typedef big_int_impl big_int;
}

///////////////////////////////////////////////////
// test code

#include <iostream>
#include <iterator>

void test_failure(co nst char* x) {
std::cerr << "TEST failed " << x << std::endl;
}
#define TEST(TKN) if (!(TKN)) { test_failure(#T KN); } /* */

namespace big_int_test
{
using namespace cdiggins;

std::ostream& operator<<(std: :ostream& o, big_int x)
{
std::vector<int > v;
if (x == 0) {
o << 0;
return o;
}
while (x > 0) {
v.push_back((x % 10).to_ulong()) ;
x /= 10;
}
std::copy(v.rbe gin(), v.rend(), std::ostream_it erator<int>(o)) ;
return o;
}

// makes a big int as a power of base to the power
big_int make_big_int(in t base, int power) {
big_int ret = 1;
for (int i=0; i < power; i++) {
ret *= base;
}
return ret;
}

void simple_test(big _int n)
{
big_int original = n;
std::cout << n << std::endl;

TEST(n == n);
TEST(n >= n);
TEST(n <= n);
TEST(!(n < n));
TEST(!(n > n));
TEST(n != 0);
TEST(!(n == 0));
TEST(n > 0);
TEST(n >= 0);
TEST(!(n < 0));
TEST(!(n <= 0));

TEST((n >> 1) <= n);
TEST((n << 1) >= n);

TEST(0 + n == n);
TEST(n + 0 == n);
TEST(n - 0 == n);
TEST(n - n == 0);
TEST(n * 1 == n);
TEST(n * 0 == 0);
TEST(n / 1 == n);
TEST(n / n == 1);
TEST(n % n == 0);
TEST(n % 1 == 0);

TEST((n += 0) == n);
TEST(n == original);
TEST((n -= 0) == n);
TEST(n == original);
TEST((n *= 1) == n);
TEST(n == original);
TEST((n /= 1) == n);
TEST(n == original);

TEST(n != n + 1);
TEST(n < n + 1);
TEST(n < n * 2);
TEST(n <= n * n);
TEST(n != (n - 1));
TEST(n > (n - 1));
TEST(n == original);

TEST((n & 1) == n[0]);
TEST((n & 1) == n % 2);
TEST((n & ~n) == 0);
TEST((n | n) == n);
TEST(((n ^ n) ^ n) == n);
TEST(n == original);

TEST(n * 2 == n << 1);
TEST(n * 2 == n + n);
TEST(n + n + n == n * 2 + n);
TEST(n + n + n == n * 3);
TEST(n / 2 == n >> 1);
TEST((n * 3) / 3 == n);
TEST(n == original);
TEST(n * 2 == n * 3 - n);
TEST(n == (n / 2) * 2 + (n % 2));
TEST(n == (n / 3) * 3 + (n % 3));
TEST(n == original);

big_int m = n;
for (int i=0; i<16; i++) {
TEST(m++ == n + i);
}
while (--m > n) { }

TEST(m == n);
TEST(m++ == n);
TEST(m == n + 1);
TEST(++m == n + 2);
TEST(m-- == n + 2);
TEST(--m == n);
TEST(m == n);
TEST(--m == n - 1);
TEST(n == original);
}

void test_main()
{
// check out all the small numbers
int i=1;
for (; i<64; i++) {
std::cout << "testing " << i << std::endl;
simple_test(i);
}
// check out some bigger numbers
for (; i<640; i += 13) {
std::cout << "testing " << i << std::endl;
simple_test(i);
}
// check out some even bigger numbers
for (; i<6400; i += 151) {
std::cout << "testing " << i << std::endl;
simple_test(i);
}
// check out various powers of two
for (int i=4; i < 64; i++) {
std::cout << "testing 2 raised to the power of " << i << std::endl;
simple_test(mak e_big_int(2, i));
}
// check out various powers of three
for (int i=2; i < 32; i++) {
std::cout << "testing 3 raised to the power of " << i << std::endl;
simple_test(mak e_big_int(3, i));
}
// check out various powers of five
for (int i=2; i < 20; i++) {
std::cout << "testing 5 raised to the power of " << i << std::endl;
simple_test(mak e_big_int(5, i));
}
// check out various powers of eleven
for (int i=2; i < 10; i++) {
std::cout << "testing 11 raised to the power of " << i << std::endl;
simple_test(mak e_big_int(11, i));
}
}
}

#endif

Jul 23 '05 #1

Subscribe Reply

1082

Similar topics

1418

Arbitrary precision binary floats?

by: Thinkit | last post by:

Are there any good libraries of arbitrary precision binary floats? I'd like to specify the mantissa length and exponent range. Hexadecimal output would be best (decimal is disgusting with binary floats).

Java

1702

Arbitrary precision binary float class?

by: Thinkit | last post by:

Are there any packages for arbitrary precision binary floats? Something along the lines of Gnu Multi Precision. I saw quite a few rationals classes, but not this. Just looking to be able to use any mantissa or exponent I want. Of course it would be software based arithmetic.

Java

1472

PLEASE HELP - Linkage problem in gcc 3.2.3 with arbitrary precision arithmetic

by: cpptutor2000 | last post by:

Could some C++ guru please help me? I am using a BigInteger class which is really a wrapper around a C source file(mpi.c) that does arbitrary precision arithmetic operations. When I compile the C file using gcc -g -o mpi mpi.c rng.c -lm there are NO compilation or linking errors. However, when I try to compile the C++ wrapper class using g++ -g -o bigint bigint.C mpi.c rng.c -lm, I get strange linkage problems that all the functions in...

C / C++

3065

Arbitrary precision decimal numbers

by: Mattias Brändström | last post by:

Hello! I am trying to find a minimal class/lib that handles arbitrary precision decimal numbers. I would be happy if this class supported as little as addition, subtraction, multiplication, division and comparisons. For some reason it's quite hard to find such a class on the net. Maybe because it is trivial to implement such a class? The only library I have found so far is MAPM (http://www.tc.umn.edu/~ringx004/mapm-main.html). This...

C / C++

2740

Diggins PDP #1 : Binary Arithmetic Algorithms (division / multiplication / full_adder )

by: christopher diggins | last post by:

Welcome to the first installment of the Diggins Public Domain Posts (PDP). There is a significant dearth of good public domain C++ code. All of it seems to come with one kind of a license or another, and even though I understand the motivations, I believe code is like mathematics and no one can really own it. Rather than stand on a pulpit, or debate the philosophical merits of the various licenses, I have decided instead to post as much...

C / C++

1970

GNU GMP arbitrary precision limitations

by: Jack | last post by:

Quick question, does anyone know what the limitations are, besides memory for GMP, and also, if I write software that uses this library, is it true that it may run differently on different hardware classes of machines ? In other words, the same calculation on 1 machine would have a different result than another machine would have .. Thanks ! Jack

C / C++

2872

Arbitrary precision modulo operation

by: Chadwick Boggs | last post by:

I need to perform modulo operations on extremely large numbers. The % operator is giving me number out of range errors and the mod(x, y) function simply seems to return the wrong results. Also, my numerator is in the format of a quoted string, which the mod function can't take. Desparately searching for solutions, Chadwick. ---------------------------(end of broadcast)---------------------------

PostgreSQL Database

2080

Heap overflow/corruption problem in an arbitrary precision class

by: Martin the Third | last post by:

Hi, I need some help! I'm writing an infinite-precision floating point library called ipfloat (I know infinite is a misnomer - but arbitrary was taken). A quick overview: I'm storing numbers as a char* mantissa, an int exponent and a sign. For example, the number "123.45" would have a mantissa of 12345, an exponent of 2, and a sign of +. I'm essentially storing it as "1.2345x10^2". The mantissa is allocated dynamically at runtime to...

C / C++

1896

New python module to simulate arbitrary fixed and infinite precisionbinary floating point

by: Rob Clewley | last post by:

Dear Pythonistas, How many times have we seen posts recently along the lines of "why is it that 0.1 appears as 0.10000000000000001 in python?" that lead to posters being sent to the definition of the IEEE 754 standard and the decimal.py module? I am teaching an introductory numerical analysis class this fall, and I realized that the best way to teach this stuff is to be able to play with the representations directly, in particular to be...

Python

9645

What is ONU?

by: marktang | last post by:

ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...

General

10325

Problem With Comparison Operator <=> in G++

by: Oralloy | last post by:

Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...

C / C++

10147

Maximizing Business Potential: The Nexus of Website Design and Digital Marketing

by: jinu1996 | last post by:

In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...

Online Marketing

10091

The easy way to turn off automatic updates for Windows 10/11

by: Hystou | last post by:

Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...

Windows Server

6739

Couldn’t get equations in html when convert word .docx file to html file in C#.

by: conductexam | last post by:

I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...

C# / C Sharp

5381

Trying to create a lan-to-lan vpn between two differents networks

by: TSSRALBI | last post by:

Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...

Networking - Hardware / Configuration

4050

transfer the data from one system to another through ip address

by: 6302768590 | last post by:

Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

C# / C Sharp

3645

How to add payments to a PHP MySQL app.

by: muto222 | last post by:

How can i add a mobile payment intergratation into php mysql website.

PHP

2879

Comprehensive Guide to Website Development in Toronto: Expert Insights from BSMN Consultancy

by: bsmnconsultancy | last post by:

In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

General