Programming Forums > Application Development > C

Sane · Oct 7th, 2006, 11:59 AM

This was for a bonus mark in my class... I felt like taking on the challenge. I got it working, but I'd like some feedback on the code. I finally got a book, so I'm learning some better habits. But this is still really only my second program in C...

Yay for bonus marks!

Example Session:

(Toggle Plain Text)

What's the highest degree in the polynomial? 4

Enter degree #4's coefficient: 4
Enter degree #3's coefficient: -4
Enter degree #2's coefficient: -51
Enter degree #1's coefficient: 106
Enter degree #0's coefficient: -40

The factored equation is: f(x) = (x - 2)(x + 4)(2x - 5)(2x - 1)

Press any key to continue . . .

Limitations:
- does not work if there is a factorable constant, or xs!
- does not work if there is only a degree of 2, 1 or 0
- does not work if not fully factorable

I tried synthetically recreating the functionality of a class using structures and functions that manipulate its data. This was not mentioned in my book, so I was wondering what programmers generally think about this approach?

calculus.c:

(Toggle Plain Text)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <stdbool.h>

typedef struct {                                
        // this structure behaves synthetically as the instance of the class
        unsigned int i, x, lim, last;
        unsigned char increment;
        _Bool is_done, is_prime, osc, is_done_osc;
        //int (*scs_pull) (scs_obj);
} scs_obj;  

_Bool is_prime (unsigned int x) {
        unsigned int i;
        if (x <= 1) {
                return (false);
        }
        if (x == 2) {
                return (true);
        }
        if (x < 9) {
                return (x%2);
        }
        if (x%2 == 0) {
                return (false);
        }        
        for (i=3 ; i<=sqrt(x) ; i+=2) {
                if (x%i == 0) {
                        return (false);
                }
        }
        return (true);
}                                    

int scs_pull (scs_obj *self) {                  
        // pull the next positive factor from x 
        assert (self->is_done == false);
        if (self->i == 0) {                     // post-initiation
                self->i = 1;                    // exit post initiation condition
                return (1);                     // 1 is the first factor
        }
        if (self->x == 0) {                     // 0 has no factors 
                self->is_done = true;
                return (0);                     // the function handler will have to realise 0 implies no factors
        }
        if (self->x == 1) {                     // 1 only has 1 factor
                self->is_done = true;
                return (1);                     // we do this instead of returning two 1s, which could look a little strange
        }
        if (self->is_prime) {
                self->is_done = true;           // if the number is prime, we already returned 1, now just return x and we're done
                return (self->x);
        }
        if (self->i == 1) {                     // post, post initiation
                if (self->x%2 == 0) {           // this is tested in pull, rather than init, so that we can return (2)
                        if (self->x == 2)
                                self->is_done = true; // we do this instead of returning two 2s, which would look a little strange
                        self->i = 2;            // 2 will be incremented to 3 next call
                        return (2);
                }
                self->i = 1;                    // 1 will be incremented to 3 next call
                self->increment = 2;            // if it's not divisible by 2, we only have to check 3, 5, 7, 9, etc...
        }
        self->i += self->increment;             // we didn't increment before exiting the last function call, so we will now
        while (self->i <= self->lim) {
                if (self->x % self->i == 0) {
                        return (self->i);
                }
                self->i += self->increment;
        }
        self->is_done = true;                   // exhaust the class
        return (self->x);                       // x is the last factor
}

int scs_pull_all (scs_obj *self) {              
        // pull the next positive/negative factor from x
        self->osc = !self->osc;
        if (self->osc) {
                if (self->is_done_osc) {
                        self->is_done = true;
                }    
                return -(self->last);
        }
        else {
                self->last = scs_pull (self);
                if (self->is_done) {
                        self->is_done_osc = true; // we still need to get the last negative factor, even though the object thinks we're done
                        self->is_done = false;
                }    
                return (self->last);
        }
}

void scs_init (scs_obj *self, int x) {          
        // initiate the factoring object, with x, to be factored
        assert (x >= 0);                        // we won't allow factoring negative numbers
        self->x           = x;                  // the number to be factored
        self->i           = 0;                  // 0 is the unique identifier for scs_pull to realise post-initiation
        self->lim         = x/2;                // x can not be divisible by a number greater than x/2
        self->increment   = 1;                  // how much we increment _i_ by
        self->is_prime    = is_prime(x);        // if the number is prime, we know its factors
        self->osc         = true;               // the oscillator for pull_all
        self->is_done_osc = false;              // to assure the last factor's negative is pulled as well
        self->is_done     = false;              // to let the class handler know when all factors have been pulled
        //self->scs_pull    = scs_pull;
}

void divide (int x, int r, int size, int *p, int *res) {
        // divide polynomial p by (x+r), and dump into res, using long division
        // !!assumes p(-r/x) = 0
        float last, deposit;
        unsigned char i;
        deposit = p[0];
        for (i=1 ; i<size ; i++) {
                last = deposit / x;
                res[i-1] = last;
                deposit = p[i] - ( r*last );
        }    
}

int function (int *p, int size, double x) {
        // evaluate res = p(x), where the degree of p = size
        char i;
        double power = 1;
        double res = 0;
        for (i=size-1 ; i>=0 ; i--) {            /* do it in reverse to avoid the need for a power function */
                res += p[i] * power; // p[i] is converted in to double before getting multiplied by power
                power *= x;
        }
        return (res);
}

