multiplying bigintegers without bigintegers

Question

Hey' all so im figuring out how to multiply bigintegers without importing them and I have it almost all. The only thing that isnt working is when multiplying with -digit the output is still +. any help appreciated. ie. -20*4=80

    Scanner scan = new Scanner(System.in);
    System.out.println("Type the first number:");
    String x = scan.nextLine();
    
    System.out.println("Type the second number:");
    String y = scan.nextLine();

    if (x.charAt(0) == '-' && y.charAt(0) != '-') {
        x = x.substring(1);
    }
    else if (x.charAt(0) != '-' && y.charAt(0) == '-') {
        y = y.substring(1);
    }
    else if (x.charAt(0) == '-' && y.charAt(0) == '-') {
        x = x.substring(1);
        y = y.substring(1);
    }
    
    String s1 = new StringBuffer(x).reverse().toString();
    String s2 = new StringBuffer(y).reverse().toString();
    
    int[] m = new int[s1.length() + s2.length()];
    
    for (int i=0; i<s1.length(); i++) {
        for (int j=0; j<s2.length(); j++) {
            m[i+j] = m[i+j] + (s1.charAt(i) - '0') * (s2.charAt(j) - '0');
        }           
    }
    
    String product = new String();
    
    for (int i=0; i<m.length; i++) {
        int digit = m[i] % 10;
        int carry = m[i] / 10;
        if (i+1 < m.length) {
            m[i+1] = m[i+1] + carry;
        }
        product = digit + product;
    }
    
    while (product.length() > 1 && product.charAt(0) == '0') {
        product = product.substring(1);
    }
    
    if (x.charAt(0) == '-' && y.charAt(0) != '-') {
        product = new StringBuffer(product).insert(0, '-').toString();
    }
    else if (x.charAt(0) != '-' && y.charAt(0) == '-') {
        product = new StringBuffer(product).insert(0, '-').toString();
    }
    else if (x.charAt(0) == '-' && y.charAt(0) == '-') {
        product = product;
    }
    System.out.println("The multiplication of\n" + x + " \nand\n" + y + " " + "\nis\n" + product);
    
    scan.close();
}

}

Answer 1

just speaking in a generic concept sense - the square root of largest safe unsigned int,

4^3^3/2-1

is approx 94906265.6242. So right off the bat you know you don't have 8-full decimal digits width to work with unless you add in special tricks.

All those fancy algorithms they talk about - they frequently waste your time by having to first convert from decimal to binary, do the math, then re-convert it back out.

I just split mine into chunks of 7-digits wide, so the the maximum multiply result per op is capped at just shy of 10^14

 - for 7 9's squaring each other, approx. 46.50699304-binary bits 
 - for 8 9's squaring ……….     is approx. 53.15084949 bits

for whatever slowness one might believe in simpleton grade school multiply, you more than gain back the savings by avoiding a bidirectional base-conversion.

Answer 2

Just remove the symbols from the numbers and save them. Then later, use them to determine if a negative is required. An exclusive or test for - is all that is necessary for a negative result.

You can create a record (or a class) to return the numbers and resulting sign, ready for processing.

record Numb(String sign,String num1, String num2) {}

String n1 = "-2123";
String n2 = "+2343";
Numb n = prepNums(n1,n2);
System.out.println(n.sign + ", " + n.num1 +  " " + n.num);

Prints

-, 2123, 2343

After multiplying, just prepend the sign to the result. Note that the default positive sign is no sign.

And here is the method that processes the strings and returns them and the resultant sign for multiplication.

public static Numb prepNums(String n1, String n2) {
    
    boolean sign1 = false;
    boolean sign2 = false;
    char firstChar = n1.charAt(0);
    if (!Character.isDigit(firstChar)) {
        sign1 = firstChar == '-';
        n1 = n1.substring(1); // remove sign
    }
    firstChar = n2.charAt(0);
    if (!Character.isDigit(firstChar)) {
        sign2 = firstChar == '-';
        n2 = n2.substring(1); // remove sign
    }
    
    return new Numb( (sign1 ^ sign2) ? "-" : "", n1, n2);
    
}

Answer 3

You're removing the negative symbol from the numbers here:

if (x.charAt(0) == '-' && y.charAt(0) != '-') {
    x = x.substring(1);
}
else if (x.charAt(0) != '-' && y.charAt(0) == '-') {
    y = y.substring(1);
}

So after those lines your x and y variables no longer contain the negative symbol.

So when you're checking it near the end here:

if (x.charAt(0) == '-' && y.charAt(0) != '-') {
    product = new StringBuffer(product).insert(0, '-').toString();
}
else if (x.charAt(0) != '-' && y.charAt(0) == '-') {
    product = new StringBuffer(product).insert(0, '-').toString();
}
else if (x.charAt(0) == '-' && y.charAt(0) == '-') {
    product = product;
}

It will never get into any of the conditions.

One good way to debug this on your end is to set a breakpoint within the condition you think it should drop into and see if it's hit. Or breakpoint before the conditions and examine the variables to ensure they are what you expect them to be. You could also throw some println statements in there temporarily just to say "I got into this conditional".

The adjustment I'd recommend making is holding onto whether each number was negative before stripping the negative so you can use that in your logic later on.

Here's the adjustment which should accomplish what you want. I used Integers instead of bools to make the check for whether to apply the negative symbol later easier (i.e. isFirstNumberNegative + isSecondNumberNegative == 1)

    Scanner scan = new Scanner(System.in);
    System.out.println("Type the first number:");
    String x = scan.nextLine();

    System.out.println("Type the second number:");
    String y = scan.nextLine();

    // hold onto which numbers are negative
    Integer isFirstNumberNegative = x.charAt(0) == '-' ? 1 : 0;
    Integer isSecondNumberNegative = y.charAt(0) == '-' ? 1 : 0;

    // strip the negative symbols from the numbers which are negative
    if (isFirstNumberNegative > 0) {
        x = x.substring(1);
    }
    if (isSecondNumberNegative > 0) {
        y = y.substring(1);
    }

    String s1 = new StringBuffer(x).reverse().toString();
    String s2 = new StringBuffer(y).reverse().toString();

    int[] m = new int[s1.length() + s2.length()];

    for (int i=0; i<s1.length(); i++) {
        for (int j=0; j<s2.length(); j++) {
            m[i+j] = m[i+j] + (s1.charAt(i) - '0') * (s2.charAt(j) - '0');
        }
    }

    String product = new String();

    for (int i=0; i<m.length; i++) {
        int digit = m[i] % 10;
        int carry = m[i] / 10;
        if (i+1 < m.length) {
            m[i+1] = m[i+1] + carry;
        }
        product = digit + product;
    }

    while (product.length() > 1 && product.charAt(0) == '0') {
        product = product.substring(1);
    }

    // if only one number is negative put a negative symbol in front
    // if both numbers are negative this condition won't hold true because it will be == 2
    // if both numbers are positive this condition won't hold true because it wil be == 0
    if (isFirstNumberNegative + isSecondNumberNegative == 1) {
        product = new StringBuffer(product).insert(0, '-').toString();
    }
    System.out.println("The multiplication of\n" + x + " \nand\n" + y + " " + "\nis\n" + product);

    scan.close();