Array Math Problem

[leverin4]

I'm having trouble coming up with a solution to this problem.

Say you have two byte arrays with numbers stored in them backwards.

For example, say you have the numbers num1 = 843234 and num2 = 5430222124 stored in two byte arrays as follows

byte[] num1 = {4, 3, 2, 3, 4, 8};
byte[] num2 = {4, 2, 1, 2, 2, 2, 0, 3, 4, 5};

// The numbers this code will be used for are much
// larger; possibly hundreds of digits long.

I need to write three methods:

1. add - This function adds the two numbers together and stores the result in a new byte array (I can write this one easily.)

2. multiply - This function multiplies the two numbers together and stores the result in a new byte array (I'm having trouble getting this one started. This method can not call add, i.e. To take 765 * 6, I can't just add 765 to itself 6 times)

3. power - This function raises num1 to the power of num2 and stores it in a new byte array. (Once I figure out the multiply, I am allowed to call multiply, but I know there has to be a faster way to do it.)

Any help would be greatly appreciated. I just need help getting started on multiply and power, if you have any ideas.

[javaAddict]

You can loop backwards the arrays, take the elements and convert them into Strings and concatenate them. Then convert the Strings to numbers and multiply them.

String s;
loop i
  take element i
  convert it to String
  concatenate it to s variable
end loop
convert s to number

[BestJewSinceJC]

What are you having trouble with. . having the numbers in forwards/normal order, or with multiplying the numbers, or both? The Math.pow method is useful, but I'm not sure how large your numbers are. You should check out the BigInteger class. It has multiplication and exponents for large numbers. http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html

[leverin4]

This is a VeryBigInteger class that I have to write. The example given is around the length of the following number, and my code should be able to handle even bigger.

465321618146514318518947646469732164976588787543544876697933133793464319739
797974634931649736413973641197639461372591543591347653154973154978346149797
543166464613462964316494613465926134696134691364982916431629534619435914635
294389464634316544613264921213346879865354657989713213682871717465135549873
241649134592359461349214651431851894764646973216497658878754354487669793313
797974634931649736413973641197639461372591543591347653154973154978346149797
543166464613462964316494613465926134696134691364982916431629534619435914635
294389464634316544613264921379346431973922231187797646532135646321654948286
214651431851894764646973216497658878754354487669793313797974634931649736413
973641197639461372591543591347653154973154978346149797543166464613462964316
494613465926134696134691364982916431629534619435914635294389464634316544613
264921379346431973922231187797646532135646321654948286465321618146514318518
947646469732164976588787543544876697933133793464319739797974634931649736413
465321618146514318518947646469732164976588787543544876697933133793464319739
797974634931649736413973641197639461372591543591347653154973154978346149797
543166464613462964316494613465926134696134691364982916431629534619435914635
294389464634316544613264921213346879865354657989713213682871717465135549873
241649134592359461349214651431851894764646973216497658878754354487669793313
797974634931649736413973641197639461372591543591347653154973154978346149797
543166464613462964316494613465926134696134691364982916431629534619435914635
294389464634316544613264921379346431973922231187797646532135646321654948286

The numbers wil be read in from text files, and I have no problem converting the numbers from strings to byte arrays or reversing the numbers, etc. The first place I run into problems is when I try to multiply two of these numbers together. I know about the BigInteger class, but these numbers are too big for that. I only need to be able to handle positive numbers. I'm sorry, I should've given more details in my first post.

[JamesCherrill]

So, I understand that you need to keep each digit separate and have algorithms that loop along the digits (no matter how many there may be) to give the answer. For the multiply - write down two multi-digit numbers on a piece of paper and multiply them together by hand. The process you just used is the algorithm you need!

[leverin4]

oh wow... I was overthinking that way way too much. Haha. Ok, thank you James.

Is there a harder/faster way to do the power function without looping multiply potentially thousands of times??

[JamesCherrill]

Is there a harder/faster way to do the power function without looping multiply potentially thousands of times??

Dunno - not a mathematician! Maybe you can pre-compute the 10th power, use that to pre-compute the 100th power, use that to pre-compute the 1000th power etc then use the digits of num2 to determine how many times to use each of those results? If that works it should scale nearly linearly with the number of digits?

[leverin4]

I have a way I think. Say I needed to take x to the 456th power. using while loops, I could just continuously square the number until I got to x to the 4096th power, and then multiply that by x to the 256th power, which I'd get using recursion), and multiply that by x to the 128th power, and that by x to the 64th power, that by x to the 16th power, and that by x to the 4th power and finally, that by x to the 1st power.

So I'd have x^4096 * x^256 * x^128 * x^64 * x^16 * x^4 * x^1
which equals X^(4096+256+128+64+16+4+1)
which equals x^4565

It'd be tricky I think, and might need some recursion, but this should work, right?

Can anyone think of a faster algorithm?

[JamesCherrill]

That sounds to me like it's probably the fastest possible algorithm, although it will need some cunning code design!
I was thinking about an approach close to the spirit of digit-by-digit decimal processing, which, although probably a bit slower, would be easy to undersand and code. It goes like this:
We want x^Y. Let's write Y in terms of its digits as:
Y = a + 10*b + 100*c + 1000*d ...
so x^Y is
x^(a + 10*b + 100*c + 1000*d ...)
= x^a * x^(10*b) * x^(100*c) * x^(1000*d) ...
= x^a * x^10^b * x^100^c * x^1000^d ...
= x^a * x^10^b * (x^10)^10^c * (x^100)^10^d ...

which is, in pseudo code, is something like:

res = x^y.digit(0) ; 
power10 = x; // running value of x^10^n
for (n = 1; n < y.numberOfDigits; n++){
  power10 = power10^10;
  res *= power10^(y.digit(n));
}  
return res;

Where all the ^ operations are now <= ^10, so can be done with simple multiplication. (If you optimise ^10 (= ^8 * ^2) you can do it in 4 multiplies.)

Have fun!
J

[BestJewSinceJC]

I have a way I think. Say I needed to take x to the 456th power. using while loops, I could just continuously square the number until I got to x to the 4096th power, and then multiply that by x to the 256th power, which I'd get using recursion), and multiply that by x to the 128th power, and that by x to the 64th power, that by x to the 16th power, and that by x to the 4th power and finally, that by x to the 1st power.

So I'd have x^4096 * x^256 * x^128 * x^64 * x^16 * x^4 * x^1
which equals X^(4096+256+128+64+16+4+1)
which equals x^4565

It'd be tricky I think, and might need some recursion, but this should work, right?

Can anyone think of a faster algorithm?

This may work, but I do not think it has an advantage over the multiply method. You're essentially doing the exact same operations either way, just making them appear different on paper. I'm pretty sure the computer is doing the same thing.

[leverin4]

EDIT: Never mind. Marked as solved.

[JamesCherrill]

Which approach did you use? How well did it work?