polynomials with open arrays

t12e07.polynomials.cpp

// t12e07.polynomials.cpp
// juanfc 2023-11-23
// https://gist.github.com/baf068a06eafb1ecba8a584fe375b780
// Elements of the polynomials are kept ordered
//  from highest to lowest degrees
//

#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, {{ // x^4 -2x^2 + x
                    {4,  1},
                    {2, -2},
                    {1,  1}
                  }}
              };
    cout << "Original:        ";
    print(p);
    cout << "Its derivative2: ";
    print(derivative2(p));
    derivative3(p);
    cout << "Its derivative3: ";
    print(p);
    cout << "Eval at 0      : ";
    cout << eval(p, 0) << endl;
    cout << "horner at 0    : ";
    cout << horner(p, 0) << endl;
    cout << "Eval at 2      : ";
    cout << eval(p, 2) << endl;
    cout << "horner at 2    : ";
    cout << horner(p, 2) << endl;
    p.noel=0;
    cout << "0 + 3x2:      ";
    print(p = add(p, (TMono) { 2,  3 }));
    cout << "..+-5x1:      ";
    print(p = add(p, (TMono) { 1, -5 }));
    cout << "..+ 5x1:      ";
    print(p = add(p, (TMono) { 1, +5 }));
    cout << "..+ 1x0:      ";
    print(p = add(p, (TMono) { 0,  1 }));
    cout << "..+ 0x33:     ";
    print(p = add(p, (TMono) { 33, 0 }));
    cout << "at 1:         ";
    cout << eval(p, 1) << endl;
    return 0;
}

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

TPoly derivative(TPoly p)
{
    TPoly r;
    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(TPoly p, float x)
{
    float eval(TMono, float);

    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 eval(TMono m, float x)
{
    float pow(float, int);

    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;
}