I need some Help with using Big Integers
I'm really new to Java and really don't have a clue how to solve this problem.
I need help for adding big integers together but I am really confused how to carry on numbers, for example
11112345
+23276467
In order to add 5 +7 = 12, I have to carry on the 1 and add it to 4.
So Far this is all that I have done.
publicclass BigInt
{
private String value;
public BigInt(String val)
{
value = val;
}
publicvoid display()
{
System.out.println(value);
}
public BigInt add(BigInt val)
{
BigInt result =new BigInt ("");
for(int i=0; i<value.length(); i++)
{
result.value = value.charAt(i) + result.value;
}
result.display();
return result;
}
Now I need to add any 2 big Integers ( No matter what their size is) together
I asked a lot of ppl how to do this but they told me to do it either in Vectors or in Arrays. I don't know any thing about Vectors and just basicly understand Arrays. I would rather do this in Arrays than in Vectors.
I would Appreciate any help that I can get. Thank You.>
[1809 byte] By [
aaf_87a] at [2007-11-26 16:22:45]
If you are really new at Java, you might be biting off more than you can chew with BigInt. Why are you doing this? Is it an assignment, or are you trying to solve a specific problem?
Actually yes it's an assignment. I don't really understand how to do this one. I managed to do my previous assignments but I am really stuck on this one. I really need help on this one.
I would suggest learning a bit about collections : http://java.sun.com/docs/books/tutorial/collections/index.htmlIn the end, using lists (Vectors are lists) will be simpler than working with arrays.
You're certain that you didn't misunderstand the assignment, and you weren't just supposed to use java.math.BigInteger?
My Professor told me not to use java.math.BigInteger at all. If I could ,that would have been way easier for me.
could someone at least give me an idea how to do this assignment, I'm not adding for someone to do it for me, instead all I'm asking is that if someone could at least start me off with what I should do here. Please.............
For a start, storing the value as a String makes calculations harder. An array of bytes or ints, or maybe a BitSet would be better. But then again that might be contrary to the specifications you've been given. Are there any such restrictions?
There is no restriction on how to do this assignment. Could you explain to me as to how to use bytes or maybe ints? If I could at least be started on this, that would be really helpful. Thank You.
Ok, so you have an array of bytes that stores the value. You can think of each byte as one digit in the number, except each digit can be 0-255 instead of the usual 0-9 in decimal or 0-1 in binary. You can perform arithmetic on these digits just like you would any other number.
It's probably simpler to store the bytes in ints, to avoid sign issues. For example to add two bytes:
int a = 100;
int b = 200;
int result = a + b;
int carry = result >> 8;
result &= 0xFF;
System.out.println(result);
System.out.println(carry);
a + b is bigger than one byte, so the result overflows into the ninth bit. Shifting this left by 8 will give you what you would have to carry over to the next step (either 1 or 0). ANDing the result with 0xFF (eight 1s in binary) masks off the overflow, leaving just one byte.
The answer is 44 in the "units" place and 1 in the "256s" place, or (44 * 256^0) + (1 * 256^1) = 300
You can just keep doing that for as many bytes as you have in the array.
I hope that's clear. There are many possible ways of doing this, this is merely the one I think is most intuitive.
This is how I would do it based on the code you have printed so far :-
public class BigIntProgram
{
public static void main (String[] args)
{
BigInt firstLargeNumber = new BigInt ("44112345");
firstLargeNumber.display();
BigInt secondLargeNumber = new BigInt ("56276467");
secondLargeNumber.display();
firstLargeNumber.add (secondLargeNumber);
}
}
public BigInt add(BigInt val)
{
BigInt result = new BigInt ("xxxxxxxxxx");
int new_carry = 0, prev_carry = 0, j = result.value.length() -1;
int placeVal = 0;
char[] answer = new char[result.value.length()];
answer = result.value.toCharArray();
for(int i = value.length() - 1; i > - 1; i--)
{
new_carry = (Integer.parseInt("" + value.charAt(i)) + Integer.parseInt("" + val.value.charAt(i)) + new_carry)/10;
placeVal = Integer.parseInt("" + value.charAt(i)) + Integer.parseInt("" + val.value.charAt(i)) + prev_carry - new_carry * 10;
prev_carry = new_carry;
answer[j--] = (char)((int) '0' + placeVal);
}
if (new_carry > 0) answer[j] = (char)((int) '0' + new_carry);
result.value = "";
for(j = 0; j < answer.length; j++)
{
if (answer[j] != 'x') result.value += answer[j];
}
result.display();
return result;
}
}
Thanks, this definitely makes a lot of sense to me, however just one question, could someone please tell me what " parseInt " does in the code, what is the purpose of that, could someone please explain, thanks........
parseInt() is a static method in the Integer class that parses a String into an int.[url] http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Integer.html#parseInt(java.lang.String)[/url]
I Thank everyone that helped me out in this project. Thank You.
The above code can be improved because the local char array answer can be replaced by using the java keyword substring to write to result.value directly. The following code does this and also implements a running total, as long as the number to be added is always smaller than the result obtained thus far. I noticed that some of the code was accidentally omitted in the fragment I pasted above. Anyway here is the code :-
class BigInt
{
public String value;
public BigInt(String val)
{
value = val;
}
public void display()
{
System.out.println(value);
}
public BigInt add(BigInt val)
{
BigInt result = new BigInt ("0000000000");
int new_carry = 0, prev_carry = 0, j = result.value.length() -1;
int placeVal = 0;
int leading_zeroes = value.length() - val.value.length();
for (int i = 0; i < leading_zeroes; i++)
{
val.value = '0' + val.value;
}
for(int i = value.length() - 1; i > - 1; i--)
{
new_carry = (Integer.parseInt("" + value.charAt(i)) + Integer.parseInt("" + val.value.charAt(i)) + new_carry)/10;
placeVal = Integer.parseInt("" + value.charAt(i)) + Integer.parseInt("" + val.value.charAt(i)) + prev_carry - new_carry * 10;
prev_carry = new_carry;
result.value = result.value.substring(0,j) + (char)((int) '0' + placeVal) + result.value.substring(j+1);
j--;
}
if (new_carry > 0) result.value = result.value.substring(0,j) + (char)((int) '0' + new_carry) + result.value.substring(j+1);
return result;
}
}
public class BigIntProgram
{
public static void main (String[] args)
{
BigInt firstLargeNumber = new BigInt ("44112345");
firstLargeNumber.display();
BigInt secondLargeNumber = new BigInt ("56276467");
secondLargeNumber.display();
BigInt result = firstLargeNumber.add (secondLargeNumber);
System.out.println (Integer.parseInt(result.value));
secondLargeNumber.display();
result = result.add (secondLargeNumber);
System.out.println (Integer.parseInt(result.value));
}
}
This could be useful in educational software to teach young computer users addition where the carry is needed to be known. In other circumstances you would use something like
long a = 5678999;
long b = 134567890123;
long result = a + b;
and not worry about the carry.
