/*
* VeryLargeInteger - manipulate N-digit integer numbers. (N <= RAM)
* Copyright (C) 2014 Daniel Latham
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
*
* VERSION:
* 1.1.2 Changed some method names, mod and remainder confused, clarified
* text in LargeIntTest, resubmitted FINAL
* 1.1.1 - Fixed mod bug where returned could be more than dividend
* Turned this version in, 3rd, //NOT//FINAL
* 1.1 - Optimized file length(Deleted extra muldiv method)
* 1.0 - Working FAST div and mod! Documentation improved!
* 0.7 everything working.
* 0.6 div and mod buggy, quit for the night
* 0.5 multiplication working
* 0.1 add/subtract working
*
*
*/
public class VeryLargeInteger
{
/**
* number declared to hold the value of given number in user
* code.
*/
public String number;
/**
* revnumber is just the reversed version of the number string
*/
public String revnumber;
/**
* Sign of number, true for positive numbers and
* false for negative numbers.
*/
public boolean sign; // true is pos, false is neg
/** VeryLargeInteger constructor, So far it can add, subtract, multiply,
* divide, compare and modulo any two VeryLargeInteger objects that
* have less than or equal to 2^32 digits because of all my calls to
* the length function of the String class
* @param a Long number to be set as this.number
* @param sig Sign (+, - referred to true, false) of this
* @author Daniel_Latham
* @author [email protected]
*/
public VeryLargeInteger(long a, boolean sig)
{
number = String.valueOf(a);
sign = sig;
StringBuffer temp = new StringBuffer(number);
temp = temp.reverse();
revnumber = temp.toString();
}
/** VeryLargeIteger constructor
* @param b String of number to set as this.number
* @param sig Sign (+, - referred to true, false) of this
*/
public VeryLargeInteger(String b, boolean sig)
{
number = b.toString();
//self explanatory but makes sure this.number != "" ; EmptyStringVal
assert (number.length() != 0) : "Empty String Value!";
sign = sig;
StringBuffer temp = new StringBuffer(number);
temp = temp.reverse();
revnumber = temp.toString();
}
/** Prints our the number with sign prepended
*/
public void print()
{
if (number.length() == 1 && (int) number.charAt(0) - '0' == 0)
{
System.out.println(number);
}
else if (sign == true)
{
String newnumber = number.replaceFirst ("^0*", "");
System.out.println(newnumber);
}
else
{
String newnumber = number.replaceFirst ("^0*", "");
System.out.println("-"+newnumber);
}
}
/** Returns string of number with sign prepended
* @return number
*/
public String toString()
{
if (number.length() == 1 && (int) number.charAt(0) - '0' == 0)
{
return(number);
}
else if (sign == true)
{
String newnumber = number.replaceFirst ("^0*", "");
return newnumber;
}
else
{
String newnumber = number.replaceFirst ("^0*", "");
return("-" + newnumber);
}
}
/** Checks to see if the two VLInumbers are the same
* @param other VLInumber you want to compare
* @return The boolean of this.number == other.number
*/
public boolean equalTo(VeryLargeInteger other)
{
boolean isequal = false;
boolean equals = (number.length() == other.number.length());
if (equals == true)
{
for(int i = number.length()-1; i >= 0; i--)
{
if (((int) number.charAt(i)-'0') != ((int) other.number.charAt(i)-'0'))
{
isequal = false;
break;
}
if (i == 0)//exact same number because previous if block was never tripped, sans sign
{
isequal = true;
}
}
}
isequal = isequal && (sign == other.sign); //same trick as seen in greaterThan method
//thank you CS250
return isequal;
}
/** Checks if this.number is larger than other.number
* @param other VLInumber to capare against, is this.number > other.number?
* @return The boolean of this.number > other.number
*/
public boolean greaterThan(VeryLargeInteger other)
{
boolean isgreater = (number.length() > other.number.length());//Final value to be returned
boolean isequal = false; //if equals block is tripped, this will be set true if the two strings are actually equal
boolean equals = (number.length() == other.number.length());
if (equals == true)
{
for(int i = number.length()-1; i >= 0; i--)
{
if (((int) revnumber.charAt(i)-'0') > ((int) other.revnumber.charAt(i)-'0'))
{
isgreater = true;
break;
}
else if (((int) other.revnumber.charAt(i)-'0') > ((int) revnumber.charAt(i)-'0'))
{
isgreater = false;
break;
}
if (i == 0)//exact same number sans sign
{
isequal = true;
}
}
}
isequal = isequal && (sign == other.sign);//true if signs are the same and isequal is true, not if not
if (isequal == true)
{
return false;//if they are equal, they are the "same" VLI x, then x is not greater than x
}
if (isgreater == true)
{
if (sign != other.sign)
{
isgreater = sign;//if signs differ, then value will equal whatever this.sign is
}
}
else if (isgreater == false)
{
if (sign != other.sign)
{
isgreater = sign;//if signs differ
}
}
return isgreater;
}
/** Adds this.number to other.number
* @param other
* @return VLInumber
*/
public VeryLargeInteger add(VeryLargeInteger other)
{
/* Check sign values, decide if we want numPlusPlus(same signs)
* or numPlusMin(different signs).
*/
VeryLargeInteger newvli = null;
if ((sign == false && other.sign == false) || (sign == true && other.sign == true))
{
if (number.length() >= other.number.length())// size of self >= other
{
newvli = numPlusPlus(revnumber, other.revnumber, 0);
}
else if (number.length() < other.number.length())//size of self < other
{
newvli = numPlusPlus(other.revnumber, revnumber, 0);
}
}
else if(sign == true && other.sign == false)
{
newvli = numPlusMin(revnumber, other.revnumber, 0);
}
else if(sign == false && other.sign == true)
{
newvli = numPlusMin(other.revnumber, revnumber, 0);
}
return newvli;
}
/** Subtracts other.number from this.number
* @param other
* @return VLInumber
*/
public VeryLargeInteger sub(VeryLargeInteger other)
{
VeryLargeInteger newvli = null;
VeryLargeInteger a = new VeryLargeInteger(number, true);
VeryLargeInteger b = new VeryLargeInteger(other.number, true);
if (sign == true && other.sign == true)//both are positive
{
newvli = numPlusMin(revnumber, other.revnumber, 0);
}
else if (sign == false && other.sign == false)//both are negative
{
newvli = numPlusMin(other.revnumber, revnumber, -1);
}
else if (sign == true && other.sign == false)// -- makes plus of other.number
{
if (a.greaterThan(b)) //BIGGER not GREATER in this case, since both are set to positive
{
newvli = numPlusPlus(revnumber, other.revnumber, 0);
}
else
{
newvli = numPlusPlus(other.revnumber, revnumber, 0);
}
}
else if (sign == false && other.sign == true)
{
if (a.greaterThan(b))
{
newvli = numPlusPlus(revnumber, other.revnumber, -1);
}
else
{
newvli = numPlusPlus(other.revnumber, revnumber, -1);
}
}
return newvli;
}
/** Multiplies this.number by other.number
* @param other
* @return VLInumber
*/
public VeryLargeInteger mul(VeryLargeInteger other)
{
VeryLargeInteger newvli = null;
if ((number.length() == 1 && ((int) revnumber.charAt(0) - '0') == 0) || //0 * num or num * 0 returns 0
(other.number.length() == 1 && ((int) other.revnumber.charAt(0) - '0') == 0))
{
newvli = new VeryLargeInteger(0L, true);
}
else
{
newvli = emult(number, other.number);
}
boolean newsign = (other.sign == sign); //false if dif signs, so neg is dif
newvli = new VeryLargeInteger(newvli.number, newsign);
return newvli;
}
/** Divides this.number by other.number, deals with sign rules
* @param other
* @throws Exception
* @return VLInumber
*/
public VeryLargeInteger div(VeryLargeInteger other)
throws Exception
{
VeryLargeInteger newvli = null;
VeryLargeInteger[] vliarray = null;
VeryLargeInteger a = new VeryLargeInteger(number, true);
VeryLargeInteger b = new VeryLargeInteger(other.number, true);
//If other == 0, exit()
if (other.number.length() == 1 && (((int) other.number.charAt(0) - '0') == 0))
{
System.out.println("You can't divide by 0!");
System.exit(0);
}
//If self == 0, return 0
if (number.length() == 1 && ((int) revnumber.charAt(0) - '0') == 0)
{
newvli = new VeryLargeInteger(0L, true);
}
//If same number, return 1
else if (this.equalTo(other) == true)
{
newvli = new VeryLargeInteger(1L, true);
}
//If trying to divide this int by a larger int
else if (b.greaterThan(a))
{
newvli = new VeryLargeInteger(0L, true);
}
//Else dividing by same signs, normal
else if (other.sign == sign)
{
newvli = moddiv(number, other.number)[0];
newvli = new VeryLargeInteger(newvli.number, true);
}
//Else dividing by dif signs, negative
else if (other.sign != sign)
{
newvli = moddiv(number, other.number)[0];
newvli = new VeryLargeInteger(newvli.number, false);
}
return newvli;
}
/** Calaculates this.number / other.number returning the remainder
* and deals with weird sign rules
* @param other
* @throws Exception
* @return VLInumber
*/
public VeryLargeInteger mod(VeryLargeInteger other)
throws Exception
{
VeryLargeInteger newvli = null;
VeryLargeInteger a = new VeryLargeInteger(number, true);
VeryLargeInteger b = new VeryLargeInteger(other.number, true);
//If trying to mod by 0, exit()
if (other.number.length() == 1 && ((int) other.revnumber.charAt(0) - '0') == 0)
{
System.out.println("You can't divide by 0!");
System.exit(0);
}
//if self == 0, return 0
if (number.length() == 1 && (((int) revnumber.charAt(0) - '0') == 0))
{
newvli = new VeryLargeInteger(0L, true);
}
//if same number, return 0
else if (a.equalTo(b) == true)
{
newvli = new VeryLargeInteger(0L, true);
}
//if this < that, return this
else if (b.greaterThan(a))
{
newvli = this;
}
//if same signs
else if (other.sign == sign && sign == true)
{
newvli = moddiv(number, other.number)[2];
newvli = new VeryLargeInteger(newvli.number, true);
}
//dif signs
else if (sign == false && other.sign == true)
{
newvli = moddiv(number, other.number)[2];
newvli = new VeryLargeInteger(newvli.number, false);
}
//same signs, weird for mod
else if (other.sign == sign && sign == false)
{
newvli = moddiv(number, other.number)[2];
newvli = new VeryLargeInteger(newvli.number, false);
}
//everything else
else
{
newvli = moddiv(number, other.number)[2];
newvli = new VeryLargeInteger(newvli.number, true);
}
return newvli;
}
/** Helper method Adds two positive or two negative numbers
* @param bigger The larger of the two VLInumber by number of digits
* @param smaller The smaller of the two VLInumbers by number of digits
* @param forcedsign If -1, then the computed new VLInumber will have
* a negative sign
* @throws ArrayOutOfBoundsException
* @return VLInumber that is the addition of the two numbers,
* forcing a negative sign if needed
*/
private VeryLargeInteger numPlusPlus(String bigger, String smaller, int forcedsign)
{
VeryLargeInteger newvli = null;
String newnumber = ""; // Must reverse this at end
boolean rollover = false;
for (int i = 0; i < bigger.length(); i++)
{
int k; //placeholder value
try
{
k = ((int) bigger.charAt(i)-'0') + ((int) smaller.charAt(i)-'0'); //throws AIOOB E
//System.out.println((int) '9' - '0'); //DEBUG
if (rollover == true) { k+=1; rollover = false; }//if rollover, add 1 to placeholder
if (k >= 10) { k -=10; rollover = true; }
newnumber+=k;
}
catch (Exception e) //Expected ArrayIndexOOB exception
{
k = ((int) bigger.charAt(i)-'0');
if (rollover == true)
{
k+=1;
if (k >= 10) { k -=10; rollover = true; }
else rollover = false;
}
newnumber+=k; //add placeholder to stack, start again
}
if (i == bigger.length()-1 && rollover == true) { newnumber+=1; rollover = false; }
}
StringBuffer vjk = new StringBuffer(newnumber); //Convert to StringBuffer object to reverse string easily
vjk.reverse();
newnumber = vjk.toString(); //convert back to string, initialize newvli;
if (forcedsign == -1)
{
newvli = new VeryLargeInteger(newnumber, false); //forces a negative sign
}
else
{
newvli = new VeryLargeInteger(newnumber, sign);
}
return newvli;
}
/** Helper method Adds a two different signed VLInumbers or subtracts two same signed
* VLInumbers
* @param bigger Bigger number as in number of digits
* @param smaller Smaller number as in number of digits
* @throws ArrayOutOfBoundsException
* @return String value of new number to numPlusMin, which then
* computes the sign
*/
private String subtralpha(String bigger, String smaller)
{ //I'm so sorry
String newnumber = "";
for(int i = 0; i < bigger.length(); i++)
{
int k; //placeholder value
int tempnum; //don't remember why I put this here
try
{
k = ((int) bigger.charAt(i)-'0') - ((int) smaller.charAt(i)-'0');
// DEBUG System.out.println(k);
}
catch (Exception e)
{
k = ((int) bigger.charAt(i)-'0');
}
if (k < 0)
{
k = ((int) bigger.charAt(i)-'0');
int j = 1;
while(k < ((int) smaller.charAt(i)-'0'))
{
if (((int) bigger.charAt(i+j)-'0') >= 1) //Borrow from number
{
int tempint = ((int) bigger.charAt(i+j)-'0');
tempint -= 1;
StringBuffer temp = new StringBuffer(bigger);
/* Took a while to understand
* StringBuffer.replace uses inclusive/exclusive/int
* I kept doing incl/incl/int and couldn't understand what
* I was doing wrong
*/
temp.replace(i+j,i+j+1,Integer.toString(tempint));
bigger = temp.toString();
k+=10;
}
else /*If can't borrow from next number, next number must
* be zero, so changed zero to 9, and iterate again
*/
{
StringBuffer temp = new StringBuffer(bigger);
temp.replace(i+j,i+j+1, "9");
bigger = temp.toString();
}
j++;//capable of iterating infinitely if needed
}
k = k - ((int) smaller.charAt(i)-'0');
}
// DEBUG System.out.println(k);
newnumber += k;
// DEBUG System.out.println(newnumber);
}
//System.out.println(newnumber);
return newnumber;
}
/** Helper method Tests which number has more digits/is larger and then calls subtralpha
* on the two numbers, only then computing the sign of the new VLInumber
* @param pos Positive number
* @param neg Negative number
* @param forcedsign If -1 then forces result to a negative
* @return VLInumber to add/sub
*/
private VeryLargeInteger numPlusMin(String pos, String neg, int forcedsign)
{
VeryLargeInteger newvli = null;
boolean longer = (pos.length() > neg.length());
boolean equals = (pos.length() == neg.length());
if (equals == true)
{
//find which one, pos or neg, is actually the greater number
//through iteration, high to low values
for(int i = pos.length()-1; i >= 0; i--)
{
if (((int) pos.charAt(i)-'0') > ((int) neg.charAt(i)-'0'))
{
longer = true; //see above
break;
}
else if (((int) neg.charAt(i)-'0') > ((int) pos.charAt(i)-'0'))
{
longer = false;
break;
}
if (i == 0)//exact same number wow you win wowow
{
newvli = new VeryLargeInteger(0L, true);
return newvli;
}
}
}
String newnumber = "";
if (longer == true)//pos is bigger
{
newnumber = subtralpha(pos, neg);
}
if(longer == false)//neg is bigger
{
newnumber = subtralpha(neg, pos);
}
StringBuffer newbuffer = new StringBuffer(newnumber);
newbuffer.reverse();
newnumber = newbuffer.toString();
newnumber = newnumber.replaceFirst ("^0*", "");
newvli = new VeryLargeInteger(newnumber, longer);
return newvli;
}
/** Helper method that multiplies two numbers using a string stack for the current computation
* and a VLInumber for the total
* @param self
* @param other
* @return VLInumber
*/
private VeryLargeInteger emult(String self, String other)
{
int place = -1;
VeryLargeInteger total = new VeryLargeInteger(0L, true); //add newvli to total every iteration
for (int i = self.length()-1; i >= 0; i--)//iterate over number on "bottom"
{
VeryLargeInteger newvli = null; //newvli to hold value temporarily of stack
String stack = ""; //stack of integers for each line computed, just like on paper
place += 1; //perm holder for number of zeros to prepend
int k = place; //set to place because need to add place number of zeroes each time
int rollover = 0;
for (int j = other.length()-1; j >= 0; j--)//iterate over number on "top"
//multiplying by digit on "bottom", adding to stack
{
while (k > 0)//iterate through all prepended zeros and add them to stack
{
stack += "0";
k -= 1;
}
int temp = ((int) self.charAt(i)-'0') * ((int) other.charAt(j)-'0');
if (temp >= 10) //2 or more digits
{
if (j == 0) //if last digit on "top", add the rollover number if there is one, split and append to stack
{
temp += rollover;
rollover -= rollover;
String tempsplit = Integer.toString(temp);
stack += (int) tempsplit.charAt(1) - '0';
stack += (int) tempsplit.charAt(0) - '0';
}
else //split, add to rollover, append
{
if (rollover > 0) //if rollover already init, add to temp
{
temp += rollover;
rollover -= rollover;
}
String tempsplit = Integer.toString(temp);
rollover = (int) tempsplit.charAt(0) - '0';
stack += (int) tempsplit.charAt(1) - '0';
}
}
else
{
stack+=temp;
}
// DEBUG System.out.println("Stack " +i+" "+ stack);
}
StringBuffer bufftemp = new StringBuffer(stack);
bufftemp = bufftemp.reverse();
stack = bufftemp.toString();
newvli = new VeryLargeInteger(stack, true);
total = total.add(newvli);
}
return total;
}
/** Final quick-and-dirty helper method for the mod(remainder, not modular arithmetic) and div by power-of-2 multiplication
* @param self Dividend
* @param other Divisor
* @throws Exception
* @return VeryLargeInteger Array
*
*/
private VeryLargeInteger[] moddiv(String self, String other)//returns array of VLIs instead of boolean deciding
throws Exception
{
VeryLargeInteger selfvli = new VeryLargeInteger(self, true);
VeryLargeInteger othervli = new VeryLargeInteger(other, true);
VeryLargeInteger totalvli = new VeryLargeInteger(other, true);//total
VeryLargeInteger countvli = new VeryLargeInteger(1L, true);//div
VeryLargeInteger newadd = new VeryLargeInteger(0L, true);//placeholder
VeryLargeInteger lastadd = new VeryLargeInteger(totalvli.number, true); //placeholder
VeryLargeInteger lastcount = new VeryLargeInteger(countvli.number, true);//placeholder
VeryLargeInteger remvli = new VeryLargeInteger(0L, true);//remainder
final VeryLargeInteger MULT_BY_2 = new VeryLargeInteger(2L, true);
while (!totalvli.equalTo(selfvli) && selfvli.greaterThan(totalvli))//powers of 2 until total >= self
{
lastcount = new VeryLargeInteger(countvli.number, true);
lastadd = new VeryLargeInteger(totalvli.number, true);
newadd = totalvli.mul(MULT_BY_2);
totalvli = new VeryLargeInteger(newadd.number, true);
countvli = countvli.mul(MULT_BY_2);
}
if (totalvli.equalTo(selfvli))//total == self, return {x, y, 0}
{
VeryLargeInteger[] final1 = {countvli, totalvli, remvli};
return final1;
}
else
{
countvli = lastcount;
totalvli = lastadd;
remvli = selfvli.sub(totalvli);
if (othervli.greaterThan(remvli)) //if this, then remainder != 0
{
VeryLargeInteger[] final1 = {countvli, totalvli, remvli};
return final1;
}
//recursion for all smaller values :)
//Base cases are above if blocks
VeryLargeInteger[] newbarray = this.moddiv(remvli.number, othervli.number);
remvli = newbarray[2]; //remainder
totalvli = totalvli.add(newbarray[1]);
countvli = countvli.add(newbarray[0]);
VeryLargeInteger[] final1 = {countvli, totalvli, remvli};
return final1;//this VLInumber is actually returned
}
}
}
Comments