URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [testsuite/] [go.test/] [test/] [chan/] [powser1.go] - Blame information for rev 858

Go to most recent revision | Details | Compare with Previous | View Log


// $G $D/$F.go && $L $F.$A && ./$A.out
 
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
 
// Power series package
// A power series is a channel, along which flow rational
// coefficients.  A denominator of zero signifies the end.
// Original code in Newsqueak by Doug McIlroy.
// See Squinting at Power Series by Doug McIlroy,
//   http://www.cs.bell-labs.com/who/rsc/thread/squint.pdf
 
package main
 
import "os"
 
type rat struct  {
        num, den  int64 // numerator, denominator
}
 
func (u rat) pr() {
        if u.den==1 {
                print(u.num)
        } else {
                print(u.num, "/", u.den)
        }
        print(" ")
}
 
func (u rat) eq(c rat) bool {
        return u.num == c.num && u.den == c.den
}
 
type dch struct {
        req chan  int
        dat chan  rat
        nam int
}
 
type dch2 [2] *dch
 
var chnames string
var chnameserial int
var seqno int
 
func mkdch() *dch {
        c := chnameserial % len(chnames)
        chnameserial++
        d := new(dch)
        d.req = make(chan int)
        d.dat = make(chan rat)
        d.nam = c
        return d
}
 
func mkdch2() *dch2 {
        d2 := new(dch2)
        d2[0] = mkdch()
        d2[1] = mkdch()
        return d2
}
 
// split reads a single demand channel and replicates its
// output onto two, which may be read at different rates.
// A process is created at first demand for a rat and dies
// after the rat has been sent to both outputs.
 
// When multiple generations of split exist, the newest
// will service requests on one channel, which is
// always renamed to be out[0]; the oldest will service
// requests on the other channel, out[1].  All generations but the
// newest hold queued data that has already been sent to
// out[0].  When data has finally been sent to out[1],
// a signal on the release-wait channel tells the next newer
// generation to begin servicing out[1].
 
func dosplit(in *dch, out *dch2, wait chan int ) {
        both := false   // do not service both channels
 
        select {
        case <-out[0].req:
 
        case <-wait:
                both = true
                select {
                case <-out[0].req:
 
                case <-out[1].req:
                        out[0], out[1] = out[1], out[0]
                }
        }
 
        seqno++
        in.req <- seqno
        release := make(chan  int)
        go dosplit(in, out, release)
        dat := <-in.dat
        out[0].dat <- dat
        if !both {
                <-wait
        }
        <-out[1].req
        out[1].dat <- dat
        release <- 0
}
 
func split(in *dch, out *dch2) {
        release := make(chan int)
        go dosplit(in, out, release)
        release <- 0
}
 
func put(dat rat, out *dch) {
        <-out.req
        out.dat <- dat
}
 
func get(in *dch) rat {
        seqno++
        in.req <- seqno
        return <-in.dat
}
 
// Get one rat from each of n demand channels
 
func getn(in []*dch) []rat {
        n := len(in)
        if n != 2 { panic("bad n in getn") }
        req := new([2] chan int)
        dat := new([2] chan rat)
        out := make([]rat, 2)
        var i int
        var it rat
        for i=0; i
                req[i] = in[i].req
                dat[i] = nil
        }
        for n=2*n; n>0; n-- {
                seqno++
 
                select {
                case req[0] <- seqno:
                        dat[0] = in[0].dat
                        req[0] = nil
                case req[1] <- seqno:
                        dat[1] = in[1].dat
                        req[1] = nil
                case it = <-dat[0]:
                        out[0] = it
                        dat[0] = nil
                case it = <-dat[1]:
                        out[1] = it
                        dat[1] = nil
                }
        }
        return out
}
 
// Get one rat from each of 2 demand channels
 
func get2(in0 *dch, in1 *dch) []rat {
        return getn([]*dch{in0, in1})
}
 
func copy(in *dch, out *dch) {
        for {
                <-out.req
                out.dat <- get(in)
        }
}
 
func repeat(dat rat, out *dch) {
        for {
                put(dat, out)
        }
}
 
type PS *dch    // power series
type PS2 *[2] PS // pair of power series
 
var Ones PS
var Twos PS
 
func mkPS() *dch {
        return mkdch()
}
 
func mkPS2() *dch2 {
        return mkdch2()
}
 
// Conventions
// Upper-case for power series.
// Lower-case for rationals.
// Input variables: U,V,...
// Output variables: ...,Y,Z
 
// Integer gcd; needed for rational arithmetic
 
func gcd (u, v int64) int64 {
        if u < 0 { return gcd(-u, v) }
        if u == 0 { return v }
        return gcd(v%u, u)
}
 
// Make a rational from two ints and from one int
 
func i2tor(u, v int64) rat {
        g := gcd(u,v)
        var r rat
        if v > 0 {
                r.num = u/g
                r.den = v/g
        } else {
                r.num = -u/g
                r.den = -v/g
        }
        return r
}
 
func itor(u int64) rat {
        return i2tor(u, 1)
}
 
var zero rat
var one rat
 
 
// End mark and end test
 
var finis rat
 
func end(u rat) int64 {
        if u.den==0 { return 1 }
        return 0
}
 
// Operations on rationals
 
func add(u, v rat) rat {
        g := gcd(u.den,v.den)
        return  i2tor(u.num*(v.den/g)+v.num*(u.den/g),u.den*(v.den/g))
}
 
func mul(u, v rat) rat {
        g1 := gcd(u.num,v.den)
        g2 := gcd(u.den,v.num)
        var r rat
        r.num = (u.num/g1)*(v.num/g2)
        r.den = (u.den/g2)*(v.den/g1)
        return r
}
 
func neg(u rat) rat {
        return i2tor(-u.num, u.den)
}
 
func sub(u, v rat) rat {
        return add(u, neg(v))
}
 
func inv(u rat) rat {   // invert a rat
        if u.num == 0 { panic("zero divide in inv") }
        return i2tor(u.den, u.num)
}
 
// print eval in floating point of PS at x=c to n terms
func evaln(c rat, U PS, n int) {
        xn := float64(1)
        x := float64(c.num)/float64(c.den)
        val := float64(0)
        for i:=0; i
                u := get(U)
                if end(u) != 0 {
                        break
                }
                val = val + x * float64(u.num)/float64(u.den)
                xn = xn*x
        }
        print(val, "\n")
}
 
// Print n terms of a power series
func printn(U PS, n int) {
        done := false
        for ; !done && n>0; n-- {
                u := get(U)
                if end(u) != 0 {
                        done = true
                } else {
                        u.pr()
                }
        }
        print(("\n"))
}
 
// Evaluate n terms of power series U at x=c
func eval(c rat, U PS, n int) rat {
        if n==0 { return zero }
        y := get(U)
        if end(y) != 0 { return zero }
        return add(y,mul(c,eval(c,U,n-1)))
}
 
// Power-series constructors return channels on which power
// series flow.  They start an encapsulated generator that
// puts the terms of the series on the channel.
 
// Make a pair of power series identical to a given power series
 
func Split(U PS) *dch2 {
        UU := mkdch2()
        go split(U,UU)
        return UU
}
 
// Add two power series
func Add(U, V PS) PS {
        Z := mkPS()
        go func() {
                var uv []rat
                for {
                        <-Z.req
                        uv = get2(U,V)
                        switch end(uv[0])+2*end(uv[1]) {
                        case 0:
                                Z.dat <- add(uv[0], uv[1])
                        case 1:
                                Z.dat <- uv[1]
                                copy(V,Z)
                        case 2:
                                Z.dat <- uv[0]
                                copy(U,Z)
                        case 3:
                                Z.dat <- finis
                        }
                }
        }()
        return Z
}
 
// Multiply a power series by a constant
func Cmul(c rat,U PS) PS {
        Z := mkPS()
        go func() {
                done := false
                for !done {
                        <-Z.req
                        u := get(U)
                        if end(u) != 0 {
                                done = true
                        } else {
                                Z.dat <- mul(c,u)
                        }
                }
                Z.dat <- finis
        }()
        return Z
}
 
// Subtract
 
func Sub(U, V PS) PS {
        return Add(U, Cmul(neg(one), V))
}
 
// Multiply a power series by the monomial x^n
 
func Monmul(U PS, n int) PS {
        Z := mkPS()
        go func() {
                for ; n>0; n-- { put(zero,Z) }
                copy(U,Z)
        }()
        return Z
}
 
// Multiply by x
 
func Xmul(U PS) PS {
        return Monmul(U,1)
}
 
func Rep(c rat) PS {
        Z := mkPS()
        go repeat(c,Z)
        return Z
}
 
// Monomial c*x^n
 
func Mon(c rat, n int) PS {
        Z:=mkPS()
        go func() {
                if(c.num!=0) {
                        for ; n>0; n=n-1 { put(zero,Z) }
                        put(c,Z)
                }
                put(finis,Z)
        }()
        return Z
}
 
func Shift(c rat, U PS) PS {
        Z := mkPS()
        go func() {
                put(c,Z)
                copy(U,Z)
        }()
        return Z
}
 
// simple pole at 1: 1/(1-x) = 1 1 1 1 1 ...
 
// Convert array of coefficients, constant term first
// to a (finite) power series
 
/*
func Poly(a []rat) PS {
        Z:=mkPS()
        begin func(a []rat, Z PS) {
                j:=0
                done:=0
                for j=len(a); !done&&j>0; j=j-1)
                        if(a[j-1].num!=0) done=1
                i:=0
                for(; i
                put(finis,Z)
        }()
        return Z
}
*/
 
// Multiply. The algorithm is
//      let U = u + x*UU
//      let V = v + x*VV
//      then UV = u*v + x*(u*VV+v*UU) + x*x*UU*VV
 
func Mul(U, V PS) PS {
        Z:=mkPS()
        go func() {
                <-Z.req
                uv := get2(U,V)
                if end(uv[0])!=0 || end(uv[1]) != 0 {
                        Z.dat <- finis
                } else {
                        Z.dat <- mul(uv[0],uv[1])
                        UU := Split(U)
                        VV := Split(V)
                        W := Add(Cmul(uv[0],VV[0]),Cmul(uv[1],UU[0]))
                        <-Z.req
                        Z.dat <- get(W)
                        copy(Add(W,Mul(UU[1],VV[1])),Z)
                }
        }()
        return Z
}
 
