Thread: Please Review My Code (Long Integer Addition)

Hello everyone, thought I'd join up as this looks like a good, popular java programming community and a place to learn new things.

I am currently doing a summer research project on the implementation and verification of long integer arithmetic (some may know it as arbitrary-precision arithmetic or bignum). There will be four programs altogether: Addition, subtraction, naive multiplication and karatsuba multiplication.

I have completed the long integer addition program using what our tutor has recommended (convert user input values into an integer array, then perform addition on a units, tens, hundreds, etc basis taking into account carried numbers; like you would do addition in school.)

The result I believe is pretty decent, the program I've made can perform addition of two 50,000 digit numbers and print the solution to a text file in about 3-4 seconds.

My reason for posting it here is so that you can all take a look at the code, review it and make suggestions on improvements and how to increase efficiency (if there is a need to do so).

Obviously if you believe there is a way I can improve the code, I would like to hear merely a hint or a suggestion of a topic/class/method to research as opposed to flat-out typing said improved code.

I look forward to hearing your comments! The code is below:

/**************************************************
  * LongIntAdd.java - Program which takes in two 
  * long integers and performs an add operation on 
  * them by converting to arrays and operating on a 
  * digit-by-digit basis, taking into account any 
  * carried digits.
  * 
  * Execution: java LongIntAdd
  * Input: [Value 1] [Value 2]
  * Runtime: Two 50000-digit numbers take roughly 
  * 3.5 seconds to add together.
  *************************************************/
 
// Package import declarations.
import java.util.Scanner;
import java.io.*;
import static java.lang.Math.*;
 
public class LongIntAdd {
 
  public static void main(String args[]) {
 
    try {
 
    // Scanner class takes user input [Value 1] [Value 2] and stores 
    // as v1 and v2.
    Scanner in = new Scanner(System.in);
    String v1 = in.next();
    String v2 = in.next();
 
    // Initialize and declare variables (c is the carried number).
    int vs1 = v1.length();
    int vs2 = v2.length();
    int vMax = max(vs1,vs2);
    int vMin = min(vs1,vs2);
    int[] vArray1 = new int[vMax];
    int[] vArray2 = new int[vMax];
    int[] sArray = new int[vMax+1];
    int c = 0;
 
    // Create int arrays from the two strings, working from right to 
    // left. Both arrays are the same size, so if one string is smaller 
    // than the other, the remaining spaces to the left are null values 
    // in the array (0).
    for(int i = 1; i <= vs1; i++){
      vArray1[vMax-i] = Integer.parseInt(v1.substring(vs1-i,vs1-i+1));
    }
 
    for(int i = 1; i <= vs2; i++){
      vArray2[vMax-i] = Integer.parseInt(v2.substring(vs2-i,vs2-i+1));
    }
 
    // Create solution int array by adding together the digits for the 
    // two value arrays from right to left, taking into account the carried 
    // value. If there is a carry, c is assigned 1 and the array index has 
    // 10 taken away to ensure it only has units and not the tens which is 
    // carried. Otherwise, the carry is assigned 0.
    for(int i = vMax; i >= 1; i--){
      sArray[i] = vArray1[i-1] + vArray2[i-1] + c;
        if (sArray[i] > 9) {
          c=1;
          sArray[i]=sArray[i]-10;
        }
        else {
          c=0;
        }
    }
 
    // The first index in the solution array is simply the carry value, whether 
    // it be 0 or 1.
    sArray[0] = c;
 
    // Converts the solution int array back into a string and writes it to a text 
    // file. Checks to see whether the first digit is 0 (in other words, there 
    // was no carry from the final addition). If so, it is ignored; else, it is 
    // kept.
      BufferedWriter out = new BufferedWriter(new FileWriter("LongIntAdditionSolution.txt"));
 
      int nullCheck = 0;
      if (sArray[0] == 0) {
        nullCheck = 1;
      }
 
      for (int i = nullCheck; i < sArray.length; i++) {
        out.write(Integer.toString(sArray[i]));
      }
 
      out.close();
    }
 
    catch (IOException e) {
      System.err.println("There has been an error!");
      e.printStackTrace();
    }
 
  }
 
}

Oh and I'm all for good programming practice, so if there's anything here that may be bad practice, please tell me and suggest improvements for them!

Originally Posted by helloworld922

The only thin i would change after a first look is main methods generally shouldn't throw checked exceptions. Not really a problem compile wise, but if there is a checked exception, it usually should be handled by your program and not the JVM (even if all you do is simply catch and ignore it). You could change your program by simply moving the "try" statement to the top of the method and removing the "throws" declaration.

I'm curious to know why you have the "//s" delimiter... That's done by the next() method (correct me if i'm wrong someone).

All in all, this is a nice piece of code. I don't see a way to optimize this substantially, though it would be easier to read if you used the charAt() method instead of the substring() method to read each individual number in.

Not your first post, but welcome anyways!

Thanks for the comments! I actually added the throw in as an afterthought. I wasn't sure whether it was required or not so took a gamble. I've always been a little iffy on exceptions and errors so that's something I need to read up on. I'm glad you've cleared things up with that though!

Regarding the delimiter, you're right, I just tested without the delimiter statement and it worked, so whitespace is the default. I thought the default was newline, hence why I explicitly specified the delimiter. Thanks for bringing that up!

Using charAt(), am I right in assuming that I would need to convert the char into a string prior to parsing it into an integer? I assume that if I directly converted the char into an int I would get the ASCII code (i.e. 1 would become 49 rather than 1). If you could clarify that. Here's what I get:

//charAt()
for(int i = 1; i <= vs1; i++) {
  vArray1[vMax-i] = Integer.parseInt(Character.toString(v1.charAt(vs1-i)));
}

And thanks for the warm welcome!

Scratch that, on another forum Character.digit() was brought up, not sure why I didn't have that in mind first time round!

Also, on the other forum, someone highlighted the fact that creating two arrays of the same size for the values could be very wasteful if, for example, one value is 50,000 digits and the other is only 1 digit! A very valid point which I had completely overlooked!!

So I've been working all night on a solution, here's what I've come up with:

/**************************************************
  * LongIntAdd.java - Program which takes in two 
  * long integers and performs an add operation on 
  * them by converting to arrays and operating on a 
  * digit-by-digit basis, taking into account any 
  * carried digits.
  * 
  * Execution: java LongIntAdd
  * Input: [Value 1] [Value 2]
  * Runtime: Two 50000-digit numbers take roughly 
  * 3.5 seconds to add together.
  *************************************************/
 
// Package import declarations.
import java.util.Scanner;
import java.io.*;
import static java.lang.Math.*;
 
public class LongIntAdd2 {
 
  public static void main(String args[]) {
    try { 
      // Scanner class takes user input [Value 1] [Value 2] and stores 
      // as v1 and v2.
      Scanner in = new Scanner(System.in);
      String v1 = in.next();
      String v2 = in.next();
 
      // Initialize and declare variables (c is the carried number).
      int vs1 = v1.length();
      int vs2 = v2.length();
      int vMax = max(vs1,vs2)+1;
      int vMin = min(vs1,vs2);
      int[] vArray1 = new int[vs1];
      int[] vArray2 = new int[vs2];
      int[] sArray = new int[vMax];
      int c = 0;
 
      // Create int arrays from the two strings.
      for(int i = 0; i < vs1; i++){
        vArray1[i] = Character.digit(v1.charAt(i),10);
      }
 
      for(int i = 0; i < vs2; i++){
        vArray2[i] = Character.digit(v2.charAt(i),10);
      }
 
      // Create solution int array by adding together the digits for the 
      // two value arrays from right to left, taking into account the carried 
      // value. If there is a carry, c is assigned 1 and the array index has 
      // 10 taken away to ensure it only has units and not the tens which is 
      // carried. Otherwise, the carry is assigned 0.
      for(int i = 1; i <= vMin; i++){
        sArray[vMax-i] = vArray1[vs1-i] + vArray2[vs2-i] + c;
 
        if (sArray[vMax-i] > 9) {
          c=1;
          sArray[vMax-i]=sArray[vMax-i]-10;
        }
        else {
          c=0;
        }
      }
 
      // After all the digits of the minimum length value have been added
      // to the other value, only the maximum length value and carry are 
      // taken into account.
      for(int i=vMin+1; i < vMax; i++){
        if(vs1 > vs2){
          sArray[vMax-i] = vArray1[vs1-i] + c;
        }
        else {
          sArray[vMax-i] = vArray2[vs2-i] + c;
        }
 
        if (sArray[vMax-i] > 9) {
          c=1;
          sArray[vMax-i]=sArray[vMax-i]-10;
        }
        else {
          c=0;
        }
      }
 
      // The first index in the solution array is simply the carry value, whether 
      // it be 0 or 1.
      sArray[0] = c;
 
      // Converts the solution int array back into a string and writes it to a text 
      // file. Checks to see whether the first digit is 0 (in other words, there 
      // was no carry from the final addition). If so, it is ignored; else, it is 
      // kept. Try-catch statements included to ensure any exceptions are caught.
      BufferedWriter out = new BufferedWriter(new FileWriter("LongIntAdditionSolution.txt"));
 
      int nullCheck = 0;
      if (sArray[0] == 0) {
        nullCheck = 1;
      }
 
      for (int i = nullCheck; i < sArray.length; i++) {
        out.write(Integer.toString(sArray[i]));
      }
 
      out.close();
    }
 
    catch (IOException e) {
      System.err.println("There has been an error!");
      e.printStackTrace();
    }
 
  }
 
}

Please tell me what you think. As you can see, the part of the code which creates the value arrays is much simpler, standard and more easy to read now. Also the arrays created are the same size as the values they're derived from, as opposed to being the same size and the smaller value's array being filled with null values!

The only downside with this revised code is I have duplicated the if-else statement regarding the carry number (it's in both for loops). Right now, I can't see any satisfactory way around this...

What I've done is explained in the code comments, it's the most efficient way of doing things from what I can see. I hope so anyway! It certainly deals with different sized values much more effectively.

Look forward to hearing your feedback.

The two for loops and repeated if-else statement issue has been solved:

    for(int i = 1; i < vMax; i++){
        if(vs1-i < 0){
          vAdd1 = 0;
        }
        else {
          vAdd1 = vArray1[vs1-i];
        }
 
        if(vs2-i < 0){
          vAdd2 = 0;
        }
        else {
          vAdd2 = vArray2[vs2-i];
        }
 
        sArray[vMax-i] = vAdd1 + vAdd2 + carry;
 
        if(sArray[vMax-i] > 9) {
          carry = 1;
          sArray[vMax-i] = sArray[vMax-i]-10;
        }
        else {
          carry=0;
        }
      }

This way, once the smaller digit value is trying to refer to negative indexes it is simply ignored (the variable is set to 0). This acts in the same way as the code in my previous post but with just one for loop, and the carry if-else statement only needs to be written once!

I think the code is pretty much sorted now, I will be grouping the different parts into their own methods once the LongIntegerSubtraction.java program is written, so that I can pass values between the two (if they're negative for example, the Add program can pass them to the Subtract program easily), but for now I don't think it's necessary.

If someone could give one last look at my code (taking into account the new code in this post) and give the OK, then I can mark this as solved! Then I'll be back in a few days so you can have a look at my Subtract program and the linking between the two!!

Look forward to hearing feedback!

a really random memory optimization i just thought of. You're already holding the read in number as a string, so you don't really need another copy as an integer array, just a string for the answer.

// code fragment
String num1 = input.next();
String num2 = input.next();
String ans = "";
boolean done = false;
boolean carry = false;
// we want to add starting from the left
int count1 = num1.length()-1;
int count2 = num2.length()-1;
while (!done)
{
     int val1 = 0;
     int val2 = 0;
     if (count1 >= 0)
    {
          val1 = Integer.parseInt(num1.charAt(count1));
     }
     if (count2 >= 0)
     {
          val2 = Integer.parseInt(num2.charAt(count2));
     }
     if (carry)
     {
          val1++;
     }
     String temp = val1+val2+"";
     if (temp.length() > 1)
     {
          carry = true;
          ans = temp.charAt(1) + ans;
     }
     else
     {
          carry = false;
          ans = temp.charAt(0) + ans;
     }
     count1--;
     count2--;
     if(count1 < 0 && count2 < 0)
     {
          done = true;
     }
}
if (carry)
{
     // left over carry
     ans = 1 + ans;
}

Sorry i don't have as nice as comments as you
edit:
oh, i didn't realize, but this method could possibly lead a trail of 0's at the beginning (given bad input). To get rid of them:

int counter;
for (counter = 0; i < ans.length()-1 && ans.charAt(i) == 0; i++)
{}
ans = ans.subString(counter,ans.length());