API tools faq
paste
isefire

VeryLargeInteger_Final

isefire
Sep 11th, 2014
339
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 20.74 KB | None | 0 0
raw download clone embed print report
  1. /*
  2.  *  VeryLargeInteger - manipulate N-digit integer numbers. (N <= RAM)
  3.  *  Copyright (C) 2014  Daniel Latham
  4.  *  
  5.  *  This program is free software: you can redistribute it and/or modify
  6.  *  it under the terms of the GNU General Public License as published by
  7.  *  the Free Software Foundation, either version 3 of the License, or
  8.  *  (at your option) any later version.
  9.  *
  10.  *  This program is distributed in the hope that it will be useful,
  11.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  *  GNU General Public License for more details.
  14.  *
  15.  *  You should have received a copy of the GNU General Public License
  16.  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17.  *
  18.  *
  19.  * VERSION:
  20.  * 1.1.2 Changed some method names, mod and remainder confused, clarified
  21.  *       text in LargeIntTest, resubmitted FINAL
  22.  * 1.1.1 - Fixed mod bug where returned could be more than dividend
  23.  *         Turned this version in, 3rd, //NOT//FINAL
  24.  * 1.1 - Optimized file length(Deleted extra muldiv method)
  25.  * 1.0 - Working FAST div and mod! Documentation improved!
  26.  * 0.7 everything working.
  27.  * 0.6 div and mod buggy, quit for the night
  28.  * 0.5 multiplication working
  29.  * 0.1 add/subtract working
  30.  *
  31.  *
  32.  */
  33. public class VeryLargeInteger
  34. {
  35.     /**
  36.      * number declared to hold the value of given number in user
  37.      * code.
  38.      */
  39.     public String number;
  40.     /**
  41.      * revnumber is just the reversed version of the number string
  42.      */
  43.     public String revnumber;
  44.     /**
  45.      * Sign of number, true for positive numbers and
  46.      * false for negative numbers.
  47.      */
  48.     public boolean sign; // true is pos, false is neg
  49.     /** VeryLargeInteger constructor, So far it can add, subtract, multiply,
  50.      * divide, compare and modulo any two VeryLargeInteger objects that
  51.      * have less than or equal to 2^32 digits because of all my calls to
  52.      * the length function of the String class
  53.      * @param a Long number to be set as this.number
  54.      * @param sig Sign (+, - referred to true, false) of this
  55.      * @author Daniel_Latham
  56.      * @author [email protected]
  57.      */
  58.     public VeryLargeInteger(long a, boolean sig)
  59.     {
  60.         number = String.valueOf(a);
  61.         sign = sig;
  62.         StringBuffer temp = new StringBuffer(number);
  63.         temp = temp.reverse();
  64.         revnumber = temp.toString();
  65.     }
  66.     /** VeryLargeIteger constructor
  67.      * @param b String of number to set as this.number
  68.      * @param sig Sign (+, - referred to true, false) of this
  69.      */
  70.     public VeryLargeInteger(String b, boolean sig)
  71.     {
  72.         number = b.toString();
  73.         //self explanatory but makes sure this.number != "" ; EmptyStringVal
  74.         assert (number.length() != 0) : "Empty String Value!";
  75.         sign = sig;
  76.         StringBuffer temp = new StringBuffer(number);
  77.         temp = temp.reverse();
  78.         revnumber = temp.toString();
  79.     }
  80.     /** Prints our the number with sign prepended
  81.      */
  82.     public void print()
  83.     {
  84.         if (number.length() == 1 && (int) number.charAt(0) - '0' == 0)
  85.         {
  86.             System.out.println(number);
  87.         }
  88.         else if (sign == true)
  89.         {
  90.             String newnumber = number.replaceFirst ("^0*", "");
  91.             System.out.println(newnumber);
  92.         }
  93.         else
  94.         {
  95.             String newnumber = number.replaceFirst ("^0*", "");
  96.             System.out.println("-"+newnumber);
  97.         }
  98.     }
  99.     /** Returns string of number with sign prepended
  100.      * @return number
  101.      */
  102.     public String toString()
  103.     {
  104.         if (number.length() == 1 && (int) number.charAt(0) - '0' == 0)
  105.         {
  106.             return(number);
  107.         }
  108.         else if (sign == true)
  109.         {
  110.             String newnumber = number.replaceFirst ("^0*", "");
  111.             return newnumber;
  112.         }
  113.         else
  114.         {
  115.             String newnumber = number.replaceFirst ("^0*", "");
  116.             return("-" + newnumber);
  117.         }
  118.     }
  119.     /** Checks to see if the two VLInumbers are the same
  120.      * @param other VLInumber you want to compare
  121.      * @return      The boolean of this.number == other.number
  122.      */
  123.     public boolean equalTo(VeryLargeInteger other)
  124.     {
  125.         boolean isequal = false;
  126.         boolean equals = (number.length() == other.number.length());
  127.         if (equals == true)
  128.         {
  129.             for(int i = number.length()-1; i >= 0; i--)
  130.             {
  131.                 if (((int) number.charAt(i)-'0') != ((int) other.number.charAt(i)-'0'))
  132.                 {
  133.                     isequal = false;
  134.                     break;
  135.                 }
  136.                 if (i == 0)//exact same number because previous if block was never tripped, sans sign
  137.                 {
  138.                     isequal = true;
  139.                 }
  140.             }
  141.         }
  142.         isequal = isequal && (sign == other.sign); //same trick as seen in greaterThan method
  143.         //thank you CS250
  144.         return isequal;
  145.     }
  146.     /** Checks if this.number is larger than other.number
  147.      * @param other VLInumber to capare against, is this.number > other.number?
  148.      * @return      The boolean of this.number > other.number
  149.      */
  150.     public boolean greaterThan(VeryLargeInteger other)
  151.     {
  152.         boolean isgreater = (number.length() > other.number.length());//Final value to be returned
  153.         boolean isequal = false; //if equals block is tripped, this will be set true if the two strings are actually equal
  154.         boolean equals = (number.length() == other.number.length());
  155.         if (equals == true)
  156.         {
  157.             for(int i = number.length()-1; i >= 0; i--)
  158.             {
  159.                 if (((int) revnumber.charAt(i)-'0') > ((int) other.revnumber.charAt(i)-'0'))
  160.                 {
  161.                     isgreater = true;
  162.                     break;
  163.                 }
  164.                 else if (((int) other.revnumber.charAt(i)-'0') > ((int) revnumber.charAt(i)-'0'))
  165.                 {
  166.                     isgreater = false;
  167.                     break;
  168.                 }
  169.                 if (i == 0)//exact same number sans sign
  170.                 {
  171.                     isequal = true;
  172.                 }
  173.             }
  174.         }
  175.         isequal = isequal && (sign == other.sign);//true if signs are the same and isequal is true, not if not
  176.         if (isequal == true)
  177.         {
  178.             return false;//if they are equal, they are the "same" VLI x, then x is not greater than x
  179.         }
  180.         if (isgreater == true)
  181.         {
  182.             if (sign != other.sign)
  183.             {
  184.                 isgreater = sign;//if signs differ, then value will equal whatever this.sign  is
  185.             }
  186.         }
  187.         else if (isgreater == false)
  188.         {
  189.             if (sign != other.sign)
  190.             {
  191.                 isgreater = sign;//if signs differ
  192.             }
  193.         }
  194.         return isgreater;
  195.     }
  196.  
  197.     /** Adds this.number to other.number
  198.      * @param other
  199.      * @return       VLInumber
  200.      */
  201.     public VeryLargeInteger add(VeryLargeInteger other)
  202.     {
  203.         /* Check sign values, decide if we want numPlusPlus(same signs)
  204.          * or numPlusMin(different signs).
  205.          */
  206.         VeryLargeInteger newvli = null;
  207.         if ((sign == false && other.sign == false) || (sign == true && other.sign == true))
  208.         {
  209.             if (number.length() >= other.number.length())// size of self >= other
  210.             {
  211.                 newvli = numPlusPlus(revnumber, other.revnumber, 0);
  212.             }
  213.             else if (number.length() < other.number.length())//size of self < other
  214.             {
  215.                 newvli = numPlusPlus(other.revnumber, revnumber, 0);
  216.             }
  217.         }
  218.         else if(sign == true && other.sign == false)
  219.         {
  220.             newvli = numPlusMin(revnumber, other.revnumber, 0);
  221.         }
  222.         else if(sign == false && other.sign == true)
  223.         {
  224.             newvli = numPlusMin(other.revnumber, revnumber, 0);
  225.         }
  226.        
  227.         return newvli;
  228.     }
  229.     /** Subtracts other.number from this.number
  230.      * @param other
  231.      * @return       VLInumber
  232.      */
  233.     public VeryLargeInteger sub(VeryLargeInteger other)
  234.     {
  235.         VeryLargeInteger newvli = null;
  236.         VeryLargeInteger a = new VeryLargeInteger(number, true);
  237.         VeryLargeInteger b = new VeryLargeInteger(other.number, true);
  238.         if (sign == true && other.sign == true)//both are positive
  239.         {
  240.             newvli = numPlusMin(revnumber, other.revnumber, 0);
  241.         }
  242.         else if (sign == false && other.sign == false)//both are negative
  243.         {
  244.             newvli = numPlusMin(other.revnumber, revnumber, -1);
  245.         }
  246.         else if (sign == true && other.sign == false)// -- makes plus of other.number
  247.         {
  248.             if (a.greaterThan(b)) //BIGGER not GREATER in this case, since both are set to positive
  249.             {
  250.                 newvli = numPlusPlus(revnumber, other.revnumber, 0);
  251.             }
  252.             else
  253.             {
  254.                 newvli = numPlusPlus(other.revnumber, revnumber, 0);
  255.             }
  256.         }
  257.         else if (sign == false && other.sign == true)
  258.         {
  259.             if (a.greaterThan(b))
  260.             {
  261.                 newvli = numPlusPlus(revnumber, other.revnumber, -1);
  262.             }
  263.             else
  264.             {
  265.                 newvli = numPlusPlus(other.revnumber, revnumber, -1);
  266.             }
  267.         }
  268.         return newvli;
  269.     }
  270.  
  271.     /** Multiplies this.number by other.number
  272.      * @param other
  273.      * @return          VLInumber
  274.      */
  275.     public VeryLargeInteger mul(VeryLargeInteger other)
  276.     {
  277.         VeryLargeInteger newvli = null;
  278.         if ((number.length() == 1 && ((int) revnumber.charAt(0) - '0') == 0) || //0 * num or num * 0 returns 0
  279.             (other.number.length() == 1 && ((int) other.revnumber.charAt(0) - '0') == 0))
  280.         {
  281.             newvli = new VeryLargeInteger(0L, true);
  282.         }
  283.         else
  284.         {
  285.             newvli = emult(number, other.number);
  286.         }
  287.         boolean newsign = (other.sign == sign); //false if dif signs, so neg is dif
  288.         newvli = new VeryLargeInteger(newvli.number, newsign);
  289.         return newvli;
  290.     }
  291.     /** Divides this.number by other.number, deals with sign rules
  292.      * @param other
  293.      * @throws Exception
  294.      * @return        VLInumber
  295.      */
  296.     public VeryLargeInteger div(VeryLargeInteger other)
  297.     throws Exception
  298.     {
  299.         VeryLargeInteger newvli = null;
  300.         VeryLargeInteger[] vliarray = null;
  301.         VeryLargeInteger a = new VeryLargeInteger(number, true);
  302.         VeryLargeInteger b = new VeryLargeInteger(other.number, true);
  303.          //If other == 0, exit()
  304.         if (other.number.length() == 1 && (((int) other.number.charAt(0) - '0') == 0))
  305.         {
  306.             System.out.println("You can't divide by 0!");
  307.             System.exit(0);
  308.         }
  309.          //If self == 0, return 0
  310.         if (number.length() == 1 && ((int) revnumber.charAt(0) - '0') == 0)
  311.         {
  312.             newvli = new VeryLargeInteger(0L, true);
  313.         }
  314.         //If same number, return 1
  315.         else if (this.equalTo(other) == true)
  316.         {
  317.             newvli = new VeryLargeInteger(1L, true);
  318.         }
  319.         //If trying to divide this int by a larger int
  320.         else if (b.greaterThan(a))
  321.         {
  322.             newvli = new VeryLargeInteger(0L, true);
  323.         }
  324.         //Else dividing by same signs, normal
  325.         else if (other.sign == sign)
  326.         {
  327.             newvli = moddiv(number, other.number)[0];
  328.             newvli = new VeryLargeInteger(newvli.number, true);
  329.         }
  330.         //Else dividing by dif signs, negative
  331.         else if (other.sign != sign)
  332.         {
  333.             newvli = moddiv(number, other.number)[0];
  334.             newvli = new VeryLargeInteger(newvli.number, false);
  335.         }
  336.        
  337.         return newvli;
  338.     }
  339.     /** Calaculates this.number / other.number returning the remainder
  340.      * and deals with weird sign rules
  341.      * @param other
  342.      * @throws Exception
  343.      * @return        VLInumber
  344.      */
  345.     public VeryLargeInteger mod(VeryLargeInteger other)
  346.     throws Exception
  347.     {
  348.         VeryLargeInteger newvli = null;
  349.         VeryLargeInteger a = new VeryLargeInteger(number, true);
  350.         VeryLargeInteger b = new VeryLargeInteger(other.number, true);
  351.         //If trying to mod by 0, exit()
  352.         if (other.number.length() == 1 && ((int) other.revnumber.charAt(0) - '0') == 0)
  353.         {
  354.             System.out.println("You can't divide by 0!");
  355.             System.exit(0);
  356.         }
  357.         //if self == 0, return 0
  358.         if (number.length() == 1 && (((int) revnumber.charAt(0) - '0') == 0))
  359.         {
  360.             newvli = new VeryLargeInteger(0L, true);
  361.         }
  362.         //if same number, return 0
  363.         else if (a.equalTo(b) == true)
  364.         {
  365.             newvli = new VeryLargeInteger(0L, true);
  366.         }
  367.         //if this < that, return this
  368.         else if (b.greaterThan(a))
  369.         {
  370.             newvli = this;
  371.         }
  372.         //if same signs
  373.         else if (other.sign == sign && sign == true)
  374.         {
  375.             newvli = moddiv(number, other.number)[2];
  376.             newvli = new VeryLargeInteger(newvli.number, true);
  377.         }
  378.         //dif signs
  379.         else if (sign == false && other.sign == true)
  380.         {
  381.             newvli = moddiv(number, other.number)[2];
  382.             newvli = new VeryLargeInteger(newvli.number, false);
  383.         }
  384.         //same signs, weird for mod
  385.         else if (other.sign == sign && sign == false)
  386.         {
  387.             newvli = moddiv(number, other.number)[2];
  388.             newvli = new VeryLargeInteger(newvli.number, false);
  389.         }
  390.         //everything else
  391.         else
  392.         {
  393.             newvli = moddiv(number, other.number)[2];
  394.             newvli = new VeryLargeInteger(newvli.number, true);
  395.         }
  396.        
  397.         return newvli;
  398.     }
  399.     /** Helper method Adds two positive or two negative numbers
  400.      * @param bigger The larger of the two VLInumber by number of digits
  401.      * @param smaller The smaller of the two VLInumbers by number of digits
  402.      * @param forcedsign If -1, then the computed new VLInumber will have
  403.      *                   a negative sign
  404.      * @throws ArrayOutOfBoundsException
  405.      * @return           VLInumber that is the addition of the two numbers,
  406.      *                   forcing a negative sign if needed
  407.      */
  408.     private VeryLargeInteger numPlusPlus(String bigger, String smaller, int forcedsign)
  409.     {
  410.         VeryLargeInteger newvli = null;
  411.         String newnumber = ""; // Must reverse this at end
  412.         boolean rollover = false;
  413.        
  414.         for (int i = 0; i < bigger.length(); i++)
  415.         {
  416.             int k; //placeholder value
  417.             try
  418.             {
  419.                 k = ((int) bigger.charAt(i)-'0') + ((int) smaller.charAt(i)-'0'); //throws AIOOB E
  420.                 //System.out.println((int) '9' - '0'); //DEBUG
  421.                 if (rollover == true) { k+=1; rollover = false; }//if rollover, add 1 to placeholder
  422.                 if (k >= 10) { k -=10; rollover = true; }
  423.                 newnumber+=k;
  424.             }
  425.             catch (Exception e) //Expected ArrayIndexOOB exception
  426.             {
  427.                 k = ((int) bigger.charAt(i)-'0');
  428.                 if (rollover == true)
  429.                 {
  430.                     k+=1;
  431.                     if (k >= 10) { k -=10; rollover = true; }
  432.                     else rollover = false;
  433.                 }
  434.                 newnumber+=k; //add placeholder to stack, start again
  435.             }
  436.             if (i == bigger.length()-1 && rollover == true) { newnumber+=1; rollover = false; }
  437.         }
  438.         StringBuffer vjk = new StringBuffer(newnumber); //Convert to StringBuffer object to reverse string easily
  439.         vjk.reverse();
  440.         newnumber = vjk.toString(); //convert back to string, initialize newvli;
  441.         if (forcedsign == -1)
  442.         {
  443.             newvli = new VeryLargeInteger(newnumber, false); //forces a negative sign
  444.         }
  445.         else
  446.         {
  447.             newvli = new VeryLargeInteger(newnumber, sign);
  448.         }
  449.         return newvli;
  450.     }
  451.     /** Helper method Adds a two different signed VLInumbers or subtracts two same signed
  452.      * VLInumbers
  453.      * @param bigger Bigger number as in number of digits
  454.      * @param smaller Smaller number as in number of digits
  455.      * @throws ArrayOutOfBoundsException
  456.      * @return          String value of new number to numPlusMin, which then
  457.      *                  computes the sign
  458.      */
  459.     private String subtralpha(String bigger, String smaller)
  460.     { //I'm so sorry
  461.         String newnumber = "";
  462.         for(int i = 0; i < bigger.length(); i++)
  463.         {
  464.             int k; //placeholder value
  465.             int tempnum; //don't remember why I put this here
  466.             try
  467.             {
  468.                 k = ((int) bigger.charAt(i)-'0') - ((int) smaller.charAt(i)-'0');
  469.                 // DEBUG System.out.println(k);
  470.             }
  471.             catch (Exception e)
  472.             {
  473.                 k = ((int) bigger.charAt(i)-'0');
  474.             }
  475.             if (k < 0)
  476.             {
  477.                 k = ((int) bigger.charAt(i)-'0');
  478.                 int j = 1;
  479.                 while(k < ((int) smaller.charAt(i)-'0'))
  480.                 {
  481.                     if (((int) bigger.charAt(i+j)-'0') >= 1) //Borrow from number
  482.                     {
  483.                         int tempint = ((int) bigger.charAt(i+j)-'0');
  484.                         tempint -= 1;
  485.                         StringBuffer temp = new StringBuffer(bigger);
  486.                         /* Took a while to understand
  487.                          * StringBuffer.replace uses inclusive/exclusive/int
  488.                          * I kept doing incl/incl/int and couldn't understand what
  489.                          * I was doing wrong
  490.                          */
  491.                         temp.replace(i+j,i+j+1,Integer.toString(tempint));
  492.                         bigger = temp.toString();
  493.                         k+=10;
  494.                     }
  495.                     else /*If can't borrow from next number, next number must
  496.                         * be zero, so changed zero to 9, and iterate again
  497.                         */
  498.                     {
  499.                         StringBuffer temp = new StringBuffer(bigger);
  500.                         temp.replace(i+j,i+j+1, "9");
  501.                         bigger = temp.toString();
  502.                     }
  503.                     j++;//capable of iterating infinitely if needed
  504.                 }
  505.                 k = k - ((int) smaller.charAt(i)-'0');
  506.             }
  507.             // DEBUG System.out.println(k);
  508.             newnumber += k;
  509.             // DEBUG System.out.println(newnumber);
  510.         }
  511.         //System.out.println(newnumber);
  512.         return newnumber;
  513.     }
  514.     /** Helper method Tests which number has more digits/is larger and then calls subtralpha
  515.      * on the two numbers, only then computing the sign of the new VLInumber
  516.      * @param pos Positive number
  517.      * @param neg Negative number
  518.      * @param forcedsign If -1 then forces result to a negative
  519.      * @return            VLInumber to add/sub
  520.      */
  521.     private VeryLargeInteger numPlusMin(String pos, String neg, int forcedsign)
  522.     {
  523.         VeryLargeInteger newvli = null;
  524.         boolean longer = (pos.length() > neg.length());
  525.         boolean equals = (pos.length() == neg.length());
  526.         if (equals == true)
  527.         {
  528.             //find which one, pos or neg, is actually the greater number
  529.             //through iteration, high to low values
  530.             for(int i = pos.length()-1; i >= 0; i--)
  531.             {
  532.                 if (((int) pos.charAt(i)-'0') > ((int) neg.charAt(i)-'0'))
  533.                 {
  534.                     longer = true; //see above
  535.                     break;
  536.                 }
  537.                 else if (((int) neg.charAt(i)-'0') > ((int) pos.charAt(i)-'0'))
  538.                 {
  539.                     longer = false;
  540.                     break;
  541.                 }
  542.                 if (i == 0)//exact same number wow you win wowow
  543.                 {
  544.                     newvli = new VeryLargeInteger(0L, true);
  545.                     return newvli;
  546.                 }
  547.             }
  548.         }
  549.  
  550.         String newnumber = "";
  551.         if (longer == true)//pos is bigger
  552.         {
  553.             newnumber = subtralpha(pos, neg);
  554.         }
  555.         if(longer == false)//neg is bigger
  556.         {
  557.             newnumber = subtralpha(neg, pos);
  558.         }
  559.         StringBuffer newbuffer = new StringBuffer(newnumber);
  560.         newbuffer.reverse();
  561.         newnumber = newbuffer.toString();
  562.         newnumber = newnumber.replaceFirst ("^0*", "");
  563.        
  564.         newvli = new VeryLargeInteger(newnumber, longer);
  565.         return newvli;
  566.     }
  567.     /** Helper method that multiplies two numbers using a string stack for the current computation
  568.      * and a VLInumber for the total
  569.      * @param self
  570.      * @param other
  571.      * @return       VLInumber
  572.      */
  573.     private VeryLargeInteger emult(String self, String other)
  574.     {
  575.         int place = -1;
  576.         VeryLargeInteger total = new VeryLargeInteger(0L, true); //add newvli to total every iteration
  577.         for (int i = self.length()-1; i >= 0; i--)//iterate over number on "bottom"
  578.         {
  579.             VeryLargeInteger newvli = null; //newvli to hold value temporarily of stack
  580.             String stack = ""; //stack of integers for each line computed, just like on paper
  581.             place += 1; //perm holder for number of zeros to prepend
  582.             int k = place; //set to place because need to add place number of zeroes each time
  583.             int rollover = 0;
  584.             for (int j = other.length()-1; j >= 0; j--)//iterate over number on "top"
  585.                                     //multiplying by digit on "bottom", adding to stack
  586.             {
  587.                 while (k > 0)//iterate through all prepended zeros and add them to stack
  588.                 {
  589.                     stack += "0";
  590.                     k -= 1;
  591.                 }
  592.                 int temp = ((int) self.charAt(i)-'0') * ((int) other.charAt(j)-'0');
  593.                 if (temp >= 10) //2 or more digits
  594.                 {
  595.                     if (j == 0) //if last digit on "top", add the rollover number if there is one, split and append to stack
  596.                     {
  597.                         temp += rollover;
  598.                         rollover -= rollover;
  599.                         String tempsplit = Integer.toString(temp);
  600.                         stack += (int) tempsplit.charAt(1) - '0';
  601.                         stack += (int) tempsplit.charAt(0) - '0';
  602.                     }
  603.                     else //split, add to rollover, append
  604.                     {
  605.                         if (rollover > 0) //if rollover already init, add to temp
  606.                         {
  607.                             temp += rollover;
  608.                             rollover -= rollover;
  609.                         }
  610.                         String tempsplit = Integer.toString(temp);
  611.                         rollover = (int) tempsplit.charAt(0) - '0';
  612.                         stack += (int) tempsplit.charAt(1) - '0';
  613.                     }
  614.                 }
  615.                 else
  616.                 {
  617.                     stack+=temp;
  618.                 }
  619.                 // DEBUG System.out.println("Stack " +i+" "+ stack);
  620.                
  621.             }
  622.             StringBuffer bufftemp = new StringBuffer(stack);
  623.             bufftemp = bufftemp.reverse();
  624.             stack = bufftemp.toString();
  625.             newvli = new VeryLargeInteger(stack, true);
  626.             total = total.add(newvli);
  627.            
  628.         }
  629.         return total;
  630.     }
  631.     /** Final quick-and-dirty helper method for the mod(remainder, not modular arithmetic) and div by power-of-2 multiplication
  632.      * @param self Dividend
  633.      * @param other Divisor
  634.      * @throws Exception
  635.      * @return VeryLargeInteger Array
  636.      *
  637.      */
  638.     private VeryLargeInteger[] moddiv(String self, String other)//returns array of VLIs instead of boolean deciding
  639.     throws Exception
  640.     {
  641.         VeryLargeInteger selfvli = new VeryLargeInteger(self, true);
  642.         VeryLargeInteger othervli = new VeryLargeInteger(other, true);
  643.         VeryLargeInteger totalvli = new VeryLargeInteger(other, true);//total
  644.         VeryLargeInteger countvli = new VeryLargeInteger(1L, true);//div
  645.         VeryLargeInteger newadd = new VeryLargeInteger(0L, true);//placeholder
  646.         VeryLargeInteger lastadd = new VeryLargeInteger(totalvli.number, true); //placeholder
  647.         VeryLargeInteger lastcount = new VeryLargeInteger(countvli.number, true);//placeholder
  648.         VeryLargeInteger remvli = new VeryLargeInteger(0L, true);//remainder
  649.         final VeryLargeInteger MULT_BY_2 = new VeryLargeInteger(2L, true);
  650.         while (!totalvli.equalTo(selfvli) && selfvli.greaterThan(totalvli))//powers of 2 until total >= self
  651.         {
  652.             lastcount = new VeryLargeInteger(countvli.number, true);
  653.             lastadd = new VeryLargeInteger(totalvli.number, true);
  654.             newadd = totalvli.mul(MULT_BY_2);
  655.             totalvli = new VeryLargeInteger(newadd.number, true);
  656.             countvli = countvli.mul(MULT_BY_2);
  657.         }
  658.         if (totalvli.equalTo(selfvli))//total == self, return {x, y, 0}
  659.         {
  660.             VeryLargeInteger[] final1 = {countvli, totalvli, remvli};
  661.             return final1;
  662.         }
  663.         else
  664.         {
  665.             countvli = lastcount;
  666.             totalvli = lastadd;
  667.             remvli = selfvli.sub(totalvli);
  668.             if (othervli.greaterThan(remvli)) //if this, then remainder != 0
  669.             {
  670.                 VeryLargeInteger[] final1 = {countvli, totalvli, remvli};
  671.                 return final1;
  672.             }
  673.             //recursion for all smaller values :)
  674.             //Base cases are above if blocks
  675.             VeryLargeInteger[] newbarray = this.moddiv(remvli.number, othervli.number);
  676.             remvli = newbarray[2]; //remainder
  677.             totalvli = totalvli.add(newbarray[1]);
  678.             countvli = countvli.add(newbarray[0]);
  679.             VeryLargeInteger[] final1 = {countvli, totalvli, remvli};
  680.             return final1;//this VLInumber is actually returned
  681.         }
  682.     }
  683. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!