I'm trying to create a function that reads two positive natural numbers from an input file and, once calculated, writes their product in an output file.
The numbers are "big numbers", they can not be stored in a variable such as int or long so I want to store their digits in an array.
I wrote the following code that seems to work with some numbers but fails when I insert for example
55545252575453525348514954525256515056485755545157575748525349575251565256515554545052494854495550525752505756 * 50485456554954525356575657575048555450535257534951545354504957495454525448485751565254525155515656575655535754
that should be
2804227435732034912849259183651914853320425721942955023578511952364152651715628400479161029284275992691222252865738869930419556645027062168262691246978645407150215825953157986304093759319409280056139599351010978148800024
I get
2804227435732034912838248072540803742208304509820742801356289729131829419382295067135726685849922558246677798320394335486985213210683628834929357923746322174827983613731945865091982648208298268945129498351010978148800024
This is the code:
public static void multiplication(String inFileName, String outFileName) {
int[] a, b, res; //a is the first number, b is the second number, res is the final result
int a_i, b_i; //indexes to navigate inside the numbers
a = readBigNumber(inFileName, 0); //This works
if(a == null) return;
System.out.print("*** a: "); printIntArray(a); System.out.println(""); //DEBUG
b = readBigNumber(inFileName, 1); //This works
if(b == null) return;
System.out.print("*** b: "); printIntArray(b); System.out.println(""); //DEBUG
res = new int[a.length + b.length + 1]; //The result cannot be longer than this
Arrays.fill(res, 0); //Fill the array with zeros
//if the length of a < length of b, swap
int[] tempArr;
if (a.length < b.length) {
tempArr = new int[a.length];
System.arraycopy(a, 0, tempArr, 0, a.length);
a = new int[b.length];
System.arraycopy(b, 0, a, 0, b.length);
b = new int[tempArr.length];
System.arraycopy(tempArr, 0, b, 0, tempArr.length);
}
//this algorithm works like the "manual" column multiplication
int temp;
int res_i = 0; //index to navigate in the res array
int carry = 0;
for(b_i = b.length-1; b_i >= 0; b_i--) {
for(a_i = a.length-1; a_i >= 0; a_i--) {
temp = a[a_i] * b[b_i] + carry; //save the product in a temp variable
res_i = res.length - 1 - (a.length - 1 - a_i) - (b.length - 1 - b_i); //calculate the index in the res array
//I need to have just one digit [0-9]
if(temp > 9) { //If temp has more than one digit, take the right-one and put the left-one in the carry
res[res_i] += temp % 10; //right-digit
carry = (temp / 10) % 10; //left-digit
} else {
res[res_i] += temp;
carry = 0;
}
}
//when I exit the a-loop, if the carry is not 0, I have to put it in the result before continuing
if(carry > 0) {
res[res_i - 1] += carry;
carry = 0;
}
}
//Once completed, each array cell could have more than one digit.
//Check it right to left and if so, keep the right-digit e sum the left-digit in the left cell
for(int i = res.length-1; i >= 0; i--) {
if(res[i] > 9) {
res[i - 1] += (res[i] / 10) % 10; //left-digit
res[i] = res[i] % 10; //right-digit
}
}
//Write the final result
String res_str = "";
int start_i = 0;
while(start_i < res.length && res[start_i] == 0) start_i++; //Ignore initial zeros
if(start_i == res.length) {
writeBigNumber(outFileName, "0"); //I checked the whole array, the product is 0
} else {
for(int i = start_i; i < res.length; i++) {
res_str += String.valueOf(res[i]);
}
writeBigNumber(outFileName, res_str);
}
System.out.println("*** res: " + res_str); //DEBUG
}
These are some "helper functions":
//This works
private static int[] readBigNumber(String inFileName, int lineIndex) {
File inputFile = new File(inFileName);
Scanner scan = null;
int i = 0;
int[] num;
char[] rawInput;
try {
scan = new Scanner(inputFile);
while(scan.hasNextLine()) {
rawInput = scan.nextLine().toCharArray();
if(i == lineIndex) {
num = new int[rawInput.length];
for(int j = 0; j < num.length; j++) {
num[j] = rawInput[j] - '0';
}
scan.close();
return num;
}
i++;
}
} catch (Exception e) {
System.out.println("An error occurred while reading the numbers from file: ");
e.printStackTrace();
} finally {
if(scan != null)
scan.close();
}
return null;
}
private static void writeBigNumber(String outFileName, String num) {
try {
File outputFile = new File(outFileName);
FileWriter writer = new FileWriter(outputFile, false);
writer.write(num);
writer.close();
} catch (Exception e) {
System.out.println("An error occurred while writing the result: ");
e.printStackTrace();
}
}
I know that there are many other algorithms that do the same thing and are a lot better than mine, but I want to understand why this doesn't always work. Thanks in advance.
Your bug is in the part where you are doing the final carry-over from cells that have numbers with more than one digit in them:
if(res[i] > 9) {
res[i - 1] += (res[i] / 10) % 10; //left-digit
res[i] = res[i] % 10; //right-digit
}
Here you are assuming that res[i] has at most two digits (isn’t greater than 99). The assumption is not sound. I tried multiplying 99 999 999 999 (eleven digits) with itself using your program, and res[12] contained 100 at this point. So (res[i] / 10) % 10 evaluates to 0 and you are not carrying anything over to res[11] or res[10] as you should.
I suppose I should leave it to yourself to find a good fix.
Edit: For the readability, this is your own fix from your comment, formatted and indented:
for (int i = res.length - 1; i >= 0; i--) {
if (res[i] > 9) {
if (res[i] > 99) {
res[i - 1] += ((res[i] / 100) % 10) * 10; // first digit (*10)
res[i - 1] += (res[i] / 10) % 10; // second digit
} else {
res[i - 1] += (res[i] / 10) % 10; // left-digit
}
res[i] = res[i] % 10; // right-digit
}
}