Trying to understand simple big number calculations

I am trying to better understand how 'big numbers' libraries work, (like GMP for example).

I want to write my own function to Add() / Subtract() / Multiply() / Divide()

The class is traditionally defined ...

std::vector<unsigned char> _numbers; // all the numbers
bool _neg; // positive or negative number
long _decimalPos; // where the decimal point is located
                  // so 10.5 would be 1
                  //    10.25 would be 2
                  //    10 would be 0 for example

First I need to normalise the numbers so I can do

Using 2 numbers 10(x) + 10.25(y) = 20.25

For simplicity, I would make them the same length,

For x: _numbers = (1,0,0,0) decimal = 2

For y: _numbers = (1,0,2,5) decimal = 2

And I can then reverse add x to y in a loop

...
// where x is 10.00 and y is 10.25
...
unsigned char carryOver = 0;
int totalLen = x._numbers.size();
for (size_t i = totalLen; i > 1 ; --i )
{
    unsigned char sum = x._numbers[i-1] + y._numbers[i-1] + carryOver;
    carryOver = 0;
    if (sum > _base)
    {
     sum -= _base;
     carryOver = 1;
    }
    numbers.insert( number.begin(), sum);
}

// any left over?
if (carryOver > 0)
{
  numbers.insert( number.begin(), 1 );
}

// decimal pos is the same for this number as x and y

...

The example above will work for adding two positive numbers, but will soon fall over once I need to add a negative number to a positive number.

And this gets more complicated when it comes to subtracting numbers, then even worse for multiplications and divisions.

Can someone suggest some simple functions to Add() / Subtract() / Multiply() / Divide()

I am not trying to re-write / improve libraries, I just want to understand how they work with numbers.

Solution

addition and substractions are pretty straightforward

You need to inspect signs and magnitudes of operands and if needed convert the operation to/from +/-. Typical C++ implementation of mine for this is like this:

//---------------------------------------------------------------------------
arbnum arbnum::operator + (const arbnum &x)
    {
    arbnum c;
    // you can skip this if you do not have NaN or Inf support
    // this just handles cases like adding inf or NaN or zero
    if (  isnan() ) return *this;
    if (x.isnan() ) { c.nan(); return c; }
    if (  iszero()) { c=x; return c; }
    if (x.iszero()) return *this;
    if (  isinf() ) { if (x.isinf()) { if (sig==x.sig) return *this;
                    c.nan(); return c; } return *this; }
    if (x.isinf()) { c.inf(); return c; }
    // this compares the sign bits if both signs are the same it is addition
    if (sig*x.sig>0) { c.add(x,this[0]); c.sig=sig; }
    // if not
    else{
        // compare absolute values (magnitudes)
        if (c.geq(this[0],x)) // |this| >= |x| ... return (this-x)
                {
                c.sub(this[0],x); 
                c.sig=sig;    // use sign of the abs greater operand
                }
        else    {             // else return (x-this)
                c.sub(x,this[0]);
                c.sig=x.sig;
                } 
        }
    return c;
    }
//---------------------------------------------------------------------------
arbnum arbnum::operator - (const arbnum &x)
    {
    arbnum c;
    if (  isnan() ) return *this;
    if (x.isnan() ) { c.nan(); return c; }
    if (  iszero()) { c=x; c.sig=-x.sig; return c; }
    if (x.iszero()) return *this;
    if (  isinf() ) { if (x.isinf()) { if (sig!=x.sig) return *this;
                    c.nan(); return c; } return *this; }
    if (x.isinf()) { c.inf(); c.sig=-x.sig;  return c; }
    if (x.sig*sig<0) { c.add(x,this[0]); c.sig=sig; }
    else{
        if (c.geq(this[0],x))
                {
                c.sub(this[0],x);
                c.sig=sig;
                }
        else    {
                c.sub(x,this[0]);
                c.sig=-x.sig;
                }
        }
    return c;
    }
//---------------------------------------------------------------------------

where:

geq is unsigned comparison greater or equal
add is unsigned +
sub is unsigned -

division is a bit more complicated

see:

bignum divisions
approximational bignum divider

For divisions you need to have already implemented things like +,-,*,<<,>> and for some more advanced approaches you need even things like: absolute comparison (you need them for +/- anyway) , sqr, number of used bits usually separate for fractional and integer part.

The most important is the multiplication see Fast bignum square computation because it is core for most division algorithms.

performance

for some hints see BigInteger numbers implementation and performance

text conversion

If your number is in ASCII or in BASE=10^n digits then this is easy but If you use BASE=2^n instead for performance reasons then you need to have fast functions capable of converting between dec and hex strings so you can actually load and print some numbers to/from your class. see: