──────────────────────────────────────────────────
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 signmagnitude 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 eightbit 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 32bit 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'scomplement 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 2
^{31}. 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:
b
^{x} = n (
b is the base,
x is the exponent, and
n is the product)
x = log
_{b}( n )
That is, given an
n value of the form b
^{x} 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 32bit 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:
log
_{16}( 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:
log
_{n}a
log
_{b}a = ─────
log
_{n}b
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.