## How to handle very large numbers in Java without using java.math.BigInteger

How would I go about doing arithmetic, + - / * % !, with arbitrarily large integers without using `java.math.BigInteger`

?

For instance, the factorial of 90 returns 0 in Java. I would like to be able to solve that.

I think a programmer should have implemented his own bignum-library once, so welcome here.

(Of course, later you'll get that BigInteger is better, and use this, but it is a valuable learning experience.)

(You can follow the source code of this course life on github. Also, I remade this (a bit polished) into a 14-part blog series.)

##### Creating a simple Big number class in Java

So, what do we need?

##### First, a representation of the number,

based on the datatypes which Java gives us.

As you think the decimal conversion is the most complicated part, let's stay in a decimal based mode. For efficiency, we'll store not real decimal digits, but work in base `1 000 000 000 = 10^9 < 2^30`

. This fits in a Java `int`

(up to `2^31`

or `2^32`

), and the product of two such *digits* fits nicely in a Java `long`

.

final static int BASE = 1000000000; final static int BASE_DECIMAL_DIGITS = 9;

Then the digits-array:

private int[] digits;

Do we store the digits in little- or big endian, i.e. the bigger parts first or last? It does not really matter, so we decide on big-endian since this is how humans want to read it. (For now we concentrate on non-negative values - later we'll add a sign bit for negative numbers.)

For testing purposes, we add a constructor which allows initializing from such a int[].

/** * creates a DecimalBigInt based on an array of digits. * @param digits a list of digits, each between 0 (inclusive) * and {@link BASE} (exclusive). * @throws IllegalArgumentException if any digit is out of range. */ public DecimalBigInt(int... digits) { for(int digit : digits) { if(digit < 0 || BASE <= digit) { throw new IllegalArgumentException("digit " + digit + " out of range!"); } } this.digits = digits.clone(); }

As a added bonus, this constructor is also usable for a single `int`

(if smaller than `BASE`

), and even for no `int`

(which we'll interpret as 0). So, we now can do this:

DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345); System.out.println(d);

This gives us `de.fencing_game.paul.examples.DecimalBigInt@6af62373`

, not so useful. So, we add a `toString()`

method:

/** * A simple string view for debugging purposes. * (Will be replaced later with a real decimal conversion.) */ public String toString() { return "Big" + Arrays.toString(digits); }

The output is now `Big[7, 5, 2, 12345]`

, which is more useful for testing, isn't it?

##### Second, conversion from decimal format.

We are lucky here: our base (10^9) is a power of the base we want to convert from (10). Thus, we always have the same number (9) of decimal digits representing one "our format" digit. (Of course, in the beginning there may be some digits less.) In the following code, `decimal`

is a String of decimal digits.

int decLen = decimal.length(); int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;

This strange formula is a Java int way of writing `bigLen = ceil(decLen/BASE_DECIMAL_DIGITS)`

. (I hope it is correct, we'll later test it.)

int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;

This is the length of the first block of decimal digits, should be between 1 and 9 (inclusive).

We create our array:

int[] digits = new int[bigLen];

Looping through the digits to be created:

for(int i = 0; i < bigLen ; i++) {

Each of *our* digits is represented by a block of digits in the original number:

String block = decimal.substring(Math.max(firstSome + (i-1)*BASE_DECIMAL_DIGITS, 0), firstSome + i *BASE_DECIMAL_DIGITS);

(The `Math.max`

is needed here for the first shorter block.)
We now use the usual Integer parsing function, and put the result into the array:

digits[i] = Integer.parseInt(block); }

From the array now created we create our DecimalBigInt object:

return new DecimalBigInt(digits);

Let's see if this works:

DecimalBigInt d2 = DecimalBigInt.valueOf("12345678901234567890"); System.out.println(d2);

Output:

Big[12, 345678901, 234567890]

Looks right :-) We should test it with some other numbers (of different length) too.

Next part will be decimal formatting, this should be even easier.

##### Third, conversion to decimal format.

We need to output our individual digits as 9 decimal digits each. For this we can use the `Formatter`

class, which supports printf-like format strings.

A simple variant would be this:

public String toDecimalString() { Formatter f = new Formatter(); for(int digit : digits) { f.format("%09d", digit); } return f.toString(); }

This returns `000000007000000005000000002000012345`

and `000000012345678901234567890`

for our two numbers. This works for a round-trip (i.e. feeding it to the `valueOf`

method gives an equivalent object), but the leading zeros are not really nice to look at (and could create confusion with octal numbers). So we need to break apart our beautiful for-each loop and use a different formatting string for the first and the following digits.

public String toDecimalString() { Formatter f = new Formatter(); f.format("%d", digits[0]); for(int i = 1 ; i < digits.length; i++) { f.format("%09d", digits[i]); } return f.toString(); }

##### Addition.

Let's start with addition, as this is simple (and we can use parts of it for the multiplication later).

/** * calculates the sum of this and that. */ public DecimalBigInt plus(DecimalBigInt that) { ... }

I want method names that you can read like you would read the formula, thus `plus`

, `minus`

, `times`

instead of `add`

, `subtract`

, `multiply`

.

So, how does addition work? It works the same as we learned it in school for decimal numbers higher than 9: add the corresponding digits, and if for some of then the result is bigger than 10 (or `BASE`

in our case), carry one to the next digit. This can cause the resulting number to have one digit more than the original ones.

First we look at the simple case that both numbers have same number of digits. Then it looks simply like this:

int[] result = new int[this.digits.length]; int carry = 0; for(int i = this.digits.length-1; i > 0; i--) { int digSum = carry + this.digits[i] + that.digits[i]; result[i] = digSum % BASE; carry = digSum / BASE; } if(carry > 0) { int[] temp = new int[result.length + 1]; System.arraycopy(result, 0, temp, 1, result.length); temp[0] = carry; result = temp; } return new DecimalBigInt(result);

(We go from right to left, so we can carry any overflows to the next digit. This would be a bit prettier if we had decided using Little Endian format.)

If both numbers do not have the same number of digits, it gets a bit more complicated.

To let it as simple as possible, we split it to several methods:

This method adds one digit to an element in the array (which may already contain some non-zero value), and stores the result back in the array. If there was overflow, we carry it to the next digit (which has index one less, not one more) by means of a recursive call. This way we make sure our digits stay always in the valid range.

/** * adds one digit from the addend to the corresponding digit * of the result. * If there is carry, it is recursively added to the next digit * of the result. */ private void addDigit(int[] result, int resultIndex, int addendDigit) { int sum = result[resultIndex] + addendDigit; result[resultIndex] = sum % BASE; int carry = sum / BASE; if(carry > 0) { addDigit(result, resultIndex - 1, carry); } }

The next does the same for a whole array of digits to add:

/** * adds all the digits from the addend array to the result array. */ private void addDigits(int[] result, int resultIndex, int... addend) { addendIndex = addend.length - 1; while(addendIndex >= 0) { addDigit(result, resultIndex, addend[addendIndex]); addendIndex--; resultIndex--; } }

Now we can implement our `plus`

method:

/** * calculates the sum of this and that. */ public DecimalBigInt plus(DecimalBigInt that) { int[] result = new int[Math.max(this.digits.length, that.digits.length)+ 1]; addDigits(result, result.length-1, this.digits); addDigits(result, result.length-1, that.digits); // cut of leading zero, if any if(result[0] == 0) { result = Arrays.copyOfRange(result, 1, result.length); } return new DecimalBigInt(result); }

We could do a bit better here if we would look before if overflow is at all possible and only then create the array one bigger than necessary.

Ah, one test: `d2.plus(d2)`

gives `Big[24, 691357802, 469135780]`

, which looks right.

##### Multiplication.

Let's remember back to school, how did we multiply bigger numbers on paper?

123 * 123 ---------- 369 <== 123 * 3 246 <== 123 * 2 123 <== 123 * 1 -------- 15129

So, we have to multiply each digit[i] of the first number with each digit[j] of the second number, and add the product in digit[i+j] of the result (and pay attention to carry). Of course, here the indexes are counted from right, not from left. *(Now i really wish I had used little-endian numbers.)*

Since the product of two of our digits can get outside of the range of `int`

, we use `long`

for multiplication.

/** * multiplies two digits and adds the product to the result array * at the right digit-position. */ private void multiplyDigit(int[] result, int resultIndex, int firstFactor, int secondFactor) { long prod = (long)firstFactor * (long)secondFactor; int prodDigit = (int)(prod % BASE); int carry = (int)(prod / BASE); addDigits(result, resultIndex, carry, prodDigit); }

Now we can see why I declared my `addDigits`

method to take a `resultIndex`

parameter. (And I just changed the last argument to a varargs parameter, to be able to write this here better.)

So, here the cross-multiplying method:

private void multiplyDigits(int[] result, int resultIndex, int[] leftFactor, int[] rightFactor) { for(int i = 0; i < leftFactor.length; i++) { for(int j = 0; j < rightFactor.length; j++) { multiplyDigit(result, resultIndex - (i + j), leftFactor[leftFactor.length-i-1], rightFactor[rightFactor.length-j-1]); } } }

I hope I have the index-calculations right. With a little-endian representation, it would have been `multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j])`

- quite clearer, isn't it?

Our `times`

method now has only to allocate the result array, invoke `multiplyDigits`

and wrap the result.

/** * returns the product {@code this × that}. */ public DecimalBigInt times(DecimalBigInt that) { int[] result = new int[this.digits.length + that.digits.length]; multiplyDigits(result, result.length-1, this.digits, that.digits); // cut off leading zero, if any if(result[0] == 0) { result = Arrays.copyOfRange(result, 1, result.length); } return new DecimalBigInt(result); }

For testing, `d2.times(d2)`

gives `Big[152, 415787532, 388367501, 905199875, 19052100]`

, which is the same what my Emacs calc calculates here.

##### Comparison

We want to be able to compare two of our objects. So, we implement `Comparable<DecimalBigInt>`

and its compareTo method.

public int compareTo(DecimalBigInt that) {

How to know if one of our numbers is bigger than another? First, we compare the length of the arrays. As we took care not to induce any leading zeros (did we?), the longer array should have the bigger number.

if(this.digits.length < that.digits.length) { return -1; } if (that.digits.length < this.digits.length) { return 1; }

If the length are same, we can compare elementwise. Since we use big endian (i.e. *the big end comes first*), we start at the beginning.

for(int i = 0; i < this.digits.length; i++) { if(this.digits[i] < that.digits[i]) { return -1; } if(that.digits[i] < this.digits[i]) { return 1; } }

If everything was same, obviously our numbers are identical, and we can return `0`

.

return 0; }

`equals`

+ `hashCode()`

Every good immutable class should implement `equals()`

and `hashCode()`

in a suitable (and compatible) way.

For our `hashCode()`

, we simply sum up the digits, multiplying them with a small prime to make sure digit-switching does not result in same hash code:

/** * calculates a hashCode for this object. */ public int hashCode() { int hash = 0; for(int digit : digits) { hash = hash * 13 + digit; } return hash; }

In the `equals()`

method we simply can delegate to the compareTo method, instead of implementing the same algorithm again:

/** * compares this object with another object for equality. * A DecimalBigInt is equal to another object only if this other * object is also a DecimalBigInt and both represent the same * natural number. */ public boolean equals(Object o) { return o instanceof DecimalBigInt && this.compareTo((DecimalBigInt)o) == 0; }

So, enough for today. Subtraction (and maybe negative numbers) and division are more complicated, so I'm omitting them for now. **For calculating the factorial of 90 this should be enough.**

##### Calculating big factorials:

Here the factorial function:

/** * calculates the factorial of an int number. * This uses a simple iterative loop. */ public static DecimalBigInt factorial(int n) { DecimalBigInt fac = new DecimalBigInt(1); for(int i = 2; i <= n; i++) { fac = fac.times(new DecimalBigInt(i)); } return fac; }

This gives us

fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000

##### Converting from arbitrary-radix representations

Prompted by the next question of frodosamoa, I wrote my answer about how to convert from arbitrary (positional) number systems in the one in which we can (or want to) calculate. (In the example there, I converted from trinary to decimal, while the question was about decimal to binary.)

Here we want to convert from an arbitrary number system (okay, with radix between 2 and 36, so we can use `Character.digit()`

to convert single digits to ints) to our system with radix `BASE`

(= 1.000.000.000, but this is not really important here).

Basically we use Horner scheme to calculate the value of polynomial with the digits as coefficients at the point given by the radix.

sum[i=0..n] digit[i] * radix^i

can be calculated with this loop:

value = 0; for i = n .. 0 value = value * radix + digit[i] return value

Since our input strings are big-endian, we don't have to count down, but can use a simple enhanced for loop. (It looks more ugly in Java, since we have no operator overloading, and no autoboxing from int to our DecimalBigInt type.)

public static DecimalBigInt valueOf(String text, int radix) { DecimalBigInt bigRadix = new DecimalBigInt(radix); DecimalBigInt value = new DecimalBigInt(); // 0 for(char digit : text.toCharArray()) { DecimalBigInt bigDigit = new DecimalBigInt(Character.digit(digit, radix)); value = value.times(bigRadix).plus(bigDigit); } return value; }

In my actual implementation I added some error checking (and exception throwing) to ensure that we really have a valid number, and of course a documentation comment.

Converting **to** an arbitrary positional system is more complicated, as it involves remainder and division (by the arbitrary radix), which we did not implement yet - so not for now. It will be done when I have a good idea on how to do division. (We need only division by small (one-digit) numbers here, which may be easier than a general division.)

##### Division by small numbers

In school, I learned long division. Here is an example for a small (one-digit) divisor, in the notation we use here in Germany (with annotations about the background calculations, which we normally would not write), in decimal system:

12345 : 6 = 02057 1 / 6 = 0 -0┊┊┊┊ 0 * 6 = 0 ──┊┊┊┊ 12┊┊┊ 12 / 6 = 2 -12┊┊┊ 2 * 6 = 12 ──┊┊┊ 03┊┊ 3 / 6 = 0 - 0┊┊ 0 * 6 = 0 ──┊┊ 34┊ 34 / 6 = 5 -30┊ 5 * 6 = 30 ──┊ 45 45 / 6 = 7 -42 7 * 6 = 42 ── 3 ==> quotient 2057, remainder 3.

Of couse, we don't need to calculate these products (0, 12, 0, 30, 42) and subtract them if we have a native remainder operation. Then it looks like this (of course, we here would not need to write the operations):

12345 : 6 = 02057 1 / 6 = 0, 1 % 6 = 1 12┊┊┊ 12 / 6 = 2, 12 % 6 = 0 03┊┊ 3 / 6 = 0, 3 % 6 = 3 34┊ 34 / 6 = 5, 34 % 6 = 4 45 45 / 6 = 7, 45 % 6 = 3 3 ==> quotient 2057, remainder 3.

This already looks quite like short division, if we write it in another format.

We can observe (and prove) the following:

If we have a two-digit number x with first digit smaller than our divisor d, than `x / d`

is a one-digit number, and `x % d`

is also a one-digit number, smaller than d. This, together with induction, shows that we only ever need to divide (with remainder) two-digit numbers by our divisor.

Coming back to our big numbers with radix BASE: all two-digit numbers are representable as a Java `long`

, and there we have native `/`

and `%`

.

/** * does one step in the short division algorithm, i.e. divides * a two-digit number by a one-digit one. * * @param result the array to put the quotient digit in. * @param resultIndex the index in the result array where * the quotient digit should be put. * @param divident the last digit of the divident. * @param lastRemainder the first digit of the divident (being the * remainder of the operation one digit to the left). * This must be < divisor. * @param divisor the divisor. * @returns the remainder of the division operation. */ private int divideDigit(int[] result, int resultIndex, int divident, int lastRemainder, int divisor) { assert divisor < BASE; assert lastRemainder < divisor; long ent = divident + (long)BASE * lastRemainder; long quot = ent / divisor; long rem = ent % divisor; assert quot < BASE; assert rem < divisor; result[resultIndex] = (int)quot; return (int)rem; }

We will now call this method in a loop, always feeding the result from the previous call back as `lastRemainder`

.

/** * The short division algorithm, like described in * <a href="http://en.wikipedia.org/wiki/Short_division">Wikipedia's * article <em>Short division</em></a>. * @param result an array where we should put the quotient digits in. * @param resultIndex the index in the array where the highest order digit * should be put, the next digits will follow. * @param divident the array with the divident's digits. (These will only * be read, not written to.) * @param dividentIndex the index in the divident array where we should * start dividing. We will continue until the end of the array. * @param divisor the divisor. This must be a number smaller than * {@link #BASE}. * @return the remainder, which will be a number smaller than * {@code divisor}. */ private int divideDigits(int[] result, int resultIndex, int[] divident, int dividentIndex, int divisor) { int remainder = 0; for(; dividentIndex < divident.length; dividentIndex++, resultIndex++) { remainder = divideDigit(result, resultIndex, divident[dividentIndex], remainder, divisor); } return remainder; }

This method still returns an int, the remainder.

Now we want to have a public method returning a DecimalBigInt, so we create one. It has the task to check the arguments, create an array for the working method, discard the remainder, and create a DecimalBigInt from the result. (The constructor removes a leading zero which may be there.)

/** * Divides this number by a small number. * @param divisor an integer with {@code 0 < divisor < BASE}. * @return the integer part of the quotient, ignoring the remainder. * @throws IllegalArgumentException if the divisor is <= 0 or >= BASE. */ public DecimalBigInt divideBy(int divisor) { if(divisor <= 0 || BASE <= divisor) { throw new IllegalArgumentException("divisor " + divisor + " out of range!"); } int[] result = new int[digits.length]; divideDigits(result, 0, digits, 0, divisor); return new DecimalBigInt(result); }

We also have a similar method, which returns the remainder instead:

/** * Divides this number by a small number, returning the remainder. * @param divisor an integer with {@code 0 < divisor < BASE}. * @return the remainder from the division {@code this / divisor}. * @throws IllegalArgumentException if the divisor is <= 0 or >= BASE. */ public int modulo(int divisor) { if(divisor <= 0 || BASE <= divisor) { throw new IllegalArgumentException("divisor " + divisor + " out of range!"); } int[] result = new int[digits.length]; return divideDigits(result, 0, digits, 0, divisor); }

These methods can be invoked like this:

DecimalBigInt d3_by_100 = d3.divideBy(100); System.out.println("d3/100 = " + d3_by_100); System.out.println("d3%100 = " + d3.modulo(100));

##### Conversion to arbitrary radix

Now we have the basics to convert to an arbitrary radix. Of course, not really arbitrary, only radixes smaller than `BASE`

are allowed, but this should not be a too big problem.

As already answered in another answer about converting numbers, we have to do "division, remainder, multiply, add. The "multiply-add" part is in fact only putting together the individual digits, so we can replace it by a simple array-access.

As we always need both the quotient and the remainder, we won't use the public methods `modulo`

and `divideBy`

, but instead repeatedly call the `divideDigits`

method.

/** * converts this number to an arbitrary radix. * @param radix the target radix, {@code 1 < radix < BASE}. * @return the digits of this number in the base-radix system, * in big-endian order. */ public int[] convertTo(int radix) { if(radix <= 1 || BASE <= radix) { throw new IllegalArgumentException("radix " + radix + " out of range!"); }

First, a special-case handling for 0.

// zero has no digits. if(digits.length == 0) return new int[0];

Then, we create an array for the result digits (long enough), and some other variables.

// raw estimation how many output digits we will need. // This is just enough in cases like BASE-1, and up to // 30 digits (for base 2) too much for something like (1,0,0). int len = (int) (Math.log(BASE) / Math.log(radix) * digits.length)+1; int[] rDigits = new int[len]; int rIndex = len-1; int[] current = digits; int quotLen = digits.length;

`quotLen`

is the number of digits (excluding leading zeroes) in the last quotient. If this is 0, we are done.

while(quotLen > 0) {

A new array for the next quotient.

int[] quot = new int[quotLen];

The quotient-and-remainder operation. The quotient is now in `quot`

,
the remainder in `rem`

.

int rem = divideDigits(quot, 0, current, current.length - quotLen, radix);

We put the remainder in the output array (filling it from the last digit).

rDigits[rIndex] = rem; rIndex --;

Then we swap the arrays for the next round.

current = quot;

If there are leading zeros in the quotient (there will be at most one, since radix is smaller than BASE), we shrink the quotient size by one. The next array will be smaller.

if(current[0] == 0) { // omit leading zeros in next round. quotLen--; } }

After the loop there may be leading zeros in the rDigits array, and we cut them off.

// cut of leading zeros in rDigits: while(rIndex < 0 || rDigits[rIndex] == 0) { rIndex++; } return Arrays.copyOfRange(rDigits, rIndex, rDigits.length); }

That's it. It looks a bit complicated, though. Here is an example of how to use it:

System.out.println("d4 in base 11: " + Arrays.toString(d4.convertTo(11))); System.out.println("d5 in base 7: " + Arrays.toString(d5.convertTo(7)));

These print `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]`

and `[1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0]`

, just the same numbers as we parsed before (from a String, though).

Based on this we can also format as a string:

/** * Converts the number to a String in a given radix. * This uses {@link Character.digit} to convert each digit * to one character. * @param radix the radix to use, between {@link Character.MIN_RADIX} * and {@link Character.MAX_RADIX}. * @return a String containing the digits of this number in the * specified radix, using '0' .. '9' and 'a' .. 'z' (as much as needed). */ public String toString(int radix) { if(radix < Character.MIN_RADIX || Character.MAX_RADIX < radix) { throw new IllegalArgumentException("radix out of range: " + radix); } if(digits.length == 0) return "0"; int[] rdigits = convertTo(radix); StringBuilder b = new StringBuilder(rdigits.length); for(int dig : rdigits) { b.append(Character.forDigit(dig, radix)); } return b.toString(); }

Handling very large numbers without using BigInteger: really performance but the program requirement was not to use the java.math class. First, a representation of the number, based on the datatypes which Java gives us. As you think the decimal conversion is the most complicated part, let's stay in a decimal based mode. For efficiency, we'll store not real decimal digits, but work in base 1 000 000 000 = 10^9 < 2^30.

You might want to implement or research a library for binary-coded decimal if you're trying to avoid `BigInteger`

. You can accomplish factorial of 90 with `BigInteger`

if you want to use it though:

public static BigInteger factorial(BigInteger value) { BigInteger total = BigInteger.ONE; for (int i = 0; value.compareTo(BigInteger.ONE) == 1; i++) { total = total.multiply(value); value = value.subtract(BigInteger.ONE); } return total; }

BigInteger class is used for mathematical operation which involves very big integer calculations that are outside the limit of all available primitive data types. This method is used to find arithmetic addition of large numbers of range much greater than the range of biggest data type double of java without compromising with the precision of the result. This method performs an operation upon the current BigInteger by which this method is called and BigInteger passed as the parameter.

Arithmetic operations in Java using the operators `+`

, `-`

, `*`

, `/`

, and `%`

are bound by the constraints of the Java primitive data types.

This means that if you can't fit your desired numbers into the range of, say a `double`

or `long`

then you'll have to use a "big number" library, such as the one built-in to Java (BigDecimal, BigInteger), or a third-party library, or write your own. This also means that you cannot use the arithmetic operators since Java does not support operator overloading.

This method is used to find arithmetic addition of large numbers of range much of biggest data type double of java without compromising with the precision of the result. the data is full precised even after adding number of very large length. Use the static valueOf method to turn an ordinary number into a big number: BigInteger a = BigInteger.valueOf(100); Unfortunately, you cannot use the familiar mathematical operators such as + and * to combine big numbers. Instead, you must use methods such as add and multiply in the big number classes.

Use the code below to multiply numbers of any length:-

public class BigNumberMultiplication { private static int[] firstBigNumber = null; private static int[] secondBigNumber = null; public static int[] baseMul(int[] baseMultiple, int base) { System.out.println("baseMultiple" + Arrays.toString(baseMultiple) + base); for (int i = 0; i < baseMultiple.length; i++) { baseMultiple[i] *= base; } System.out.println("basemultipleresultwithoutcarryforward" + baseMultiple); return carryForward(baseMultiple); } public static int[] basePowerMul(int[] basePowerMultiple, int base, int power) { int basePowerMultipleTemp[] = baseMul(basePowerMultiple, base); System.out.println("basePowerMultipleTemp" + Arrays.toString(basePowerMultipleTemp) + "power" + power); int basePowerMultipleResult[] = new int[basePowerMultipleTemp.length + (power - 1)]; for(int i = 0; i < basePowerMultipleTemp.length; i++) basePowerMultipleResult[i] = basePowerMultipleTemp[i]; if(power > 1){ for(int i = 0; i < (power - 1); i++) basePowerMultipleResult[basePowerMultipleTemp.length + i] = 0; } System.out.println("basepowermulresult" + Arrays.toString(basePowerMultipleResult)); return basePowerMultipleResult; } public static int[] addBigNumber(int[] finalNumberInArray, int[] finalNumberInArrayTemp){ System.out.println("final number in array" + Arrays.toString(finalNumberInArray) + "finalNumberInTemp" + Arrays.toString(finalNumberInArrayTemp)); int n = finalNumberInArray.length; for(int i = (finalNumberInArrayTemp.length - 1); i >= 0; i--){ finalNumberInArray[n - 1] += finalNumberInArrayTemp[i]; n--; } return carryForward(finalNumberInArray); } public static int[] carryForward(int[] arrayWithoutCarryForward){ int[] arrayWithCarryForward = null; System.out.println("array without carry forward" + Arrays.toString(arrayWithoutCarryForward)); for (int i = arrayWithoutCarryForward.length - 1; i > 0; i--) { if (arrayWithoutCarryForward[i] >= 10) { int firstDigit = arrayWithoutCarryForward[i] % 10; int secondDigit = arrayWithoutCarryForward[i] / 10; arrayWithoutCarryForward[i] = firstDigit; arrayWithoutCarryForward[i - 1] += secondDigit; } } if(arrayWithoutCarryForward[0] >= 10){ arrayWithCarryForward = new int[arrayWithoutCarryForward.length + 1]; arrayWithCarryForward[0] = arrayWithoutCarryForward[0] / 10; arrayWithCarryForward[1] = arrayWithoutCarryForward[0] % 10; for(int i = 1; i < arrayWithoutCarryForward.length; i++) arrayWithCarryForward[i + 1] = arrayWithoutCarryForward[i]; } else{ arrayWithCarryForward = arrayWithoutCarryForward; } System.out.println("array with carry forward" + Arrays.toString(arrayWithCarryForward)); return arrayWithCarryForward; } public static int[] twoMuscularNumberMul(){ int finalNumberInArray[] = null; for(int i = 0; i < secondBigNumber.length; i++){ if(secondBigNumber[i] == 0){} else { int[] finalNumberInArrayTemp = basePowerMul(Arrays.copyOf(firstBigNumber, firstBigNumber.length), secondBigNumber[i], secondBigNumber.length - i); if(finalNumberInArray == null){ finalNumberInArray = finalNumberInArrayTemp; System.out.println("finalNumberInArray" + Arrays.toString(finalNumberInArray)); } else{ finalNumberInArray = addBigNumber(finalNumberInArray, finalNumberInArrayTemp); System.out.println("finalNumberInArray" + Arrays.toString(finalNumberInArray)); } } } return finalNumberInArray; } public static int [] readNumsFromCommandLine() { Scanner s = new Scanner(System.in); System.out.println("Please enter the number of digit"); int count = s.nextInt(); System.out.println("please enter the nuumber separated by space"); s.nextLine(); int [] numbers = new int[count]; Scanner numScanner = new Scanner(s.nextLine()); for (int i = 0; i < count; i++) { if (numScanner.hasNextInt()) { numbers[i] = numScanner.nextInt(); } else { System.out.println("You didn't provide enough numbers"); break; } } return numbers; } public static void main(String[] args) { firstBigNumber = readNumsFromCommandLine(); secondBigNumber = readNumsFromCommandLine(); System.out.println("1st number" + Arrays.toString(firstBigNumber) + "2nd number" + Arrays.toString(secondBigNumber)); int[] finalArray = twoMuscularNumberMul(); System.out.println(Arrays.toString(finalArray)); } }

Use the BigInteger or BigDecimal values in package java.math : // BigNums.java System.out.println("Here's Long.MAX_VALUE: " + Long.MAX_VALUE); This class can handle very large integers and the size of the integer is only limited by the available memory of the JVM. However BigInteger should only be used if it is absolutely necessary as using BigInteger is less intuitive compared to built-in types (since Java doesn’t support operator overloading)

**strong text** public class BigInteger {

public static String checkSignWithRelational(int bigInt1, int bigInt2){ if( bigInt1 < 0){ return "negative"; }else { return "positive"; } } BigInteger( long init) { Long.parseLong(bigInt1); } BigInteger String (String init){ return null; } private static int intLenght(int bigInt) { return Integer.toString(bigInt).length(); } private static int[] intToArray(int bigInt, int bigIntLength, int arrayLength) { int array[] = new int[arrayLength ]; for (int i = 0; i < arrayLength ; i++) { array[i] = ( i<bigIntLength ? getDigitAtIndex(bigInt, bigIntLength - i -1) :0 ); } return array; } static String add(int bigInt1, int bigInt2) { //Find array length int length1 = intLenght(bigInt1); int length2 = intLenght(bigInt2); int arrayLength = Math.max(length1, length2); int array1[] = intToArray(bigInt1, length1, arrayLength); int array2[] = intToArray(bigInt2, length2, arrayLength); return add(array1, array2); } private static String add(int[] array1, int[] array2) { int carry=0; int addArray[] = new int[array1.length + 1]; for (int i = 0; i < array1.length; i++) { addArray[i] = (array1[i] + array2[i] + carry) % 10 ; carry = (array1[i] + array2[i] + carry) / 10; } addArray[array1.length] = carry; return arrayToString(addArray); } private static int getDigitAtIndex(int longint,int index){ return Integer.parseInt(Integer.toString(longint).substring(index, index+1)); } private static String arrayToString(int[] addArray) { String add = ""; boolean firstNonZero = false; for (int i = addArray.length-1; i >= 0 ; i--) { if(!firstNonZero && (addArray[i]==0)){ continue; } else{ firstNonZero=true; } add += addArray[i]; if((i%3 ==0)&&i!=0){ add +=",";} //formatting } String sumStr = add.length()==0?"0":add; return sumStr; } public static String sub(int bigInt1, int bigInt2) { int length1 = intLenght(bigInt1); int length2 = intLenght(bigInt2); int arrayLength = Math.max(length1, length2); int array1[] = intToArray(bigInt1, length1, arrayLength); int array2[] = intToArray(bigInt2, length2, arrayLength); return sub(array1, array2); } private static String sub(int[] array1, int[] array2) { int carry=0; int sub[] = new int[array1.length + 1]; for (int i = 0; i < array1.length; i++) { sub[i] = (array1[i] - array2[i] + carry) % 10 ; //sum digits + carry; then extract last digit carry = (array1[i] - array2[i] + carry) / 10; //Compute carry } sub[array1.length] = carry; return arrayToString(sub); } public static String mul(int bigInt1, int bigInt2) { int length1 = intLenght(bigInt1), length2 = intLenght(bigInt2), length = Math.max(length1, length2); int array1[] = intToArray(bigInt1, length1, length); int array2[] = intToArray(bigInt2, length2, length); return mul(array1, array2); } private static String mul(int[] array1, int[] array2) { int product[] = new int[array1.length + array2.length]; for(int i=0; i<array1.length; i++){ for(int j=0; j<array2.length; j++){ int prod = array1[i] * array2[j]; int prodLength = intLenght(prod); int prodAsArray[] = intToArray(prod, prodLength, prodLength); for (int k =0; k < prodAsArray.length; k++) { product[i+j+k] += prodAsArray[k]; int currentValue = product[i+j+k]; if(currentValue>9){ product[i+j+k] = 0; int curValueLength = intLenght(currentValue); int curValueAsArray[] = intToArray(currentValue, curValueLength, curValueLength); for (int l = 0; l < curValueAsArray.length; l++) { product[i+j+k+l] += curValueAsArray[l]; } } } } } return arrayToString(product); } public static int div(int bigInt1, int bigInt2) { if ( bigInt2 == 0){ throw new ArithmeticException("Division by 0 is undefined:" + bigInt1+ "/" + bigInt2); } int sign = 1; if(bigInt1 < 0) { bigInt1 = -bigInt1; sign = -sign; } if (bigInt2 < 0){ bigInt2 = -bigInt2; sign = -sign; } int result =0; while (bigInt1 >= 0){ bigInt1 -= bigInt2; result++; } return (result - 1) * sign; } public static String check(String bigInt1, String bigInt2){ int difference; StringBuilder first = new StringBuilder(bigInt1); StringBuilder second = new StringBuilder(bigInt2); if(bigInt1.length()> bigInt2.length()){ difference = bigInt1.length() - bigInt2.length(); for(int x = difference; x > 0; x--){ second.insert(0,"0"); } bigInt2 = second.toString(); return bigInt2; }else { difference = bigInt2.length() - bigInt1.length(); for (int x = difference; x> 0; x--) { first.insert(0, "0"); } bigInt1 = first.toString(); return bigInt1; } } public static int mod(int bigInt1, int bigInt2){ int res = bigInt1 % bigInt2; return (res); } public static void main(String[] args) { int bigInt1 = Integer.parseInt("987888787"); int bigInt2 = Integer.parseInt("444234343"); System.out.println(bigInt1+" + "+bigInt2+" = "+add(bigInt1, bigInt2)); System.out.println(bigInt1+" - "+bigInt2+" = "+sub(bigInt1, bigInt2)); System.out.println(bigInt1+" * "+bigInt2+" = "+mul(bigInt1, bigInt2)); System.out.println(bigInt1+" / "+bigInt2+" = "+div(bigInt1, bigInt2)); System.out.println(bigInt1+" % "+bigInt2+" = "+mod(bigInt1, bigInt2)); }

}

Java program to add two numbers, a user enters two integers, and we calculate their sum and display it. Using int data data type). If you want to add very large numbers, then you may use BigInteger class. In the program, we create two objects of BigInteger class of java.math package. Java exception handling tutorial Thanks for your responses. I have tried to code by passing the numbers as string and add each character from the end. It works fine for me. Is there any big difference between the addition of two very large numbers using BigInteger and the method, i specified above (add each character from end and store remainder in temporary variable and goes on).

Another way to add two big int values without using java.math.BigInteger? Hi, is there At sufficient size, BigInt is really the only thing that can handle integers. BigInteger Class in Java BigInteger class is used for mathematical operation which involves very big integer calculations that are outside the limit of all available primitive data types. For example factorial of 100 contains 158 digits in it so we can’t store it in any primitive data type available.

If you need greater or lesser values, you have to use the BigInteger class in the package java.math . A BigInteger object can represent any integer (as large as Since you are summing up some int values together, there is no need to use BigInteger. long is enough for that. int is 32 bits, while long is 64 bits, that can contain the sum of all int values. For this question, my answer is a bit our of scope.

view src/share/classes/java/math/BigInteger.java @ 9107:687fd7c7986d ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or The input array is assumed to be in <i>big-endian</i> * int-order: the most < 0) throw new ArithmeticException("start < 0: " + this); // Handle trivial cases if ((this.signum I'm trying to read some really big numbers from standard input and add them together. However, to add to BigInteger, I need to use BigInteger.valueOf (long);: That works fine, but as the BigInteger.valueOf () only takes a long, I cannot add numbers greater than long 's max value (9223372036854775807). Whenever I try to add 9223372036854775808

##### Comments

- Why would you want to replace it?
`s/How/Why/`

and you've got a good question.- @frodosamoa: 600 is way small. People looking for large prime numbers need millions of digits.
- You could copy the code from BigInteger, removing anything you want to avoid. However you are unlikely to gain anything and some JVMs provide special handling optimizations for BigInteger/BigDecimal which a copy of the class is unlikely to enjoy. I would at least read the code for BigInteger before attempting this as it has all the code you appear to need.
- The (int) factorial(34) == 0, the (long) factorial(66) == 0, if you only take the last bits of a large number you shouldn't expect to get the right answer. This has been recently covered in stackoverflow.com/questions/5317732/…
- Ah, I just realized that I implemented a kind of (packed) binary-coded decimal in my answer :-)
- It can multiply any digit of number. Enjoy.
- Welcome to Stackoverflow! Please don't just post code. It is much more helpful if you try to answer the question with an explanation.
- The explanation belongs to the answer, and not to the comment section. And please add further explanation, code only answers aren't very helpful.
- Does this implementation of a BigInteger class contribute anything that is not already in another answer?