N: A C++ bignum Header-only Library with Thread Support and Static Memory Usage Support

• https://github.com/WindowsNT/N

Introduction

This is a new version of my older library. Native types can only be as large as 2^64 in a form of unsigned long long. Sometimes, you need math between much larger numbers (for example, in cryptography). This class allows math between any size big number, as long as your available memory can handle it.

Compile Definitions

If you define N_MT, it includes a small C++ only Threadpool library. This allows to do multi-core additions and multiplications.

By default, the library uses std::vector. However, you may want to restrict memory allocations if the numbers are limited, so, by defining N_SMALLVECTOR, it includes a LLVM implementation of a small vector here. This version (stripped from LLVM dependencies) has a compile time maximum stack capacity and if the vector grows beyond that, then it allocates memory.

The N Class Internals

N is a template class, taking an integer which by default is 100 - the maximum number of digits before heap allocation must occur if you define N_SMALLVECTOR (If you don't define N_SMALLVECTOR, then this number is ignored because it uses std::vector instead).

N stores all its digits in a vector<D> (D being a typedef for unsigned char), as a decimal array, a base value (default 10) to know what base system the digits are, and a bool flag to keep the sign value. Construction is done via either an integer, or a string:

N<> n(5LL);
N<> n(-12438LL);
N<> n("384747274747282882818373"); // If a non digit is encountered, parsing stops
N<> n("-274727372737");
N<> n("111",2); // n = 7

N has also a member function ParseBase:

N n;
n.ParseBase("FFFF",16);  // n = 65535

N Representation and Access

In the debug version of the library, after each operation that changes N, a special function is called to aid you in debugging.

N::operator[](size_t) gives the specific digit from the right, for example, if n = 12345 then n[0] is 5. If the specified digit exceeds the number, the function does not crash, but returns 0 instead, allowing itself to be used when adding or multiplying.

Function s(unsigned long long base = b); returns a string representation of N, in the specified base system.

Function tobase(unsigned long long nb) returns a new N which stores the same value in a different base system.

Function upperpart() and lowerpart() return a subpart of the number:

N<> a("12345");
auto a2 = a.upperpart(2); // a2 = 12
auto a3 = a.lowerpart(3); // a3 = 345
a.Set(16LL);
auto str = a.s();         // str = "16"
str = a.tobase(2).s();    // str = "10000"
str = a.tobase(16).s();   // str = "10"
str = a.tobase(10).s();   // str = "16" 

Addition and Multiplication

A simple loop of the digits.

size_t j = 0;
   for (size_t i = 0; i < n1.NumDigits() || i < n2.NumDigits() ; i++)
       {
       j = i;
       D sum = n1[i] + n2[i] + carry;
       carry = 0;
       if (sum >= n1.b)
           {
           carry = 1;
           sum -= n1.b;
           }
       n.n.push_back(sum);
       }
   n.n.push_back(carry);
   n.RemoveZeroes();
   }

When trying a multithread addition (if there are more than two items to be added), we use the thread pool:

static N<static_digits> w_add2(n_vv<N<static_digits>>& n, ThreadPool& pool)
{
    if (n.size() == 0)
        return 0LL;
    if (n.size() == 1)
        return n[0];
    if (n.size() == 2)
    {
        N res = n[0];
        res += n[1];
        return res;
    }
    struct Z
    {
        N<static_digits>* n1;
        N<static_digits>* n2;
        N<static_digits>* res;
        std::future<void> v;
    };
    n_vv<Z> z(n.size());
    n_vv<N<static_digits>> res(n.size() / 2);

    for (size_t i = 0; i < n.size(); i += 2)
    {
        if (i == (n.size() - 1))
            break; // odd number of additions

        auto a = [](Z* z)
        {
            *z->res = w_add(*z->n1, *z->n2);
        };
        Z& zz = z[i];
        zz.n1 = &n[i];
        zz.n2 = &n[i + 1];
        zz.res = &res[i / 2];

        zz.v = pool.enqueue([&](Z* z) { a(z); }, &zz);
    }
    for (size_t i = 0; i < n.size(); i += 2)
    {
        if (z[i].v.valid())
            z[i].v.get();
    }
    if (n.size() % 2)
        res.push_back(n[n.size() - 1]);
    return w_add2(res, pool);
}

