UVA 787 and Big Number Multiplication

UVA 787 and Big Number Multiplication

Problem

Background: Big Numbers in this problem

Big numbers are effectively storing sequence of digit chunks and directly manipulating them as if they were a large number. The most intuitive way to do this is to make an array where every element is a digit, but this is not effectively using the memory. Hence, it is logical to store numbers "millions at a time", i.e.

324876498726832746
 [2]  | [1] | [0]

like that.

Necessities to Implement

Notice that although this problem may LOOK like DP, it's really solvable by O(N^2) enumeration. Also notice that in this enumeration we will only be multiplying a large number with a normal number. Pseudocode for algorithm:

CREATE LargeNumber NAME best SET -INFINITY
FOR EACH i BETWEEN 0 and LENGTH OF list DO:
    CREATE LargeNumber NAME product SET 1
    FOR EACH j BETWEEN i AND LENGTH OF list DO
        SET product TO product TIMES list[j]
        IF product IS GREATER THAN best DO
           SET best TO product

From here it's obvious the only methods we need to implement is initialization, equation, multiplication and greater-comparison.

My code demonstrates a simple, minimalist, object-oriented implementation.

Code

#include <iostream>

#include <algorithm>

#include <cstring>

#include <iomanip>

using namespace std;

long long arr[105];

long long preProd[105];

#define LEN 500

#define MOD 1000000

#define MS 6

struct Large

{

int64_t digits[LEN];

int sign; // -1, 0, or 1

Large()

{

memset(digits, 0, sizeof digits);

sign = 0;

}

Large& operator=(Large& other)

{

if(this != &other)

{

sign = other.sign;

memcpy(digits, other.digits, sizeof digits);

}

return *this;

}

Large& operator=(int other)

{

memset(digits, 0, sizeof digits);

if(other == 0) sign = 0;

else if(other > 0) sign = 1;

else sign = -1;

other = sign*other; // now it's positive

digits[0] = other%MOD;

digits[1] = other/MOD;

digits[2] = digits[1]/MOD;

digits[1] %= MOD;

return *this;

}

void operator*=(int other)

{

int osign;

if(other == 0) osign = 0;

else if(other > 0) osign = 1;

else osign = -1;

sign = sign*osign;

for(int i=0; i<LEN; i++)

digits[i] = digits[i]*osign*other;

for(int i=0; i<LEN-1; i++)

{

digits[i+1] += digits[i]/MOD;

digits[i] %= MOD;

}

}

const bool operator<(Large& other)

{

if(sign != other.sign) return sign < other.sign;

if(sign == 0 && other.sign == 0) return false;

for(int i=LEN-1; i>=0; i--)

{

if(sign*digits[i] < sign*other.digits[i]) return true;

if(sign*digits[i] > sign*other.digits[i]) return false;

}

return false;

}

void setVeryLow()

{

sign = -1;

memset(digits, 31, sizeof digits);

}

void printOut()

{

if(sign == 0)

{

cout << 0 << endl;

return;

}

if(sign == -1)

cout << "-";

int GRV = -1;

for(int i=LEN-1; i>=0 && GRV == -1; i--)

if(digits[i] != 0)

GRV = i;

cout << digits[GRV];

for(int i=GRV-1; i>=0; i--)

cout << setfill('0') << setw(MS) << digits[i];

cout << endl;

}

};

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(0);

while(cin >> arr[0])

{

int n = 1;

Large bestPreProd; bestPreProd.setVeryLow();

while(arr[n-1] != -999999) cin >> arr[n++];

n--;

for(int i=0; i<n; i++)

{

Large current; current = 1;

for(int j=i; j<n; j++)

{

current *= arr[j];

if(bestPreProd < current)

bestPreProd = current;

}

}

bestPreProd.printOut();

}

}