How to multiply two big big numbers

Question

You are given a list of n numbers L=<a_1, a_2,...a_n>. Each of them is either 0 or of the form +/- 2^k, 0 <= k <= 30. Describe and implement an algorithm that returns the largest product of a CONTINUOUS SUBLIST p=a_i*a_i+1*...*a_j, 1 <= i <= j <= n.

For example, for the input <8 0 -4 -2 0 1> it should return 8 (either 8 or (-4)*(-2)).

You can use any standard programming language and can assume that the list is given in any standard data structure, e.g. int[], vector<int>, List<Integer>, etc.

What is the computational complexity of your algorithm?

Answer 1

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]);       
}