Bruteforce integer multiplication in Java

Question

Intro

This time, I have attempted to prove the following bruteforce multiplication formula: $$ (a_n \cdots a_0) \cdot (b_m \cdots b_0) = \sum_{i = 0}^n \sum_{j = 0}^m a_i b_j \cdot 10^{i + j}, $$ where \$a_n, \ldots, a_0, b_m, \ldots, b_0 \in \{ 0, 1, \ldots, 9\}\$ are decimal digits.

Code

com.github.coderodde.research.multiply.BruteForceMultiply.java:

package com.github.coderodde.research.multiply;
import java.util.Scanner;
/**
 * This class provides the method for doing brute-force integer multiplication.
 */
public final class BruteForceMultiply {
 /**
 * This method performs the brute-force integer operation for non-negative
 * long integers.
 * 
 * @param number1 the first number.
 * @param number2 the second number.
 * @return the product of {@code number1} and {@code number2}.
 */
 public static long multiply(final long number1, final long number2) {
 checkNotNegative(number1);
 checkNotNegative(number2);
 
 final String number1String = Long.toString(number1);
 final String number2String = Long.toString(number2);
 
 final long[] a = convertLongStringToDecimalDigitArray(number1String);
 final long[] b = convertLongStringToDecimalDigitArray(number2String);
 
 long product = 0L;
 
 for (int i = 0; i < a.length; i++) {
 for (int j = 0; j < b.length; j++) {
 product += a[i] * b[j] * myPow(10, i + j);
 }
 }
 
 return product;
 }
 
 public static void main(String[] args) {
 final Scanner scanner = new Scanner(System.in);
 
 while (true) {
 System.out.print(">>> ");
 final long a = scanner.nextLong();
 final long b = scanner.nextLong();
 System.out.println(multiply(a, b));
 }
 }
 
 private static void checkNotNegative(final long number) {
 if (number < 0) {
 final String exceptionMessage = 
 String.format("number(%d) < 0", number);
 
 throw new IllegalArgumentException(exceptionMessage);
 }
 }
 
 private static long[] convertLongStringToDecimalDigitArray(
 final String numberString) {
 final long[] digitArray = new long[numberString.length()];
 
 for (int i = 0; i < digitArray.length; i++) {
 digitArray[i] = numberString.charAt(digitArray.length - 1 - i)
 - '0';
 }
 
 return digitArray;
 }
 
 private static long myPow(final long base, final long exponent) {
 long p = 1L;
 
 for (int i = 0; i < exponent; i++) {
 p *= base;
 }
 
 return p;
 }
}

com.github.coderodde.research.multiply.BruteForceMultiplyTest.java:

package com.github.coderodde.research.multiply;
import org.junit.Test;
import static org.junit.Assert.*;
public final class BruteForceMultiplyTest {
 
 @Test
 public void bruteforceTest() {
 for (long a = 0L; a < 1000L; a++) {
 for (long b = 0L; b < 1000L; b++) {
 assertEquals(a * b, 
 BruteForceMultiply.multiply(a, b));
 }
 }
 }
}

Critique request

Please, as always, give me any critique regarding any aspect of my code.

• user272752: Check the sizes of the variables used in myPow()... Does int == long in Java???
• coderodde: @Fe2O3 Oops. My bad.
• user555045: That formula can be generalized to other bases and some things that aren't even numbers such as polynomials (arguably a number expressed in positional notation is a particular kind of polynomial too), but it's well known
• Basilevs: What about integer overflow? Why is the upper limit so low?

Answer 1

I get a feeling that you're doing this string conversion just to get the number of digits in the input:

 final String number1String = Long.toString(number1);
 final long[] a = convertLongStringToDecimalDigitArray(number1String);

It seems a bit confusing. You can get the length of a number using (int) (Math.log10(number) + 1) as long as you add a special case for 0. But then again you could replace the whole conversion part with series of divisions and modulo 10s.

public static long multiply(final long number1, final long number2) {
 long product = 0L;
 int i = 0;
 long a = number1;
 while (a > 0) {
 int j = 0;
 long b = number2;
 while (b > 0) {
 product += (a % 10) * (b % 10) * myPow(10, i + j);
 b /= 10;
 j++;
 }
 a /= 10;
 i++;
 }
 return product;
}

Pardon me, I did not test that at all.

Personally I am not a fan of having a this many single character variables but I suppose the context in which they are used is so short that you don't lose track of what each of them means.

This class JavaDoc seems a bit forced, given the class name. You probably should explain what the brute force means in this case. Starting the comments with "This class" and "This method" is unnecessary.

/**
 * This class provides the method for doing brute-force integer multiplication.
 */
public final class BruteForceMultiply {

• coderodde: Nice one! However, I took a look at Long.toString: it seems to do more or less the same what I did.
• TorbenPutkonen: @coderodde It does work just fine, especially for code of this purpose, but why not just have a convertToDigitArray(long) method and hide the implementation details there?
• Kelly Bundy: For 999999999999999, which has 15 digits, your log10 suggestion says 16.

Answer 2

You can avoid the repeated calls to myPow if you store the result in an array.

final long[] c = new int[a.length + b.length - 1];
 c[i+j] = a[i] * b[j];
long multiplier = 1;
for (long multiplicand : c) {
 product += multiplicand * multiplier;
 multiplier *= 10;
}

This does one more multiplication than the greatest call to myPow but replaces all the calls.

It's trickier, but you could probably do the same thing without the array.

• Basilevs: A popular library has void Preconditions.checkArgument() method
• Thomas Hirsch: There is also check in Kotlin.