C++

Forum

 
Bignum Challange

Pages: 1234
Duthomhas (13206)
As an integer class, you should implement integer division and integer remainder (/ and %).

Bignum systems will usually be organized something like:
1
2
3
4
5
 
+ bignum
  + bigcomplex
    + bigfloat
    + bigrational
      + biginteger
Duthomhas (13206)
───────────────────────────────────────────────────────
S O M E   T H O U G H T S   O N   A D D I T I O N   A N D   S U B T R A C T I O N
───────────────────────────────────────────────────────

Here I'll review some methods for doing addition and subtraction. Again, I assume your bignum class is composed of a list of digits in the number and a flag indicating the sign of the number.

First, a little terminology.

    a + b = c        a is the augend. b is the addend. c is the sum.
    a - b = c        a is the minuend. b is the subtrahend. c is the difference.

It is important to note that the difference obtained from a subtraction is a signed number -- it may be either postive or negative.

Also, the magnitude of a number is its absolute value.


──────── Sign & Algorithm Choice ────────

A little algebra is necessary for dealing with the signs of the numbers you are adding. You'll remember that in grade-school you learned that 4 + (-5) is the same as 4 - 5. Subtraction is nothing more than adding a negative number. Of course, implementing that behavior is another thing altogether.

With two's complement systems there is a little trickery involved to make addition and subtraction the same thing. But for all other systems, including with our big integers, addition and subtraction must be handled separately. The trick is in choosing which algorithm to apply. Here is where some algebra is handy.

Given two numbers, a and b, with an explicit sign, the following identities hold true:

    1.  +((+a) + (+b)) == -((-a) + (-b))
    2.    (+a) + (-b)  ==   (+a) - (+b)
    3.    (-a) + (+b)  ==   (-a) - (-b)

Identity 1 is pretty obvious: add two numbers with the same sign and you get a result with the same sign as the addends.

Identities 2 and 3 should draw your attention. Notice that only the sign of b changed when we switch from addition to subtraction? You should also notice that they are the same identity. The sign of a did not matter in the equation.

Where it does matter is in choosing whether we use identity 1 (stick with the current algorithm) or identity 2 aka 3 (switch to the other algorithm).

Simply put, if the sign of the numbers is different then you'll want to switch algorithms.


──────── Magnitude & Comparison ────────

When you implement your algorithms, the number with the greater magnitude should be the number on the top of your equation (the augend for addition, or the minuend for subtraction). In other terms, you must assure that

    |a| ≥ |b|

The reasons for this are not so obvious when dealing with addition, but the answer is simply -- implement addition using the operator += () function -- not the operator + () function.

For subtraction the rule simply assures that you do the least amount of work to compute your difference.

Be careful when checking magnitude. A gross indicator of relative magnitude is to compare the lengths of the numbers, but if the lengths are equal you need to compare the values of the most significant digit in each number. For example:

    123 ≥  79        True because '123' is longer than '79'.
    941 ≥ 284        True because '9' is greater than or equal to '2'.

If the most significant digits are equal, check each succeeding digit until you find a difference. Consider: is 941 ≥ 952 ?

Thus, in order to compute 28 - 93 you must reorder it to -(93 - 28).


──────── Addition ────────

The next thing to think about is how exactly to perform the addition and subtraction operations. At first I wanted to just use the STL algorithms and make life simple and pretty.

My big integer is stored with radix ten, and since a byte is sufficient to handle 102, I have enough storage to use a simple two-pass STL algorithm.

  1. Add each corresponding piece of the two numbers.
  2. Adjust for carries.

Notice how this algorithm deals with carries after the addition has been performed. This is similar to the grade-school method, but simply defers carrying instead of doing it as it goes.

Here is a little functor that deals with carries:

1
2
3
4
5
6
7
8
9
10
11
 
struct carry: public std::unary_function <char, char>
  {
  char k;
  carry(): k( 0 ) { }
  char operator () ( char digit )
    {
    char result = (k += digit) % radix;
    k /= radix;
    return result;
    }
  };

and here is the code in my operator += ( const bignum& b ) function that actually does the work of summation (after I have dealt with sign and magnitude issues):

