Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
polynomials with open arrays
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment