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
– n. m. could be an AI, Commented Nov 22, 2015 at 5:34
At least you're dealing with simple not complex numbers.. :P — Paul Evans
– Paul Evans, Commented Nov 22, 2015 at 5:41
Did you try to have a look to the implementation this kind of feature? (on 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
– OznOg, Commented Nov 22, 2015 at 8: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
– FFMG, Commented Nov 22, 2015 at 9:10

Community · Accepted Answer · 2017-05-23 12:15:13Z

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:

Collectives™ on Stack Overflow

Trying to understand simple big number calculations

1 Answer 1

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Linked

Related