Incorrect Output when applying Divide & Conquer

Question

I have to solve an one-root equation in an interval, using Divide & Couquer. Here is my code:

#include<bits/stdc++.h>

double coef[4];
int d=3;

double f(double x){
    int i;
    double res;
    for(i=0;i<=d;i++) res+=coef[i]*pow(x,i);
    return res;
}

double solve(double left,double right){
    double mid=(left+right)/2;

    if(abs(f(mid))<=1e-8) return mid;
    if(right-left<=1e-4) return mid;

    printf("%.4f %.4f %.4f\n",left,mid,right);

    if(f(mid)*f(left)>=0) return solve(mid,right); 
    if(f(mid)*f(right)>=0) return solve(left,mid);
}

int main(){

    coef[0]=-10;
    coef[1]=0;
    coef[2]=0;
    coef[3]=1.5;

    printf("%lf\n",solve(-10,10));
}

Then I use it to solve 1.5x^3-10=0 with two bound -10 and 10, but it seems to me that if(f(mid)*f(right)>=0) return solve(left,mid); doesn't work at all.

-10.0000 0.0000 10.0000
0.0000 5.0000 10.0000
5.0000 7.5000 10.0000
7.5000 8.7500 10.0000
8.7500 9.3750 10.0000
9.3750 9.6875 10.0000
9.6875 9.8438 10.0000
9.8438 9.9219 10.0000
9.9219 9.9609 10.0000
9.9609 9.9805 10.0000
...

I know that the root of the equation is 1.8821 so the output is incorrect.

The same happens with [-20, 20].

If I test with [-1.000.000, 1.000.000] the output gives me the root 500000.0000 which is clearly incorrect.

So what's wrong with my function solve()?

Any help will be highly appreciated!

So did you debug your code? What did you observe when you debugged your code? What values were being passed on each recursive call? And please post a [mcve] instead of a description of how you're using this function. — PaulMcKenzie, Nov 18 '18 at 09:09
@PaulMcKenzie Actually I'm very new to C++, I don't even know how to debug :) I'm using Dev-C++ and is that the button in the bottom? — , Nov 18 '18 at 09:13
Debugging code is part and parcel of learning how to write programs -- you will need to learn it fast, as you can't write anything beyond toy programs without learning how to use the debugger. Dev-C++ is an IDE (a very old one), and not a compiler. So I don't know where the debug "button" is. — PaulMcKenzie, Nov 18 '18 at 09:15
About *completeness*: You should at least post the implementation of your `f` function. Your comparisons `f*f >= 0` appear suspect to me, but can only really tell upon knowing `f`'s implementation... — Aconcagua, Nov 18 '18 at 09:21
@PaulMcKenzie I edited my question so that you can compile my code. I think that the `printf(...);` command in `solve()` is enough to know what values were being passed on each recursive call. — , Nov 18 '18 at 09:22
@Aconcagua what they're trying to do with those multiplications is to detect whether the sign changes in that interval. A more intuitive check would probably be `f(mid) * f(right) < 0` instead of `f(mid) * f(left) >= 0`. — Pezo, Nov 18 '18 at 09:23
@joule_voo Also [don't do this](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — PaulMcKenzie, Nov 18 '18 at 09:25
@Hiroki C++ overloads `abs` to work with real numbers as well, so OP should be fine. — HolyBlackCat, Nov 18 '18 at 09:31
@WilliamLee Actually I checked the function -- it works quite well, or I'm not testing a good input. Could you please give me one example in which `f(x)` doesn't work? — , Nov 18 '18 at 09:31
One problem is probably that stupid header I pointed out. @joule_voo -- Please use the proper headers, i.e. `` and ``, not the one you're using now. — PaulMcKenzie, Nov 18 '18 at 09:32
@HolyBlackCat thx. I think that is true when `using namespace std` is declared. I noticed that `res` is not initialized. — Hiroki, Nov 18 '18 at 09:32
@PaulMcKenzie Yes, I checked, not only `cmath` and `cstdio`, but also `stdio.h`, `math.h`... . The command I asked worked, but (1) the recursive process ends sooner than expected (it ends when `left = 0, right = 2.5, and mid = 1.25`, and (2) the root returned is surprisingly `-44.0292`. — , Nov 18 '18 at 09:36
Well, you do have a variable that is uninitialized, which was pointed out in the previous comment. — PaulMcKenzie, Nov 18 '18 at 09:37

Hiroki · Accepted Answer · 2018-11-18T10:14:46.530

0

In your code, res is not initialized in f which sould be initialized as zero.

In addition, abs should be replaced by std::fabs or std::abs if you don't type using namespace std;.

Fixing these two points, it will work fine.

DEMO is here.

edited Nov 18 '18 at 10:14

answered Nov 18 '18 at 09:39

Hiroki

2,780
3
12
26

Oh, I get it now! Thank you Hiroki, as well as many people who have helped me much in the comments! – Nov 18 '18 at 09:41

score 0 · Answer 2 · answered Nov 18 '18 at 10:18

0

res should be initialised in the function f(double x)
and
using namespace std;
should be used to provide scope for your variables

answered Nov 18 '18 at 10:18

kanishk verma

382
2
9

Incorrect Output when applying Divide & Conquer

2 Answers2