Array comparison and multiplication

Question

So the goal is to read in two huge integers and add, subtract, and multiply them together back into one 40 element long integer array while also comparing the initial two integers, equalTo, notEqualTo, etc. I have most of it complete but I am stuck on a couple points. My isGreaterThan method returns the opposite of what it should, for example: huge integer 1 = 100 and huge integer 2 = -100. The method will spit out false and say that huge integer 1 isLessThan huge integer 2. The next part I am stuck on is the multiplication. As of right now I can multiply integers together resulting in a new integer of no more than 11 elements. For some unknown reason to me, anything larger will result in a miscalculation. It was suggested to me to multiple for loops but I don't see how that will help. My final issue is whenever the result of any operation is equal to zero, for example 100 + (-100), my add/substract/multiply methods do not return 0. Below is my current code.

import java.util.Scanner;
import java.util.Arrays;

// Class that prompts the user to enter two HugeIntegers
// then compares those integers and performs addition, subtraction,
// and multiplication on those two HugeIntegers
public class HugeInteger {
    private static final int NUM_DIGITS = 40;
    private int digits[] = new int[NUM_DIGITS];
    private boolean positive;

    // Constructor
    public HugeInteger (String num){
        String parts [] = num.split(" ");
        digits = new int[parts.length];
        for(int n = 0; n < parts.length; n++) {
            digits[n] = Integer.parseInt(parts[n]);
        }
    }

    // Finds first non-zero position for first HugeInteger
    public int findFirstNonZeroPosition(){
        int position = NUM_DIGITS-1;
        for (int i = 0; i < digits.length; i++){
            if (digits[i] > 0){
                position = i;
                break;
            }
        }
        return position;
    }

    // Determines if h1 isEqualTo h2
    public boolean isEqualTo(HugeInteger hi){
        if(Arrays.equals(this.digits, hi.digits)){
            return true;
        }else {
            return false;
        }
    }

    // Determines if hi isGreaterThan h2
    public boolean isGreaterThan(HugeInteger hi){
        // different signs
        if (this.positive && (!hi.positive)){
            return true;
        }
        else if (!this.positive && hi.positive){
            return false;
        }

        // same sign
        else {

            // first number’s length is less than second number’s length
            if (findFirstNonZeroPosition() > hi.findFirstNonZeroPosition()) {
                if (positive)
                    return false;
                else
                    return true;
            }

            // first number’s length is larger than that of second number
            else if (findFirstNonZeroPosition() < hi.findFirstNonZeroPosition()) {
                if (positive)
                    return true;
                else
                    return false;
            }

            // two numbers have same length
            else {
                for (int i = 0; i < digits.length; i++ ) {
                    if ( this.digits[i] > hi.digits[i] )
                        if (positive)
                            return true;
                        else
                            return false;
                }
                if (positive)
                    return false;
                else
                    return true;
            }
        }
    }

    // Determines if h1 isNotEqualTo h2
    public boolean isNotEqualTo(HugeInteger hi){
        if(Arrays.equals(this.digits, hi.digits)){
            return false;
        }else {
            return true;
        }
    }

    // Determines if h1 isLessThan h2
    public boolean isLessThan(HugeInteger hi){
        return !(isGreaterThan(hi) || isEqualTo(hi) );
    }

    // Determines if h1 isGreaterThanOrEqualTo h2
    public boolean isGreaterThanOrEqualTo(HugeInteger hi){
        return !isLessThan(hi);
    }

    // Determines if h1 isLessThanOrEqualTo h2
    public boolean isLessThanOrEqualTo(HugeInteger hi){
        return !isGreaterThan(hi);
    }

    // instance variables are digits, NUM_DIGITS, positive
    // addArrayDigits and subtractArrayDigits
    // Determines how to add h1 and h2
    public void add(HugeInteger hi){
        if(positive!=hi.positive){
            if(this.positive){
                // "this" is positive, hi is negative
                hi.negate(); // negate hi temporarily

                if(this.isGreaterThan(hi)){
                    // |this| > |hi|
                    this.digits = subtractArrayDigits(this.digits, hi.digits);
                }else{
                    // |this| <= |hi|
                    this.digits = subtractArrayDigits(hi.digits, this.digits);
                    // negate the "this"
                    negate();
                }
                hi.negate(); // restore hi's sign
            }else{
                // "this" is negative, hi is positive

            }
        }else{
            // same sign :)
            digits = addArrayDigits(this.digits, hi.digits);
        }
    }