1
2
3
 
std::transform( b.digits.begin(), b.digits.end(), digits.begin(), digits.begin(), std::plus <char> () );
digits.push_back( 0 );
std::transform( digits.begin(), digits.end(), digits.begin(), carry() );

All that needs to be done after that is make sure there aren't any extra zeros in the most-significant digit position. I have a little method does that. Short and sweet.

There's a problem. It takes two passes over the data. One to do the first add, and one to do the carries. For really, really big numbers, this can cause some excessive memory paging. It is also unsatisfactory simply because the logic of the carry is somewhere else in my code -- instead of with the addition itself.

It turns out that it is shorter and sweeter just to do it in a simple loop, keeping track of the carry after every addition. A single loop means just one pass over the digits of my number, minimizing memory accesses and potential memory paging. It also has the advantage that the logic of the operation is all in one spot, and much more readable and understandable.

Here is my improved algorithm:

1
2
3
4
5
6
7
8
9
 
int    carry = 0;
size_t i     = 0;
while (i < digits.size())
  {
  carry += digits[ i ] + ((i < b.digits.size()) ? b.digits[ i ] : 0);
  digits[ i++ ] = carry % radix;
  carry /= radix;
  }
if (carry) digits.push_back( carry );


to be continued...
Last edited on
Duthomhas (13206)
...continued
──────── Subtraction ────────

Subtraction is a tiny bit more complicated a subject. For the purposes of using just the STL, I thought about the 'subtraction by complements' method -- which is the basis for all computer subtraction. I found a good, simple description of it here:
http://www.sonoma.edu/users/w/wilsonst/courses/math_300/groupwork/altsub/3d.html

I liked it because it gave me the opportunity to reuse my carry functor above. Here was my STL subtraction (again after handling sign and magnitude issues):

1
2
3
4
5
6
 
std::transform( digits.begin(), digits.begin() + b.digits.size(), digits.begin(), std::bind2nd( std::plus <char> (), (char)9 ) );
std::transform( digits.begin(), digits.begin() + b.digits.size(), b.digits.begin(), digits.begin(), std::minus <char> () );
digits.push_back( 0 );
digits[ 0 ] += 1;
std::transform( digits.begin(), digits.end(), digits.begin(), carry() );
digits[ b.digits.size() ] -= 1;

Again it has that short, C/BCPL-esque brevity to it. And again, it is a bit difficult to really see what is happening. But this time it has the disadvantage of traversing the digits three times! Disaster!

It turns out that, just as before, a simple loop that tracks whether or not there was a borrow on the last iteration performs superiorly and is significantly more readable and debuggable.

Here is my new algorithm:

1
2
3
4
5
6
7
8
 
int    borrow = 0;
size_t i      = 0;
while (i < digits.size())
  {
  int d = digits[ i ] - ((i < b.digits.size()) ? b.digits[ i ] : 0) - borrow;
  if ((borrow = (d < 0))) d += radix;
  digits[ i++ ] = d;
  }

Oh, don't forget: after terminating, it is very likely that there are extraneous zero digits in the most significant places of your number. I apply my little class method to remove them. Of course, if your bigint class has a fixed number of digits, then you don't need to worry about this.


──────── Final thoughts ────────

You should notice, either from the link I gave you or from googling around "subtraction algorithms" that there are more than one way to skin this particular cat. Figure out how it works best for you and your design goals.

My design goals are:

    - keep code that does stuff together
    - keep memory accesses to a minimum
    - only introduce complexity to improve storage compactness (and hence, something yet to do)

The issues presented here become important when you decide to make a more industrial version of a bignum class. This challenge grew from my own desire to learn more about this particular subject. So the first thing I did is make a simple class that develops the concepts necessary to make a more advanced class later.

Well, enough of this lecture. I hope this proves useful to you.

:-)
Last edited on
m4ster r0shi (2201)
Duoas wrote:
It turns out that it is shorter and sweeter just to do it in a simple loop

But is it actually faster?

