# 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 at 17:50

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.
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.