Suggestions

Hexus0

Gawd
Joined
Feb 28, 2005
Messages
590
Hey everyone, I've been working on an assignment for the past couple of days and while it is due tomorrow, I am very close to completing :D. While the assignment WAS due today, and I did have a method for the one I am stuck one, my professor had informed me half an hour before the assignment was due that he didn't want me to go about my method the way I had it, and had offered the class a day extension because everyone seemed to be stuck.

I've worked for the better part of the night on re-writing the multiplication method for this class and while it almost works I have found 2 pitfalls.
1. Multiplying two "BigInts" such as 2 x 40 will not yield 80, but 0, while 40 x 2 will yield 80. I've realized this is due to the size in the nested loop within multiply that increases the size of result, so when the number 2 enters to multiply 40, it will only increment size to 1 (rather then 2).
2. Multiplying two numbers such as 987 and 65 will yield 63,155 when the answer is 64,155. I haven't exactly narrowed this problem, but I think it has to do with the carry.

I'm not exactly asking for any specific coding changes, but I can't come up with anymore ideas, so any suggestions will be taking into mind.

The class:
Code:
import java.lang.Math;

class BigInt {
	private int digit[]; // represent the integer as an array of digits
	private int size; // number of digits in the integer
	private final int max = 50; // maximum number of digits in the integer
	
	public BigInt() { // default constructor
		digit = new int[max];
		digit[0] = 0;
		size = 1;
	}
	public BigInt(String num) { // constructor with initial String value
		size = num.length();
		digit = new int[max];
		for (int ct = size - 1; ct >= 0; ct --) {
			digit[ct] = Integer.parseInt(num.substring(size - ct - 1, size - ct));
		}
	}
	
	public BigInt(int num) { // constructor with initial integer value
		digit = new int[max];
		int i = 0;
		size = 0;
		do {
			digit[i] = num % 10;
			num = num / 10;
			i++;
			size++;
		}while(num > 0);
		
	}
	
	public BigInt(BigInt num) {
		int i = 0;
		this.size = num.size;
		digit = new int[max];
		for(i = 0; i < num.size; i++) {
			this.digit[i] = num.digit[i];
		}
	}

	public String toString() { // override Objectís version
		String intString = "";
		for (int ct = size - 1; ct >= 0; ct --) {
			intString = intString + String.valueOf(digit[ct]);
		}
		return intString;
	}
	
	public int compareTo(BigInt other) { 
		int compare = 0; //variable to store the return value after both objects are compared
		
		if(this.size > other.getSize()) { // return 1 if this greater than other
			compare = 1;
		}else if(this.size < other.getSize()) { // return -1 if this is less than other
			compare = -1;
		}else if(this.size == other.getSize()) { // return 0 if both are equal
			//int i = size-1;
			int cnt = 0;
			int othercnt = 0;
			for(int i = size-1; i >= 0; i--) {
				if(this.digit[i] > other.digit[i]) {
					cnt++;
				}
				else if(this.digit[i] < other.digit[i]) {
					othercnt++;
				}
			}
					
			if(cnt > othercnt)
					compare = 1;
			else if (cnt < othercnt)
					compare = -1;
			else
					compare = 0;
		}
		
		return compare;
	}
	/* [0][5][2]
		[5][5][3]	 
	*/

	public BigInt plus(BigInt arg) { // add two BigIntís
		BigInt sum = new BigInt();
		int carry = 0;
		if(this.size > arg.getSize()) {
			sum.size = this.size;
			for(int i = 0; i < this.size; i++) {
				sum.digit[i] = ((this.digit[i] + arg.digit[i] + carry) % 10); //take out the smaller digit of the two
				carry = (this.digit[i] + arg.digit[i] + carry) / 10; //carry overthe extra
				//System.out.println("carry " +  carry);
			}
		} else if(this.size < arg.getSize()) {
			sum.size = arg.size;
			for(int i = 0; i < arg.size; i++) {
				sum.digit[i] = ((this.digit[i] + arg.digit[i] + carry) % 10); //take out the smaller digit of the two
				carry = (this.digit[i] + arg.digit[i] + carry) / 10; //carry overthe extra
				//System.out.println("carry " +  carry);
			}
		} else { //if(this.size == arg.getSize()) {
			sum.size = this.size;
			for(int i = 0; i < this.size; i++) {
				sum.digit[i] = (this.digit[i] + arg.digit[i] + carry) % 10;
				carry = (this.digit[i] + arg.digit[i]) / 10;
				//System.out.println("carry " +  carry);
				//System.out.println(sum.size);
			}
		}
		if(carry > 0) {
			//sum.size++;
			sum.digit[sum.size] = carry;
			sum.size++;
		}
		return sum;
	}
	
