Last active
February 10, 2019 03:54
-
-
Save rgb-24bit/931e45660d8826fce2053c943d0b2c99 to your computer and use it in GitHub Desktop.
An easy implementation of large numbers.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
import java.util.Formatter; | |
/** | |
* An easy implementation of large numbers. | |
*/ | |
public class BigInteger implements Comparable<BigInteger> { | |
/** | |
* The radix used when storing large numbers | |
*/ | |
private static final int BASE = 1000000000; | |
/** | |
* The number of decimal digits corresponding to a single array element | |
*/ | |
private static final int BASE_DECIMAL_DIGITS = 9; | |
/** | |
* An array of integers for storing large numbers | |
*/ | |
public final int[] digits; | |
/** | |
* Create large numbers based on small endian integer arrays | |
* | |
* Array [999999999, 1] representing large numbers 1999999999 | |
* | |
* NOTE: The range of values for each element of the array is [0, 999999999] | |
*/ | |
public BigInteger(int... digits) { | |
if (digits.length > 0) { | |
for (int digit : digits) { | |
if (digit < 0 || digit >= BASE) { | |
throw new IllegalArgumentException(String.format("Digit %d out of range !", digit)); | |
} | |
} | |
this.digits = digits.clone(); | |
} else { | |
this.digits = new int[] {0}; | |
} | |
} | |
/** | |
* Create large numbers based on decimal strings | |
*/ | |
public BigInteger(String digitsString) { | |
int stringLength = digitsString.length(); | |
// Array size required to store large numbers, equal ceil(digitsLength / BASE_DECIMAL_DIGITS) | |
int digitsLength = (stringLength - 1) / BASE_DECIMAL_DIGITS + 1; | |
// Length of the large number of heads | |
int head = stringLength % BASE_DECIMAL_DIGITS; | |
this.digits = new int[digitsLength]; | |
for (int i = 0; i < digitsLength; ++i) { | |
String block = digitsString.substring(Math.max(head + (i - 1) * BASE_DECIMAL_DIGITS, 0), head + i * BASE_DECIMAL_DIGITS); | |
this.digits[digitsLength - i - 1] = Integer.parseInt(block); | |
} | |
} | |
@Override | |
public String toString() { | |
Formatter formatter = new Formatter(); | |
formatter.format("%d", digits[digits.length - 1]); | |
for (int i = digits.length - 2; i >= 0; --i) { | |
formatter.format("%09d", digits[i]); | |
} | |
return formatter.toString(); | |
} | |
public int compareTo(BigInteger other) { | |
if (this.digits.length > other.digits.length) { | |
return 1; | |
} | |
if (this.digits.length < other.digits.length) { | |
return -1; | |
} | |
for (int i = this.digits.length - 1; i >= 0; --i) { | |
if (this.digits[i] > other.digits[i]) { | |
return 1; | |
} else if (this.digits[i] < other.digits[i]) { | |
return -1; | |
} | |
} | |
return 0; | |
} | |
public BigInteger plus(BigInteger other) { | |
int[] result = new int[Math.max(this.digits.length, other.digits.length) + 1]; | |
System.arraycopy(this.digits, 0, result, 0, this.digits.length); | |
int carry = 0; | |
for (int i = 0; i < other.digits.length; ++i) { | |
int sum = carry + result[i] + other.digits[i]; | |
result[i] = sum % BASE; | |
carry = sum / BASE; | |
} | |
if (carry != 0) { | |
for (int i = other.digits.length; i < result.length && carry != 0; ++i) { | |
int sum = carry + result[i]; | |
result[i] = sum % BASE; | |
carry = sum / BASE; | |
} | |
} | |
if (result[result.length - 1] == 0) { | |
result = Arrays.copyOfRange(result, 0, result.length - 1); | |
} | |
return new BigInteger(result); | |
} | |
public BigInteger mul(BigInteger other) { | |
long[] temp = new long[this.digits.length + other.digits.length]; | |
for (int i = 0; i < this.digits.length; ++i) { | |
for (int j = 0; j < other.digits.length; ++j) { | |
temp[i + j] += (long) this.digits[i] * (long) other.digits[j]; | |
} | |
} | |
for (int i = 0; i < temp.length; ++i) { | |
if (temp[i] >= BASE) { | |
temp[i + 1] += temp[i] / BASE; | |
temp[i] = temp[i] % BASE; | |
} | |
} | |
int zeroCount = 0; | |
for (int i = temp.length - 1; i >= 0; --i) { | |
if (temp[i] > 0) { | |
break; | |
} | |
zeroCount++; | |
} | |
int[] result = new int[temp.length - zeroCount]; | |
for (int i = 0; i < result.length; ++i) { | |
result[i] = (int) temp[i]; | |
} | |
return new BigInteger(result); | |
} | |
public static void main(String[] args) { | |
BigInteger a = new BigInteger("1000000000999999999"); | |
BigInteger b = new BigInteger("809"); | |
System.out.println(a.toString()); | |
System.out.println(a.plus(b).toString()); | |
System.out.println(a.mul(b).toString()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment