-3

I have started writing a bignum library, with a vector of shorts to represent the value, a print function, and negative number support. However, I cannot find a good way to implement long addition, like this:

 123
+123
----
 246

The latest code I have that doesn't give a segfault is this:

void add(unsigned long long b)
    {   
        for(long long i=v.size()-1;i>=0;--i)
        {
            if((b+v[i])<10)
                v[i]+=b;
            else // Carry
                {
                    if(i==0) // 1st digit
                    {
                        v.push_front(1); // Can't be more than 1
                    }
                    else
                        v[i-1]++; // Increment digit to the left
                }

        }
    }

, but addition with a carry is not correct (10+1 is 21)

EDIT: It is implemented as a class

built1n
  • 1,518
  • 14
  • 25
  • 4
    Addition is simple. You add digits, and if the sum is larger than a single digit can hold, have a carry for the next place. – Daniel Fischer Mar 31 '13 at 18:25
  • 1
    Unless you *really* want `base-10` digits, bignum libraries typically use `base-B`, where `B=2**w` and `w` is the number of bits in the (unsigned) integer type. – Brett Hale Mar 31 '13 at 18:42
  • 1
    "*it doesn't do anything*" When `v.size()` is `1`, what work do you see this function doing? – Drew Dormann Mar 31 '13 at 18:45
  • When I assign it a value of 1, it still does nothing to the value – built1n Apr 01 '13 at 12:49
  • The carry mechanism is incorrect – built1n Apr 01 '13 at 13:09
  • @Daniel Fischer: How to detect an overflow? – SasQ Apr 21 '14 at 10:17
  • @SasQ That depends on the chosen representation. If the type you use for the digits can hold `2*(base-1)`, then you can just add and check whether the result is `>= base` afterwards. If it can't, you can check whether `base-digit_1 > digit_2` to see whether there will be a carry. – Daniel Fischer Apr 21 '14 at 10:27
  • @Daniel Fischer: In the first case, doesn't it mean that there's always 1 bit wasted in each word? The second choice seems better, but it has some overhead (subtraction and comparison) over just plain addition. Long time ago I used a technique in 6502 assembly which simply used the CPU's carry flag for that, and it is the quickest solution I guess. Can it be used somehow from C/C++ level? Or going down to the assembly level is the only option if one needs speed? – SasQ Apr 21 '14 at 12:54
  • @SasQ Yes, in the first case, we need one extra bit per digit. Depending on the base you choose for the representation, that may however be a machine constraint. If you choose base 100, you need an octet per digit or use some time-consuming bit-fiddling to use only seven bits per digit (I'm aware that one ought to use a power of 2 for the base if efficiency is desired, just covering possibilities). If you use machine-word digits, I'd also guess checking the carry-flag is the fastest. But I think you need inline assembly (or assembly functions) for that from C or C++, can't check it directly. – Daniel Fischer Apr 21 '14 at 13:10
  • Will it work if I wrap such assembly into an `inline` function and call it where I need to check the carry? – SasQ Apr 21 '14 at 13:29
  • If you want to perform the multi-precision math yourself, then I suggest you take a look at Donald Knuth's [Art of Computer Programming](https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming). I believe Volume II, Seminumerical Algorithms, Chapter 4, Multiple Precision Arithmetic, is what you are interested in. – jww Aug 29 '17 at 17:42

1 Answers1

0

Consider passing 11 to the function:
If vector[i] >= 0, then b+vector[i] > 11, thus b+vector[i]<10 will never be true.

A few other things:

  • You're using vector and v, I'm pretty sure there should only be one.

  • i>0 should be i>=0, otherwise the loop skips the first element.

  • Having each element represent a digit is a bit overkill. You can have each element represent 0-65535 (range of unsigned short). Just change 10 to 65535 below. Or 0-10000 may also make sense, since then breaking up into digits would be simpler.

  • Shouldn't the function rather take in a parameter of type of your BigNum class?

  • A loop from first to last element would make more sense.

A better (untested) add function may look like: 

const int BASE = 10;
void add(unsigned long long b)
{
    for (int i = 0; b > 0 && i < v.size(); ++i)
    {
        unsigned long long val = b + v[i];
        b = val / BASE;
        v[i] = val % BASE;
    }
    // if adding more digits
    while (b > 0)
    {
        v.push_back(b % BASE);
        b /= BASE;
    }
}
Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138