/* * Author : Yerucham * Date Created : 4 Jan 2018 * Bugs : The occasional Memory limit exceeded particularly with the getQuotientAndRemainder method * Bug Fix on 8 Jan 2018 : Remove initialDigits array and associated methods. Reset digits altered by subtract using the digits of a new object instantiated with the old object's string value * Bug Fix on 13 Jan 2018 thanks to Gordie : Bug in add method * Bug Fix on 14 Jan 2018 thanks to Gordie : Bug in subtract method * Bug Fix on 16 Jan 2018 thanks to Gordie : Bug in subtract method * StringIndexOutOfBounds Exception occurs for digit sizes greater than 2**16 - 1(The limit of short) * To fix it use int instead of short at all points in the code where short is used */ /** * My Implementation of the BigInteger Class in Java * Far from perfect but works(ish) */ public class Program { public static void main(String[] args) { //Feel free to play around with the methods BigInteger a = BigInteger.valueOf("50"); System.out.println(a.toString() + "! = " + fact(a)); BigInteger b = new BigInteger(2); System.out.println(b.toString() + " ^ " + a.toString() + " = " + b.pow(a)); BigInteger c = BigInteger.valueOf(3); System.out.println(c.toString() + " * " + a.toString() + " ^ " + a.toString() + " = " + c.multiply(a.pow(a))); } /** * Method to find the factorial of a number * @param x The number whose factorial is to be found * @return x! */ public static BigInteger fact(BigInteger x) { if (x.isZero() || x.isOne()) { return BigInteger.ONE; } else return x .multiply(fact(x .subtract(BigInteger.ONE))); } } /** * BigInteger Class */ class BigInteger { public static final BigInteger ONE = new BigInteger("1"); //Constant ONE public static final BigInteger ZERO = new BigInteger("0"); //Constant ZERO private byte[] digits; //Byte array holding all the digits private byte sign; //Byte holding the sign, 1 means positive, -1 is negative and 0 is 0 private final byte initialSign; //Byte holding the sign, 1 means positive, -1 is negative and 0 is 0 private String value; //The string representation of the number /** * Default Constructor */ public BigInteger() { this("0"); } /** * Constructor for initialization with a byte, short, int or long * @param num The number to initialize with */ public BigInteger(long num) { this(String.valueOf(num)); } /** * Main Constructor * @param num The string representation of the number */ public BigInteger(String num) { if (num.charAt(0) == '-') //If the first character is "-" The number is negative { digits = new byte[num.length() - 1]; sign = -1; initialSign = -1; num = num.substring(1); } else if (isZero(num)) //If the number is 0 sign is 0 { digits = new byte[num.length()]; sign = 0; initialSign = 0; } else //else the sign is 1 { digits = new byte[num.length()]; sign = 1; initialSign = 1; } /* Fill up the byte arrays with the digits The first element of the array is the last digit, the second element the penultimate digit and so on This arrangement allows the digits of two BigInteger objects to align in a manner required for addition and subtraction For example: 94803851 --> 15830849 + 8934 --> 4398 ---------- 74253851 --> 15835247 ---------- */ for (short i = (short) (num.length() - 1) ,j = 0 ;i >= 0;i--, j++) { byte value = (byte)num.charAt(i); if (value < 48 || value > 57) { throw new IllegalArgumentException ("Not a number"); } digits[j] = (byte)(value - 48); } value = num; } /** * Get a BigInteger object initialized with a string * @param value The string representation of the number * @return The BigInteger Object */ public static BigInteger valueOf (String value) { return new BigInteger(value); } /** * Get a BigInteger object initialized with a byte, short, int or long * @param value The number * @return The BigInteger Object */ public static BigInteger valueOf (long value) { return new BigInteger (String.valueOf(value)); } /** * Method to check if a number(in string) is 0 * @param num The string representation of the number * @return True if 0 else false */ private boolean isZero(String num) { return sumOfDigits(num) == 0; } /** * Method to check if the current BigInteger object is 0 * @return True if 0 else false */ public boolean isZero() { return this.compareTo(ZERO) == 0; } /** * Method to check if the current BigInteger object is 1 * @return True if 1 else false */ public boolean isOne() { return this.compareTo(ONE) == 0; } /** * Method to calculate the sum of the digits of the string representation of a number * @param num The string representation of the number * @return the sum of the digits */ private short sumOfDigits(String num) { short sum = 0; for (short i = 0 ;i < (short)num.length() ;i++) { sum += (short)(num.charAt(i) - 48); } return sum; } /** * Method to add one BigInteger object to another BigInteger object * @param other The other BigInteger object * @return The sum */ public BigInteger add(BigInteger other) { /* If the first number is negative and the other is positive, make the first number positive and subtract it from the second number. Change the first number's sign back to negative and return the result */ if (this.getSign() < 0 && other.getSign() > 0) { this.setSign((byte)1); BigInteger result = other.subtract(this); this.setSign (this.getInitialSign()); return result; } /* If the first number is positive and the other is negative, make the second number positive and subtract it from the first number. Change the second number's sign back to negative and return the result */ if (this.getSign() > 0 && other.getSign() < 0) { other.setSign((byte)1); BigInteger result = this.subtract(other); other.setSign (other.getInitialSign()); return result; } /* If the first number is negative and the other is also negative, make the first number and the second number positive and add them. Change the first and second number's sign back to negative and return the result */ if (this.getSign() < 0 && other.getSign() < 0) { this.setSign((byte)1); other.setSign((byte)1); BigInteger result = this .add(other); result.setSign((byte)-1); this.setSign (this.getInitialSign()); other.setSign (other.getInitialSign()); return result; } /* If the first number is 0 return a new BigInteger object equal to the second number */ if (this.isZero()) return new BigInteger(other.toString()); /* If the second number is 0 return a new BigInteger object equal to the first number */ if (other.isZero()) return new BigInteger(this.toString()); if (this.compareTo(other) < 0) return other.add(this); byte[] result; // byte array for the result's digits byte[] otherDigits = other.getDigits(); // increase result size by 1 because result digit length can be one greater than max digit length //E.g 99 + 1 = 100 // if (this.size() > other.size()) result = new byte[this.size() + 1]; /* else result = new byte [other.size() + 1];*/ byte carry = 0; //Sorry too tired to comment this part for (short i = 0;i < result.length;i++) { if (i >= this.size()) { result[i] = carry; continue; } if (i >= otherDigits.length) { byte sum = (byte) (this.digits[i] + carry); result[i] = (byte) (sum % 10); carry = (byte)(sum / 10); continue; } byte sum = (byte) (this.digits[i] + otherDigits[i] + carry); result[i] = (byte)(sum % 10); carry = (byte)(sum / 10); } StringBuilder res = new StringBuilder(result.length); short i = (short)(result.length - 1); while (result[i] == 0 && i > 0) i--; for (;i >= 0;i--) res .append(String.valueOf(result[i])); return new BigInteger(res.toString()); } /** * Method to subtract one BigInteger object from another BigInteger object * @param other The other BigInteger object to subtract * @return The difference */ public BigInteger subtract (BigInteger other) { if (this.isZero()) { BigInteger result = new BigInteger(other.toString()); result.setSign((byte)(-1 * other.getSign())); return result; } if (other.isZero()) { return new BigInteger(this.toString()); } if (this.compareTo(other) < 0) { BigInteger result = other.subtract(this); other .setDigits(new BigInteger (other.toString()).getDigits()); result.setSign((byte)-1); return result; } if (this.compareTo(other) == 0) return ZERO; if (this.getSign() < 0 && other.getSign() < 0) { other.setSign((byte)1); BigInteger result = this.add(other); other.setSign(other.getInitialSign()); return result; } if (this.getSign() > 0 && other.getSign() < 0) { other.setSign((byte)1); BigInteger result = this.add(other); other.setSign(other.getInitialSign()); return result; } byte[] difference = new byte[this.size()]; byte[] otherDigits = other.getDigits(); for (short i = 0 ;i < difference.length;i++) { if (i > otherDigits.length - 1) difference[i] = this.digits[i]; else if (this.digits[i] < otherDigits[i]) { short j = i; while (this.digits[++j] == 0); while (j != i) { this.digits[--j] += 10; this.digits[j + 1] -= 1; } difference[i] = (byte) (this.digits[i] - otherDigits[i]); } else difference[i] = (byte) (this.digits[i] - otherDigits[i]); } StringBuilder res = new StringBuilder(difference.length); short i = (short) (difference.length - 1); while (difference[i] == 0 && i > 0) i--; for (;i >= 0;i--) res .append(String .valueOf(difference[i])); this .setDigits (new BigInteger(this .toString()).getDigits()); return new BigInteger(res.toString()); } /** * Method to multiply one BigInteger object with another BigInteger object * @param other The other BigInteger object * @return The product */ public BigInteger multiply (BigInteger other) { BigInteger result; if (this.isZero() || other.isZero()) return ZERO; if (this.isOne()) return new BigInteger(other.toString()); if (other.isOne()) return new BigInteger(this.toString()); if (this.compareToNeglectingSign(other) < 0) return other.multiply(this); //byte[] digits = this.getDigits(); byte[] otherDigits = other.getDigits(); if (otherDigits.length > 1) { if (isAPowerOfTen(other)) { result = this .multiply (new BigInteger (otherDigits [otherDigits .length - 1])); result = result .appendZeros(result, (short) (otherDigits .length - 1)); } else { BigInteger[] otherSplit = split(other); result = this .multiply(otherSplit[0]) .add(this .multiply(otherSplit[1])); } } else { result = ZERO; for (BigInteger i = ZERO ; i.compareToNeglectingSign(other) < 0 ; i = i.add(ONE)) { result = result.add(this); } } result.setSign ((byte) (this.getSign() * other.getSign())); return result; } /** * Method to find both the quotient and remainder when one BigInteger divides another * @param other The other BigInteger * @return The quotient and the remainder */ private BigInteger[] getQuotientAndRemainder(BigInteger other) { if (other.isZero()) throw new ArithmeticException ("Cannot divide by Zero"); BigInteger quotient = ZERO; BigInteger remainder = new BigInteger(this.toString()); while(remainder.compareTo(other) >= 0) { quotient = quotient.add(ONE); remainder = remainder.subtract(other); } return new BigInteger[] {quotient, remainder}; } /** * Method to divide one BigInteger object with another BigInteger object * without remainder * @param other The other BigInteger object * @return The quotient */ public BigInteger divideWithoutRemainder(BigInteger other) { BigInteger result = getQuotientAndRemainder (other)[0]; result.setSign((byte) (this.getSign() * other.getSign())); return result; } /** * Method to divide one BigInteger object with another BigInteger object * and get the remainder * @param other The other BigInteger object * @return The remainder */ public BigInteger remainder (BigInteger other) { return getQuotientAndRemainder (other)[1]; } /** * Method to raise one BigInteger to the poweranother BigInteger * @param exponent The BigInteger to raise to * @return this ^ other // I know crappy explanation lol :) */ public BigInteger pow(BigInteger exponent) { if (exponent.compareTo(ZERO) < 0) return ZERO; if (exponent.isZero()) return ONE; if (exponent.isOne()) return this; else return this .multiply(pow(exponent .subtract(ONE))); } /** * Method to add zeros to a BigInteger * @param value The BigInteger to add zeros to * @param numberOfZeros The number of zeros to add * @return A new BigInteger object with the zeros appended */ private BigInteger appendZeros (BigInteger value, short numberOfZeros) { byte[] result = new byte[value.size() + numberOfZeros]; byte[] digits = value.getDigits(); short i; for (i = (short)(result.length - 1) ;i >= numberOfZeros;i--) { result[i] = digits [i - numberOfZeros]; } for (;i >= 0;i--) result[i] = 0; StringBuilder res = new StringBuilder(result.length); i = (short)(result.length - 1); for (;i >= 0;i--) res .append(String.valueOf(result[i])); return new BigInteger(res.toString()); } /** * Method to divide a BigInteger object into two to simplify multiplication * Division happens after the first digit //Recall first digit is the last in the byte array * A value like 1473 becomes 1000(1) and 473(2) * Makes multiplication easy because * 27 * 1473 = 27 * (1000 + 473) * = (27 * 1000) + (27 * 473) * = (27 * 1000) + (27 * (400 + 73)) * = (27 * 1000) + ((27 * 400) + (27 * 73))) * = (27 * 1000) + ((27 * 400) + (27 * (70 + 3)) * = (27 * 1000) + ((27 * 400) + (27 * 70) + (27 * 3)) * = (27 * 1000) + (27 * 4 * 100) + (27 * 7 * 10) + (27 * 3) * Basically the multiplication can be simplified * and solved using less time * Multiplying by a power of ten simply means appending zeros * @param value The value to split * @return An array containing the two parts */ private BigInteger[] split (BigInteger value) { short size = value.size(); byte[] digits = value.getDigits(); byte[] firstPart = new byte[size]; byte[] secondPart = new byte[size - 1]; firstPart[size - 1] = digits[size - 1]; for (short i = (short)(size - 2) ;i >= 0;i--) secondPart[i] = digits[i]; StringBuilder res1 = new StringBuilder(size); short i = (short)(size - 1); for (;i >= 0;i--) res1 .append(String .valueOf(firstPart[i])); StringBuilder res2 = new StringBuilder(size - 1); i = (short)(size - 2); for (;i >= 0;i--) res2 .append(String .valueOf(secondPart[i])); BigInteger first = new BigInteger(res1.toString()); BigInteger second = new BigInteger(res2.toString()); return new BigInteger[]{first, second}; } /** * Method to determine if a BigInteger is a power of 10 * @param value The BigInteger to be tested * @return True if is a power of 10 else false */ private boolean isAPowerOfTen (BigInteger value) { byte[] digits = value.getDigits(); for (short i = 0 ;i < digits.length - 1;i++) { if (digits[i] != 0) return false; } return true; } /** * Method to get the number of digits in a BigInteger * @return The number of digits */ public short size() { short size = (short)this.value.length(); short i = 0; while (size > 1 && this.value.charAt(i) == '0') { i++; size--; } return size; } /** * Method to get the digits of a BigInteger * @return The digits */ public byte[] getDigits() { return this.digits; } /** * Method to set the digits of a BigInteger */ public void setDigits(byte[] digits) { this.digits = digits; } /** * Method to compare two BigIntegers * @param other The other BigInteger * @return 1 if this BigInteger is greater, -1 if it is less 0 if both are equal */ public byte compareTo(BigInteger other) { if (this.getSign() < other.getSign()) return -1; if (this.getSign() > other.getSign()) return 1; if (this.size() < other.size()) if (this.getSign() < 0) return 1; else return -1; if (this.size() > other.size()) if (this.getSign() < 0) return -1; else return 1; for (short i = (short) (this.size() - 1);i >= 0;i--) { if (this.getDigits()[i] < other.getDigits()[i]) if (this.getSign() < 0) return 1; else return -1; if (this.getDigits()[i] > other.getDigits()[i]) if (this.getSign() < 0) return -1; else return 1; } return 0; } /** * Method to compare two BigIntegers neglecting the sign * @param other The other BigInteger * @return 1 if this BigInteger is greater, -1 if it is less 0 if both are equal */ public byte compareToNeglectingSign (BigInteger other) { if (this.size() < other.size()) return -1; if (this.size() > other.size()) return 1; for (short i = (short) (this.size() - 1);i >= 0;i--) { if (this.getDigits()[i] < other.getDigits()[i]) return -1; if (this.getDigits()[i] > other.getDigits()[i]) return 1; } return 0; } /** * Method to get the sign of this BigInteger * @return 1 is positive, -1 if negative and 0 if 0 */ public byte getSign() { return this.sign; } /** * Method to get the initial sign of this BigInteger * This method is useful in methods like add and subtract * when the signs of BigInteger objects are altered for easy manipulation * @return 1 is positive, -1 if negative and 0 if 0 */ public byte getInitialSign() { return this.initialSign; } /** * Method to set the sign of this BigInteger * @param sign The new sign value */ public void setSign(byte sign) { this.sign = sign; } /** * Overriden toString() method * @return The string representation of the BigInteger */ @Override public String toString() { short size = this.size(); String val = this.value.substring(this.value.length() - size); return (this.getSign() < 0 ? "-" : "") + val; } }