private static String gradeSchoolMult(int[] multX, int[] multY){ // the size of the result is at most going to be the size of X and Y int[] result = new int[multX.length + multY.length]; // this is where the algorithm really starts; the previous lines were "pre-computation" // fix y (the second multiplier) on a single digit, multiply it through for each digit in x startTime = System.currentTimeMillis(); for (int i = 0; i < multY.length; i++) { for (int j = 0; j < multX.length; j++){ result[i + j] += multY[i]*multX[j]; } } private static int[] carryCorrect(int[] toCorrect) { // we're starting at 1 because the first digit will never need correction for (int i = 1; i < toCorrect.length; i++){ // affecting i+1 is normally dangerous as it can lead to an index out of bounds exception // except here we know that most significant digit won't ever trigger these if-statements if (toCorrect[i] > 1) { // if the entry is an even number, we know that this should be a binary 0 if (toCorrect[i]%2 == 0) { toCorrect[i+1] += toCorrect[i]/2; // carry the total complete bits to the next column toCorrect[i] = 0; // otherwise the entry is an odd number, so } else { toCorrect[i+1] += (toCorrect[i] - 1)/2; // carry the total complete bits to the next column toCorrect[i] = 1; } } } return toCorrect; }