How to multiply two big big numbers

Question

Hey guys,

Consider a list of numbers L=. We can only have the series between +=2^j, while 0<=j<=32.We have to implement an algorithm which implements the largest product.

Answer 1

EDIT: I adjusted the algorithm outline to match the actual pseudo code and put the complexity analysis directly into the answer:

Outline of algorithm

Go seqentially over the sequence and store value and first/last index of the product (positive) since the last 0. Do the same for another product (negative) which only consists of the numbers since the first sign change of the sequence. If you hit a negative sequence element swap the two products (positive and negative) along with the associagted starting indices. Whenever the positive product hits a new maximum store it and the associated start and end indices. After going over the whole sequence the result is stored in the maximum variables.

To avoid overflow calculate in binary logarithms and an additional sign.

Pseudo code

maxProduct = 0
maxProductStartIndex = -1
maxProductEndIndex = -1
sequence.push_front( 0 ) // reuses variable intitialization of the case n == 0

for every index of sequence
   n = sequence[index]
   if n == 0
       posProduct = 0
       negProduct = 0
       posProductStartIndex = index+1
       negProductStartIndex = -1
   else
       if n < 0
           swap( posProduct, negProduct )
           swap( posProductStartIndex, negProductStartIndex )
           if -1 == posProductStartIndex // start second sequence on sign change
               posProductStartIndex = index
           end if
           n = -n;
       end if
       logN = log2(n) // as indicated all arithmetic is done on the logarithms
       posProduct += logN
       if -1 < negProductStartIndex // start the second product as soon as the sign changes first
          negProduct += logN
       end if
       if maxProduct < posProduct // update current best solution
          maxProduct = posProduct
          maxProductStartIndex = posProductStartIndex
          maxProductEndIndex = index
       end if
   end if
end for

// output solution

print "The maximum product is " 2^maxProduct "."
print "It is reached by multiplying the numbers from sequence index " 
print maxProductStartIndex " to sequence index " maxProductEndIndex

Complexity

The algorithm uses a single loop over the sequence so its O(n) times the complexity of the loop body. The most complicated operation of the body is log2. Ergo its O(n) times the complexity of log2. The log2 of a number of bounded size is O(1) so the resulting complexity is O(n) aka linear.

Answer 2

Since k <= 30, any integer i = 2^k will fit into a Java int. However the product of such two integers might not necessarily fit into a Java int since 2^k * 2^k = 2^2*k <= 2⁶⁰ which fill into a Java long. This should answer Your question regarding the "(multiplication of) two numbers...".