// Differentiate
 
func Diff(U PS) PS {
        Z:=mkPS()
        go func() {
                <-Z.req
                u := get(U)
                if end(u) == 0 {
                        done:=false
                        for i:=1; !done; i++ {
                                u = get(U)
                                if end(u) != 0 {
                                        done = true
                                } else {
                                        Z.dat <- mul(itor(int64(i)),u)
                                        <-Z.req
                                }
                        }
                }
                Z.dat <- finis
        }()
        return Z
}
 
// Integrate, with const of integration
func Integ(c rat,U PS) PS {
        Z:=mkPS()
        go func() {
                put(c,Z)
                done:=false
                for i:=1; !done; i++ {
                        <-Z.req
                        u := get(U)
                        if end(u) != 0 { done= true }
                        Z.dat <- mul(i2tor(1,int64(i)),u)
                }
                Z.dat <- finis
        }()
        return Z
}
 
// Binomial theorem (1+x)^c
 
func Binom(c rat) PS {
        Z:=mkPS()
        go func() {
                n := 1
                t := itor(1)
                for c.num!=0 {
                        put(t,Z)
                        t = mul(mul(t,c),i2tor(1,int64(n)))
                        c = sub(c,one)
                        n++
                }
                put(finis,Z)
        }()
        return Z
}
 
// Reciprocal of a power series
//      let U = u + x*UU
//      let Z = z + x*ZZ
//      (u+x*UU)*(z+x*ZZ) = 1
//      z = 1/u
//      u*ZZ + z*UU +x*UU*ZZ = 0
//      ZZ = -UU*(z+x*ZZ)/u
 
func Recip(U PS) PS {
        Z:=mkPS()
        go func() {
                ZZ:=mkPS2()
                <-Z.req
                z := inv(get(U))
                Z.dat <- z
                split(Mul(Cmul(neg(z),U),Shift(z,ZZ[0])),ZZ)
                copy(ZZ[1],Z)
        }()
        return Z
}
 
// Exponential of a power series with constant term 0
// (nonzero constant term would make nonrational coefficients)
// bug: the constant term is simply ignored
//      Z = exp(U)
//      DZ = Z*DU
//      integrate to get Z
 
func Exp(U PS) PS {
        ZZ := mkPS2()
        split(Integ(one,Mul(ZZ[0],Diff(U))),ZZ)
        return ZZ[1]
}
 
// Substitute V for x in U, where the leading term of V is zero
//      let U = u + x*UU
//      let V = v + x*VV
//      then S(U,V) = u + VV*S(V,UU)
// bug: a nonzero constant term is ignored
 
func Subst(U, V PS) PS {
        Z:= mkPS()
        go func() {
                VV := Split(V)
                <-Z.req
                u := get(U)
                Z.dat <- u
                if end(u) == 0 {
                        if end(get(VV[0])) != 0 {
                                put(finis,Z)
                        } else {
                                copy(Mul(VV[0],Subst(U,VV[1])),Z)
                        }
                }
        }()
        return Z
}
 
// Monomial Substition: U(c x^n)
// Each Ui is multiplied by c^i and followed by n-1 zeros
 
func MonSubst(U PS, c0 rat, n int) PS {
        Z:= mkPS()
        go func() {
                c := one
                for {
                        <-Z.req
                        u := get(U)
                        Z.dat <- mul(u, c)
                        c = mul(c, c0)
                        if end(u) != 0 {
                                Z.dat <- finis
                                break
                        }
                        for i := 1; i < n; i++ {
                                <-Z.req
                                Z.dat <- zero
                        }
                }
        }()
        return Z
}
 
 
func Init() {
        chnameserial = -1
        seqno = 0
        chnames = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
        zero = itor(0)
        one = itor(1)
        finis = i2tor(1,0)
        Ones = Rep(one)
        Twos = Rep(itor(2))
}
 
func check(U PS, c rat, count int, str string) {
        for i := 0; i < count; i++ {
                r := get(U)
                if !r.eq(c) {
                        print("got: ")
                        r.pr()
                        print("should get ")
                        c.pr()
                        print("\n")
                        panic(str)
                }
        }
}
 
const N=10
func checka(U PS, a []rat, str string) {
        for i := 0; i < N; i++ {
                check(U, a[i], 1, str)
        }
}
 
