Since modern possessors are highly efficient when dealing with fixed bit length numbers why don't you have an array of them?
Suppose you use unsigned long long. They should be 64 bits width, so max possible unsigned long long should be 2^64 - 1. Lets represent any number as a collection of numbers as:
-big_num = ( n_s, n_0, n_1, ...)
-n_s will take only 0 and 1 to represent + and - sign
-n_0 will represent number between 0 and 10^a -1 (exponent a to be determent)
-n_1 will represent number between 10^a and 10^(a+1) -1
and so on, and so on ...
DETERMINING a:
All n_ MUST be bounded by 10^a-1. Thus when adding two big_num this means we need to add the n_ as follow:
// A + B = ( (to be determent later),
// bound(n_A_1 + n_B_1) and carry to next,
// bound(n_A_2 + n_B_2 + carry) and carry to next,
// ...)
The bounding can be done as:
bound(n_A_i + n_B_i + carry) = (n_A_i + n_B_i + carry)%(10^a)
Therefore the carry to i+1 is determined as:
// carry (to be used in i+1) = (n_A_i + n_B_i + carry)/(10^a)
// (division of unsigned in c++ will floor the result by construction)
This tell us that the worst case is carry = 10^a -1, and thus the worst addition (n_A_i + n_B_i + carry) is:
(worst case) (10^a-1) + (10^a-1) + (10^a-1) = 3*(10^a-1)
Since type is unsigned long long if we don't want to have overflow on this addition we must bound our exponent a such that:
// 3*(10^a-1) <= 2^64 - 1, and a an positive integer
// => a <= floor( Log10((2^64 - 1)/3 + 1) )
// => a <= 18
So this has now fixed are maximum possible a=18 and thus the biggest possible n_ represented with unsigned long long is 10^18 -1 = 999,999,999,999,999,999. With this basic set up lets now get to some actual code. For now I will use std::vector to hold the big_num we discussed, but this can change:
// Example code with unsigned long long
#include <cstdlib>
#include <vector>
//
// FOR NOW BigNum WILL BE REPRESENTED
// BY std::vector. YOU CAN CHANGE THIS LATTER
// DEPENDING ON WHAT OPTIMIZATIONS YOU WANT
//
using BigNum = std::vector<unsigned long long>;
// suffix ULL garanties number be interpeted as unsigned long long
#define MAX_BASE_10 999999999999999999ULL
// random generate big number
void randomize_BigNum(BigNum &a){
// assuming MyRandom() returns a random number
// of type unsigned long long
for(size_t i=1; i<a.size(); i++)
a[i] = MyRandom()%(MAX_NUM_BASE_10+1); // cap the numbers
}
// wrapper functions
void add(const BigNum &a, const BigNum &b, BigNum &c); // c = a + b
void add(const BigNum &a, BigNum &b); // b = a + b
// actual work done here
void add_equal_size(const BigNum &a, const BigNum &b, BigNum &c, size_t &N);
void add_equal_size(const BigNum &a, const BigNum &b, size_t &N);
void blindly_add_one(BigNum &c);
// Missing cases
// void add_equal_size(BigNum &a, BigNum &b, BigNum &c, size_t &Na, size_t &Nb);
// void add_equal_size(BigNum &a, BigNum &b, size_t &Na, size_t &Nb);
int main(){
size_t n=10;
BigNum a(n), b(n), c(n);
randomize_BigNum(a);
randomize_BigNum(b);
add(a,b,c);
return;
}
The wrapper functions should look as follows. They will safe guard against incorrect size of array calls:
// To do: add support for when size of a,b,c not equal
// c = a + b
void add(const BigNum &a, const BigNum &b, BigNum &c){
c.resize(std::max(a.size(),b.size()));
if(a.size()==b.size())
add_equal_size(a,b,c,a.size());
else
// To do: add_unequal_size(a,b,c,a.size(),b.size());
return;
};
// b = a + b
void add(const BigNum &a, const BigNum &b){
if(a.size()==b.size())
add_equal_size(a,b,a.size());
else{
b.resize(a.size());
// To do: add_unequal_size(a,b,a.size());
}
return;
};
The main grunt of the work will be done here (which you can call directly and skip a function call, if you know what you are doing):
// If a,b,c same size array
// c = a + b
void add_equal_size(const BigNum &a, const BigNum &b, BigNum &c, const size_t &N){
// start with sign of c is sign of a
// Specific details follow on whether I need to flip the
// sign or not
c[0] = a[0];
unsigned long long carry=0;
// DISTINGUISH TWO GRAND CASES:
//
// a and b have the same sign
// a and b have oposite sign
// no need to check which has which sign (details follow)
//
if(a[0]==b[0]){// if a and b have the same sign
//
// This means that either +a+b or -a-b=-(a+b)
// In both cases I just need to add two numbers a and b
// and I already got the sign of the result c correct form the
// start
//
for(size_t i=1; i<N;i++){
c[i] = (a[i] + b[i] + carry)%(MAX_BASE_10+1);
carry = c[i]/(MAX_BASE_10+1);
}
if(carry){// if carry>0 then I need to extend my array to fit the final carry
c.resize(N+1);
c[N]=carry;
}
}
else{// if a and b have opposite sign
//
// If I have opposite sign then I am subtracting the
// numbers. The following is inspired by how
// you can subtract two numbers with bitwise operations.
for(size_t i=1; i<N;i++){
c[i] = (a[i] + (MAX_BASE_10 - b[i]) + carry)%(MAX_BASE_10+1);
carry = c[i]/(MAX_BASE_10+1);
}
if(carry){ // I carried? then I got the sign right from the start
// just add 1 and I am done
blindly_add_one(c);
}
else{ // I didn't carry? then I got the sign wrong from the start
// flip the sign
c[0] ^= 1ULL;
// and take the compliment
for(size_t i=1; i;<N;i++)
c[i] = MAX_BASE_10 - c[i];
}
}
return;
};
A few details about the // if a and b have opposite sign case follow:
Lets work in base 10. Lets say we are subtracting a - b Lets convert this to an addition. Define the following operation:
Lets name the base 10 digits of a number di. Then any number is n = d1 + 10*d2 + 10*10*d3... The compliment of a digit will now be defined as:
`compliment(d1) = 9-d1`
Then the compliment of a number n is:
compliment(n) = compliment(d1)
+ 10*compliment(d2)
+ 10*10*compliment(d3)
...
Consider two case, a>b and a<b:
EXAMPLE OF a>b: lest say a=830 and b=126. Do the following 830 - 126 -> 830 + compliment(126) = 830 + 873 = 1703 ok so if a>b, I drop the 1, and add 1 the result is 704!
EXAMPLE OF a<b: lest say a=126 and b=830. Do the following 126 - 830 -> 126 + compliment(830) = 126 + 169 = 295 ...? Well what if I compliment it? compliment(295) = 704 !!! so if a<b I already have the result... with opposite sign.
Going to our case, since each number in the array is bounded by MAX_BASE_10 the compliment of our numbers is
compliment(n) = MAX_BASE_10 - n
So using this compliment to convert subtraction to addition
I only need to pay attention to if I carried an extra 1 at
the end of the addition (the a>b case). The algorithm now is
- FOR EACH ARRAY subtraction (ith iteration):
- na_i - nb_i + carry(i-1)
- convert -> na_i + compliment(nb_i) + carry(i-1)
- bound the result -> (na_i + compliment(nb_i) + carry(i-1))%MAX_BASE_10
find the carry -> (na_i + compliment(nb_i) + carry(i-1))/MAX_BASE_10
keep on adding the array numbers...
At the end of the array if I carried, forget the carry
and add 1. Else take the compliment of the result
This "and add one" is done by yet another function:
// Just add 1, no matter the sign of c
void blindly_add_one(BigNum &c){
unsigned long long carry=1;
for(size_t i=1; i<N;i++){
c[i] = carry%(MAX_BASE_10+1);
carry = c[i]/(MAX_BASE_10+1);
}
if(carry){ // if carry>0 then I need to extend my basis to fit the number
c.resize(N+1);
c[N]=carry;
}
};
Good up to here. Specifically in this code don't forget that at the start of the function we set the sign of c to the sign of a. So if I carry at the end, that means I had |a|>|b| and I did either +a-b>0 or -a+b=-(a-b)<0. In either case setting the results c sign to a sign was correct. If I don't carry I had |a|<|b| with either +a-b<0 or -a+b=-(a-b)>0. In either case setting the results c sign to a sign was INCORRECT so I need to flip the sign if I don't carry.
The following functions opperates the same way as the above one, only rather than do c = a + b it dose b = a + b
// same logic as above, only b = a + b
void add_equal_size(BigNum &a, BigNum &b, size_t &N){
unsigned long long carry=0;
if(a[0]==b[0]){// if a and b have the same sign
for(size_t i=1; i<N;i++){
b[i] = (a[i] + b[i] + carry)%(MAX_BASE_10+1);
carry = b[i]/(MAX_BASE_10+1);
}
if(carry){// if carry>0 then I need to extend my basis to fit the number
b.resize(N+1);
b[N]=carry;
}
}
else{ // if a and b have oposite sign
b[0] = a[0];
for(size_t i=1; i<N;i++){
b[i] = (a[i] + (MAX_BASE_10 - b[i]) + carry)%(MAX_BASE_10+1);
carry = b[i]/(MAX_BASE_10+1);
}
if(carry){
add_one(b);
}
else{
b[0] ^= 1ULL;
for(size_t i=1; i;<N;i++)
b[i] = MAX_BASE_10 - b[i];
}
}
return;
};
And that is a basic set up on how you could use unsigned numbers in arrays to represent very large integers.
WHERE TO GO FROM HERE
Their are many thing to do from here on out to optimise the code, I will mention a few I could think of:
-Try and replace addition of arrays with possible BLAS calls
-Make sure you are taking advantage of vectorization. Depending on how you write your loops you may or may not be generating vectorized code. If your arrays become big you may benefit from this.
-In the spirit of the above make sure you have properly aligned arrays in memory to actually take advantage of vectorization. From my understanding std::vector dose not guaranty alignment. Neither dose a blind malloc. I think boost libraries have a vector version where you can declare a fixed alignment in which case you can ask for a 64bit aligned array for your unsigned long long array. Another option is to have your own class that manages a raw pointer and dose aligned allocations with a custom alocator. Borrowing aligned_malloc and aligned_free from https://embeddedartistry.com/blog/2017/02/22/generating-aligned-memory/ you could have a class like this to replace std::vector:
// aligned_malloc and aligned_free from:
// https://embeddedartistry.com/blog/2017/02/22/generating-aligned-memory/
// wrapping in absolutly minimal class to handle
// memory allocation and freeing
class BigNum{
private:
unsigned long long *ptr;
size_t size;
public:
BigNum() : ptr(nullptr)
, size(0)
{};
BigNum(const size_t &N) : ptr(nullptr)
, size(N)
{
resize(N);
}
// Defining destructor this will now delete copy and move constructor and assignment. Make your own if you need them
~BigNum(){
aligned_free(ptr);
}
// Access an object in aligned storage
const unsigned long long& operator[](std::size_t pos) const{
return *reinterpret_cast<const unsigned long long*>(&ptr[pos]);
}
// return my size
void size(){
return size;
}
// resize memory allocation
void resize(const size_t &N){
size = N;
if(N){
void* temp = aligned_malloc(ptr,N+1); // N+1, always keep first entry for the sign of BigNum
if(temp!=nullptr)
ptr = static_cast<unsigned long long>(temp);
else
throw std::bad_alloc();
}
else{
aligned_free(ptr);
}
}
};