In case that You might want to multiply more than two numbers, which is implied by Your assignment saying "...largest product of a CONTINUOUS SUBLIST..." (a sublist's length could be > 2), have a look at Java's BigInteger class.

Answer 3

Hmmm.. since they're all powers of 2, you can just add the exponent instead of multiplying the numbers (equivalent to taking the logarithm of the product). For example, 2^3 * 2^7 is 2^(7+3)=2^10. I'll leave handling the sign as an exercise to the reader.

Regarding the sublist problem, there are less than n^2 pairs of (begin,end) indices. You can check them all, or try a dynamic programming solution.

Answer 4

Actually, the most efficient way of multiplication is doing addition instead. In this special case all you have is numbers that are powers of two, and you can get the product of a sublist by simply adding the expontents together (and counting the negative numbers in your product, and making it a negative number in case of odd negatives).

Of course, to store the result you may need the BigInteger, if you run out of bits. Or depending on how the output should look like, just say (+/-)2^N, where N is the sum of the exponents.

Parsing the input could be a matter of switch-case, since you only have 30 numbers to take care of. Plus the negatives.

That's the boring part. The interesting part is how you get the sublist that produces the largest number. You can take the dumb approach, by checking every single variation, but that would be an O(N^2) algorithm in the worst case (IIRC). Which is really not very good for longer inputs.

What can you do? I'd probably start from the largest non-negative number in the list as a sublist, and grow the sublist to get as many non-negative numbers in each direction as I can. Then, having all the positives in reach, proceed with pairs of negatives on both sides, eg. only grow if you can grow on both sides of the list. If you cannot grow in both directions, try one direction with two (four, six, etc. so even) consecutive negative numbers. If you cannot grow even in this way, stop.

Well, I don't know if this alogrithm even works, but if it (or something similar) does, its an O(N) algorithm, which means great performance. Lets try it out! :-)

Answer 5

In my first answer I addressed the OP's problem in "multiplying two big big numbers". As it turns out, this wish is only a small part of a much bigger problem which I'm going to address now:

"I still haven't arrived at the final skeleton of my algorithm I wonder if you could help me with this."

(See the question for the problem description)

All I'm going to do is explain the approach Amnon proposed in little more detail, so all the credit should go to him.

You have to find the largest product of a continuous sublist from a list of integers which are powers of 2. The idea is to:

1. Compute the product of every continuous sublist.
2. Return the biggest of all these products.

You can represent a sublist by its start and end index. For start=0 there are n-1 possible values for end, namely 0..n-1. This generates all sublists that start at index 0. In the next iteration, You increment start by 1 and repeat the process (this time, there are n-2 possible values for end). This way You generate all possible sublists.

Now, for each of these sublists, You have to compute the product of its elements - that is come up with a method computeProduct(List wholeList, int startIndex, int endIndex). You can either use the built in BigInteger class (which should be able to handle the input provided by Your assignment) to save You from further trouble or try to implement a more efficient way of multiplication as described by others. (I would start with the simpler approach since it's easier to see if Your algorithm works correctly and first then try to optimize it.)

Now that You're able to iterate over all sublists and compute the product of their elements, determining the sublist with the maximum product should be the easiest part.

If it's still to hard for You to make the connections between two steps, let us know - but please also provide us with a draft of Your code as You work on the problem so that we don't end up incrementally constructing the solution and You copy&pasting it.

edit: Algorithm skeleton

public BigInteger listingSublist(BigInteger[] biArray)
{       
    int start = 0;
    int end = biArray.length-1;
    BigInteger maximum;

    for (int i = start; i <= end; i++)
    {
        for (int j = i; j <= end; j++)
        {
            //insert logic to determine the maximum product.
            computeProduct(biArray, i, j);
        }
    }

    return maximum;                
}

public BigInteger computeProduct(BigInteger[] wholeList, int startIndex, 
                                                         int endIndex)
{
    //insert logic here to return
    //wholeList[startIndex].multiply(wholeList[startIndex+1]).mul...(
    //    wholeList[endIndex]);       
}

Answer 6

useless code. I will put up the final implementation after fixing some bugs.

Answer 7

I'd like to combine Amnon's observation about multiplying powers of 2 with one of mine concerning sublists.

Lists are terminated hard by 0's. We can break the problem down into finding the biggest product in each sub-list, and then the maximum of that. (Others have mentioned this).

This is my 3rd revision of this writeup. But 3's the charm...

Approach

Given a list of non-0 numbers, (this is what took a lot of thinking) there are 3 sub-cases:

1. The list contains an even number of negative numbers (possibly 0). This is the trivial case, the optimum result is the product of all numbers, guaranteed to be positive.

2. The list contains an odd number of negative numbers, so the product of all numbers would be negative. To change the sign, it becomes necessary to sacrifice a subsequence containing a negative number. Two sub-cases:

   a. sacrifice numbers from the left up to and including the leftmost negative; or

   b. sacrifice numbers from the right up to and including the rightmost negative.

   In either case, return the product of the remaining numbers. Having sacrificed exactly one negative number, the result is certain to be positive. Pick the winner of (a) and (b).

Implementation

The input needs to be split into subsequences delimited by 0. The list can be processed in place if a driver method is built to loop through it and pick out the beginnings and ends of non-0 sequences.

Doing the math in longs would only double the possible range. Converting to log2 makes arithmetic with large products easier. It prevents program failure on large sequences of large numbers. It would alternatively be possible to do all math in Bignums, but that would probably perform poorly.

Finally, the end result, still a log2 number, needs to be converted into printable form. Bignum comes in handy there. There's new BigInteger("2").pow(log); which will raise 2 to the power of log.

Complexity

This algorithm works sequentially through the sub-lists, only processing each one once. Within each sub-list, there's the annoying work of converting the input to log2 and the result back, but the effort is linear in the size of the list. In the worst case, the sum of much of the list is computed twice, but that's also linear complexity.

Answer 8

See this code. Here I implement exact factorial of a huge large number. I am just using integer array to make big numbers. Download the code from Planet Source Code.