CODEWITHSUNDEEP
c++algorithmperformancetime-complexityinteger-overflow
chanzerre
chanzerre

Reputation: 2429

Program taking too long for large input

I am using an equation in which we have to find the maximum value that x can take given the value of b. Both x and b can take only nonnegative integer values. The equation is:

x^4+x^3+x^2+x+1≤b

I have written the following code(apparently dumb) to solve it:

#include<iostream>
#include<climits>

using namespace std;

int main()
{
    unsigned long long b,x=0;
    cout<<"hey bro, value of b:";
    cin>>b;
    while(x++<b)
        if(x*x*x*x+x*x*x+x*x+x+1>b)
        break;
    if(b==0)
    cout<<"Sorry,no value of x satisfies the inequality"<<endl;
    else
    cout<<"max value of x:"<<x-1<<endl;
    return 0;
}

The above code works fine upto b=LONG_MAX but after for b=LONG_LONG_MAX or b=ULLONG_MAX, it starts taking forever. How can I solve this problem so that it works fine for at most b=ULLONG_MAX?

Upvotes: 2

Views: 458

Answers (8)

KevinZ
KevinZ

Reputation: 3319

Here's a slightly more optimized version:

#include<iostream>
int main()
{
    std::cout << "Sorry, no value of x satisfies the inequality" << std::endl;
    return 0;
}

Why? Because x^4+x^3+x^2+x+1 is unbounded as x approaches positive infinity. There is no b for which your inequality holds. Computer Science is a subset of math.

Upvotes: -1

GGC
GGC

Reputation: 100

Quick answer:

First af all you are starting from x=0 and then increasing it which is not the best solution since you are looking for the maximum value and not the first one. So for that I would go from an upperbound that can be

x=abs((b)^(1/4))

than decrease from that value, and as soon you find an element <=b you are done.

You can even think in this way:

for y=b to 1
   solve(x^4+x^3+x^2+x+1=y)
   if has an integer solution then return solution

See this

This is a super quick answer I hope I didn't write too many stupid things, and sorry I don't know yet how to write math here.

Upvotes: 0

Ilya
Ilya

Reputation: 4689

Old answer (real problem here is not big number of iterations, but integer overflow; please read from 'Update' part; I keep this part here for history of false assumptions):

These values are very big. When your program checks each value from 0 to LONG_LONG_MAX, it shold make about 9*10^12 operations, isn't it? For ULLONG_MAX we have about 18*10^12 operations. Try to modify this program to see actual speed of processing:

while (x++ < b)
{
    if (x % 1000000 == 0)
        cout << " current x: " << x << endl;
    if (x*x*x*x+x*x*x+x*x+x+1>b)
        break;
}

So, you need to optimize this algorithm (i.e. reduce number of iterations): since your function is monotonic, you can use Binary search algorithm (see Bisection method too for clarification).

Also there is a possible problem with integer overflow: function x*x*x*x for big values x will be calculated wrong. Just imagine thay your type is unsigned char (1 byte). For example, when your program calculates 250*250*250*250 you expect 3906250000, but in fact you have 3906250000 % 256 (i.e. 16). So, if x is too big, it is possible, that your function will return value < b (and it will be strange; theoretically it can brake your optimized algorithm). Good news is that you will not see this problem, if do every check correctly. But for more complex functions you would also need to support long math (for example, use GMP or another implementation).

Update: How to avoid overflow risks?

We need to find maximal allowed value of x (let's call it xmax). Value x is allowed if x*x*x*x+x*x*x+x*x+x+1 < ULLONG_MAX. So, answer on initial question (about x*x*x*x+x*x*x+x*x+x+1 < b) is not bigger than xmax. Let's find xmax (just solve equation x*x*x*x+x*x*x+x*x+x+1=ULLONG_MAX in any system, for example WolframAlpha: anwer is about 65535.75..., so xmax==65535. So, if we check x from 0 to xmax we will not have overflow problems. Also it is our initial values for binary search algorithm.

Also it means, that we do not need to use binary search algorithm here, because it is enought to check only 65535 values. If x==65535 is not answer, we have to stop and return answer 65536.

If we need cross-platform solution without hardcoding of xmax, we can use any bigint implementation (GMP or any simpler solution) or implement more accurate multiplication and other operations. Example: if we need to multyply x and y, we can calculate z=ULLONG_MAX/x and compare this value and y. If z<y, we can't multiply x and y without overflow.

Upvotes: 2

vish4071
vish4071

Reputation: 5277

A really simple observation solves your problem in O(1) time.

Find k = sqrt(sqrt(b))

If k satisfies your inequality, k is your answer. If it does not, k-1 is your answer.

Upvotes: 2

user1196549
user1196549

Reputation:

Don't let x exceed 65535. If 65535 satisfies the inequality, 65536 will not.

Upvotes: 1

Evil Dog Pie
Evil Dog Pie

Reputation: 2320

You could try finding an upper limit and working down from there.

// Find the position of the most significant bit.
int topBitPosition = 0;
while(b >> topBitPosition)
    topBitPosition++;
// Find a rough estimate of b ^ 1/4
unsigned long long x = b >> (topBitPosition - topBitPosition/4);
// Work down from there
while(x*x*x*x+x*x*x+x*x+x+1 > b)
    x--;
cout<<"max value of x:"<<x-1<<endl;

Upvotes: 1

Klitos Kyriacou
Klitos Kyriacou

Reputation: 11642

This is not just an optimization issue. (For optimization, see IVlad's answer). It is also a correctness issue. With very large values, the expression causes integer overflow: to put it simply, it wraps around from ULLONG_MAX back to zero, and your loop carries on having not detected this. You need to build overflow detection in your code.

Upvotes: 3

IVlad
IVlad

Reputation: 43487

If for x = m, the inequality holds, then it also holds for all integers < m. If it doesn't hold for m, then it doesn't hold for any integer > m. What algorithm does this suggest?

If you want to spoil yourself, click here for the algorithm.

Upvotes: 4

Related Questions