CODEWITHSUNDEEP
java
xtheosirian
xtheosirian

Reputation: 298

Multiplying a numeric string in java

I'm a beginner in programming and I've been doing the Project Euler programming problems to practice, I've been able to make my way so far, but this time I had to ask for help. Without spoilers, the problem I'm trying to solve consists of finding the sum of the digits of a very large number, so I can't hold it in an int or a double. So I made this method to multiply two strings containing a numeric value.

    private static String multiply(String a, String b) {

    // No, I'm not checking if the strings are numeric

    int subTotal = 1, extra = 0;

    String waitingString = "";
    StringBuilder number1 = new StringBuilder(a);
    StringBuilder number2 = new StringBuilder(b);
    List<String> numbers = new ArrayList<String>();
    // The reason I reverse the numbers is the for() loops
    // I don't want to count down through the numbers, that
    // would just confuse me more.
    number1.reverse();
    number2.reverse();

    for (int i = 0; i < number1.length(); i++) {

        waitingString = "";
        subTotal = Character.getNumericValue(number1.charAt(i));

        for (int j = 0; j < number2.length(); j++) {

            subTotal *= Character.getNumericValue(number2.charAt(j));
            subTotal += extra;

            char[] temp = String.valueOf(subTotal).toCharArray();
            waitingString = temp[temp.length - 1] + waitingString;

            if (subTotal >= 10 || ((j == number2.length() - 1) && (String.valueOf(subTotal).length() > 1))) {

                extra = Integer.parseInt(String.valueOf(subTotal).substring(0, temp.length - 1));

            } else {

                extra = 0;

            }

            subTotal = Character.getNumericValue(number1.charAt(i));

        }

        for (int k = 0; k < i; k++) {
            waitingString += "0";
        }

        waitingString = extra + "" + waitingString;

        numbers.add(waitingString);

    }

    // sumAll() is not the problem just in case you were wondering.
    // Because as you've read the code, I'm passing a List<String>
    // to it and as I was trying to find the error I printed the list
    // before everything to check the values and the error was already
    // there, 3 of the values are wrong.
    return sumAll(numbers);
}

When testing I'm multiplying this number by itself: 1125899906842624. The result should be 1267650600228229401496703205376. But I'm getting 1267650600228229401607703205376. That's a difference of 111000000000. I've been trying to find the error for 2 days and i just can't. I'm not looking for alternative or better ways to do this, I just can't find the error in my code that adds more than it should. If you need to see the rest of the code I can provide it and please don't mind spelling/grammar errors, english is not my native language.

Upvotes: 2

Views: 4375

Answers (3)

ajb
ajb

Reputation: 31689

Without trying to run this or look at it under a debugger: it looks like you're setting up an extra variable which is a carry, i.e. the value which should get added to the next product as you move to the left (in your original numbers, not the reversed ones). One problem I can see is that if the last product in your inner loop produces something greater than or equal to 10, you compute extra; but then when you go the next outer loop, extra still has that value and gets added to subTotal when it shouldn't be. Try adding the statement extra = 0; at the beginning of your outer loop, and before the inner loop starts. That may fix the problem.

P.S. You're making a lot of extra work for yourself by representing the subTotal as a string and working with it. While I understand why you'd want to use strings for the two multiplicands and the product, subTotal is the product of two single digits with a carry added, and it can never be greater than 89. So you should never have to convert it to a string and work with the string. Thus, instead of 

char[] temp = String.valueOf(subTotal).toCharArray();
waitingString = temp[temp.length - 1] + waitingString;

you could say

waitingString = String.valueOf(subTotal % 10) + waitingString;

or something similar (subTotal % 10 gives the remainder when subTotal is divided by 10, and is therefore the last digit of subTotal); and instead of the complex code to compute extra, just say

extra = subTotal / 10;

which divides by 10 and throws away the remainder. You shouldn't be computing String.valueOf(subTotal) at all.

PPS. Don't worry about the answers that tell you to use BigInteger. If you were doing a real programming project, that's what you'd use. But for someone learning how to program, I think that writing a program to compute the product of two numbers, the long way, is a good learning tool.

Upvotes: 4

Epiglottal Axolotl
Epiglottal Axolotl

Reputation: 1048

As someone commented, this would probably be a job for the BigInteger class. Just say 

BigInteger intA = new BigInteger(a)
BigInteger intB = new BigInteger(b)

and then call 

intA.multiply(intB)

and that will get you a BigInteger containing the result.

Upvotes: 1

Elliott Frisch
Elliott Frisch

Reputation: 201437

I would use BigInteger like this

private static String multiply(String a, String b) {
  if (a == null || b == null) {
    if (b != null) return b;
    return a;
  }
  BigInteger v = new BigInteger(a, 10);
  if (v != null) {
    BigInteger t = new BigInteger(b, 10);
    if (t != null) {
      BigInteger r = v.multiply(t);
      return r.toString();
    }
  }

  return "";
}

public static void main(String[] args) {
  String result = multiply("1125899906842624", "1125899906842624");
  String good = "1267650600228229401496703205376";
  System.out.println(result.equals(good));
}

Which prints true when I run it.

Upvotes: 0

Related Questions