Why to use higher base for implementing BigInt?
The CPU cycles spent multiplying or adding a number that fits in a register tend to be identical. So you will get the least number of iterations, and best performance, by using up the whole register. That is, on a 32-bit architecture, make your base unit 32 bits, and on a 64-bit architecture, make it 64 bits. Otherwise--say, if you only fill up 8 bits of your 32 bit register--you are wasting cycles.
How using large base is more efficient when writing custom BigInt in Java
Using what we would consider a natural base, such as 10, leads to lots of operations. Have you ever multiplied two 9-digit numbers? Using a method that we typically learn in school, that would involve 81 digit multiplications. However, Java would use one multiply instruction.
What about large numbers, such as 18-digit numbers? For us, that would involve 324 digit multiplications. Here, the implementation would use 2 ints, equivalent to multiplying 2-digit numbers for us. That would result in 4 multiplication instructions for Java.
Why not use a larger base in Java, to further reduce the number of operations? Because of multiplication. It is guaranteed that the result of multiplying two ints in Java will fit in a long, and 1 billion (10^9) is the largest power of 10 that fits in an int. These operations are still very easy for Java - just multiply instructions. It is possible to use a somewhat larger number, such as 2 billion, or Integer.MAX_VALUE (slightly over 2 billion), but that answer chose to use 1 billion, for human readability purposes. Anything larger than Integer.MAX_VALUE would require something with larger ranges, but that's what the answer is already trying to do.
Also, using less ints in the representation saves on memory usage.
The code
int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;
attempts to determine how many ints are needed in the internal representation to store the incoming number as a String representation. It's 9 decimal digits per int. I would have used Math.ceil( (double) decLen / BASE_DECIMAL_POINTS).
What is the simplest way of implementing bigint in C?
If you're looking for a simple library, libtommath (from libtomcrypt) is probably what you want.
If you're looking to write a simple implementation yourself (either as a learning exercise or because you only need a very limited subset of bigint functionality and don't want to tack on a dependency to a large library, namespace pollution, etc.), then I might suggest the following for your problem:
Since you can bound the size of the result based on n, simply pre-allocate an array of uint32_t of the required size to hold the result. I'm guessing you'll want to print the result, so it makes sense to use a base that's a power of 10 (i.e. base 1000000000) rather than a power of 2. That is to say, each element of your array is allowed to hold a value between 0 and 999999999.
To multiply this number by a (normal, non-big) integer n, do something like:
uint32_t carry=0;
for(i=0; i<len; i++) {
uint64_t tmp = n*(uint64_t)big[i] + carry;
big[i] = tmp % 1000000000;
carry = tmp / 1000000000;
}
if (carry) big[len++] = carry;
If you know n will never be bigger than 100 (or some other small number) and want to avoid going into the 64-bit range (or if you're on a 64-bit platform and want to use uint64_t for your bigint array), then make the base a smaller power of 10 so that the multiplication result will always fit in the type.
Now, printing the result is just something like:
printf("%lu", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.9lu", (long)big[i-1]);
putchar('\n');
If you want to use a power of 2 as the base, rather than a power of 10, the multiplication becomes much faster:
uint32_t carry=0;
for(i=0; i<len; i++) {
uint64_t tmp = n*(uint64_t)big[i] + carry;
big[i] = tmp;
carry = tmp >> 32;
}
if (carry) big[len++] = carry;
However, printing your result in decimal will not be so pleasant... :-) Of course if you want the result in hex, then it's easy:
printf("%lx", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.8lx", (long)big[i-1]);
putchar('\n');
Hope this helps! I'll leave implementing other things (like addition, multiplication of 2 bigints, etc) as an exercise for you. Just think back to how you learned to do base-10 addition, multiplication, division, etc. in grade school and teach the computer how to do that (but in base-10^9 or base-2^32 instead) and you should have no problem.
How to represent a number in base 2³²?
You are trying to find something of the form
a0 + a1 * (2^32) + a2 * (2^32)^2 + a3 * (2^32)^3 + ...
which is exactly the definition of a base-232 system, so ignore all the people that told you that your question doesn't make sense!
Anyway, what you are describing is known as base conversion. There are quick ways and there are easy ways to solve this. The quick ways are very complicated (there are entire chapters of books dedicated to the subject), and I'm not going to attempt to address them here (not least because I've never attempted to use them).
One easy way is to first implement two functions in your number system, multiplication and addition. (i.e. implement BigInt add(BigInt a, BigInt b) and BigInt mul(BigInt a, BigInt b)). Once you've solved that, you will notice that a base-10 number can be expressed as:
b0 + b1 * 10 + b2 * 10^2 + b3 * 10^3 + ...
which can also be written as:
b0 + 10 * (b1 + 10 * (b2 + 10 * (b3 + ...
so if you move left-to-right in your input string, you can peel off one base-10 digit at a time, and use your add and mul functions to accumulate into your BigInt:
BigInt a = 0;
for each digit b {
a = add(mul(a, 10), b);
}
Disclaimer: This method is not computationally efficient, but it will at least get you started.
Note: Converting from base-16 is much simpler, because 232 is an exact multiple of 16. So the conversion basically comes down to concatenating bits.
Big integer numbers & C
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);
}
}
};
Implementing BigInteger
You need to implement two functions for your UINT1024 class, multiply by integer and add integer. Then for each digit you convert, multiply the previous value by 10 and add the value of the digit.
How to implement big int in C++
Things to consider for a big int class:
Mathematical operators: +, -, /,
*, % Don't forget that your class may be on either side of the
operator, that the operators can be
chained, that one of the operands
could be an int, float, double, etc.I/O operators: >>, << This is
where you figure out how to properly
create your class from user input, and how to format it for output as well.Conversions/Casts: Figure out
what types/classes your big int
class should be convertible to, and
how to properly handle the
conversion. A quick list would
include double and float, and may
include int (with proper bounds
checking) and complex (assuming it
can handle the range).
Related Topics
Pointer Comparisons ">" with One Before the First Element of an Array Object
How to Change Directshow Filter Properties C++
Differencebetween If (Null == Pointer) VS If (Pointer == Null)
Vs: Unexpected Optimization Behavior with _Bitscanreverse64 Intrinsic
Can You Access Private Member Variables Across Class Instances
Create 2D Array Using Size from Parameters in C++
Cin >> Fails with Bigger Numbers But Works with Smaller Ones
How to Test Whether a Number Is a Power of 2
Calculating Execution Time in C++
How to Test Whether Class B Is Derived from Template Family of Classes
Throwing the Fattest People Off of an Overloaded Airplane
How to Build a Program Using C++ Driver of Mongodb
How to Resume Input Stream After Stopped by Eof in C++