func main() {
        Init()
        if len(os.Args) > 1 {  // print
                print("Ones: "); printn(Ones, 10)
                print("Twos: "); printn(Twos, 10)
                print("Add: "); printn(Add(Ones, Twos), 10)
                print("Diff: "); printn(Diff(Ones), 10)
                print("Integ: "); printn(Integ(zero, Ones), 10)
                print("CMul: "); printn(Cmul(neg(one), Ones), 10)
                print("Sub: "); printn(Sub(Ones, Twos), 10)
                print("Mul: "); printn(Mul(Ones, Ones), 10)
                print("Exp: "); printn(Exp(Ones), 15)
                print("MonSubst: "); printn(MonSubst(Ones, neg(one), 2), 10)
                print("ATan: "); printn(Integ(zero, MonSubst(Ones, neg(one), 2)), 10)
        } else {  // test
                check(Ones, one, 5, "Ones")
                check(Add(Ones, Ones), itor(2), 0, "Add Ones Ones")  // 1 1 1 1 1
                check(Add(Ones, Twos), itor(3), 0, "Add Ones Twos") // 3 3 3 3 3
                a := make([]rat, N)
                d := Diff(Ones)
                for i:=0; i < N; i++ {
                        a[i] = itor(int64(i+1))
                }
                checka(d, a, "Diff")  // 1 2 3 4 5
                in := Integ(zero, Ones)
                a[0] = zero  // integration constant
                for i:=1; i < N; i++ {
                        a[i] = i2tor(1, int64(i))
                }
                checka(in, a, "Integ")  // 0 1 1/2 1/3 1/4 1/5
                check(Cmul(neg(one), Twos), itor(-2), 10, "CMul")  // -1 -1 -1 -1 -1
                check(Sub(Ones, Twos), itor(-1), 0, "Sub Ones Twos")  // -1 -1 -1 -1 -1
                m := Mul(Ones, Ones)
                for i:=0; i < N; i++ {
                        a[i] = itor(int64(i+1))
                }
                checka(m, a, "Mul")  // 1 2 3 4 5
                e := Exp(Ones)
                a[0] = itor(1)
                a[1] = itor(1)
                a[2] = i2tor(3,2)
                a[3] = i2tor(13,6)
                a[4] = i2tor(73,24)
                a[5] = i2tor(167,40)
                a[6] = i2tor(4051,720)
                a[7] = i2tor(37633,5040)
                a[8] = i2tor(43817,4480)
                a[9] = i2tor(4596553,362880)
                checka(e, a, "Exp")  // 1 1 3/2 13/6 73/24
                at := Integ(zero, MonSubst(Ones, neg(one), 2))
                for c, i := 1, 0; i < N; i++ {
                        if i%2 == 0 {
                                a[i] = zero
                        } else {
                                a[i] = i2tor(int64(c), int64(i))
                                c *= -1
                        }
                }
                checka(at, a, "ATan")  // 0 -1 0 -1/3 0 -1/5
/*
                t := Revert(Integ(zero, MonSubst(Ones, neg(one), 2)))
                a[0] = zero
                a[1] = itor(1)
                a[2] = zero
                a[3] = i2tor(1,3)
                a[4] = zero
                a[5] = i2tor(2,15)
                a[6] = zero
                a[7] = i2tor(17,315)
                a[8] = zero
                a[9] = i2tor(62,2835)
                checka(t, a, "Tan")  // 0 1 0 1/3 0 2/15
*/
        }
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [testsuite/] [go.test/] [test/] [chan/] [powser1.go] - Blame information for rev 858

Line No.	Rev	Author	Line
1	700	jeremybenn	`// $G $D/$F.go && $L $F.$A && ./$A.out`
2
3			`// Copyright 2009 The Go Authors. All rights reserved.`
4			`// Use of this source code is governed by a BSD-style`
5			`// license that can be found in the LICENSE file.`
6
7			`// Power series package`
8			`// A power series is a channel, along which flow rational`
9			`// coefficients. A denominator of zero signifies the end.`
10			`// Original code in Newsqueak by Doug McIlroy.`
11			`// See Squinting at Power Series by Doug McIlroy,`
12			`// http://www.cs.bell-labs.com/who/rsc/thread/squint.pdf`
13
14			`package main`
15
16			`import "os"`
17
18			`type rat struct {`
19			`num, den int64 // numerator, denominator`
20			`}`
21
22			`func (u rat) pr() {`
23			`if u.den==1 {`
24			`print(u.num)`
25			`} else {`
26			`print(u.num, "/", u.den)`
27			`}`
28			`print(" ")`
29			`}`
30
31			`func (u rat) eq(c rat) bool {`
32			`return u.num == c.num && u.den == c.den`
33			`}`
34
35			`type dch struct {`
36			`req chan int`
37			`dat chan rat`
38			`nam int`
39			`}`
40
41			`type dch2 [2] *dch`
42
43			`var chnames string`
44			`var chnameserial int`
45			`var seqno int`
46
47			`func mkdch() *dch {`
48			`c := chnameserial % len(chnames)`
49			`chnameserial++`
50			`d := new(dch)`
51			`d.req = make(chan int)`
52			`d.dat = make(chan rat)`
53			`d.nam = c`
54			`return d`
55			`}`
56
57			`func mkdch2() *dch2 {`
58			`d2 := new(dch2)`
59			`d2[0] = mkdch()`
60			`d2[1] = mkdch()`
61			`return d2`
62			`}`
63
64			`// split reads a single demand channel and replicates its`
65			`// output onto two, which may be read at different rates.`
66			`// A process is created at first demand for a rat and dies`
67			`// after the rat has been sent to both outputs.`
68
69			`// When multiple generations of split exist, the newest`
70			`// will service requests on one channel, which is`
71			`// always renamed to be out[0]; the oldest will service`
72			`// requests on the other channel, out[1]. All generations but the`
73			`// newest hold queued data that has already been sent to`
74			`// out[0]. When data has finally been sent to out[1],`
75			`// a signal on the release-wait channel tells the next newer`
76			`// generation to begin servicing out[1].`
77
78			`func dosplit(in dch, out dch2, wait chan int ) {`
79			`both := false // do not service both channels`
80
81			`select {`
82			`case <-out[0].req:`
83
84			`case <-wait:`
85			`both = true`
86			`select {`
87			`case <-out[0].req:`
88
89			`case <-out[1].req:`
90			`out[0], out[1] = out[1], out[0]`
91			`}`
92			`}`
93
94			`seqno++`
95			`in.req <- seqno`
96			`release := make(chan int)`
97			`go dosplit(in, out, release)`
98			`dat := <-in.dat`
99			`out[0].dat <- dat`
100			`if !both {`
101			`<-wait`
102			`}`
103			`<-out[1].req`
104			`out[1].dat <- dat`
105			`release <- 0`
106			`}`
107
108			`func split(in dch, out dch2) {`
109			`release := make(chan int)`
110			`go dosplit(in, out, release)`
111			`release <- 0`
112			`}`
113
114			`func put(dat rat, out *dch) {`
115			`<-out.req`
116			`out.dat <- dat`
117			`}`
118
119			`func get(in *dch) rat {`
120			`seqno++`
121			`in.req <- seqno`
122			`return <-in.dat`
123			`}`
124
125			`// Get one rat from each of n demand channels`
126
127			`func getn(in []*dch) []rat {`
128			`n := len(in)`
129			`if n != 2 { panic("bad n in getn") }`
130			`req := new([2] chan int)`
131			`dat := new([2] chan rat)`
132			`out := make([]rat, 2)`
133			`var i int`
134			`var it rat`
135			`for i=0; i`
136			`req[i] = in[i].req`
137			`dat[i] = nil`
138			`}`
139			`for n=2*n; n>0; n-- {`
140			`seqno++`
141
142			`select {`
143			`case req[0] <- seqno:`
144			`dat[0] = in[0].dat`
145			`req[0] = nil`
146			`case req[1] <- seqno:`
147			`dat[1] = in[1].dat`
148			`req[1] = nil`
149			`case it = <-dat[0]:`
150			`out[0] = it`
151			`dat[0] = nil`
152			`case it = <-dat[1]:`
153			`out[1] = it`
154			`dat[1] = nil`
155			`}`
156			`}`
157			`return out`
158			`}`
159
160			`// Get one rat from each of 2 demand channels`
161
162			`func get2(in0 dch, in1 dch) []rat {`
163			`return getn([]*dch{in0, in1})`
164			`}`
165
166			`func copy(in dch, out dch) {`
167			`for {`
168			`<-out.req`
169			`out.dat <- get(in)`
170			`}`
171			`}`
172
173			`func repeat(dat rat, out *dch) {`
174			`for {`
175			`put(dat, out)`
176			`}`
177			`}`
178
179			`type PS *dch // power series`
180			`type PS2 *[2] PS // pair of power series`
181
182			`var Ones PS`
183			`var Twos PS`
184
185			`func mkPS() *dch {`
186			`return mkdch()`
187			`}`
188
189			`func mkPS2() *dch2 {`
190			`return mkdch2()`
191			`}`
192
193			`// Conventions`
194			`// Upper-case for power series.`
195			`// Lower-case for rationals.`
196			`// Input variables: U,V,...`
197			`// Output variables: ...,Y,Z`
198
199			`// Integer gcd; needed for rational arithmetic`
200
201			`func gcd (u, v int64) int64 {`
202			`if u < 0 { return gcd(-u, v) }`
203			`if u == 0 { return v }`
204			`return gcd(v%u, u)`
205			`}`
206
207			`// Make a rational from two ints and from one int`
208
209			`func i2tor(u, v int64) rat {`
210			`g := gcd(u,v)`
211			`var r rat`
212			`if v > 0 {`
213			`r.num = u/g`
214			`r.den = v/g`
215			`} else {`
216			`r.num = -u/g`
217			`r.den = -v/g`
218			`}`
219			`return r`
220			`}`
221
222			`func itor(u int64) rat {`
223			`return i2tor(u, 1)`
224			`}`
225
226			`var zero rat`
227			`var one rat`
228
229
230			`// End mark and end test`
231
232			`var finis rat`
233
234			`func end(u rat) int64 {`
235			`if u.den==0 { return 1 }`
236			`return 0`
237			`}`
238
239			`// Operations on rationals`
240
241			`func add(u, v rat) rat {`
242			`g := gcd(u.den,v.den)`
243			`return i2tor(u.num(v.den/g)+v.num(u.den/g),u.den*(v.den/g))`
244			`}`
245
246			`func mul(u, v rat) rat {`
247			`g1 := gcd(u.num,v.den)`
248			`g2 := gcd(u.den,v.num)`
249			`var r rat`
250			`r.num = (u.num/g1)*(v.num/g2)`
251			`r.den = (u.den/g2)*(v.den/g1)`
252			`return r`
253			`}`
254
255			`func neg(u rat) rat {`
256			`return i2tor(-u.num, u.den)`
257			`}`
258
259			`func sub(u, v rat) rat {`
260			`return add(u, neg(v))`
261			`}`
262
263			`func inv(u rat) rat { // invert a rat`
264			`if u.num == 0 { panic("zero divide in inv") }`
265			`return i2tor(u.den, u.num)`
266			`}`
267
268			`// print eval in floating point of PS at x=c to n terms`
269			`func evaln(c rat, U PS, n int) {`
270			`xn := float64(1)`
271			`x := float64(c.num)/float64(c.den)`
272			`val := float64(0)`
273			`for i:=0; i`
274			`u := get(U)`
275			`if end(u) != 0 {`
276			`break`
277			`}`
278			`val = val + x * float64(u.num)/float64(u.den)`
279			`xn = xn*x`
280			`}`
281			`print(val, "\n")`
282			`}`
283
284			`// Print n terms of a power series`
285			`func printn(U PS, n int) {`
286			`done := false`
287			`for ; !done && n>0; n-- {`
288			`u := get(U)`
289			`if end(u) != 0 {`
290			`done = true`
291			`} else {`
292			`u.pr()`
293			`}`
294			`}`
295			`print(("\n"))`
296			`}`
297
298			`// Evaluate n terms of power series U at x=c`
299			`func eval(c rat, U PS, n int) rat {`
300			`if n==0 { return zero }`
301			`y := get(U)`
302			`if end(y) != 0 { return zero }`
303			`return add(y,mul(c,eval(c,U,n-1)))`
304			`}`
305
306			`// Power-series constructors return channels on which power`
307			`// series flow. They start an encapsulated generator that`
308			`// puts the terms of the series on the channel.`
309
310			`// Make a pair of power series identical to a given power series`
311
312			`func Split(U PS) *dch2 {`
313			`UU := mkdch2()`
314			`go split(U,UU)`
315			`return UU`
316			`}`
317
318			`// Add two power series`
319			`func Add(U, V PS) PS {`
320			`Z := mkPS()`
321			`go func() {`
322			`var uv []rat`
323			`for {`
324			`<-Z.req`
325			`uv = get2(U,V)`
326			`switch end(uv[0])+2*end(uv[1]) {`
327			`case 0:`
328			`Z.dat <- add(uv[0], uv[1])`
329			`case 1:`
330			`Z.dat <- uv[1]`
331			`copy(V,Z)`
332			`case 2:`
333			`Z.dat <- uv[0]`
334			`copy(U,Z)`
335			`case 3:`
336			`Z.dat <- finis`
337			`}`
338			`}`
339			`}()`
340			`return Z`
341			`}`
342
343			`// Multiply a power series by a constant`
344			`func Cmul(c rat,U PS) PS {`
345			`Z := mkPS()`
346			`go func() {`
347			`done := false`
348			`for !done {`
349			`<-Z.req`
350			`u := get(U)`
351			`if end(u) != 0 {`
352			`done = true`
353			`} else {`
354			`Z.dat <- mul(c,u)`
355			`}`
356			`}`
357			`Z.dat <- finis`
358			`}()`
359			`return Z`
360			`}`
361
362			`// Subtract`
363
364			`func Sub(U, V PS) PS {`
365			`return Add(U, Cmul(neg(one), V))`
366			`}`
367
368			`// Multiply a power series by the monomial x^n`
369
370			`func Monmul(U PS, n int) PS {`
371			`Z := mkPS()`
372			`go func() {`
373			`for ; n>0; n-- { put(zero,Z) }`
374			`copy(U,Z)`
375			`}()`
376			`return Z`
377			`}`
378
379			`// Multiply by x`
380
381			`func Xmul(U PS) PS {`
382			`return Monmul(U,1)`
383			`}`
384
385			`func Rep(c rat) PS {`
386			`Z := mkPS()`
387			`go repeat(c,Z)`
388			`return Z`
389			`}`
390
391			`// Monomial c*x^n`
392
393			`func Mon(c rat, n int) PS {`
394			`Z:=mkPS()`
395			`go func() {`
396			`if(c.num!=0) {`
397			`for ; n>0; n=n-1 { put(zero,Z) }`
398			`put(c,Z)`
399			`}`
400			`put(finis,Z)`
401			`}()`
402			`return Z`
403			`}`
404
405			`func Shift(c rat, U PS) PS {`
406			`Z := mkPS()`
407			`go func() {`
408			`put(c,Z)`
409			`copy(U,Z)`
410			`}()`
411			`return Z`
412			`}`
413
414			`// simple pole at 1: 1/(1-x) = 1 1 1 1 1 ...`
415
416			`// Convert array of coefficients, constant term first`
417			`// to a (finite) power series`
418
419			`/*`
420			`func Poly(a []rat) PS {`
421			`Z:=mkPS()`
422			`begin func(a []rat, Z PS) {`
423			`j:=0`
424			`done:=0`
425			`for j=len(a); !done&&j>0; j=j-1)`
426			`if(a[j-1].num!=0) done=1`
427			`i:=0`
428			`for(; i`
429			`put(finis,Z)`
430			`}()`
431			`return Z`
432			`}`
433			`*/`
434
435			`// Multiply. The algorithm is`
436			`// let U = u + x*UU`
437			`// let V = v + x*VV`
438			`// then UV = uv + x(uVV+vUU) + xxUU*VV`
439
440			`func Mul(U, V PS) PS {`
441			`Z:=mkPS()`
442			`go func() {`
443			`<-Z.req`
444			`uv := get2(U,V)`
445			`if end(uv[0])!=0 \|\| end(uv[1]) != 0 {`
446			`Z.dat <- finis`
447			`} else {`
448			`Z.dat <- mul(uv[0],uv[1])`
449			`UU := Split(U)`
450			`VV := Split(V)`
451			`W := Add(Cmul(uv[0],VV[0]),Cmul(uv[1],UU[0]))`
452			`<-Z.req`
453			`Z.dat <- get(W)`
454			`copy(Add(W,Mul(UU[1],VV[1])),Z)`
455			`}`
456			`}()`
457			`return Z`
458			`}`
459
460			`// Differentiate`
461
462			`func Diff(U PS) PS {`
463			`Z:=mkPS()`
464			`go func() {`
465			`<-Z.req`
466			`u := get(U)`
467			`if end(u) == 0 {`
468			`done:=false`
469			`for i:=1; !done; i++ {`
470			`u = get(U)`
471			`if end(u) != 0 {`
472			`done = true`
473			`} else {`
474			`Z.dat <- mul(itor(int64(i)),u)`
475			`<-Z.req`
476			`}`
477			`}`
478			`}`
479			`Z.dat <- finis`
480			`}()`
481			`return Z`
482			`}`
483
484			`// Integrate, with const of integration`
485			`func Integ(c rat,U PS) PS {`
486			`Z:=mkPS()`
487			`go func() {`
488			`put(c,Z)`
489			`done:=false`
490			`for i:=1; !done; i++ {`
491			`<-Z.req`
492			`u := get(U)`
493			`if end(u) != 0 { done= true }`
494			`Z.dat <- mul(i2tor(1,int64(i)),u)`
495			`}`
496			`Z.dat <- finis`
497			`}()`
498			`return Z`
499			`}`
500
501			`// Binomial theorem (1+x)^c`
502
503			`func Binom(c rat) PS {`
504			`Z:=mkPS()`
505			`go func() {`
506			`n := 1`
507			`t := itor(1)`
508			`for c.num!=0 {`
509			`put(t,Z)`
510			`t = mul(mul(t,c),i2tor(1,int64(n)))`
511			`c = sub(c,one)`
512			`n++`
513			`}`
514			`put(finis,Z)`
515			`}()`
516			`return Z`
517			`}`
518
519			`// Reciprocal of a power series`
520			`// let U = u + x*UU`
521			`// let Z = z + x*ZZ`
522			`// (u+xUU)(z+x*ZZ) = 1`
523			`// z = 1/u`
524			`// uZZ + zUU +xUUZZ = 0`
525			`// ZZ = -UU(z+xZZ)/u`
526
527			`func Recip(U PS) PS {`
528			`Z:=mkPS()`
529			`go func() {`
530			`ZZ:=mkPS2()`
531			`<-Z.req`
532			`z := inv(get(U))`
533			`Z.dat <- z`
534			`split(Mul(Cmul(neg(z),U),Shift(z,ZZ[0])),ZZ)`
535			`copy(ZZ[1],Z)`
536			`}()`
537			`return Z`
538			`}`
539
540			`// Exponential of a power series with constant term 0`
541			`// (nonzero constant term would make nonrational coefficients)`
542			`// bug: the constant term is simply ignored`
543			`// Z = exp(U)`
544			`// DZ = Z*DU`
545			`// integrate to get Z`
546
547			`func Exp(U PS) PS {`
548			`ZZ := mkPS2()`
549			`split(Integ(one,Mul(ZZ[0],Diff(U))),ZZ)`
550			`return ZZ[1]`
551			`}`
552
553			`// Substitute V for x in U, where the leading term of V is zero`
554			`// let U = u + x*UU`
555			`// let V = v + x*VV`
556			`// then S(U,V) = u + VV*S(V,UU)`
557			`// bug: a nonzero constant term is ignored`
558
559			`func Subst(U, V PS) PS {`
560			`Z:= mkPS()`
561			`go func() {`
562			`VV := Split(V)`
563			`<-Z.req`
564			`u := get(U)`
565			`Z.dat <- u`
566			`if end(u) == 0 {`
567			`if end(get(VV[0])) != 0 {`
568			`put(finis,Z)`
569			`} else {`
570			`copy(Mul(VV[0],Subst(U,VV[1])),Z)`
571			`}`
572			`}`
573			`}()`
574			`return Z`
575			`}`
576
577			`// Monomial Substition: U(c x^n)`
578			`// Each Ui is multiplied by c^i and followed by n-1 zeros`
579
580			`func MonSubst(U PS, c0 rat, n int) PS {`
581			`Z:= mkPS()`
582			`go func() {`
583			`c := one`
584			`for {`
585			`<-Z.req`
586			`u := get(U)`
587			`Z.dat <- mul(u, c)`
588			`c = mul(c, c0)`
589			`if end(u) != 0 {`
590			`Z.dat <- finis`
591			`break`
592			`}`
593			`for i := 1; i < n; i++ {`
594			`<-Z.req`
595			`Z.dat <- zero`
596			`}`
597			`}`
598			`}()`
599			`return Z`
600			`}`
601
602
603			`func Init() {`
604			`chnameserial = -1`
605			`seqno = 0`
606			`chnames = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"`
607			`zero = itor(0)`
608			`one = itor(1)`
609			`finis = i2tor(1,0)`
610			`Ones = Rep(one)`
611			`Twos = Rep(itor(2))`
612			`}`
613
614			`func check(U PS, c rat, count int, str string) {`
615			`for i := 0; i < count; i++ {`
616			`r := get(U)`
617			`if !r.eq(c) {`
618			`print("got: ")`
619			`r.pr()`
620			`print("should get ")`
621			`c.pr()`
622			`print("\n")`
623			`panic(str)`
624			`}`
625			`}`
626			`}`
627
628			`const N=10`
629			`func checka(U PS, a []rat, str string) {`
630			`for i := 0; i < N; i++ {`
631			`check(U, a[i], 1, str)`
632			`}`
633			`}`
634
635			`func main() {`
636			`Init()`
637			`if len(os.Args) > 1 { // print`
638			`print("Ones: "); printn(Ones, 10)`
639			`print("Twos: "); printn(Twos, 10)`
640			`print("Add: "); printn(Add(Ones, Twos), 10)`
641			`print("Diff: "); printn(Diff(Ones), 10)`
642			`print("Integ: "); printn(Integ(zero, Ones), 10)`
643			`print("CMul: "); printn(Cmul(neg(one), Ones), 10)`
644			`print("Sub: "); printn(Sub(Ones, Twos), 10)`
645			`print("Mul: "); printn(Mul(Ones, Ones), 10)`
646			`print("Exp: "); printn(Exp(Ones), 15)`
647			`print("MonSubst: "); printn(MonSubst(Ones, neg(one), 2), 10)`
648			`print("ATan: "); printn(Integ(zero, MonSubst(Ones, neg(one), 2)), 10)`
649			`} else { // test`
650			`check(Ones, one, 5, "Ones")`
651			`check(Add(Ones, Ones), itor(2), 0, "Add Ones Ones") // 1 1 1 1 1`
652			`check(Add(Ones, Twos), itor(3), 0, "Add Ones Twos") // 3 3 3 3 3`
653			`a := make([]rat, N)`
654			`d := Diff(Ones)`
655			`for i:=0; i < N; i++ {`
656			`a[i] = itor(int64(i+1))`
657			`}`
658			`checka(d, a, "Diff") // 1 2 3 4 5`
659			`in := Integ(zero, Ones)`
660			`a[0] = zero // integration constant`
661			`for i:=1; i < N; i++ {`
662			`a[i] = i2tor(1, int64(i))`
663			`}`
664			`checka(in, a, "Integ") // 0 1 1/2 1/3 1/4 1/5`
665			`check(Cmul(neg(one), Twos), itor(-2), 10, "CMul") // -1 -1 -1 -1 -1`
666			`check(Sub(Ones, Twos), itor(-1), 0, "Sub Ones Twos") // -1 -1 -1 -1 -1`
667			`m := Mul(Ones, Ones)`
668			`for i:=0; i < N; i++ {`
669			`a[i] = itor(int64(i+1))`
670			`}`
671			`checka(m, a, "Mul") // 1 2 3 4 5`
672			`e := Exp(Ones)`
673			`a[0] = itor(1)`
674			`a[1] = itor(1)`
675			`a[2] = i2tor(3,2)`
676			`a[3] = i2tor(13,6)`
677			`a[4] = i2tor(73,24)`
678			`a[5] = i2tor(167,40)`
679			`a[6] = i2tor(4051,720)`
680			`a[7] = i2tor(37633,5040)`
681			`a[8] = i2tor(43817,4480)`
682			`a[9] = i2tor(4596553,362880)`
683			`checka(e, a, "Exp") // 1 1 3/2 13/6 73/24`
684			`at := Integ(zero, MonSubst(Ones, neg(one), 2))`
685			`for c, i := 1, 0; i < N; i++ {`
686			`if i%2 == 0 {`
687			`a[i] = zero`
688			`} else {`
689			`a[i] = i2tor(int64(c), int64(i))`
690			`c *= -1`
691			`}`
692			`}`
693			`checka(at, a, "ATan") // 0 -1 0 -1/3 0 -1/5`
694			`/*`
695			`t := Revert(Integ(zero, MonSubst(Ones, neg(one), 2)))`
696			`a[0] = zero`
697			`a[1] = itor(1)`
698			`a[2] = zero`
699			`a[3] = i2tor(1,3)`
700			`a[4] = zero`
701			`a[5] = i2tor(2,15)`
702			`a[6] = zero`
703			`a[7] = i2tor(17,315)`
704			`a[8] = zero`
705			`a[9] = i2tor(62,2835)`
706			`checka(t, a, "Tan") // 0 1 0 1/3 0 2/15`
707			`*/`
708			`}`
709			`}`