/*******************************************************************
* Author: Isai Damier
* Title: LargeInteger.java
* Project: geekviewpoint
* Package: datastructure
*
* Description: Normally modern computers cannot handle very large
* numbers. So the task here is to create a datastructure that
* can handle numbers of perhaps infinite size. And to prove that
* the datastructure works, included are arithmetic operators.
*
* Naturally the numbers are represented as Strings. And to
* perform addition and subtraction, stacks are used as the media.
* Finally, as any trusty calculator, this datastructure returns
* erroneous values for erroneous inputs and correct values for
* correct inputs. This is to say, if an input string does not
* represent a valid decimal integer, then the output string
* will be bogus.
******************************************************************/
import java.util.Stack;
public class LargeInteger {
private String number;
public LargeInteger(String number) {
this.number = number;
}//constructor
/***************************************************************
* Function: plus
* Inputs: @param addend
* The value to be added to this number
* Output: String
* The sum of the addend and this number
*
* Description: Add the given value (i.e. addend) to this number.
*
* Technical Details: This is pretty much a brute force
* algorithm. The strings are changed to stacks of integers.
* Then the stacks are popped and the values are added and
* passed to the result.
*
* The result is assembled in reverse just to keep things
* simple (Java has a nice append function). The result could
* have otherwise been assembled as result = sum + result.
*
**************************************************************/
public String plus(String addend) {
Stack<Integer> augendStack = toIntegerStack(this.number);
Stack<Integer> addendStack = toIntegerStack(addend);
StringBuffer result = new StringBuffer();
int carry = 0, sum = 0, radix = 10;
while (!augendStack.isEmpty() && !addendStack.isEmpty()) {
sum = augendStack.pop() + addendStack.pop() + carry;
result.append(sum % radix);
carry = sum / radix;
}
while (!augendStack.isEmpty()) {
sum = augendStack.pop() + carry;
result.append(sum % radix);
carry = sum / radix;
}
while (!addendStack.isEmpty()) {
sum = addendStack.pop() + carry;
result.append(sum % radix);
carry = sum / radix;
}
if (carry > 0) {
result.append(carry);
}
result.reverse();
return result.toString();
}
}
import org.junit.Test;
import static org.junit.Assert.*;
public class LargeIntegerTest {
public LargeIntegerTest() {
}
/**
* Test of plus method, of class LargeInteger.
*/
@Test
public void testPlus() {
System.out.println("plus");
LargeInteger bigInteger;
String a = "8787284297498234897287345";
String b = "7971813897918381831891879249579839712938";
String p = "7971813897918390619176176747814737000283";
bigInteger = new LargeInteger(a);
assertEquals(p, bigInteger.plus(b));
int max = 54321;
for (int x = 0; x <= max; x += 31) {
for (int y = 0; y <= max; y += 31) {
bigInteger = new LargeInteger(x + "");
assertEquals(x + y, Integer.parseInt(bigInteger.plus(y + "")));
assertEquals(x + "", bigInteger.value());
assertEquals((x + "").length(), bigInteger.size());
}
}
}
}