	public BigInt times(BigInt other) { //multiply two BigInts
		BigInt result = new BigInt();
		BigInt product = new BigInt();
	//	product.size = 0;
		int carry = 0;
		//if(this.size > other.size) {
			result.size = 0; //set size of the result to 0, original would be set to 1
			for(int i = 0; i < other.size; i++) {
				carry = 0; //make sure the carry is 0 before it enters the loop for the second iteration
				if(i > 0) {
					for(int k = 0; k <= i; k++) 
						result.digit[i-k] = 0;
				}
				for(int j = 0; j < this.size; j++) {
					if(i == 0) { //only increments size the first time through the iteration of the loop
						result.size++;
						System.out.println("size " + result.size); 
					}
					if(i > 0) {
						result.digit[i+j] = ((other.digit[i] * this.digit[j]) + carry) % 10; //mulitply operation
						carry = (other.digit[i] * this.digit[j]) / 10; // carry for the digits
					} else { 
						result.digit[j] = ((other.digit[i] * this.digit[j]) + carry) % 10; //mulitply operation
						carry = (other.digit[i] * this.digit[j]) / 10; // carry for the digits
					}
					if(j == this.size-1 && carry > 0) { //if a carry remains and all the mulitplication has been done
						result.digit[result.size] = carry; //set the last digit to the carry
						result.size++;
					} 
				}
				for(int j = result.size; j >= 0; j--) {
					System.out.print(result.digit[j]);
				}
				System.out.println();
				product = product.plus(result);
			}
	//	}
	//	product = product.plus(result);
		return product;
	}
	public int getSize() {
		return this.size;
	}

}

The driver:
Code:
import java.io.*;    // for BufferedReader

public class BigIntSimpleTest {

   public static void main(String[] args) throws IOException {
      BigInt num, num1, num2 = new BigInt("1");
      BigInt zero = new BigInt();
	   BufferedReader stdin = new BufferedReader(
		new InputStreamReader(System.in));
		//System.out.println(10 % 10);
      System.out.println("First BigInt: " + new BigInt(234));
      System.out.println("Next BigInt: " + new BigInt("5678"));
		while (num2.compareTo(zero) != 0) {
         System.out.print("A big integer: ");
         num = new BigInt(stdin.readLine());
         System.out.println(num);
         System.out.print("Another big integer: ");
         num1 = new BigInt(stdin.readLine());
         System.out.println(num1);
         if (num.compareTo(num1) == 1) {
            System.out.println(num + " is bigger.");
         }
         else if (num.compareTo(num1) == -1) {
            System.out.println(num1 + " is bigger.");
         }
         else {
            System.out.println(" They are both " + num);
         }
       	num2 = num1.plus(num);
         System.out.println("The sum is:  " + num2);   
		   num2 = num.times(num1);
         System.out.println("The product is: " + num2);
      }
   }
}

Thanks for all the help!
 
didnt test

Code:
public BigInt times(BigInt other) { //multiply two BigInts
		BigInt result = new BigInt();

    for (int i = 0; i < other.size; i ++)
    {
         int digit = other.digit[other.size - i - 1];
         BigInt a = new BigInt();
         int shift = i; // the shift only works if the digit array is initialized to 0 and if the digit array is more than big enough!
         for (int j = 0; j < this.size; j++)
         {
               a.digit[j+shift] = this.digit[j]*digit;
         }

        // carry over bigger digits
        int j = 0;
         while (1)
         {
             if (a.digit[a.size - j] > 9)
             {
                     int temp = a.digit[a.size-j] - 10;
                     a.digit[a.size-j] -= temp;
                     a.digit[a.size-j-1] += temp;
             }
             else if (j > a.size -1) //it is implied that [a.size-j] is under 10
                     break;
             j++;
         }

         result.add(a);
    }

    return result;

	}
 
Do you have to implement the methods in a specific way?

An easy way to think of multiplication is as a series of additions, e.g. 4 x 3 is 4 added to 4 twice (4 + 4 + 4). Since I assume you have already implemented the method for adding correctly, most of the work is done.

You need two methods - one to convert a BigInt back to simple integer, lets call it X. The second method times, simply adds the implicit parameter (this) to itself X times. Your add method produces a BigInt; so, after all of the additions you should have what you want.
 
Back
Top