void reduce (int a, int b, int *resa, int *resb) {
        // reduce the fraction a/b to resa/resb
        unsigned char f1, f2, rf1, rf2;
        unsigned int absa, absb;
        
        absa = abs(a);
        absb = abs(b);
        
        scs_obj a_factors;
        scs_obj b_factors;
           
        /* 
        Let a = any positive value
            f = factor of "a"
            rf = the reverse factor of "f" (e.g. 8 -> 2's reverse is 4)
            
        "a / f" = "rf", because we want the highest common first.
        since "a / rf" = "f", therefore the simplified fraction ("a / rf") is "f".
        
        to make sure we aren't dividing each value by 1, we need "rf" > 1.
        since "a / f" = "rf", therefore "a / f" > 1, then "a" > "f".
        
        Note: "rf" must be the same as the other "rf", because that
        is what we have divided by, and that must be the same to keep the
        fraction true.
        */   
        
        scs_init (&a_factors, absa);        
        while (a_factors.is_done == 0) {
                f1 = scs_pull (&a_factors); 
                rf1 = absa / f1; 
                scs_init (&b_factors, absb);
                while (b_factors.is_done == 0) {
                        f2 = scs_pull (&b_factors);
                        rf2 = absb / f2;
                        if (rf1 == rf2 && absa > f1) {
                                *resa = f1;
                                *resb = f2;
                                if (a < 0) {            // follow the sign of the original number
                                         *resa = -*resa;
                                }
                                if (b < 0) {                // if there is a negative on the bottom           
                                         *resa = -*resa;    // flip the top sign
                                         // *resb = -*resb; // flip the bottom sign
                                         // *resb = -*resb; // follow the sign of the original number   // rendundant
                                }
                                return;
                        }       
                }
        }
        *resa = a;
        *resb = b;
        if (b < 0) {                // if there is a negative on the bottom           
                *resa = -*resa;     // flip the top sign
                *resb = -*resb;     // flip the bottom sign
        }
}

void quadratic (int a, int b, int c, int *x1a, int *x1b, int *x2a, int *x2b) {
        // factor the quadratic (0 = ax^2 + bx + c) to (x1a-x1b)(x2a-x2b)
        int product, bf = 0, f = 0;
        scs_obj p_factors;
        
        product = a*c;
        scs_init (&p_factors, abs(product));        
        while ((p_factors.is_done == 0) && (f*bf != product)) {
                f = scs_pull_all (&p_factors);
                bf = b-f;
        }

        reduce (bf, a, x1b, x1a);
        reduce (f, a, x2b, x2a);
}

void display (int x, int a) {
        // output the data in mathematical form
        if (x == 1) {
                printf ("(x ");
        }
        else {
                printf ("(%ix ", x);
        }
        
        if (a < 0) {
                printf ("+ %i)", -a);
        }
        else {
                printf ("- %i)", a);
        }
}