    // instance variables are digits, NUM_DIGITS, positive
    // addArrayDigits and subtractArrayDigits
    // Determines how to subtract h1 and h2
    public void subtract(HugeInteger hi){
        if(positive!=hi.positive){
            if(this.positive){
                // "this" is positive, hi is negative
                hi.negate(); // negate hi temporarily

                if(this.isGreaterThan(hi)){
                    // |this| > |hi|
                    this.digits = addArrayDigits(this.digits, hi.digits);
                }else{
                    // |this| <= |hi|
                    this.digits = addArrayDigits(hi.digits, this.digits);
                    // negate the "this"
                    negate();
                }
                hi.negate(); // restore hi's sign
            }else{
                // "this" is negative, hi is positive
            }
        }else{
            // same sign :)
            digits = subtractArrayDigits(this.digits, hi.digits);
        }
    }

    // Multiplies h1 and h2
    public void multiply(HugeInteger hi){
        for (int i = 0; i < digits.length; ++i) {
            digits[i] = this.digits[i] * hi.digits[i];
        }
    }

    // Flips the sign
    public void negate(){
        positive =! positive;
    }

    // Determines if an element is zero
    public boolean isZero(){
        for(int i = 0; i < digits.length; i++)
        if(digits[i]!= 0)
            return false;
        return true;
    }

    // Puts HugeInteger into a String in LSD format
    public String toString() {
        String str = "";
        int i;
        for(i = digits.length -1; i >= 0; i--) {
            if(digits[i] != 0)
            break;
        }
        for(int j = i; j >= 0; j--) {
            str = digits[j] + str;
        }
        return str;
    }

    // Subtracts h2 from h1
    private static int[] subtractArrayDigits(int[] array1, int[] array2){
        for (int i = 0; i < array1.length; ++i) {
            array1[i] = array1[i] - array2[i];
        }
        return array1;
    }

    // Adds h2 to h1
    private static int[] addArrayDigits(int[] array1, int[] array2){
        //int i = 0;
        for (int i = 0; i < array1.length; ++i) {
            array1[i] = array1[i] + array2[i];
        }
        return array1;
    }

    // Main method
    public static void main(String args[]){
        HugeInteger h1, h2;
        String num;
        Scanner scan=new Scanner(System.in);

        System.out.print("Please enter the first huge integer (h1): ");
        num=scan.nextLine();
        h1=new HugeInteger(num);

        System.out.print("Please enter the second huge integer (h2): ");
        num=scan.nextLine();
        h2=new HugeInteger(num);

        if(h1.isEqualTo(h2)){
            System.out.println("h1 is equal to h2.");
        }
        if(h1.isNotEqualTo(h2)){
            System.out.println("h1 is not equal to h2.");
        }
        if(h1.isGreaterThan(h2)){
            System.out.println("h1 is greater than h2.");
        }
        if(h1.isLessThan(h2)){
            System.out.println("h1 is less than to h2.");
        }
        if(h1.isGreaterThanOrEqualTo(h2)){
            System.out.println("h1 is greater than or equal to h2.");
        }
        if(h1.isLessThanOrEqualTo(h2)){
            System.out.println("h1 is less than or equal to h2.");
        }

        h1.add(h2);
        System.out.printf("h1 + h2 = %s\n",h1);
        h1.subtract(h2);
        h1.subtract(h2);
        System.out.printf("h1 - h2 = %s\n",h1);
        h1.add(h2);
        h1.multiply(h2);
        System.out.printf("h1 * h2 = %s\n",h1);
    }
}

Answer 1

Your code has numerous problems.

First and foremost, the internal form in which it represents Huge values is undocumented (other than by code analysis) and seems inconsistent. It appears to be some form of sign/magnitude, which is fine, but in which order do the digits appear? That's actually pretty crucial.

For most purposes, it would be simpler for the digit array to run from least-significant to most-significant, with the least-significant digit at index zero, but that's opposite from the way numbers are written (at least in English-language locales). It could also work to run from most-significant to least-significant, but in that case the only reasonable index for the least-significant digit is MAX_DIGITS - 1. From your constructor, I think you have digits running from most- to least-significant digit, with the least-significant digit at some random point in the middle of the digit array. I think you mean to do it the other way around, though.

Second, your constructor never sets the positive field. (In fact, it doesn't check for negative digits at all).

Third, your add() and subtract() methods should not modify their argument, even temporarily. It's very bad form, and unnecessary, unless the modification is part of the purpose of the method.

Fourth, with some sign combinations your add() and subtract() methods do nothing at all.

But you were really interested in why your arithmetic methods produce wrong results. Let me start there by saying that you absolutely cannot do arithmetic properly unless you know which digit is each Huge's least-significant. As to your actual algorithms, you should basically be implementing the same procedures that you use to do decimal arithmetic on paper. Very importantly, you must not neglect carrying from one digit place to the next (or borrowing from more-significant places in the case of subtraction) where necessary. Your code does not do that.

Note also that your arithmetic results may have a different number of non-zero digits than either operand. In particular, multiplication of an m-digit number by an n-digit number can produce up to an (n+m)-digit number. Addition may require one extra digit. Of course, subtraction may reduce the number of significant nonzero digits.