The same function is called from the multicore multiplication function:

static N<static_digits> w_mul2(const N<static_digits>& n1, 
       const N<static_digits>& n2, ThreadPool& pool)
    {
        size_t muls = n1.NumDigits() * n2.NumDigits();
        n_vv<N<static_digits>> a;
        a.reserve(muls);
        for (size_t i = 0; i < n1.NumDigits(); i++)
        {
            for (size_t ii = 0; ii < n2.NumDigits(); ii++)
            {
                N<static_digits> rr;
                D d1 = n1[i];
                D d2 = n2[ii];
                unsigned long long r = d1 * d2;
                rr = r;
                rr.shl(ii + i);
                a.push_back(rr);
            }
        }
        return w_add2(a, pool);
    }

Operators and the pow() function eventually call these functions.

Division

This cannot be spawn in multiple threads. It returns the division result and a remainder in a std::tuple:

static std::tuple<N<static_digits>, N<static_digits>> w_div(const N<static_digits>& n1, 
       const N<static_digits>& n2, bool NoChangeBase = false)
    {
        if (n1.b != n2.b && NoChangeBase == false)
            return w_div(n1.b, n2.tobase(n1.b));
        if (n2 > n1)
        {
            N<static_digits> res = n1;
            return std::make_tuple<N<static_digits>, 
                   N<static_digits>>(0LL, std::forward<N<static_digits>>(res));
        }
        if (n2 == n1)
            return std::make_tuple<N<static_digits>, N<static_digits>>(1LL, 0LL);

        N<static_digits> rem = n1;
        N<static_digits> res;
        res.ChangeInternalBase(n1.b);

        for (;;)
        {
            auto nd2 = n2.NumDigits();
            auto upper = rem.upperpart(nd2);
            if (upper < n2)
            {
                nd2++;
                upper = rem.upperpart(nd2);
                if (upper < n2)
                {
                    // End...
                    return std::make_tuple<N, N>(std::forward<N>(res), 
                           std::forward<N>(rem));
                }
            }

            D js = 9;
            N<static_digits> m1;
            for (; js >= 1; js--)
            {
                m1 = w_mul(n2, js);
                if (m1 < upper)
                    break;
            }

            res.n.insert(res.n.begin(), js);
#ifdef N_DEBUG
            res.srx();
#endif
            upper -= m1;
            upper.shl(rem.NumDigits() - nd2);
            upper += rem.lowerpart(rem.NumDigits() - nd2);
            rem = upper;
        }
    }

Logical Operations

Operator &,|,^ and friends eventually call the logical function:

static N<static_digits> w_logical(const N<static_digits>& n1, 
                        const N<static_digits>& n2, int x)
    {
        if (n1.b != 2)
            return w_logical(n1.tobase(2), n2, x);
        if (n2.b != 2)
            return w_logical(n1, n2.tobase(2), x);

        N<static_digits> n;
        n.ChangeInternalBase(2);
        n.n.reserve(std::max(n1.NumDigits(), n2.NumDigits()));

        for (size_t i = 0; i < n1.NumDigits() || i < n2.NumDigits(); i++)
        {
            D sum = 0;
            if (x == 0) sum = n1[i] & n2[i];
            if (x == 1) sum = n1[i] | n2[i];
            if (x == 2) sum = n1[i] ^ n2[i];
            n.n.push_back(sum);
#ifdef N_DEBUG
            n.srx();
#endif
        }
        n.RemoveZeroes();
        return n;
    }

This is slow. It requires converting the N to base-2 which means a lot of digits if the number is high.

Memory Usage

Except the s() function which returns a std::string, the rest of the class uses the smallvector which allows for stack-allocations when the number size is known and switches automatically to heap allocation when it gets high.

History

• 6^th September, 2022: Second release