int main () {
        // fully factor a polynomimial
        // Limitations:
        //  - does not work if there is a factorable constant, or xs!
        //  - does not work if there is only a degree of 2, 1 or 0
        //  - does not work if not fully factorable
        
        int i, fp, fq, size;
        int qx1, qa1, qx2, qa2;
        int *p, *tempp;
        scs_obj p_factors;
        scs_obj q_factors;
        _Bool hold = false;
    
        printf ("What's the highest degree in the polynomial? ");
        scanf ("%i", &size);
        printf ("\n");
        size ++; // the constant term needs to be included

        p = malloc (size*sizeof(int));
        for (i=0 ; i < size ; i++) {
                printf ("Enter degree #%i's coefficient: ", size-i-1);
                scanf ("%i", &p[i]);
        }
        printf ("\nThe factored equation is: f(x) = ");
        
        // 1, -8, -3, 90
        // 4, -4, -51, 106, -40

        scs_init (&q_factors, abs(p[0])); // reinit these?
        while (q_factors.is_done == false) {
                fq = scs_pull (&q_factors); // fp will cover the negatives
                scs_init (&p_factors, abs(p[size-1]));
                while (p_factors.is_done == false) {
                        if (hold) {
                                hold = false;
                        }
                        else {
                                fp = scs_pull_all (&p_factors);
                        }   
                        // printf ("%i"
                        if (function (p, size, fp/fq) == 0) { // test for p(f) = 0
                                display (fq, fp);
                                tempp = malloc ((size-1)*sizeof(int)); // allocate tempp to one shorter than original
                                divide (fq, -fp, size, p, tempp); // pass in tempp to inherit p
                                size --;
                                p = realloc (p, size*sizeof(int)); // we need to reallocate since it's now one shorter??
                                memcpy (p, tempp, size*sizeof(int)); // copy tempp to original
                                free (tempp);
                                //scs_init (&q_factors, abs(p[0]));
                                //scs_init (&p_factors, abs(p[size-1]));
                                hold = true; // try the same factor again, it can work successively!
                                if (size == 3) { // quadratic
                                        p_factors.is_done = true;
                                        q_factors.is_done = true; // exit the nested while loop
                                }
                        }
                }    
        } 
        quadratic (p[0], p[1], p[2], &qx1, &qa1, &qx2, &qa2);
        display (qx1, -qa1);
        display (qx2, -qa2);
        free (p);
        
        printf ("\n\n");
        system ("PAUSE");
        return (0);
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <stdbool.h>

typedef struct {                                
        // this structure behaves synthetically as the instance of the class
        unsigned int i, x, lim, last;
        unsigned char increment;
        _Bool is_done, is_prime, osc, is_done_osc;
        //int (*scs_pull) (scs_obj);
} scs_obj;  

_Bool is_prime (unsigned int x) {
        unsigned int i;
        if (x <= 1) {
                return (false);
        }
        if (x == 2) {
                return (true);
        }
        if (x < 9) {
                return (x%2);
        }
        if (x%2 == 0) {
                return (false);
        }        
        for (i=3 ; i<=sqrt(x) ; i+=2) {
                if (x%i == 0) {
                        return (false);
                }
        }
        return (true);
}                                    

int scs_pull (scs_obj *self) {                  
        // pull the next positive factor from x 
        assert (self->is_done == false);
        if (self->i == 0) {                     // post-initiation
                self->i = 1;                    // exit post initiation condition
                return (1);                     // 1 is the first factor
        }
        if (self->x == 0) {                     // 0 has no factors 
                self->is_done = true;
                return (0);                     // the function handler will have to realise 0 implies no factors
        }
        if (self->x == 1) {                     // 1 only has 1 factor
                self->is_done = true;
                return (1);                     // we do this instead of returning two 1s, which could look a little strange
        }
        if (self->is_prime) {
                self->is_done = true;           // if the number is prime, we already returned 1, now just return x and we're done
                return (self->x);
        }
        if (self->i == 1) {                     // post, post initiation
                if (self->x%2 == 0) {           // this is tested in pull, rather than init, so that we can return (2)
                        if (self->x == 2)
                                self->is_done = true; // we do this instead of returning two 2s, which would look a little strange
                        self->i = 2;            // 2 will be incremented to 3 next call
                        return (2);
                }
                self->i = 1;                    // 1 will be incremented to 3 next call
                self->increment = 2;            // if it's not divisible by 2, we only have to check 3, 5, 7, 9, etc...
        }
        self->i += self->increment;             // we didn't increment before exiting the last function call, so we will now
        while (self->i <= self->lim) {
                if (self->x % self->i == 0) {
                        return (self->i);
                }
                self->i += self->increment;
        }
        self->is_done = true;                   // exhaust the class
        return (self->x);                       // x is the last factor
}

int scs_pull_all (scs_obj *self) {              
        // pull the next positive/negative factor from x
        self->osc = !self->osc;
        if (self->osc) {
                if (self->is_done_osc) {
                        self->is_done = true;
                }    
                return -(self->last);
        }
        else {
                self->last = scs_pull (self);
                if (self->is_done) {
                        self->is_done_osc = true; // we still need to get the last negative factor, even though the object thinks we're done
                        self->is_done = false;
                }    
                return (self->last);
        }
}

void scs_init (scs_obj *self, int x) {          
        // initiate the factoring object, with x, to be factored
        assert (x >= 0);                        // we won't allow factoring negative numbers
        self->x           = x;                  // the number to be factored
        self->i           = 0;                  // 0 is the unique identifier for scs_pull to realise post-initiation
        self->lim         = x/2;                // x can not be divisible by a number greater than x/2
        self->increment   = 1;                  // how much we increment _i_ by
        self->is_prime    = is_prime(x);        // if the number is prime, we know its factors
        self->osc         = true;               // the oscillator for pull_all
        self->is_done_osc = false;              // to assure the last factor's negative is pulled as well
        self->is_done     = false;              // to let the class handler know when all factors have been pulled
        //self->scs_pull    = scs_pull;
}

void divide (int x, int r, int size, int *p, int *res) {
        // divide polynomial p by (x+r), and dump into res, using long division
        // !!assumes p(-r/x) = 0
        float last, deposit;
        unsigned char i;
        deposit = p[0];
        for (i=1 ; i<size ; i++) {
                last = deposit / x;
                res[i-1] = last;
                deposit = p[i] - ( r*last );
        }    
}

int function (int *p, int size, double x) {
        // evaluate res = p(x), where the degree of p = size
        char i;
        double power = 1;
        double res = 0;
        for (i=size-1 ; i>=0 ; i--) {            /* do it in reverse to avoid the need for a power function */
                res += p[i] * power; // p[i] is converted in to double before getting multiplied by power
                power *= x;
        }
        return (res);
}

void reduce (int a, int b, int *resa, int *resb) {
        // reduce the fraction a/b to resa/resb
        unsigned char f1, f2, rf1, rf2;
        unsigned int absa, absb;
        
        absa = abs(a);
        absb = abs(b);
        
        scs_obj a_factors;
        scs_obj b_factors;
           
        /* 
        Let a = any positive value
            f = factor of "a"
            rf = the reverse factor of "f" (e.g. 8 -> 2's reverse is 4)
            
        "a / f" = "rf", because we want the highest common first.
        since "a / rf" = "f", therefore the simplified fraction ("a / rf") is "f".
        
        to make sure we aren't dividing each value by 1, we need "rf" > 1.
        since "a / f" = "rf", therefore "a / f" > 1, then "a" > "f".
        
        Note: "rf" must be the same as the other "rf", because that
        is what we have divided by, and that must be the same to keep the
        fraction true.
        */   
        
        scs_init (&a_factors, absa);        
        while (a_factors.is_done == 0) {
                f1 = scs_pull (&a_factors); 
                rf1 = absa / f1; 
                scs_init (&b_factors, absb);
                while (b_factors.is_done == 0) {
                        f2 = scs_pull (&b_factors);
                        rf2 = absb / f2;
                        if (rf1 == rf2 && absa > f1) {
                                *resa = f1;
                                *resb = f2;
                                if (a < 0) {            // follow the sign of the original number
                                         *resa = -*resa;
                                }
                                if (b < 0) {                // if there is a negative on the bottom           
                                         *resa = -*resa;    // flip the top sign
                                         // *resb = -*resb; // flip the bottom sign
                                         // *resb = -*resb; // follow the sign of the original number   // rendundant
                                }
                                return;
                        }       
                }
        }
        *resa = a;
        *resb = b;
        if (b < 0) {                // if there is a negative on the bottom           
                *resa = -*resa;     // flip the top sign
                *resb = -*resb;     // flip the bottom sign
        }
}

void quadratic (int a, int b, int c, int *x1a, int *x1b, int *x2a, int *x2b) {
        // factor the quadratic (0 = ax^2 + bx + c) to (x1a-x1b)(x2a-x2b)
        int product, bf = 0, f = 0;
        scs_obj p_factors;
        
        product = a*c;
        scs_init (&p_factors, abs(product));        
        while ((p_factors.is_done == 0) && (f*bf != product)) {
                f = scs_pull_all (&p_factors);
                bf = b-f;
        }

        reduce (bf, a, x1b, x1a);
        reduce (f, a, x2b, x2a);
}

void display (int x, int a) {
        // output the data in mathematical form
        if (x == 1) {
                printf ("(x ");
        }
        else {
                printf ("(%ix ", x);
        }
        
        if (a < 0) {
                printf ("+ %i)", -a);
        }
        else {
                printf ("- %i)", a);
        }
}

int main () {
        // fully factor a polynomimial
        // Limitations:
        //  - does not work if there is a factorable constant, or xs!
        //  - does not work if there is only a degree of 2, 1 or 0
        //  - does not work if not fully factorable
        
        int i, fp, fq, size;
        int qx1, qa1, qx2, qa2;
        int *p, *tempp;
        scs_obj p_factors;
        scs_obj q_factors;
        _Bool hold = false;
    
        printf ("What's the highest degree in the polynomial? ");
        scanf ("%i", &size);
        printf ("\n");
        size ++; // the constant term needs to be included

        p = malloc (size*sizeof(int));
        for (i=0 ; i < size ; i++) {
                printf ("Enter degree #%i's coefficient: ", size-i-1);
                scanf ("%i", &p[i]);
        }
        printf ("\nThe factored equation is: f(x) = ");
        
        // 1, -8, -3, 90
        // 4, -4, -51, 106, -40

        scs_init (&q_factors, abs(p[0])); // reinit these?
        while (q_factors.is_done == false) {
                fq = scs_pull (&q_factors); // fp will cover the negatives
                scs_init (&p_factors, abs(p[size-1]));
                while (p_factors.is_done == false) {
                        if (hold) {
                                hold = false;
                        }
                        else {
                                fp = scs_pull_all (&p_factors);
                        }   
                        // printf ("%i"
                        if (function (p, size, fp/fq) == 0) { // test for p(f) = 0
                                display (fq, fp);
                                tempp = malloc ((size-1)*sizeof(int)); // allocate tempp to one shorter than original
                                divide (fq, -fp, size, p, tempp); // pass in tempp to inherit p
                                size --;
                                p = realloc (p, size*sizeof(int)); // we need to reallocate since it's now one shorter??
                                memcpy (p, tempp, size*sizeof(int)); // copy tempp to original
                                free (tempp);
                                //scs_init (&q_factors, abs(p[0]));
                                //scs_init (&p_factors, abs(p[size-1]));
                                hold = true; // try the same factor again, it can work successively!
                                if (size == 3) { // quadratic
                                        p_factors.is_done = true;
                                        q_factors.is_done = true; // exit the nested while loop
                                }
                        }
                }    
        } 
        quadratic (p[0], p[1], p[2], &qx1, &qa1, &qx2, &qa2);
        display (qx1, -qa1);
        display (qx2, -qa2);
        free (p);
        
        printf ("\n\n");
        system ("PAUSE");
        return (0);
}

Jessehk · Oct 7th, 2006, 1:05 PM

I can tell you that the math went way over my head (:p), but when I compiled the program with extra warnings, a few things popped up.

(Toggle Plain Text)

$ gcc -Wall -Wextra calculus.c -lm -o calculus
calculus.c: In function ‘function’:
calculus.c:129: warning: array subscript has type ‘char’
calculus.c: In function ‘main’:
calculus.c:273: warning: implicit declaration of function ‘memcpy’
calculus.c:273: warning: incompatible implicit declaration of built-in function ‘memcpy’

But I'll let the people who actually know what they're talking about give any compliments or criticism to the coding style.

Sane · Oct 7th, 2006, 1:17 PM

Oh, I didn't build my code to be GCC standard. I haven't got to that chapter in my book yet.

It seems you can fix some of those things by changing the unsigned chars to unsigned ints (I was being a memory nazi).

Not sure about the implicit declaration of function memcpy, that might have to do with a missing library that Dev-C++ implicitely includes.

Regardless... It'll compile in something like Dev-C++.

And ... Hey! The math isn't really complicated. I learned it in school, and I was only 15 three days ago.

Prm753 · Oct 7th, 2006, 2:46 PM

You were only 15 three days ago? Well, I hope you had a happy birthday then.

Ah, even I can understand the math. The program compiled cleanly in Dev-C++. Nice work, Sane.

Sane · Oct 7th, 2006, 3:00 PM

Yep, I did. Got myself a nice O'Reilly Book for C.

The math is pretty easy. It's the application of grade 10/11 math composed into the "Factor Thereom", used in Calculus for factoring large polynomials. The hardest part in the math to wrap your head around is the function "divide", which is synthetically long dividing a polynomial by (x+r). That's the part you learn in grade 12, but it's incredibly simple (just an expansion of long division).

pufuwozu · Oct 8th, 2006, 12:26 AM

Change line 129 to this:

 C Syntax (Toggle Plain Text) 
res += p[(int)i] * power;
res += p[(int)i] * power;

Then add this:

C Syntax (Toggle Plain Text)

#include <string.h>

That makes it compile under GCC without any warnings.

Sane · Oct 8th, 2006, 12:49 AM

Converting i to an int every iteration is a tad bit silly, no? Why not just make the iterator an integer as I had proposed earlier?

pufuwozu · Oct 8th, 2006, 2:15 AM

Quote:

Originally Posted by Sane

Converting i to an int every iteration is a tad bit silly, no? Why not just make the iterator an integer as I had proposed earlier?

Oh yeah, sorry. I should probably think first.

Oct 8th, 2006, 12:26 AM	#6
pufuwozu Newbie Join Date: Oct 2006 Location: Brisbane, Australia Posts: 14 Rep Power: 0	Change line 129 to this: C Syntax (Toggle Plain Text) res += p[(int)i] * power; res += p[(int)i] * power; Then add this: C Syntax (Toggle Plain Text) #include <string.h> #include <string.h> That makes it compile under GCC without any warnings. __________________ The real DRM.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Degree questions	Patrick	Coder's Corner Lounge	7	Jun 15th, 2005 4:30 PM

Oct 7th, 2006, 11:59 AM	#1
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,076 Rep Power: 6	Fully Factoring A Polynomial Of A Dynamic Degree This was for a bonus mark in my class... I felt like taking on the challenge. I got it working, but I'd like some feedback on the code. I finally got a book, so I'm learning some better habits. But this is still really only my second program in C... Yay for bonus marks! Example Session: (Toggle Plain Text) What's the highest degree in the polynomial? 4 Enter degree #4's coefficient: 4 Enter degree #3's coefficient: -4 Enter degree #2's coefficient: -51 Enter degree #1's coefficient: 106 Enter degree #0's coefficient: -40 The factored equation is: f(x) = (x - 2)(x + 4)(2x - 5)(2x - 1) Press any key to continue . . . What's the highest degree in the polynomial? 4 Enter degree #4's coefficient: 4 Enter degree #3's coefficient: -4 Enter degree #2's coefficient: -51 Enter degree #1's coefficient: 106 Enter degree #0's coefficient: -40 The factored equation is: f(x) = (x - 2)(x + 4)(2x - 5)(2x - 1) Press any key to continue . . . Limitations: - does not work if there is a factorable constant, or xs! - does not work if there is only a degree of 2, 1 or 0 - does not work if not fully factorable I tried synthetically recreating the functionality of a class using structures and functions that manipulate its data. This was not mentioned in my book, so I was wondering what programmers generally think about this approach? calculus.c: (Toggle Plain Text) #include <stdio.h> #include <stdlib.h> #include <math.h> #include <assert.h> #include <stdbool.h> typedef struct { // this structure behaves synthetically as the instance of the class unsigned int i, x, lim, last; unsigned char increment; _Bool is_done, is_prime, osc, is_done_osc; //int (scs_pull) (scs_obj); } scs_obj; _Bool is_prime (unsigned int x) { unsigned int i; if (x <= 1) { return (false); } if (x == 2) { return (true); } if (x < 9) { return (x%2); } if (x%2 == 0) { return (false); } for (i=3 ; i<=sqrt(x) ; i+=2) { if (x%i == 0) { return (false); } } return (true); } int scs_pull (scs_obj self) { // pull the next positive factor from x assert (self->is_done == false); if (self->i == 0) { // post-initiation self->i = 1; // exit post initiation condition return (1); // 1 is the first factor } if (self->x == 0) { // 0 has no factors self->is_done = true; return (0); // the function handler will have to realise 0 implies no factors } if (self->x == 1) { // 1 only has 1 factor self->is_done = true; return (1); // we do this instead of returning two 1s, which could look a little strange } if (self->is_prime) { self->is_done = true; // if the number is prime, we already returned 1, now just return x and we're done return (self->x); } if (self->i == 1) { // post, post initiation if (self->x%2 == 0) { // this is tested in pull, rather than init, so that we can return (2) if (self->x == 2) self->is_done = true; // we do this instead of returning two 2s, which would look a little strange self->i = 2; // 2 will be incremented to 3 next call return (2); } self->i = 1; // 1 will be incremented to 3 next call self->increment = 2; // if it's not divisible by 2, we only have to check 3, 5, 7, 9, etc... } self->i += self->increment; // we didn't increment before exiting the last function call, so we will now while (self->i <= self->lim) { if (self->x % self->i == 0) { return (self->i); } self->i += self->increment; } self->is_done = true; // exhaust the class return (self->x); // x is the last factor } int scs_pull_all (scs_obj self) { // pull the next positive/negative factor from x self->osc = !self->osc; if (self->osc) { if (self->is_done_osc) { self->is_done = true; } return -(self->last); } else { self->last = scs_pull (self); if (self->is_done) { self->is_done_osc = true; // we still need to get the last negative factor, even though the object thinks we're done self->is_done = false; } return (self->last); } } void scs_init (scs_obj self, int x) { // initiate the factoring object, with x, to be factored assert (x >= 0); // we won't allow factoring negative numbers self->x = x; // the number to be factored self->i = 0; // 0 is the unique identifier for scs_pull to realise post-initiation self->lim = x/2; // x can not be divisible by a number greater than x/2 self->increment = 1; // how much we increment _i_ by self->is_prime = is_prime(x); // if the number is prime, we know its factors self->osc = true; // the oscillator for pull_all self->is_done_osc = false; // to assure the last factor's negative is pulled as well self->is_done = false; // to let the class handler know when all factors have been pulled //self->scs_pull = scs_pull; } void divide (int x, int r, int size, int p, int res) { // divide polynomial p by (x+r), and dump into res, using long division // !!assumes p(-r/x) = 0 float last, deposit; unsigned char i; deposit = p[0]; for (i=1 ; i<size ; i++) { last = deposit / x; res[i-1] = last; deposit = p[i] - ( rlast ); } } int function (int p, int size, double x) { // evaluate res = p(x), where the degree of p = size char i; double power = 1; double res = 0; for (i=size-1 ; i>=0 ; i--) { /* do it in reverse to avoid the need for a power function / res += p[i] power; // p[i] is converted in to double before getting multiplied by power power = x; } return (res); } void reduce (int a, int b, int resa, int resb) { // reduce the fraction a/b to resa/resb unsigned char f1, f2, rf1, rf2; unsigned int absa, absb; absa = abs(a); absb = abs(b); scs_obj a_factors; scs_obj b_factors; / Let a = any positive value f = factor of "a" rf = the reverse factor of "f" (e.g. 8 -> 2's reverse is 4) "a / f" = "rf", because we want the highest common first. since "a / rf" = "f", therefore the simplified fraction ("a / rf") is "f". to make sure we aren't dividing each value by 1, we need "rf" > 1. since "a / f" = "rf", therefore "a / f" > 1, then "a" > "f". Note: "rf" must be the same as the other "rf", because that is what we have divided by, and that must be the same to keep the fraction true. / scs_init (&a_factors, absa); while (a_factors.is_done == 0) { f1 = scs_pull (&a_factors); rf1 = absa / f1; scs_init (&b_factors, absb); while (b_factors.is_done == 0) { f2 = scs_pull (&b_factors); rf2 = absb / f2; if (rf1 == rf2 && absa > f1) { resa = f1; resb = f2; if (a < 0) { // follow the sign of the original number resa = -resa; } if (b < 0) { // if there is a negative on the bottom resa = -resa; // flip the top sign // resb = -resb; // flip the bottom sign // resb = -resb; // follow the sign of the original number // rendundant } return; } } } resa = a; resb = b; if (b < 0) { // if there is a negative on the bottom resa = -resa; // flip the top sign resb = -resb; // flip the bottom sign } } void quadratic (int a, int b, int c, int x1a, int x1b, int x2a, int x2b) { // factor the quadratic (0 = ax^2 + bx + c) to (x1a-x1b)(x2a-x2b) int product, bf = 0, f = 0; scs_obj p_factors; product = ac; scs_init (&p_factors, abs(product)); while ((p_factors.is_done == 0) && (fbf != product)) { f = scs_pull_all (&p_factors); bf = b-f; } reduce (bf, a, x1b, x1a); reduce (f, a, x2b, x2a); } void display (int x, int a) { // output the data in mathematical form if (x == 1) { printf ("(x "); } else { printf ("(%ix ", x); } if (a < 0) { printf ("+ %i)", -a); } else { printf ("- %i)", a); } } int main () { // fully factor a polynomimial // Limitations: // - does not work if there is a factorable constant, or xs! // - does not work if there is only a degree of 2, 1 or 0 // - does not work if not fully factorable int i, fp, fq, size; int qx1, qa1, qx2, qa2; int p, tempp; scs_obj p_factors; scs_obj q_factors; _Bool hold = false; printf ("What's the highest degree in the polynomial? "); scanf ("%i", &size); printf ("\n"); size ++; // the constant term needs to be included p = malloc (sizesizeof(int)); for (i=0 ; i < size ; i++) { printf ("Enter degree #%i's coefficient: ", size-i-1); scanf ("%i", &p[i]); } printf ("\nThe factored equation is: f(x) = "); // 1, -8, -3, 90 // 4, -4, -51, 106, -40 scs_init (&q_factors, abs(p[0])); // reinit these? while (q_factors.is_done == false) { fq = scs_pull (&q_factors); // fp will cover the negatives scs_init (&p_factors, abs(p[size-1])); while (p_factors.is_done == false) { if (hold) { hold = false; } else { fp = scs_pull_all (&p_factors); } // printf ("%i" if (function (p, size, fp/fq) == 0) { // test for p(f) = 0 display (fq, fp); tempp = malloc ((size-1)sizeof(int)); // allocate tempp to one shorter than original divide (fq, -fp, size, p, tempp); // pass in tempp to inherit p size --; p = realloc (p, sizesizeof(int)); // we need to reallocate since it's now one shorter?? memcpy (p, tempp, sizesizeof(int)); // copy tempp to original free (tempp); //scs_init (&q_factors, abs(p[0])); //scs_init (&p_factors, abs(p[size-1])); hold = true; // try the same factor again, it can work successively! if (size == 3) { // quadratic p_factors.is_done = true; q_factors.is_done = true; // exit the nested while loop } } } } quadratic (p[0], p[1], p[2], &qx1, &qa1, &qx2, &qa2); display (qx1, -qa1); display (qx2, -qa2); free (p); printf ("\n\n"); system ("PAUSE"); return (0); } #include <stdio.h> #include <stdlib.h> #include <math.h> #include <assert.h> #include <stdbool.h> typedef struct { // this structure behaves synthetically as the instance of the class unsigned int i, x, lim, last; unsigned char increment; _Bool is_done, is_prime, osc, is_done_osc; //int (scs_pull) (scs_obj); } scs_obj; _Bool is_prime (unsigned int x) { unsigned int i; if (x <= 1) { return (false); } if (x == 2) { return (true); } if (x < 9) { return (x%2); } if (x%2 == 0) { return (false); } for (i=3 ; i<=sqrt(x) ; i+=2) { if (x%i == 0) { return (false); } } return (true); } int scs_pull (scs_obj self) { // pull the next positive factor from x assert (self->is_done == false); if (self->i == 0) { // post-initiation self->i = 1; // exit post initiation condition return (1); // 1 is the first factor } if (self->x == 0) { // 0 has no factors self->is_done = true; return (0); // the function handler will have to realise 0 implies no factors } if (self->x == 1) { // 1 only has 1 factor self->is_done = true; return (1); // we do this instead of returning two 1s, which could look a little strange } if (self->is_prime) { self->is_done = true; // if the number is prime, we already returned 1, now just return x and we're done return (self->x); } if (self->i == 1) { // post, post initiation if (self->x%2 == 0) { // this is tested in pull, rather than init, so that we can return (2) if (self->x == 2) self->is_done = true; // we do this instead of returning two 2s, which would look a little strange self->i = 2; // 2 will be incremented to 3 next call return (2); } self->i = 1; // 1 will be incremented to 3 next call self->increment = 2; // if it's not divisible by 2, we only have to check 3, 5, 7, 9, etc... } self->i += self->increment; // we didn't increment before exiting the last function call, so we will now while (self->i <= self->lim) { if (self->x % self->i == 0) { return (self->i); } self->i += self->increment; } self->is_done = true; // exhaust the class return (self->x); // x is the last factor } int scs_pull_all (scs_obj self) { // pull the next positive/negative factor from x self->osc = !self->osc; if (self->osc) { if (self->is_done_osc) { self->is_done = true; } return -(self->last); } else { self->last = scs_pull (self); if (self->is_done) { self->is_done_osc = true; // we still need to get the last negative factor, even though the object thinks we're done self->is_done = false; } return (self->last); } } void scs_init (scs_obj self, int x) { // initiate the factoring object, with x, to be factored assert (x >= 0); // we won't allow factoring negative numbers self->x = x; // the number to be factored self->i = 0; // 0 is the unique identifier for scs_pull to realise post-initiation self->lim = x/2; // x can not be divisible by a number greater than x/2 self->increment = 1; // how much we increment _i_ by self->is_prime = is_prime(x); // if the number is prime, we know its factors self->osc = true; // the oscillator for pull_all self->is_done_osc = false; // to assure the last factor's negative is pulled as well self->is_done = false; // to let the class handler know when all factors have been pulled //self->scs_pull = scs_pull; } void divide (int x, int r, int size, int p, int res) { // divide polynomial p by (x+r), and dump into res, using long division // !!assumes p(-r/x) = 0 float last, deposit; unsigned char i; deposit = p[0]; for (i=1 ; i<size ; i++) { last = deposit / x; res[i-1] = last; deposit = p[i] - ( rlast ); } } int function (int p, int size, double x) { // evaluate res = p(x), where the degree of p = size char i; double power = 1; double res = 0; for (i=size-1 ; i>=0 ; i--) { / do it in reverse to avoid the need for a power function / res += p[i] power; // p[i] is converted in to double before getting multiplied by power power = x; } return (res); } void reduce (int a, int b, int resa, int resb) { // reduce the fraction a/b to resa/resb unsigned char f1, f2, rf1, rf2; unsigned int absa, absb; absa = abs(a); absb = abs(b); scs_obj a_factors; scs_obj b_factors; / Let a = any positive value f = factor of "a" rf = the reverse factor of "f" (e.g. 8 -> 2's reverse is 4) "a / f" = "rf", because we want the highest common first. since "a / rf" = "f", therefore the simplified fraction ("a / rf") is "f". to make sure we aren't dividing each value by 1, we need "rf" > 1. since "a / f" = "rf", therefore "a / f" > 1, then "a" > "f". Note: "rf" must be the same as the other "rf", because that is what we have divided by, and that must be the same to keep the fraction true. / scs_init (&a_factors, absa); while (a_factors.is_done == 0) { f1 = scs_pull (&a_factors); rf1 = absa / f1; scs_init (&b_factors, absb); while (b_factors.is_done == 0) { f2 = scs_pull (&b_factors); rf2 = absb / f2; if (rf1 == rf2 && absa > f1) { resa = f1; resb = f2; if (a < 0) { // follow the sign of the original number resa = -resa; } if (b < 0) { // if there is a negative on the bottom resa = -resa; // flip the top sign // resb = -resb; // flip the bottom sign // resb = -resb; // follow the sign of the original number // rendundant } return; } } } resa = a; resb = b; if (b < 0) { // if there is a negative on the bottom resa = -resa; // flip the top sign resb = -resb; // flip the bottom sign } } void quadratic (int a, int b, int c, int x1a, int x1b, int x2a, int x2b) { // factor the quadratic (0 = ax^2 + bx + c) to (x1a-x1b)(x2a-x2b) int product, bf = 0, f = 0; scs_obj p_factors; product = ac; scs_init (&p_factors, abs(product)); while ((p_factors.is_done == 0) && (fbf != product)) { f = scs_pull_all (&p_factors); bf = b-f; } reduce (bf, a, x1b, x1a); reduce (f, a, x2b, x2a); } void display (int x, int a) { // output the data in mathematical form if (x == 1) { printf ("(x "); } else { printf ("(%ix ", x); } if (a < 0) { printf ("+ %i)", -a); } else { printf ("- %i)", a); } } int main () { // fully factor a polynomimial // Limitations: // - does not work if there is a factorable constant, or xs! // - does not work if there is only a degree of 2, 1 or 0 // - does not work if not fully factorable int i, fp, fq, size; int qx1, qa1, qx2, qa2; int p, tempp; scs_obj p_factors; scs_obj q_factors; _Bool hold = false; printf ("What's the highest degree in the polynomial? "); scanf ("%i", &size); printf ("\n"); size ++; // the constant term needs to be included p = malloc (sizesizeof(int)); for (i=0 ; i < size ; i++) { printf ("Enter degree #%i's coefficient: ", size-i-1); scanf ("%i", &p[i]); } printf ("\nThe factored equation is: f(x) = "); // 1, -8, -3, 90 // 4, -4, -51, 106, -40 scs_init (&q_factors, abs(p[0])); // reinit these? while (q_factors.is_done == false) { fq = scs_pull (&q_factors); // fp will cover the negatives scs_init (&p_factors, abs(p[size-1])); while (p_factors.is_done == false) { if (hold) { hold = false; } else { fp = scs_pull_all (&p_factors); } // printf ("%i" if (function (p, size, fp/fq) == 0) { // test for p(f) = 0 display (fq, fp); tempp = malloc ((size-1)sizeof(int)); // allocate tempp to one shorter than original divide (fq, -fp, size, p, tempp); // pass in tempp to inherit p size --; p = realloc (p, sizesizeof(int)); // we need to reallocate since it's now one shorter?? memcpy (p, tempp, size*sizeof(int)); // copy tempp to original free (tempp); //scs_init (&q_factors, abs(p[0])); //scs_init (&p_factors, abs(p[size-1])); hold = true; // try the same factor again, it can work successively! if (size == 3) { // quadratic p_factors.is_done = true; q_factors.is_done = true; // exit the nested while loop } } } } quadratic (p[0], p[1], p[2], &qx1, &qa1, &qx2, &qa2); display (qx1, -qa1); display (qx2, -qa2); free (p); printf ("\n\n"); system ("PAUSE"); return (0); }

Oct 7th, 2006, 1:05 PM	#2
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 648 Rep Power: 4	I can tell you that the math went way over my head (:p), but when I compiled the program with extra warnings, a few things popped up. (Toggle Plain Text) $ gcc -Wall -Wextra calculus.c -lm -o calculus calculus.c: In function ‘function’: calculus.c:129: warning: array subscript has type ‘char’ calculus.c: In function ‘main’: calculus.c:273: warning: implicit declaration of function ‘memcpy’ calculus.c:273: warning: incompatible implicit declaration of built-in function ‘memcpy’ $ gcc -Wall -Wextra calculus.c -lm -o calculus calculus.c: In function ‘function’: calculus.c:129: warning: array subscript has type ‘char’ calculus.c: In function ‘main’: calculus.c:273: warning: implicit declaration of function ‘memcpy’ calculus.c:273: warning: incompatible implicit declaration of built-in function ‘memcpy’ But I'll let the people who actually know what they're talking about give any compliments or criticism to the coding style. __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Oct 7th, 2006, 1:17 PM	#3
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,076 Rep Power: 6	Oh, I didn't build my code to be GCC standard. I haven't got to that chapter in my book yet. It seems you can fix some of those things by changing the unsigned chars to unsigned ints (I was being a memory nazi). Not sure about the implicit declaration of function memcpy, that might have to do with a missing library that Dev-C++ implicitely includes. Regardless... It'll compile in something like Dev-C++. And ... Hey! The math isn't really complicated. I learned it in school, and I was only 15 three days ago.

Oct 7th, 2006, 2:46 PM	#4
Prm753 Professional Programmer Join Date: Oct 2005 Location: United States Posts: 447 Rep Power: 4	You were only 15 three days ago? Well, I hope you had a happy birthday then. Ah, even I can understand the math. The program compiled cleanly in Dev-C++. Nice work, Sane. __________________ The world's first athletic computer geek! The home of PrProgramsStudios How not to post a question: <-- Please don't reply

Oct 7th, 2006, 3:00 PM	#5
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,076 Rep Power: 6	Yep, I did. Got myself a nice O'Reilly Book for C. The math is pretty easy. It's the application of grade 10/11 math composed into the "Factor Thereom", used in Calculus for factoring large polynomials. The hardest part in the math to wrap your head around is the function "divide", which is synthetically long dividing a polynomial by (x+r). That's the part you learn in grade 12, but it's incredibly simple (just an expansion of long division).

Oct 8th, 2006, 12:49 AM	#7
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,076 Rep Power: 6	Converting i to an int every iteration is a tad bit silly, no? Why not just make the iterator an integer as I had proposed earlier?

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C

Fully Factoring A Polynomial Of A Dynamic Degree