Multiplying and comparing big numbers

Question

I have this problem: There are K lines of N numbers (32-bit). I have to choose the line with the max product of numbers.

The main problem is that N can go up to 20. I'm trying to do this with logarithms:

ld sum = 0, max = 0;
int index = 0;

for(int i = 0; i < k; i ++) { // K lines
    sum = 0, c = 0;
    for(int j = 0; j < n; j ++) { // N numbers
        cin >> t;
        if(t < 0)
            c++; // If the number is less than 0 i memorize it

        if(t == 1 || t == -1) { // if numbers = 1 OR -1
            sum += 0.00000001; // Because log(1) = 0
            if(t == -1)
                c ++;
        }
        else if(t == 0) { // if some number is equal to zero then the sum is = 0
            sum = 0;
            break;
        }
        else {
            sum += log10(fabs(t));
        }
    }

    if(c % 2 == 1) // if c is odd than multiply by -1
        sum *= -1;

    if(sum >= max) { 
        max = sum;
        index = i;
    }
    if((sum - max) < eps) { // if sum is equal to max i'm also have to choose it
        max = sum;
        index = i;
    }
}
cout << index + 1 << endl;

The program works in 50% of test cases. Is there a way to optimize my code?

Answer 1

In the case of t == -1, you increment c twice.

Answer 2

I think that this line is definitely wrong:

if(c % 2 == 1) // if c is odd than multiply by -1
    sum *= -1;

If your product is in the range [0,1] then its logarithm will be negative and this will make it positive. I think you should keep it separate.

Answer 3

if you want to avoid bignum libs you can exploit that if you multiply b1 and b2 bits numbers then the result is b1+b2 bits long

1. so just sum the bit count of all multiplicants in a line together

   • and compare that

   • remember the results in some array

     int bits(DWORD p) // count how many bits is p DWORD is 32bit unsigned int
         {
         DWORD m=0x80000000; int b=32;
         for (;m;m>>=1,b--)
          if (p>=m) break;
         return b;
         } 
     

2. index sort the lines by the result bit count descending

3. if the first bitcount after sort is also the max then its line is the answer
4. if you have more than one max (more lines have the same bitcount and are the max also)
   • only then you have to multiply them together

Now the multiplication

• you know should multiply all the max lines at once
• each time all sub results are divisible by the same prime
• divide them by it
• this way the result will be truncated to much less bit count
• so it should fit into 64 bit value
• you should check out primes up to sqrt(max value)
• when your max value is 32bit then check primes up to 65536
• so you can make a static table of primes to check to speed thing up
• also there is no point in checking primes bigger then your actual sub result
• if you know how then this can be extremly speeded up by Sieves of Eratosthenes
• but you will need to keep track of index offset after each division and use periodic sieve tables which is a bit complicated but doable
• if you do not check all the primes but just few selected ones
• then the result can still overflow
• so you should handle that too (throw some error or something)
• or divide all subresults by some value but that can invalidate the the result

Another multiplication approach

• you can also sort the multiplicant by value
• and check if some are present in all max lines
• if yes then change them for one (or delete from lists)
• this can be combined with the previous approach

bignum multiplication

• you can make your own bignum multiplication
• the result is max 20*32=640 bit
• so the result will be array of unsigned ints (bit wide 8,16,32 ... whatever you like)
• you can also handle the number as a string
• look here for how to compute fast exact bignum square in C++
• it contains also the multiplication approaches
• and here NTT based Schönhage-Strassen multiplication in C++
• but that will be slower for such small numbers like yours
• at last you need to compare results
• so compare from MSW do LSW and which ever line has bigger number in it is the max line
• (MSW is most significant word, LSW is least significant word)