EQUATION SOLVER absurd result despite correct algorithm

Question

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
void bisect(float *p,int n,int a);
float value(float *p,int n,int a);
int main()
{
    int a,i;
    float *p;
    printf("enter the degree of the polynomial\n");
    scanf("%d",&a);
    p=(float *) malloc(a*sizeof(float));
    for(i=0;i<=a;i++)
    {
        printf("enter the coefficient of x^%d\n",i);
        scanf("%f",p+i);
    }
    printf("%f\n",value(p,-2,a));
    printf("%f\n",value(p,1,a));
    printf("%f\n",value(p,0,a));
    for(i=-100;i<100;i++)
    {
        if(value(p,i,a)*value(p,i+1,a)==0.000)
        {
            printf("%d\n",value(p,i+1,a));
            if(value(p,i,a)==0&&value(p,i+1,a)==0.00)
            {
                printf("the roots are %d,%d\n",i,i+1);
            }
            if(value(p,i+1,a)==0.0)
            {
                printf("the real root is %d\n",i+1);
                i++;
                continue;
            }
        }

        if(value(p,i,a)*value(p,i+1,a)<0)
        {
            bisect(p,i,a);
        }
    }
    return 0;
}
float value(float *p,int n,int a)
{
    float sum=0.0;
    int i;
    for(i=0;i<=a;i++)
    {
        sum=sum+*(p+i)*pow(n,i);
    }
    return sum;
}

void bisect(float *p,int n,int a)
{
    float j,k,l;
    int i;
    j=n;k=n+1;l=(j+k)/2;
    for(i=0;i<50;i++)
    {
        if(value(p,j,a)*value(p,l,a)==0){break;}
        if(value(p,j,a)*value(p,l,a)<0)
        {
            j=j;k=l;l=(j+k)/2;
        }
        else if(value(p,l,a)*value(p,k,a)<0)
        {
            l=(l+k)/2;j=l;
        } 
    }
    printf("the root of the equation is %f\n",l);
}

I tried inserting print statements in the main function, and found that the value function is giving absurd results for simple polynomials, but the roots are correct for some polynomials but wrong for many. Why would the roots be correct for some if the algorithm was wrong?

I forget who said it, but he who compares floating points directly is living in a state of sin. — Foon, Jun 13 '15 at 12:36
or `p=(float *) malloc(a*sizeof(float));` change to `p=(float *) malloc((a+1)*sizeof(float));` — BLUEPIXY, Jun 13 '15 at 12:51
A few examples of input and output would be nice. This is recommended in [Creating an MCVE](http://stackoverflow.com/help/mcve). — Jongware, Jun 13 '15 at 12:53
alright...please forget about the printf statements since they are meant to find out which part of the code is incorrect but they are not a part of the code, ... even a+1 doesn't work because there is a lot of space in stack for this small code that it can accomodate more float variables without allocating, the mistake is something else — BootTrap, Jun 13 '15 at 16:11
I have done all the changes given by all the users the code just gives the result for integers but not float solutions(decimal) please help... — BootTrap, Jun 13 '15 at 18:14
"value function is giving absurd results for simple polynomials" --> 1) What is the absurd value? 2) What are the coefficient of the simple polynomial? 3) How you expect `float` solutions since `bisect()` is only stepping in integer steps? — chux - Reinstate Monica, Jul 08 '15 at 19:41
Please compile your code with the option `-Wall` (as you should always do to ensure clean code without "easy" mistakes) to capture implicit downcasting from `float` to `int` that is responsible for part of your problems. Roots are almost certainly not integers. — Lutz Lehmann, Jul 10 '15 at 19:11

score 2 · Answer 1 · edited May 23 '17 at 10:26

2

There are so many problems in your code:

In main method,

printf("%d\n",value(p,-2,a));

Compiler should give you warning:

warning: format '%d' expects argument of type 'int', but argument 2 has type 'double'

Use %f instead of %d as value() returns float.

You are not allocating enough space and you are casting the return value of malloc. Casting the return value of malloc should be avoided since malloc returns a void * (which means that it needs no cast) and casting the return value can conceal errors. You can read more about this issue here.

p = (float *) malloc(a*sizeof(float));

to

p=malloc((a+1) * sizeof *p);

You are comparing floating ponit number here:

if(value(p,i,a)==0&&value(p,i+1,a)==0.00)

Don't do this, read What Every Computer Scientist Should Know About Floating-Point Arithmetic for the reason. You can use one of this (e.g nearlyEqual()) functions for your purpose.

In method bisect():

j=j;k=l;l=(j+k)/2; // j = j, kidding?

edited May 23 '17 at 10:26

Community

1
1

answered Jun 13 '15 at 12:48

mazhar islam

5,561
3
20
41

1

Never cast the return value of Malloc. It returns a `void *` and casting it can conceal errors. http://stackoverflow.com/questions/953112/should-i-explicitly-cast-mallocs-return-value – David Hoelzer Jun 13 '15 at 13:06
1

Now you suggest a correction and then immediately recommend that it not be done. – David Hoelzer Jun 13 '15 at 13:11
@rakeb.void i have tried all your suggestions, instead of comparing two float variables i defined epsilon using #define as pow(10,-34) and using the fabs function i applied that change yet the program doesnt work, it is giving all the roots of the polynomial which are integer but i got to find the decimal roots too...please help – BootTrap Jun 13 '15 at 18:10
Give some sample `input output`, did you fix the `j = j` bug? And tell me what's the purpose of these `for` loops, `for(i=-100;i<100;i++)` in `main` and `for(i=0;i<50;i++)` in `bisect`. – mazhar islam Jun 13 '15 at 19:12
for the polynomial x^2-2.5x+1.5 should give you roots 1 and 1.5...And the use of for loops is that in bisection method the first root is checked randomly by checking the change of sign between two integer values, since we don't know where the root lies the initial for loop guesses it if the roots lies between -100 and +100, And the second for loop is the number of iterations you want to make for the bisection method, it actually doesn't matter much as even i<20 works out to get a 5 significant figure perfect root.. and j=j is not any bug and i know its not needed but there is no fault with it. – BootTrap Jun 14 '15 at 14:48
Actually, `j=j` is not an error, just a reminder that the left point `j` remains unchanged. The second branch however has a grave error in that at its end one has `j==l`, the interval is shrunk to a single point. And it is not consistent what the interval end points and the midpoint are, j,l,k are mixed liberally in these roles. – Lutz Lehmann Jul 08 '15 at 16:00
`p=malloc((a+1) * sizeof(p));` is not correct. Should be `p=malloc((a+1) * sizeof *p);` `*p` vs `p`. – chux - Reinstate Monica Jul 08 '15 at 19:23

Lutz Lehmann · Answer 2 · 2015-07-10T19:07:25.863

The biggest conceptual or mathematical error (apart from the programming errors explained in the other answer) is that you use integers for the arguments in the value function. It is rarely the case that random polynomials have integer roots. Rename n to x for intuitive readability and set the type of x to float.

Check again your assignment, if the prototype is really value(p,n,a), then maybe the intention is that n is the degree and a the evalution point, thus the signature should be (*float,int,float).

Using this signature, you should really use the Horner scheme to evaluate densely coded polynomials

float value(float *p, int deg, float a) {
    int i;
    float val = p[deg];
    for(i=deg; i-- > 0; ) val = val*a+p[i];
    return val;
}

and use descriptive names for variables in the bisection method (instead of j,k,l usually associated to integers) to avoid mixing them up

float left=a, right = a+1, mid =(left+right)/2;

etc.

EQUATION SOLVER absurd result despite correct algorithm

2 Answers2