CODEWITHSUNDEEP
c++optimizationnumbers
user13793398
user13793398

Reputation:

Optimizing a Project-Euler question (#8) more

The problem is solved. (Project-Euler #8)

But I was wondering - Can we optimize it even more?

Problem - Given a text array of numbers (lets say DATA).
Find 13 adjacent digits, whose product is the largest possible in DATA.

What I did - [Main logic]

//We could process through each digit 
//"Product" it till 13 numbers - p *= digit
//Check for Larger than previous - keep this, drop that`

[First Optimization - Chunking]

// 0 zeros are such party poopers, we will avoid them.
// the digits between 0 should have some status clearance. (0XXXXX0) >= 13
//Lets call each of rest a "chunk"`

The Problem - after this optimization, there are still ~263 chunks. *I can smell that not all chunks are as heavy as we want. If somehow we could drop lighter of these chunks? *

This is the code block, I came up with.


//Method: (DATA, window_size) ---> largest product of adjacent digits  
data func(char textnum[], int n)
{
    //Sub-method: DATA[char] ---> DATA[int]
    int bignum[1000];

    for(int i = 0; i < 1000; i++ )
    {
        bignum[i] = int( textnum[i] ) - 48;
    }

    //Chunking: In between zeros, all the (adjacent digits) < n are dropped
    //int chunk[] : holds the index to an appropriate "chunk"
    int cnt = 0, s = 0;

    std::vector<int> chunks;

    for ( int i = 0; i < 1000; i++ )
    {
        if( bignum[i] )
            cnt++;
        else cnt = 0;
        if( cnt >= n )
        {
            chunks.push_back((i + 1) - n); 
        }
    }

    //Main Logic: 
    data p = 1, x = 1;
    for ( int i = 0; i < chunks.size(); i++)    //Loop: (processing through chunks in DATA)
    {
        for ( int j = 0; j < n; j++ )           //Loop: (processing till the window_size)
        {
            p *= bignum[chunks.at(i) + j];      //Product of n adjacent digits
        }
        if ( p > x )                            //Largest 
            x = p;
        p = 1;
    }

    return x;
}

How to optimize her more?

Upvotes: 0

Views: 76

Answers (1)

Botje
Botje

Reputation: 30907

Consider a span of non-zero numbers of size N >= 13: (presented as groups of four letters each for easy reading)

abcd efgh ijkl mnop qrstu ...

In your terminology, every sub-span of size 13 would be a 'chunk'. There are N-13 such chunks (a-m, b-n, c-o, etc.)

Your current code recalculates the product from scratch for each chunk from the same span:

p_1 = a * b * ... * m;
p_2 =     b * ... * m * n;
p_3 =         ... * m * n * o;

In other words: p_2 = p_1 / a * n; and p_3 = p_2 / b * o;

You can do this for other chunks in the same span and come out ahead, as L1 cache accesses are cheap but not free.

Upvotes: 0

Related Questions