Trying to understand simple big number calculations

Question

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.

If you know how to do long arithmetic with pencil and paper, you don't need a library. If you don't, a library won't help you. — n. m. could be an AI, Nov 22 '15 at 05:34
At least you're dealing with simple not complex numbers.. :P — Paul Evans, Nov 22 '15 at 05:41
Did you try to have a look to the implementation this kind of feature? (on https://gmplib.org/devel/repo-usage.html), you will probably have better details about implementation than the one we can give here in 2 or 3 lines. Nevertheless, I would say that people write lib exactly because they don't want to bother with the complexity of implementation when they use the lib. If things were trivial and really simple, probably you wouldn't even think to making them a lib. — OznOg, Nov 22 '15 at 08:42
Yes, I did have a look at it, but for obvious reasons they optimise a lot of their code, and how simple calculations are done is lost in some of those optimisations. I just wanted to try understand the logic of some of those libraries. — FFMG, Nov 22 '15 at 09:10
[This question in Java.](http://stackoverflow.com/q/5318068/2336725) — Teepeemm, Nov 22 '15 at 14:17

score 2 · Accepted Answer · edited May 23 '17 at 12:15

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:

Thanks a lot, this really helps! – FFMG Nov 22 '15 at 12:43 — FFMG, Nov 22 '15 at 12:43

Trying to understand simple big number calculations

1 Answers1