polynomials with open arrays

t11e07.polynomials.cpp

// t11e07.polynomials.cpp
// juanfc 2018-12-17
// https://gist.github.com/baf068a06eafb1ecba8a584fe375b780

#include <array>
#include <iostream>
using namespace std;

const int N = 100;
struct TMono {
    int deg;
    float coef;
};
typedef array<TMono, N> TVec;
struct TPoly {
    int noel;
    TVec ar;
};

void print(TPoly p);
float eval(TPoly p, float x);
float horner(TPoly p, float x);
TPoly add(TPoly p, TMono m);
TPoly derivative(TPoly p);
TPoly derivative2(TPoly p);
void derivative3(TPoly& p);

int main()
{
    TPoly p = { 3, { { { 4, 1 }, { 2, -2 }, { 1, 1 } } } };
    print(p);
    print(derivative2(p));
    derivative3(p);
    print(p);
    cout << eval(p, 0) << endl;
    cout << horner(p, 0) << endl;
    cout << eval(p, 2) << endl;
    cout << horner(p, 2) << endl;
    p = (TPoly) { 0 };
    print(p = add(p, (TMono) { 2, 3 }));
    print(p = add(p, (TMono) { 1, -5 }));
    print(p = add(p, (TMono) { 0, 1 }));
    print(p = add(p, (TMono) { 33, 0 }));
    cout << eval(p, 1) << endl;
    return 0;
}

TPoly add(TPoly p, TMono m)
{
    TPoly r;
    if (m.coef == 0) // !!
        r = p;
    else {
        int j = 0;
        bool found = false;
        for (int i = 0; i < p.noel; ++i) {
            if (m.deg == p.ar[i].deg) {
                found = true;
                float c = m.coef + p.ar[i].coef;
                if (c != 0) {
                    r.ar[j++] = (TMono) { m.deg, c };
                }
            } else {
                if (p.ar[i].deg < m.deg) {
                    found = true;
                    r.ar[j++] = m;
                } else
                    r.ar[j++] = p.ar[i];
            }
        }
        if (not found) {
            r.ar[j++] = m;
        }
        r.noel = j;
    }
    return r;
}

TPoly derivative(TPoly p)
{
    TPoly r = { 0 };
    int i = 0;
    while (i < p.noel and p.ar[i].deg > 0) {
        float coef = p.ar[i].coef;
        int deg = p.ar[i].deg;
        r = add(r, (TMono) { deg - 1, coef * deg });
        ++i;
    }
    return r;
}

TPoly derivative2(TPoly p)
{
    TPoly r = p;
    int i = 0;
    while (i < p.noel and p.ar[i].deg > 0) {
        float coef = p.ar[i].coef;
        int deg = p.ar[i].deg;
        r.ar[i] = (TMono) { deg - 1, coef * deg };
        ++i;
    }
    r.noel = i;
    return r;
}

void derivative3(TPoly& p)
{
    int i = 0;
    while (i < p.noel and p.ar[i].deg > 0) {
        float coef = p.ar[i].coef;
        int deg = p.ar[i].deg;
        p.ar[i] = (TMono) { deg - 1, coef * deg };
        ++i;
    }
    p.noel = i;
}

void print(TPoly p)
{
    for (int i = 0; i < p.noel; ++i) {
        float coef = p.ar[i].coef;
        int deg = p.ar[i].deg;
        if (coef < 0) {
            cout << " - ";
            if (coef != -1 or deg == 0)
                cout << -coef;
        } else {
            if (i != 0)
                cout << " + ";
            if (coef != 1 or deg == 0)
                cout << coef;
        }
        if (deg > 0)
            cout << "x";
        if (deg > 1)
            cout << "^" << deg;
    }
    cout << endl;
}

float eval(TMono m, float x);

float eval(TPoly p, float x)
{
    float s = 0;
    for (int i = 0; i < p.noel; ++i) {
        s += eval(p.ar[i], x);
    }
    return s;
}

float horner(TPoly p, float x)
{
    float s = p.ar[0].coef;

    int j = 1;
    for (int i = p.ar[0].deg-1; i >= 0; --i) {
        if (i != p.ar[j].deg or j >= p.noel) {
            s *= x;
        } else {
            s = s * x + p.ar[j].coef;
            ++j;
        }
    }
    return s;
}

float pow(float x, int deg);
float eval(TMono m, float x)
{
    return m.coef * pow(x, m.deg);
}

float pow(float x, int deg)
{
    float r = 1;
    for (int i = 0; i < deg; ++i) {
        r *= x;
    }
    return r;
}