[Ghoser777]

I'm teaching an algebra class while I'm doing my student teaching experience (over in a week!) and I decided to write a tiny little C program that would do brute force polynomial long division. Unfortunately, I'm running into some weird results. Here's my code:

main.c

Code:
#include <stdio.h>
#include "LongDivider.h"

int main (int argc, const char * argv[]) 
{
    Polynomial dividend;
    Polynomial divisor;
    Polynomial *remainder;
    Polynomial *quotient;
    
    dividend.length = 3;
    dividend.coefficients = (double*)malloc(sizeof(double)*3); 
    (dividend.coefficients)[0] = 1;
    (dividend.coefficients)[1] = -5;
    (dividend.coefficients)[2] = 6;
    
    divisor.length = 2;
    divisor.coefficients = (double*)malloc(sizeof(double)*2); 
    (divisor.coefficients)[0] = 1;
    (divisor.coefficients)[1] = -3;
    
    quotient = dividePolynomial(&dividend,&divisor,remainder);
    
    printPolynomial(quotient);
    
    printf(" + (");
    
    printPolynomial(remainder);
    
    printf(")/(");
    
    printPolynomial(&divisor);
    
    printf(")\n");
    
    fflush(stdout);
    
    return 0;
}

LongDivide.h

Code:
#ifndef __LONG_DIVIDER_H__
#define __LONG_DIVIDER_H__

#include <stdlib.h>

struct PolyStruct
{
    double *coefficients;
    int length;
};
typedef struct PolyStruct Polynomial;


void dissposePolynomial(Polynomial *poly);

Polynomial *dividePolynomial(Polynomial *dividend, Polynomial *divisor, Polynomial *remainder);

void printPolynomial(Polynomial *poly);

#endif

LongDivide.c

Code:
#include "LongDivider.h"
#include "stdio.h"

void dissposePolynomial(Polynomial *poly)
{
    free((*poly).coefficients);
}

Polynomial *dividePolynomial(Polynomial *dividend, Polynomial *divisor, Polynomial *remainder)
{
    remainder = (Polynomial*)malloc(sizeof(Polynomial));
    Polynomial *quotient = (Polynomial*)malloc(sizeof(Polynomial));
    
    int divisorLength = (*divisor).length;
    int dividendLength = (*dividend).length;
    int quotientLength = dividendLength-divisorLength+1;
    
    (*remainder).coefficients = (double*)malloc(sizeof(double)*(dividendLength-1));
    (*quotient).coefficients = (double*)malloc(sizeof(double)*(quotientLength));
    (*quotient).length = quotientLength;
    
    int dividendLocation = 0;
    int quotientLocation = 0;
    
    while(dividendLength - dividendLocation >= divisorLength)
    {
        //find value for first quotientLocation
        double val = ((*dividend).coefficients)[dividendLocation]/((*divisor).coefficients)[0];
        ((*quotient).coefficients)[quotientLocation] = val;
        
        int i;
        int j = dividendLocation;
        int continuousZeros = 1;
        
        for(i=0; i<divisorLength; i++)
        {
        
            ((*dividend).coefficients)[j+i] -= val*((*divisor).coefficients)[i];
            
            if(continuousZeros == 1 && ((*dividend).coefficients)[j+i]==0.0)
            {
                quotientLocation++;
                ((*quotient).coefficients)[quotientLocation] = 0;
                
                dividendLocation++;
            }
            else
                continuousZeros = 0;
        }
    }
    
    while(quotientLocation < quotientLength)
    {
        ((*quotient).coefficients)[quotientLocation] = 0;
        quotientLocation++;
    }
    
    //what is the remainder?
    int k;
    int l = 0;
    int contZeros = 1;
    
    (*remainder).length = dividendLength - dividendLocation;
    
    for(k=dividendLocation; k<dividendLength; k++)
    {
        if(contZeros == 1 && ((*dividend).coefficients)[k] == 0.0)
        {
            (*remainder).length--;
        }
        else
        {
            contZeros = 0;
            ((*remainder).coefficients)[l] = ((*dividend).coefficients)[k];
            l++;
        }
    }
    
    return quotient;
}

void printPolynomial(Polynomial *poly)
{
    int i;
    int length = (*poly).length;
    
    for(i=0; i<length; i++)
    {
        if(i != 0)
            printf(" + ");
    
        printf("%fx^%d",((*poly).coefficients)[i],length-i-1);
    }
}

The weirdness starts when I try to print out the remainder. If I call printPolynomial(remainder) inside of dividePolynomial, then the remainder is properly printed. But if I try to print it from my main method, nothing is printed! I don't think there should be any scope issues as I malloced my Polynomial and didn't counter balance it with any frees yet, or call the dispose method I wrote.

Does anyone see what's wrong? (I can explain a little more what Polynomial Long Division is if so desired).

Thanks,
Matt Fahrenbacher

[Detrius]

Here's some basics that I see right off the bat:

- You labled the file as LongDivide.h, but your code refers to it as LongDivider.h. I suspect that is not the problem as you should at least be getting warnings about this.

- In main, you #include <stdio.h> but in LongDivide, you #include "stdio.h" which may be the problem.

If that doesn't fix it, let us know and I'll look more in-depth at the code.

[Detrius]

One more detail, just as a style recommendation:

instead of ((*remainder).coefficients)[1], you can do remainder->coefficients[1]

[Ghoser777]

Bah, minor things =D

I did get the proble to go away if I did the following:

- In my main.m, I declared remainder as a Polynomial instead of a pointer to a Polynomial.

- Because my remainder object is now created, I don't need to malloc anything for remainder (except for the double*) in my dividePolynomial method.

Weird. I have no idea why this is happening. You should be able to do this, right?

Code:
int main()
{
    int *ptr;
    int i;

    foo(ptr);

    for(i=0; i<5; i++)
        printf("%d\n",i);

    free(ptr);

    return 0;
}

void foo(int *ptr)
{
    int i = 0;

    ptr = (int *)malloc(sizeof(int)*5);
    for(i=0; i<5; i++)
        ptr[i] = i;
}

Or is there something wrong with doing something like this?


Thanks,
Matt Fahrenbacher

[Detrius]

I think I figured out your problem:

int *foo;

declares a pointer to an int.

bar(foo);

passes the VALUE of foo, which at this point is an undefined pointer to a memory location. You ARE actually having scope issues. You change foo inside of bar() by assigning a memory block to it. This doesn't leave bar() because main() has no way of knowing the new VALUE, so foo inside of main still has the original undefined pointer value. You need to pass an address such that main() can use the results. Here's what you need:

Code:

void bar(int **foo);

int main(void)
{
   int *foo;
   bar(&foo);
   // do something with *foo
   free(foo);
   return;
}

void bar(int **foo)
{
   *foo = (int)malloc(sizeof(int));
   return;
}

[Ghoser777]

Gah! Duh... I'm a moron.

I will now go hide my head in shame (or realize why I like working in Objective-C so much).

Thanks,
Matt Fahrenbacher

[Detrius]

Originally posted by Ghoser777:
Gah! Duh... I'm a moron.

I will now go hide my head in shame (or realize why I like working in Objective-C so much).

Thanks,
Matt Fahrenbacher

Well, technically, the same thing would be true of Objective-C... and glad I could help.


Hank

[Ghoser777]

Originally posted by Detrius:
Well, technically, the same thing would be true of Objective-C... and glad I could help.


Hank

True, but I could use Foundation objects in Objective-C (I understand the whole superset idea though).

Thanks,
Matt Fahrenbacher