Take a look at this -> http://codepad.org/Jfrd1aTy
(for the loops version just don't define STL_WAY)

For the last multiplication,
doing it the STL way gives me times like (436, 172), while
doing it with loops gives me times like (568, 188).

Also, separating the adding from the carrying process, not only as sub-processes of the same function, but as different functions, is something very useful. When you want to add many numbers at the same time, doing it like this is way faster than performing carrying after each addition. And before someone says that this is a science fiction scenario that only exists inside my head, take a look at this here:

1
2
3
4
5
6
 
//...
    BigInt result(array[0]);

    for (int i=1; i<min_size; i++)
        result=result+(array[i]<<i);
//...

Here I add min_size numbers and perform carrying after each addition even though it's unnecessary...
It could be done much faster (suppose I've defined operator <<= ):

1
2
3
4
5
6
7
8
9
 
//...
    BigInt result;

    for (int i=1; i<min_size; i++)
        array[i]<<=i;

    result=add(array,min_size); //<- adds min_size numbers without carrying
    result=carry(result); //<- performs carrying only once
//...

I was hoping someone would notice this and make this optimization,
but I guess my expectations were too high... :/
Last edited on
m4ster r0shi (2201)
Okay, I've put some more effort into it and managed to reduce my times to (280, 110).
Also, Duoas can be happy now, as I only traverse my container once per operation :)

Here's the improved version -> http://codepad.org/cIqbzvRl
Duthomhas (13206)
Yay!

The real time stopper for bignum handling is memory accesses. The more times you traverse the number, the slower the functions. Hence, my recommendation for loops. m4ster r0shi has shown it very possible with the STL also.


I still can't replicate your results. My code was nearly identical to your penultimate posting and I'm still getting a difference when multiplying by an integer:
Each 100000 multiplications by int took X seconds
9999999999999999999999999999999999999999 * 9999
 = 99989999999999999999999999999999999999990001 (what it should be)
 = 99989999999999999999999999999999999999990001 (what it is)

Average using STL:   0.745 seconds
Average using loops: 0.285 seconds

This is compiling with -O2 optimizations and stripping the executable.
(I'll have to play with putting the add and carry operations together like you just did.)


The goal of this project isn't just pure fun, but as a stepping stone for writing more advanced bignum representations. Both of us have written our play systems storing the digits of the number with radix ten. This is really inefficient. I'm trying to encourage techniques that will translate to using radix N where N accomodates the maximum unsigned integer size of the CPU.


I've been ill these last few days, and I've had some other business to attend to this week, so I haven't had much time to play with everyone's entries. Hence, I think I will postpone that for next week -- meaning there is still time to post for those of you lurking here!

Also, since multiplication is the whole point of bignum systems, I suppose I'll post more about it eventually.

BTW, m4ster r0shi, it is entirely possible to do bignum long multiplication in linear space with fewer passes. Remember also to choose the shorter number for multiple passes (as they do it in grade school, that would mean to make the multiplicand the shorter number). Your idea to add and carry at the same time applies here, too. ;-)
m4ster r0shi (2201)
Oh, I didn't use any optimizations above.

Using -O2 with the last version some times gives (31, 31) and other times gives (31, 15) :P :D
(always talking about the times for the last multiplication)

Duoas wrote:
Both of us have written our play systems storing the digits
of the number with radix ten. This is really inefficient.

I agree.

Duoas wrote:
I'm trying to encourage techniques that will translate to using radix N
where N accommodates the maximum unsigned integer size of the CPU.

I'll try something like this in my next post here, then.
Last edited on
closed account (D80DSL3A)
Looks like I'd better get my submission in! It sounds like the deadline is near.

I went with a base 104 method so that my BigInts are contained in 4 digit chunks. I am using a magnitude + sign representation for them.
I am doing my array allocation manually (with new/delete) instead of using vectors.
The operators defined and used in the test program are just those needed to make everything work. I think I have developed all of the required features - including (of course) finding 100!

All code including a test program and its output are posted here:
http://codepad.org/9c6jSs2b

I'd like to include my BigInt class header here for the purpose of providing a summary/ preview.

BigInt.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#pragma once
#include <iostream>
#include <cmath>
#include <string>
using namespace std;

class BigInt
{
private:
	string str;// to hold string representation of BigInt
	bool isPositive;// for indicating the sign
	int len;// total # of digits in BigNum
	int lastLen;// length of last < 4 digit #
	int Nsubs;// # of 4 digit #'s	
	int* pInt;// pointer to array of integers, which will be used to dynamically allocate	
			  // Nsubs + 2 integers for the array. This should make the array large enough
			  // for worst case. z may be one digit longer than the longest of x or y
			  // due to carrying of a digit following the summation of x and y

	// private functions
	void addMags(const BigInt& x, const BigInt& y);// this->Nsubs must be right
	void subtractMags(const BigInt& larger, const BigInt& smaller);// this->Nsubs must be right
	void findCorrectLength(void);// reduces Nsubs to eliminate leading pInt[] == 0

public:
	// functions
	void INIT_userEntry(void);// prompts user for value
	void fillIntArray(void);// parses string into integer elements
	void to_string(void);// builds up string from integer elements
	void printElements(void);// lists elements and other info		
	bool isLowerMagnitude(const BigInt& x) const;	// for working with magnitudes only

	// operators
	BigInt& operator=(const BigInt& x);
	BigInt& operator=(const std::string& strVal);
	BigInt& operator=(int x);
	BigInt operator+(const BigInt& x) const;
	BigInt operator-(const BigInt& x) const;
	BigInt operator*(const BigInt& x) const;// BigInt * BigInt
	BigInt operator*(int x) const;// BigInt * int
	friend BigInt operator*(int x, const BigInt& BigX);// int * BigInt
	bool operator<(const BigInt& x) const;
	
	// constructors
	BigInt();// NULL construction (no allocation to pInt)
	BigInt( int length);// for given # of digits
	BigInt(const std::string& strVal);// for given string
	BigInt(const BigInt& x);// copy

	// destructor
	~BigInt();// deletion of pInt handled here	
};


This is what I submitted as an example for using the class and to support testing of most features:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
#include<iostream>
#include "BigInt.h"

using std::cout;
using std::cin;
using std::endl;

int main()
{
	//** testing constructors **
	BigInt x("-876543");// from string
	x.printElements();
	cout << "x = "; x.to_string();	

	BigInt z;// NULL construction
	z = "234";// assign from string
	BigInt y(x*z);// copy constructor with use of BigInt*BigInt operator
	y.printElements();// -876543*234 = -205111062
	cout << "y = "; y.to_string();

	//** testing multiplication of BigInt*int **
	z = 2;// assign integer value
	for( int j=3; j<=100; j++)// find 100! THE CRUCIAL TEST
		z = z*j;
	z.printElements();// all 40 4-digit elements shown
	cout << endl << "100! = "; z.to_string();

	//** testing addition and subtraction of BigInts **
	int k=0;// for looping

	// find 30!
	BigInt fact30("2");
	for( k=3; k<=30; k++)
		fact30 = fact30*k;
	cout << "30! = "; fact30.to_string();
	// find 40!
	BigInt fact40("2");
	for( k=3; k<=40; k++)
		fact40 = fact40*k;
	cout << "40! = "; fact40.to_string();
	// find 50!
	BigInt fact50("2");
	for( k=3; k<=50; k++)
		fact50 = k*fact50;// using int*BigInt operator
	cout << "50! = "; fact50.to_string();
		
	// perform a series of additions and subtractions of BigInts
	z = fact30 - fact50;// z = 30!-50!
	cout << " 30!-50! = "; z.to_string();

	z = z - fact30;// z = ( 30!-50! ) - 30! = -50!
	cout << "-50! = "; z.to_string();

	z = z + fact40;// z = -50! + 40!				
	cout << "-50!+40! = "; z.to_string();

	z = z + fact50;// z = ( -50!+40! ) + 50! = 40!
	cout << "40! = "; z.to_string();

	cout << endl;
	return 0;
}


@Douas: Hope you get well soon and that you can find the time to evaluate all the contest entries. You may have taken on a lot of work there!!

EDIT: My methods may differ a lot from the methods suggested in other posts in this thread. I avoided looking at any of the "tutorial" posts here because I wanted to figure this out entirely on my own.

EDIT2:
@m4ster0shi I borrowed from your code to time my BigInt*BigInt operation, but I am getting time = 0 for your biggest test case (which can't be right). Here is the code I am using. What is wrong with it?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
int start_s, stop_s;// for timing operations
BigInt x, z, prod;

x = "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789";

	z = "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"		
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
		"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789";	

start_s=clock();
prod = z*x;// timed process
stop_s=clock();

cout << "len = " << prod.getLength() << endl;// 2879 digits! wow!
cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;// I'm getting 0 here


OK - I tried looping that operation:
1
2
3
4
 
start_s=clock();
for(int j=0; j<10; j++)
	prod = z*x;// timed process
stop_s=clock();

That takes 16 milliseconds.
Last edited on
m4ster r0shi (2201)
fun2code wrote:
What is wrong with it?

Nothing. You're working with a bigger base. It's only natural your calculations are faster than mine.
closed account (D80DSL3A)
Thank you. I wasn't sure that my use of a bigger base would have that much of an effect on speed.
I'm working on a division method now, but it's not working out just yet...
closed account (D80DSL3A)
I have the division working now, so I have added these methods to my BigInt class:
1
2
3
4
5
6
7
 
BigInt operator/(const BigInt& x) const;// BigInt / BigInt - returns quotient
BigInt operator%(const BigInt& x) const;// BigInt % BigInt - returns remainder
BigInt operator/( int x) const;// BigInt / int
BigInt operator%( int x) const;// BigInt % int

// for use within the above operators
bool isLowerOrEqualMag(const BigInt& x) const;


That 1st operator was tough to work out, but I think I got it.
The other 3 were easy once I cracked that first one.

The new test program adds testing of the division operators to the first test program.
Here are 2 examples from it:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
BigInt numer, denom;
BigInt Q, rem;

// test #1	
numer = 2;// generating values below
for( j=3; j<=30; j++)// 30!
	numer = numer*j;
rem = 4567;
numer = numer + rem;// so numer = 30! + 4567	
denom = 21;
for( j=22; j<=30; j++)// so denom = 30!/20!
	denom = denom*j;// Q = 20! = 2432902008176640000, rem = 4567 expected
cout << endl << "** test #1 of division **" << endl;
cout << "numer = "; numer.to_string();
cout << "denom = "; denom.to_string();
Q = numer/denom;
cout << "quotient = "; Q.to_string();
rem = numer%denom;
cout << "remainder = "; rem.to_string();

// test #2
numer = "5735405000000";
denom = "654321";// Q = 8765430, rem = 76970 expected
cout << endl << "** test #2 **" << endl;
cout << "numer = "; numer.to_string();
cout << "denom = "; denom.to_string();
Q = numer/denom;
cout << "quotient = "; Q.to_string();
rem = numer%denom;
cout << "remainder = "; rem.to_string();


The use of base 104 turned out to be good for division too as the method finds 4 digits of the quotient at a time. My code is now a bit lengthy at 947 lines (including the test program). The full code and its test output is pasted here:
http://codepad.org/OtfWo0i4
hamsterman (4538)
Few suggestions: use of vectors could make your life much easier. You don't need to define operator for bigint and int if you have a constructor that takes int (and constructs a bigint with that value, unlike your current constructor)
closed account (D80DSL3A)
Thank you hamsterman. My main reason for not using vectors is that I've just barely started learning to use them. I didn't want to add that struggle to this project (and look like an idiot by not doing it right). However, this project has made it very clear that I should focus on learning to use them. There are an enormous number of allocations and deletions of arrays going on with the way I did this. Consider this simple addition and assignment: numer = numer + rem;
There are 2 allocations and deletions of arrays being done there. A local BigInt is constructed in the + operator and the l-value (numer) has its array deleted and re-allocated by the = operator every time, whether a larger array is needed or not (though I think I could easily correct for that).

As it happens, this challenge was posed right as I started a new job and had family visiting from out of state - so I had little time and had to hurry my work on this.

I created this constructor BigInt( int length);// for given # of digits because I need to construct based on length (array size) in the operators. I get around not having a constructor taking an integer value with this BigInt();// NULL construction (no allocation to pInt) followed by an assignment to an integer value. Having a constructor BigInt( int value); would be very useful though. I am considering making the constructor dual purpose by adding a 2nd argument ( char = 'L' or 'V' ) to indicate how the 1st (int) argument should be used. Does that seem convoluted though?

I'm thinking that I need some of the operators to be BigInt and int so I can do things like find a factorial value in a simple way (as in my test code above) or if I want to find BigInt/2, etc.

Thanks for the input. I'm sure I'll be refining this long after the current challenge has ended.
Duthomhas (13206)
──────────────────────────────────────────────────
S O M E   T H O U G H T S   O N   D E A L I N G   W I T H   I N T E G E R S
──────────────────────────────────────────────────

As I have played around with testing, I have been surprised with the difficulty of working with simple ints compared to the bignum class directly.

Here is something that my testing revealed to be problematic: two's complement representations.

The first problem is that division and remainder operations are not uniformly (or even always) defined on negative numbers across processors. This means that you really should make sure you are using a postive integer value when handling integers. This isn't such a trouble as your bignums should (probably) be in sign-magnitude representation already. (If it isn't I can assume you have special requirements and you know what it means for implementing your bignum.)

The next problem is a special corner case: the minimum value an integer may have. For simplicity in this lecture, I will assume integers have eight bits. That means that a two's complement representation will give an eight-bit integer a maximum value of 127 and a minimum value of -128.

Which leads to our problem: You cannot represent the smallest integer value as a positive integer value. But, you still want to work with it unsigned, since division and remainder operations produce inconsistently across processors. Here is my original code to convert an integer to a bignum:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
class bignum
  {
  private:
    static const int radix = 10;

    bool        is_negative;
    std::string digits;
    ...

  public:
    bignum& operator = ( int n )  //fails for n = -2147483648
      {
      is_negative = (n < 0);
      if (is_negative) n = -n;
      digits.clear();
      do digits.push_back( n % radix );
      while (n /= radix);
      return minimize();
      }

Notice the flaw: if I pass as argument a maximally small integer (-128 for our example, -2147483648 for my processor), line 14 will not do the right thing. On my processor (Intel Pentium), the number is not changed! (It is still negative!) Lines 16 and 17 are then compromised -- they do not perform as I think they are. (Both modulo and division produce negative values for me.) So right at the start two things are going horribly wrong.

We need, then, to handle the special case. Notice again that this special case is specific to two's complement number representations -- it is not a problem with other systems. Fortunately, our fixes do not interfere with other systems, since the trick is to adjust the number's value to be closer to zero.

You may ask, "Why not just use a larger integer type?" Sure, if I start with a char or short, but there are problems with that. C++'s integer types require a minimum number of bits per integer type, but not a maximum. Using GCC on my computer, both int and long are 32-bit entities. Remember also that a professional bigint will not use radix = 10; it will use the full bitspace of the available machine integer values.

So this is how I fixed my integer problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
    bignum& operator = ( int n )  //ok
      {
      bool is_adjust = false;
      is_negative = (n < 0);
      if (is_negative)
        {
        // This numeric limits stuff is to handle a special corner 
        // case with two's complement integer representations.
        is_adjust = (n == std::numeric_limits <int> ::min());
        if (is_adjust) n += 1;
        n = -n;
        }
      digits.clear();
      do digits.push_back( n % radix );
      while (n /= radix);
      if (is_adjust) *this -= 1;
      return minimize();
      }

On line 9 I checked to see if the integer is its maximally negative value. If it was, I adjusted its value closer to zero by one (line 10). This is representable as a positive integer value, so lines 11, 14, and 15 work properly.

Of course, now that are bignum value is off by one, we need to fix it, moving it away from zero by one, on line 16 (I have operator -= () overloaded for my bignum class).


──────── Multiplication by Integer ────────

There is one other place in my code that I needed to handle this special case: multiplication by int. My fix was simple: keep special code in one spot, if possible. If the argument value was the smallest integer value, I simply farmed out to the multiplication by bignum routine.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
    bignum operator * ( int n ) const
      {
      bignum result;

      if (n == 0)
        return result;

      result.is_negative = (n < 0);

      if (result.is_negative)
        {
        // A special case in two's-complement integer representations
        if (n == std::numeric_limits <int> ::min())
          return *this * bignum( n );

        n = -n;
        }

      ...

Now I can safely continue by assuming that it is possible to make n positive.


──────── Some Fun Math ────────

One last fun (though not necessarily useful) thing: when doing multiplication, you can determine the maximum number of digit elements needed in your result by simply adding the number of elements in your source bignum digit arrays.

    result.digits.resize( a.digits.size() + b.digits.size() );

When multiplying by integer, you can simply use a sufficiently large number, like 40.

    result.digits.resize( a.digits.size() + 40 );

But if you really want to know the answer, you'll need to study some mathematics. :-)
The number of digits required by your radix is conveniently defined by the logarithm function, which is the inverse of exponentiation.

For example, an integer on my Pentium processer is 32 bits wide. Subtract one for the sign bit and you have 31 bits of value. That's 231. To write that number in binary, you need, conveniently enough, 31 digits (binary digit values are '0' and '1').

So, how many digits is that in decimal? The identities you need are:

    bx = n    (b is the base, x is the exponent, and n is the product)

    x = logb( n )

That is, given an n value of the form bx you can learn what x is using the logarithm. If you are using base 10 (b = 10), then the STL gives you something useful:

    std::numeric_limits <int> ::digits10

This is the number of digits you can fully use with the parameterized type (int in this example). That is, it is the number of digits long your number may be where each digit may be any value from 0 to 9. It is possible (likely) that there is one more digit possible, but its value is limited. For my 32-bit Pentium, an int can represent nine digits fully, plus one digit with a value of 0, 1, or 2.

But, what if you are using some base other than radix 10? Back to logarithms: remember the definition. The number of digits you can fully represent in, say, radix 16 is:

    log16( std::numeric_limits <int> ::max() )

Of course, in C and C++, you don't have a <cmath> function to calculate the logarithm using any random base. You'll need one more mathematical identity:

            logna
    logba = ─────
            lognb

Since the base on the right side can be anything, any logarithm function will do, such as the <cmath> function log().

     static size_t ndigits_in_int = (log( std::numeric_limits <int> ::max() ) / log( radix )) + 1;

Well, that should be enough rambling. Hope you found it entertaining.
Last edited on
hamsterman (4538)
@fun2code, that constructor is not for your direct convenience. if you have a constructor bignum(int), c++ cas use that constructor to implicitly convert integers to bignums. See my code for an example. That way you don't need to rewrite every operator three times. ( bignum + bignum, int + bignum, bignum + int )

@Douas, that's all nice, but really, you said it yourself:
Remember also that a professional bigint will not use radix = 10; it will use the full bitspace of the available machine integer values.
So the 'lecture' isn't really useful.. Though I suppose someone might have learned some things from this.

Speaking of using base 2full bitspace, how should one deal with multiplication? I mean, sizeof(int*int) = 2*sizeof(int). In my code, I used a long long int, but as you mentioned, that is not a great solution.
One alternative I see is to split each int into two shorts, but then one multiplication turns into four.
Another one is to use asm, which (performance-wise) would be awesome, but not very portable..
What are your ideas?
closed account (z05DSL3A)
So the 'lecture' isn't really useful.. Though I suppose someone might have learned some things from this.

That reads as a very rude (impolite) tone.
hamsterman (4538)
ahh. sorry. I didn't mean it..
closed account (z05DSL3A)
The other day I found a listing of a BigNum class that was developed while I was at University. It's old and faded and Pre-Standard so may take me some time to type it back in and get it working.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
    class Integer
    {
    public:
        Integer(const char *str);
        Integer(int i);
        Integer(unsigned int i=0);
        Integer(long i);
        Integer(const Integer &v);
        ~Integer(){
            delete[]p;
        };
        
        friend Integer operator+(Integer x, const Integer &y);
        friend Integer operator-(Integer x, const Integer &y);
        friend Integer operator*(Integer x, const Integer &y);
        friend Integer operator/(Integer x, const Integer &y);
        friend Integer operator%(Integer u, const Integer &y);
        friend Integer operator<<(Integer x, unsigned int k);
        friend Integer operator>>(Integer x, unsigned int k);
        
        Integer operator-()const;
        Integer &operator=(const Integer &y);
        Integer &operator+=(const Integer &y);
        Integer &operator-=(const Integer &y);
        Integer &operator*=(int y);
        Integer &operator*=(Integer y);
        Integer &operator/=(Integer y);
        Integer &operator%=(Integer y); 
        Integer &operator<<=(unsigned int k);
        Integer &operator>>=(unsigned int k);
        
        friend  int operator==(const Integer &x, const Integer &y)
        {
            return x.compare(y) == 0;
        }
        friend int operator!=(const Integer &x, const Integer &y)
        {
            return x.compare(y) != 0;
        }
        friend int operator<(const Integer &x, const Integer &y)
        {
            return x.compare(y) < 0;
        }
        friend int operator>(const Integer &x, const Integer &y)
        {
            return x.compare(y) > 0;
        }
        friend int operator<=(const Integer &x, const Integer &y)
        {
            return x.compare(y) <= 0;
        }
        friend int operator>=(const Integer &x, const Integer &y)
        {
            return x.compare(y) >= 0;
        }
        friend std::ostream &operator<<(std::ostream &os, const Integer &v);
        friend std::istream &operator>>(std::istream &is, Integer &v);
        friend Integer power(Integer x, unsigned int n);
        friend Integer sqrt(const Integer &x);
        friend Integer abs(const Integer &x);
        
    private:
        unsigned int *p;
        int len;
        int Len;
        int neg;
        
        void IncrLen(int lenNew);
        int RoundUp(int i)const;
        void SetLen(unsigned int n);
        void reduce();
        void MakeLarge(unsigned int i);
        int compare(const Integer &y)const;
        void DDproduct( unsigned int A, unsigned int B, unsigned int &Hi, unsigned int &Lo)const;
        unsigned int DDquotient(unsigned int A, unsigned int B, unsigned int d)const;
        void subtractmul(unsigned int *a, unsigned int *b, int n, unsigned int &q)const;
        int normalise( Integer &denom, Integer &num, int &x)const;
        void unnormalise(Integer &rem, int x, int SecondDone)const;
        void divide (Integer denom, Integer &quot, Integer &rem, int RemDesired)const;
        
        friend class numstring;
        
    };

Duthomhas (13206)
You forget that even if you use a full-sized integer value that you must still account for the minimum two's complement value properly in order to make your integer non-negative.

For my optimized biginteger class, I simply access the array as a series of half-values for multiplication purposes. This way I can directly access the data as either full or half integer value arrays, and the algorithms that use them are significantly uncomplicated. That said, I still need to do some profiling to learn which is faster.

Big number multiplication is slow, but processor multiplication is still relatively fast. The idea is to reduce as many bignum multiplications as possible. You have to do all those processor multiplications... (If you are smart, you only need to do three instead of four though.)

The question about sizeof(int) has nothing to do with the number of bytes used by the int, but the maximum number of bigits used to store a full-sized integer value.

...
hamsterman (4538)
You forget that even if you use a full-sized integer value that you must still account for the minimum two's complement value properly in order to make your integer non-negative.

nope. try it:
1
2
3
4
5
6
7
8
9
 
void f(int i){
     int j = i;
     if(i < 0){
          std::cout << "i is negative, ";
          i = -i;
     }
     unsigned val = i;
     std::cout << "i is " << j << ", unsigned i is " << val <<'\n';
}

(or is this behaviour unportable?)

For my optimized biginteger class, I simply access the array as a series of half-values for multiplication purposes.
Makes sense, but I have a feeling this is very much slower than a long long int (and especially asm).

edit: my integer class. I did / and % while was at school. http://pastebin.com/9T4fAGEh
will do decimal input/output next. then maybe some optimizations..
Last edited on
Pages: 1234