# Polynomial implementation in Golang

I am writing a numerical analysis library in golang for which I need to implement a polynomial struct. Here is the source code:

package numerical

import (
"strconv"
)

type Poly struct {
Coeffs []float64
}

func (p *Poly) Str() string {
d := p.Deg()

if d == -1 {
return "0"
}

s := ""
if p.Coeffs[d] == -1 {
if d == 0 {
s += "-1"
} else {
s += "-"
}
} else if p.Coeffs[d] != 1 || d == 0 {
s += strconv.FormatFloat(p.Coeffs[d], 'g', -1, 64)
}
if d == 1 {
s += "x"
} else if d > 1 {
s += "x^" + strconv.Itoa(d)
}
for i := d-1; i >= 0; i-- {
if p.Coeffs[i] > 0 {
s +=  " + "
if p.Coeffs[i] != 1 || i == 0 {
s += strconv.FormatFloat(p.Coeffs[i], 'g', -1, 64)
}
} else if p.Coeffs[i] < 0 {
s += " - "
if p.Coeffs[i] != -1 || i == 0 {
s += strconv.FormatFloat(-p.Coeffs[i], 'g', -1, 64)
}
}
if p.Coeffs[i] != 0 {
if i == 1 {
s += "x"
} else if i > 1 {
s += "x^" + strconv.Itoa(i)
}
}
}

return s
}

func (p *Poly) Deg() int {
i := len(p.Coeffs) - 1
for ; i >= 0 && p.Coeffs[i] == 0; i-=1 {
}
return i
}

func (p *Poly) Eval(x float64) float64 {
val := p.Coeffs
pow := 1.0
for i:=1; i <= p.Deg(); i+=1 {
pow *= x
val += p.Coeffs[i]*pow
}
return val
}

func PolyAdd(p, q Poly) Poly {
var big, small, r Poly
if p.Deg() > q.Deg() {
big = p
small = q
} else {
big = q
small = p
}
r = big
for i := 0; i <= small.Deg(); i+=1 {
r.Coeffs[i] += small.Coeffs[i]
}
return r
}

func PolySub(p, q Poly) Poly {
degp := p.Deg()
degq := q.Deg()
big := degp
if degp < degq {
big = degq
}
r := Poly{make([]float64, big+1)}
for i := 0; i <= big; i++ {
if i <= degp {
r.Coeffs[i] = p.Coeffs[i]
}
if i <= degq {
r.Coeffs[i] -= q.Coeffs[i]
}
}
return r
}

func PolyMul(p, q Poly) Poly {
m, n := p.Deg(), q.Deg()
r := Poly{make([]float64, m+n+1)}
for i := 0; i <= m; i++ {
for j := 0; j <= n; j++ {
r.Coeffs[i+j] += p.Coeffs[i]*q.Coeffs[j]
}
}
return r
}

func PolyDiv(a, b Poly) (Poly, Poly) {
var q Poly
for b.Deg() <= a.Deg() {
dega := a.Deg()
degb := b.Deg()
qc := a.Coeffs[dega]/b.Coeffs[degb]
qp := dega - degb
qi := Poly{make([]float64, qp+1)}
qi.Coeffs[qp] = qc
a = PolySub(a, PolyMul(qi, b))
}
return q, a
}


A few things that I observed about the code are:

• The Poly.Deg is a method. I should probably make a non-method field (what are they called?) for that purpose, but then I will have to create a Poly.UpdateDeg which will set the degree for a new polynomial, and then I will have to call this UpdateDeg in all the other functions like PolyAdd, PolyMul etc. Is their a better way to achieve this.

• The Poly.Str method, which basically pretty-prints the polynomial looks very complicated. The purpose of this method is to return a string containing the polynomial in human readable form. For example, the polynomial {-1, 2, -1} will give -x^2 + 2x - 1 (pay special attention to the leading coefficients and spaces around + and -). Can this method be simplified?

Any other suggestion/improvements are welcome, in particular, I would like to know if the code is idiomatic Go. I am new to Go, and would like to learn the Go-way of doing things.

EDIT: Here is the code on Playground (slightly modified to run on Playground).

• @200_success I am sorry, but your edit was at the same time as my update and it undid my update. So I had to rollback to my update but I have included the tag suggested by you. – feynhat Feb 8 '19 at 17:50

Your code is missing automatic tests.

One test case you definitely need is to ensure that PolyAdd and the related functions do not modify their arguments. As far as I can see by reading the code, the current version of PolyAdd modifies the bigger of its arguments, which is unexpected.

The reason that the argument is modified is that slices are essentially pointers, and when passing them as arguments, their content is not copied.

You should define a constructor function NewPoly(deg int) to hide all the implementation details. Using this constructor will also solve the aliasing problem mentioned above.

Regarding the long code for Str, you can merge some of the duplicate code:

    c := p.Coeffs[i]
if c == 0 {
continue;
}

if c > 0 {
s += " + "
} else {
s += " - "
}

if (c != 1 && c != -1) || i == 0 {
s += strconv.FormatFloat(c, 'g', -1, 64)
}
if i > 1 {
s += "x^" + strconv.Itoa(i)
} else if i == 1 {
s += "x"
}


By extracting the expression p.Coeffs[i] into a variable, the code gets a bit cleaner.

If you need to speed up Str, use a strings.Builder instead of the += operator.

• I added a section on making Str shorter. – Roland Illig May 4 at 5:56