Please Review My Code (Long Integer Addition)

[Saradus]

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. 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();
    }

  }
  
}

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!

[angryboy]

    for(int i = 1; i <= vs1; i++){
      vArray1[vMax-i] = Integer.parseInt(v1.substring(vs1-i,vs1-i+1));
    }

I think its more readable if you start from left to right with i=0 and using charAt() instead of substring.

[Saradus]

Code:

for(int i = 1; i <= vs1; i++){ vArray1[vMax-i] = Integer.parseInt(v1.substring(vs1-i,vs1-i+1)); }

I think its more readable if you start from left to right with i=0 and using charAt() instead of substring.

Hi, thanks for your reply. The reason I've created the value arrays from right to left is that basically I want to perform addition from right to left, thus I need to line values up on the right rather than the left. Hopefully I can explain better using an example.

If I want to add say 1924 and 421, the program would convert them to arrays from right to left. The two arrays would be 1,9,2,4 and 0,4,2,1. Then the arrays are added from right to left:

1 9 2 4
+ 0 4 2 1
2 3 4 5

The 1 is carried from the 9 and 4 column (stored as c) and added to the 1 and 0 column.

From this you can see its important the arrays are formed from right to left so that if one value is smaller than the other, the beginning indexes are automatically null so that the units, tens, hundreds etc line up.

If things were to be done left to right for this I would have the following:

1 9 2 4
+ 4 2 1 0

Which would of course give the wrong answer. Or I would have to construct if statements to determine the starting index for smaller values based on the difference between the larger and smaller value, which would probably be unneccesary additional code.

I can see your reasoning with charAt() though, I will play around with the code to implement that. Thanks!

[angryboy]

ic, thanks for clearing that up.

[Saradus]

I've looked into using charAt(), here's the conclusions I've drawn up:

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

I kept i at 1, because if I were to set it at 0, I would have to edit the vs1-i in charAt() to vs1-i+1 (as vs1-i when i is 0 would be vs1 and there is no array index at v1.length() because of indexes starting at 0). I believe this would be messier than having a 1 instead of a 0.

As you can see I had to convert the character to a string before parsing due to the fact that if you directly convert the char to int, you get the ASCII value of the digit (ie 1 would convert to 49, not 1), which screws up all the values not to mention creates an out of bounds exception!

Would you say that this new code snippet is more or less tidy/efficient? I'm unsure whether to go with this new one utilising charAt() or stick with the old code using substring. It probably doesn't matter a great deal, the difference between the two is a few characters, but here's both to compare:

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

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

While the charAt() has to utilise an extra method, substring requires two variables (one of which is pretty ugly (vs1-i+1)). So I'm torn between the two!

[Saradus]

I just found that the default delimiter for scanner is whitespace (I thought it was newline), so I've removed the delimiter statement.

[Saradus]

I think I will go with the charAt() method you recommended, it looks much tidier and easier to read. I hope the one I drafted above is suitable, it certainly works when tested! Thanks for the helpful comments!

[angryboy]

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

I will have to play around w/ this over the weekend before I can comment any further. Right now, I believe this is extremly resource hungry for large numbers because you are creating two arrays with the same size just to align the digits. So if you have a long number, say 64kb long, you will need to create two arrays of 64kb long.

[Saradus]

Code:

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

I will have to play around w/ this over the weekend before I can comment any further. Right now, I believe this is extremly resource hungry for large numbers because you are creating two arrays with the same size just to align the digits. So if you have a long number, say 64kb long, you will need to create two arrays of 64kb long.

Ah! Yes thats a much better idea, much neater! I see what you're saying about the array sizes, that's not something I'd considered and a very valid point! I'll have a look at my code and see if there's a way to solve this, thanks for your continued input!

[Saradus]

I have taken into consideration what you said about creating two same-size arrays.

Here's my revised code, which creates two different sized arrays (based on the size of the original value):

/**************************************************
  * 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.

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's certainly much better than the original code particularly if the values entered were a 50000 digit number and a 1 digit number!!

Look forward to hearing your feedback.

[angryboy]

for calculation, you are using two loops and one statment. You can actually shorten that to only one loop by checking for negative numbers (which mean array out of bounds here). for example:

if(vs1-i<0) 
  a = 0;
else 
  a = vArray1[vs1-i];

//and the same for b 
// then
int sum = a + b + c;
...

And I would suggest breaking it down to small manageable methods:
getInput()
add()
write()

edit:
also in the input, how do you plan to handle negative values?

[Saradus]

for calculation, you are using two loops and one statment. You can actually shorten that to only one loop by checking for negative numbers (which mean array out of bounds here). for example:

Code:

if(vs1-i<0) a = 0; else a = vArray1[vs1-i]; //and the same for b // then int sum = a + b + c; ...

And I would suggest breaking it down to small manageable methods:
getInput()
add()
write()

edit:
also in the input, how do you plan to handle negative values?

Yes perfect! This is much more elegant. Fantastic! As for breaking down into methods, I will be doing that but not until the subtraction program is completed, at which time I will link them in together and would then find it useful to clump into methods.

With that in mind, negative values will be handled by passing them over to the LongIntegerSubtract.java program and taking it from there. However, I haven't created that yet, hence why I have no code dealing with negative input yet.

Is that everything covered now? I think there's been significant improvement to this code thanks to your help and I really appreciate it!

[corlettk]

Saradus,

As angryboy has already stated, you're making a ubiqitious noob "mistake" by lumping everything together into one big "do everything" main method.

While this approach can be made to "work" for relatively simple problems, it has a number of deficiencies. First and foremost it's "hard". Huh? What? Well it's just a lot more complicated than it needs to be.

Pretend you asked: Why do you say that? To which I answer:

Glad you asked. Lumping everything into one method means you're dealing with all "concerns" together... meaning that if any of the underlying requirements changes you've got to basically "change the whole program".

A "concern" in this context means "anything which impacts the program"... basically the concerns are the sum of the requirements and the known limitations. Basically: The more "concerns" you have when implementing any particular piece of functionality, the deeper the pool, the higher the risk of drowning (i.e. not producing an adequate product).

The "best practice" approach is to try to break-down the problem into it's component parts, and implement each part as-independantly-as-possible. It's called reducing coupling.

For instance what if I asked you to change your program to give me the option to print the result of the addition to stdout (i.e. System.out) instead of to file? You'd have to make significant changes to your main method, which carries an inherest risk of breaking existing working functionality (i.e. introducing a "regression bug")... But if the "print" functionality was in it's own method, which presents a "well-defined minimal interface" to the rest of the application, then you'd just have to change the "print" method... with basically zero risk of breaking the existing working "add" functionality.

Oh, and I want you to also give me the option to input my number on the command line, so I can use your program more easily from a script. You're rewriting than "whole program" again... Get the point?

The key concept here is "managing complexity". You try to carve up the problem into small "do-able" pieces, and implement them independantly from one-another. This isn't a big issue when you're dealing with relatively simple programs which address relatively simple problems, but as the complexity of the problem ramps up, the more important it is that you design a solution... in fact, clarity and simplicity of the design becomes n^2 important. Human beings will never be smart enough to implement MS-Word in one big main method... so we simply don't try.

So... I second Angry's suggestion to seperate the input phase of the program, from the processing, from the output... this is a really really common (and useful) way to divy-up just about every problem into more-bight-sized chunks.

HTH... and yes I do tend to prattle on... but this is important stuff ;-)

Cheers. Keith.