Large Numbers
Ranch Hand
 0
Conditions:
1. The most important condition is to use as little memory as possible
2. Try to design such that the performance does not degrade drastically with increase in the number of digits
3. The numbers can be nonintegral with a period as in example #2 below
4. Michael and Jim cannot start coding before next 24 hours ;)
Examples

Input:
123456789123456789123456789123456789
+
876543210876543210876543210876543211
Output:
1000000000000000000000000000000000000

Input:
111111111222222222.333333333444444444
+
777.777
Output:
111111111222223000.110333333444444444

Input:
333333333333333333.333333333333333333

244444444444444444.444444444444444444
Output:
088888888888888888.888888888888888889
 0
Usage:
java Adder [first number] [second number]
Sheriff
 0
Jignesh  when we minimize memory used, you're talking about memory for instance data, right? If we use more memory in local variables (i.e. temporarily while adding/subtracting) that doesn't count, does it? I'm not sure yet (since I haven't started coding) but it seems that the best scheme I can come up with to minimize instance data might require additional memory for temp variables, so I want to make sure this requirement is clear.
4. Michael and Jim cannot start coding before next 24 hours ;)
In fact I'm about to hit the road to go to JavaOne, so you probably won't hear much else from me until much later. And Michael is busy today with his daughter's wedding. So it will be up to someone else to challenge David for supremacy here. Have fun, everyone.
[ June 08, 2003: Message edited by: Jim Yingst ]
"I'm not back."  Bill Harding, Twister
Ranch Hand
 0
I should have said if you had to design a library that provides features like that provided by the BigDecimal class how would you do it so that it is efficient memory/time wise?.
Jignesh  when we minimize memory used, we minimize the instance data, right? If we use more memory in local variables (i.e. temporarily while adding/subtracting) that doesn't count, does it?
Well, to be honest, I did not really think about memory in terms of instance verses local data because i did not even think of the problem as an OO class. All I was thinking was about a method that accepts two Strings and returns a String and whether we use memory from heap or from stack, how should we keep the total amount of memory consumed by the process to a minimum when that method is executing? But I see your point. We can start with using minimum memory for representation (instance data) and later work on the usage of memory for the operations (local data).
Some approaches if we use a char[] to represent individual digits as chars, then a 50 digit number occupies 100 bytes. If we use a byte[], then it would use 50 bytes. So how about using packed Binary Coded Decimals (BCD) to pack two digits in a single byte. That would require only 25 bytes. But in this case, the arithmatic operations will involve more memory and calculations. Another approach would be to use an array of longs to represent large numbers. E.g an array such as "new long[2]" can be viewed as a 128 bit value, and "new long[3]" can represent 192 bits, and so on. The operations + and  will probably be easy to implement but converting from decimal String to 128 bits binary and vice versa might require some thinking.
Anyways, have a nice time at JavaOne.
 0
On the other hand having a class named something like BigSummableDecimal that stored numbers in a compact form would make sense. You would be able to do several additions in sequence before it was necessary to convert back to a String for display or serialize it quite efficiently.
If I have a few moments late tonight I'll see if I can work out a solution that's a bit more like what you were looking for
 0
Here are the results:
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius  and a lot of courage  to move in the opposite direction.  Ernst F. Schumacher
Ranch Hand
 0
Step1: Start from right most bit and go left "without" flipping over all the 0 bits till you find the first 1 bit.
Step2: Keep that first 1 bit as it is. Do not flip it.
Step3: Continue going left and flip the rest of the bits.
Rest of the code is done really well the matching decimal point, adding, padding, and matching the bits, etc. Two Thumbs Up!
David: If we're assuming a single method where the input and output are both strings in base 10, than converting them to a more space efficient form doesn't change the fact that you still needed the memory for the char array/String.
True. :) I forgot that part.
 0
I would like to see someone try using a long[] array to do this. It wouldn't be a whole lot differnt my code but might be more efficient since there would be fewer iterations for complementing, etc.
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius  and a lot of courage  to move in the opposite direction.  Ernst F. Schumacher
Sheriff
 0
"I'm not back."  Bill Harding, Twister
 0
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius  and a lot of courage  to move in the opposite direction.  Ernst F. Schumacher
Ranch Hand
 0
I wonder how NetRexx does it. NetRexx translates REXX to Java then compiles, lets you mix syntax from both languages.
A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
 0
I was playing around with turning 10^n into binary using the BigInteger class. you get patterns appearing in the sequence of 0/1 as a function of n & power of 2.
10 = 1010
100 = 1100100
1000 = 1111101000
etc, the pattern starts of something like:
last n digits are zero,
n+1 digit = 1
n+2 digit = 0
n+3 digit = n >> 2 % 2
n+4 digit = n >> 3 % 2 ^ (n % 8) == 1 (???)
after that there is repetition, so for n+5 this pattern is repeated every 16n, n+6  32n, n+7 64n, n+8 128n, n+9 256n.
It's really made me start scratching my head to come up with a formula for the "mth binary digit of 10^n (base10)", and I'm determined to figure it out for myself (rather than google it).
I know someone came up with a similar formula for pi some years ago, & am starting to realise how hard it must have been!!
Sheriff
 0
IEEE 754: wouldn't that lead to roundoff errors? I think you're going to have a hard time getting answers exactly like Jignesh originally specified. The alternative of using a binary integer combined with a base10 exponent (i.e. what M^2 did, and what I had planned to do, and what BigDecimal does internally) seems like the most memoryefficient choice that also gives exact answers for all decimal numbers of finite length. Methinks there must be an IEEE standard somewhere which describes this sort of format, as it seems a natural choice for exact decimal calculations.
"I'm not back."  Bill Harding, Twister
 0
Originally posted by Jim Yingst:
NetRexx: dunno, but I'm going to guess they just use BigDecimal.
IEEE 754: wouldn't that lead to roundoff errors? I think you're going to have a hard time getting answers exactly like Jignesh originally specified. The alternative of using a binary integer combined with a base10 exponent (i.e. what M^2 did, and what I had planned to do, and what BigDecimal does internally) seems like the most memoryefficient choice that also gives exact answers for all decimal numbers of finite length. Methinks there must be an IEEE standard somewhere which describes this sort of format, as it seems a natural choice for exact decimal calculations.
Would it be possible to extend IEEE 754 such that you calculate the number of bits required for both significand and exponent to get an exact result? Or would you always have numbers that fall between representations regardless of bit size? I really haven't done any serious calcultaions on it, just popped into my mind.
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius  and a lot of courage  to move in the opposite direction.  Ernst F. Schumacher
Sheriff
 0
"I'm not back."  Bill Harding, Twister
 0
It's not fully tested, needs error handling and additional code if negative numbers are entered, but it does seem to work OK with the samples given.
(also needs a bit of polish  e.g. I wasn't sure what the regex code for a . (dot) was, so I used a workaround)
 0
I found the code written by Micheal very helpfull..
In fact i'm trying to solve this same problem (very large numbers arithmethics) but only for binary numbers.
one two important methods i want to write is shiftLeft() & shiftRight() for very large binaries.
can some one give me a clue on how to implement this ?
I would appreciate a lot some code .
thanks for helping.
I agree. Here's the link: http://aspose.com/filetools 