What Variable Type For Extremely Big Integer Numbers

What variable type can I use to hold huge numbers (30+ digits) in java?

You can use BigInteger class.

BigInteger bi1 = new BigInteger("637824629384623845238423545642384"); 
BigInteger bi2 = new BigInteger("3039768898793547264523745379249934"); 

BigInteger bigSum = bi1.add(bi2);
        
BigInteger bigProduct = bi1.multiply(bi2);
       
System.out.println("Sum : " + bigSum);
System.out.println("Product : " + bigProduct);

Output:

Sum : 3677593528178171109762168924892318

Product : 1938839471287900434078965247064711159607977007048190357000119602656

I should mention BigDecimal, which is excellent for amount calculations compare to double.

BigDecimal bd = new BigDecimal("123234545.4767");
BigDecimal displayVal = bd.setScale(2, RoundingMode.HALF_EVEN);

NumberFormat usdFormat = NumberFormat.getCurrencyInstance(Locale.US);        
System.out.println(usdFormat.format(displayVal.doubleValue()));

Output:

$123,234,545.48

How should I store a extremely large Data Type

You can create and edit BigInteger In java, e.g.:

BigInteger bigInteger = new BigInteger("3");
bigInteger = bigInteger.pow(600);
bigInteger = bigInteger.add(new BigInteger("20"));
bigInteger = bigInteger.subtract(new BigInteger("20"));
bigInteger = bigInteger.multiply(new BigInteger("20"));
bigInteger = bigInteger.divide(new BigInteger("20"));

And you can get any part of BigInteger as an Integer, e.g.:

int i = Integer.parseInt(bigInteger.toString().substring(3, 8));

I hope this will help you.

Which data type to use for a very large numbers in C++?

long long is fine, but you have to use a suffix on the literal.

long long x = 600851475143ll; // can use LL instead if you prefer.

If you leave the ll off the end of the literal, then the compiler assumes that you want it to be an int, which in most cases is a 32-bit signed number. 32-bits aren't enough to store that large value, hence the warning. By adding the ll, you signify to the compiler that the literal should be interpreted as a long long, which is big enough to store the value.

The suffix is also useful for specifying which overload to call for a function. For example:

void foo(long long x) {}
void foo(int x) {}

int main()
{
    foo(0); // calls foo(int x)
    foo(0LL); // calls foo(long long x)
}

How to store extremely large numbers?

If you already have a boost dependency (which many people these days do), you can use the boost multi-precision library. In fact, it already has an example of a factorial program that can support output up to 128 bits, though extending it further is pretty trivial.

Large Numbers in Java

You can use the BigInteger class for integers and BigDecimal for numbers with decimal digits. Both classes are defined in java.math package.

Example:

BigInteger reallyBig = new BigInteger("1234567890123456890");
BigInteger notSoBig = new BigInteger("2743561234");
reallyBig = reallyBig.add(notSoBig);

Extremely large numbers in javascript

You are going to need a javascript based BigInteger library. There are many to choose from. Here is one https://github.com/peterolson/BigInteger.js

You can use it like this

var n = bigInt("91942213363574161572522430563301811072406154908250")
    .plus("91942213363574161572522430563301811072406154908250");

Number too big for BigInteger

First of all, you need to check your physics / chemistry text book.

Avogadro's number is not 602,200,000,000,000,000,000,000. It is approximately 6.022 x 10²³. The key word is "approximately". As of 2019, the precise value is 6.02214076×10²³ mol⁻¹

(In 2015 when I originally wrote this reply, the current best approximation for Avogadro's number was 6.022140857(74)×10²³ mol⁻¹, and the relative error was +/- 1.2×10^–8. In 2019, the SI redefined the mole / Avogadro's number to be the precise value above. Source: Wikipedia)

My original (2015) answer was that since the number only needed 8 decimal digits precision, the Java double type was an appropriate type to represent it. Hence, I recommended:

final double AVOGADROS_CONSTANT = 6.02214076E23;

Clearly, neither int or long can represent this number. A float could, but not with enough precision (assuming we use the best available measured value).

Now (post 2019) the BigInteger is the simplest correct representation.

---

Now to your apparent problems with declaring the constant as (variously) an double, a long and a BigInteger.

I expect you did something like this:

  double a = 602200000000000000000000;

and so on. That isn't going to work, but the reason it won't work needs to be explained. The problem is that the number is being supplied as an int literal. An int cannot be that big. The largest possible int value is 2³¹ - 1 ... which is a little bit bigger than 2 x 10⁹.

That is what the Java compiler was complaining about. The literal is too big to be an int.

It is too big for long literal as well. (Do the math.)

But it is not too big for a double literal ... provided that you write it correctly.

The solution using BigInteger(String) works because it side-steps the problem of representing the number as a numeric literal by using a string instead, and parsing it at runtime. That's OK from the perspective of the language, but (IMO) wrong because the extra precision is an illusion.

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);
    }
  }
};

---

Related Topics