diff options
Diffstat (limited to 'test/chan/powser2.go')
-rw-r--r-- | test/chan/powser2.go | 585 |
1 files changed, 292 insertions, 293 deletions
diff --git a/test/chan/powser2.go b/test/chan/powser2.go index 0c523ac99..bc329270d 100644 --- a/test/chan/powser2.go +++ b/test/chan/powser2.go @@ -19,12 +19,12 @@ package main import "os" type rat struct { - num, den int64; // numerator, denominator + num, den int64 // numerator, denominator } type item interface { - pr(); - eq(c item) bool; + pr() + eq(c item) bool } func (u *rat) pr(){ @@ -37,14 +37,14 @@ func (u *rat) pr(){ } func (u *rat) eq(c item) bool { - c1 := c.(*rat); + c1 := c.(*rat) return u.num == c1.num && u.den == c1.den } type dch struct { - req chan int; - dat chan item; - nam int; + req chan int + dat chan item + nam int } type dch2 [2] *dch @@ -54,20 +54,20 @@ 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 item); - d.nam = c; - return d; + c := chnameserial % len(chnames) + chnameserial++ + d := new(dch) + d.req = make(chan int) + d.dat = make(chan item) + d.nam = c + return d } func mkdch2() *dch2 { - d2 := new(dch2); - d2[0] = mkdch(); - d2[1] = mkdch(); - return d2; + d2 := new(dch2) + d2[0] = mkdch() + d2[1] = mkdch() + return d2 } // split reads a single demand channel and replicates its @@ -85,98 +85,97 @@ func mkdch2() *dch2 { // generation to begin servicing out[1]. func dosplit(in *dch, out *dch2, wait chan int ){ - var t *dch; - both := false; // do not service both channels + both := false // do not service both channels select { case <-out[0].req: - ; + case <-wait: - both = true; + both = true select { case <-out[0].req: - ; + case <-out[1].req: - t=out[0]; out[0]=out[1]; out[1]=t; + 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; + 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; + <-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; + release := make(chan int) + go dosplit(in, out, release) + release <- 0 } func put(dat item, out *dch){ - <-out.req; - out.dat <- dat; + <-out.req + out.dat <- dat } func get(in *dch) *rat { - seqno++; - in.req <- seqno; - return (<-in.dat).(*rat); + seqno++ + in.req <- seqno + return (<-in.dat).(*rat) } // Get one item from each of n demand channels func getn(in []*dch) []item { - n:=len(in); - if n != 2 { panic("bad n in getn") }; - req := make([] chan int, 2); - dat := make([] chan item, 2); - out := make([]item, 2); - var i int; - var it item; + n:=len(in) + if n != 2 { panic("bad n in getn") } + req := make([] chan int, 2) + dat := make([] chan item, 2) + out := make([]item, 2) + var i int + var it item for i=0; i<n; i++ { - req[i] = in[i].req; - dat[i] = nil; + req[i] = in[i].req + dat[i] = nil } for n=2*n; n>0; n-- { - seqno++; + seqno++ select{ case req[0] <- seqno: - dat[0] = in[0].dat; - req[0] = nil; + dat[0] = in[0].dat + req[0] = nil case req[1] <- seqno: - dat[1] = in[1].dat; - req[1] = nil; + dat[1] = in[1].dat + req[1] = nil case it = <-dat[0]: - out[0] = it; - dat[0] = nil; + out[0] = it + dat[0] = nil case it = <-dat[1]: - out[1] = it; - dat[1] = nil; + out[1] = it + dat[1] = nil } } - return out; + return out } // Get one item from each of 2 demand channels func get2(in0 *dch, in1 *dch) []item { - return getn([]*dch{in0, in1}); + return getn([]*dch{in0, in1}) } func copy(in *dch, out *dch){ for { - <-out.req; - out.dat <- get(in); + <-out.req + out.dat <- get(in) } } @@ -186,8 +185,8 @@ func repeat(dat item, out *dch){ } } -type PS *dch; // power series -type PS2 *[2] PS; // pair of power series +type PS *dch // power series +type PS2 *[2] PS // pair of power series var Ones PS var Twos PS @@ -217,29 +216,29 @@ func gcd (u, v int64) int64{ // Make a rational from two ints and from one int func i2tor(u, v int64) *rat{ - g := gcd(u,v); - r := new(rat); + g := gcd(u,v) + r := new(rat) if v > 0 { - r.num = u/g; - r.den = v/g; + r.num = u/g + r.den = v/g } else { - r.num = -u/g; - r.den = -v/g; + r.num = -u/g + r.den = -v/g } - return r; + return r } func itor(u int64) *rat{ - return i2tor(u, 1); + return i2tor(u, 1) } -var zero *rat; -var one *rat; +var zero *rat +var one *rat // End mark and end test -var finis *rat; +var finis *rat func end(u *rat) int64 { if u.den==0 { return 1 } @@ -249,72 +248,72 @@ func end(u *rat) int64 { // 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)); + 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); - r := new(rat); - r.num =(u.num/g1)*(v.num/g2); - r.den = (u.den/g2)*(v.den/g1); - return r; + g1 := gcd(u.num,v.den) + g2 := gcd(u.den,v.num) + r := new(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); + return i2tor(-u.num, u.den) } func sub(u, v *rat) *rat{ - return add(u, neg(v)); + 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); + 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); + xn := float64(1) + x := float64(c.num)/float64(c.den) + val := float64(0) for i:=0; i<n; i++ { - u := get(U); + u := get(U) if end(u) != 0 { - break; + break } - val = val + x * float64(u.num)/float64(u.den); - xn = xn*x; + val = val + x * float64(u.num)/float64(u.den) + xn = xn*x } - print(val, "\n"); + print(val, "\n") } // Print n terms of a power series func Printn(U PS, n int){ - done := false; + done := false for ; !done && n>0; n-- { - u := get(U); + u := get(U) if end(u) != 0 { done = true } else { u.pr() } } - print(("\n")); + print(("\n")) } func Print(U PS){ - Printn(U,1000000000); + Printn(U,1000000000) } // 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); + y := get(U) if end(y) != 0 { return zero } - return add(y,mul(c,eval(c,U,n-1))); + return add(y,mul(c,eval(c,U,n-1))) } // Power-series constructors return channels on which power @@ -324,105 +323,105 @@ func eval(c *rat, U PS, n int) *rat{ // 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; + UU := mkdch2() + go split(U,UU) + return UU } // Add two power series func Add(U, V PS) PS{ - Z := mkPS(); + Z := mkPS() go func(U, V, Z PS){ - var uv [] item; + var uv [] item for { - <-Z.req; - uv = get2(U,V); + <-Z.req + uv = get2(U,V) switch end(uv[0].(*rat))+2*end(uv[1].(*rat)) { case 0: - Z.dat <- add(uv[0].(*rat), uv[1].(*rat)); + Z.dat <- add(uv[0].(*rat), uv[1].(*rat)) case 1: - Z.dat <- uv[1]; - copy(V,Z); + Z.dat <- uv[1] + copy(V,Z) case 2: - Z.dat <- uv[0]; - copy(U,Z); + Z.dat <- uv[0] + copy(U,Z) case 3: - Z.dat <- finis; + Z.dat <- finis } } - }(U, V, Z); - return Z; + }(U, V, Z) + return Z } // Multiply a power series by a constant func Cmul(c *rat,U PS) PS{ - Z := mkPS(); + Z := mkPS() go func(c *rat, U, Z PS){ - done := false; + done := false for !done { - <-Z.req; - u := get(U); + <-Z.req + u := get(U) if end(u) != 0 { done = true } else { Z.dat <- mul(c,u) } } - Z.dat <- finis; - }(c, U, Z); - return Z; + Z.dat <- finis + }(c, U, Z) + return Z } // Subtract func Sub(U, V PS) PS{ - return Add(U, Cmul(neg(one), V)); + 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(); + Z := mkPS() go func(n int, U PS, Z PS){ for ; n>0; n-- { put(zero,Z) } - copy(U,Z); - }(n, U, Z); - return Z; + copy(U,Z) + }(n, U, Z) + return Z } // Multiply by x func Xmul(U PS) PS{ - return Monmul(U,1); + return Monmul(U,1) } func Rep(c *rat) PS{ - Z := mkPS(); - go repeat(c,Z); - return Z; + Z := mkPS() + go repeat(c,Z) + return Z } // Monomial c*x^n func Mon(c *rat, n int) PS{ - Z:=mkPS(); + Z:=mkPS() go func(c *rat, n int, Z PS){ if(c.num!=0) { for ; n>0; n=n-1 { put(zero,Z) } - put(c,Z); + put(c,Z) } - put(finis,Z); - }(c, n, Z); - return Z; + put(finis,Z) + }(c, n, Z) + return Z } func Shift(c *rat, U PS) PS{ - Z := mkPS(); + Z := mkPS() go func(c *rat, U, Z PS){ - put(c,Z); - copy(U,Z); - }(c, U, Z); - return Z; + put(c,Z) + copy(U,Z) + }(c, U, Z) + return Z } // simple pole at 1: 1/(1-x) = 1 1 1 1 1 ... @@ -432,17 +431,17 @@ func Shift(c *rat, U PS) PS{ /* func Poly(a [] *rat) PS{ - Z:=mkPS(); + Z:=mkPS() begin func(a [] *rat, Z PS){ - j:=0; - done:=0; + 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<j; i=i+1) put(a[i],Z); - put(finis,Z); - }(); - return Z; + if(a[j-1].num!=0) done=1 + i:=0 + for(; i<j; i=i+1) put(a[i],Z) + put(finis,Z) + }() + return Z } */ @@ -452,82 +451,82 @@ func Poly(a [] *rat) PS{ // then UV = u*v + x*(u*VV+v*UU) + x*x*UU*VV func Mul(U, V PS) PS{ - Z:=mkPS(); + Z:=mkPS() go func(U, V, Z PS){ - <-Z.req; - uv := get2(U,V); + <-Z.req + uv := get2(U,V) if end(uv[0].(*rat))!=0 || end(uv[1].(*rat)) != 0 { - Z.dat <- finis; + Z.dat <- finis } else { - Z.dat <- mul(uv[0].(*rat),uv[1].(*rat)); - UU := Split(U); - VV := Split(V); - W := Add(Cmul(uv[0].(*rat),VV[0]),Cmul(uv[1].(*rat),UU[0])); - <-Z.req; - Z.dat <- get(W); - copy(Add(W,Mul(UU[1],VV[1])),Z); + Z.dat <- mul(uv[0].(*rat),uv[1].(*rat)) + UU := Split(U) + VV := Split(V) + W := Add(Cmul(uv[0].(*rat),VV[0]),Cmul(uv[1].(*rat),UU[0])) + <-Z.req + Z.dat <- get(W) + copy(Add(W,Mul(UU[1],VV[1])),Z) } - }(U, V, Z); - return Z; + }(U, V, Z) + return Z } // Differentiate func Diff(U PS) PS{ - Z:=mkPS(); + Z:=mkPS() go func(U, Z PS){ - <-Z.req; - u := get(U); + <-Z.req + u := get(U) if end(u) == 0 { - done:=false; + done:=false for i:=1; !done; i++ { - u = get(U); + u = get(U) if end(u) != 0 { done=true } else { - Z.dat <- mul(itor(int64(i)),u); - <-Z.req; + Z.dat <- mul(itor(int64(i)),u) + <-Z.req } } } - Z.dat <- finis; - }(U, Z); - return Z; + Z.dat <- finis + }(U, Z) + return Z } // Integrate, with const of integration func Integ(c *rat,U PS) PS{ - Z:=mkPS(); + Z:=mkPS() go func(c *rat, U, Z PS){ - put(c,Z); - done:=false; + put(c,Z) + done:=false for i:=1; !done; i++ { - <-Z.req; - u := get(U); + <-Z.req + u := get(U) if end(u) != 0 { done= true } - Z.dat <- mul(i2tor(1,int64(i)),u); + Z.dat <- mul(i2tor(1,int64(i)),u) } - Z.dat <- finis; - }(c, U, Z); - return Z; + Z.dat <- finis + }(c, U, Z) + return Z } // Binomial theorem (1+x)^c func Binom(c *rat) PS{ - Z:=mkPS(); + Z:=mkPS() go func(c *rat, Z PS){ - n := 1; - t := itor(1); + 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(t,Z) + t = mul(mul(t,c),i2tor(1,int64(n))) + c = sub(c,one) + n++ } - put(finis,Z); - }(c, Z); - return Z; + put(finis,Z) + }(c, Z) + return Z } // Reciprocal of a power series @@ -536,19 +535,19 @@ func Binom(c *rat) PS{ // (u+x*UU)*(z+x*ZZ) = 1 // z = 1/u // u*ZZ + z*UU +x*UU*ZZ = 0 -// ZZ = -UU*(z+x*ZZ)/u; +// ZZ = -UU*(z+x*ZZ)/u func Recip(U PS) PS{ - Z:=mkPS(); + Z:=mkPS() go func(U, Z PS){ - 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); - }(U, Z); - return Z; + 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) + }(U, Z) + return Z } // Exponential of a power series with constant term 0 @@ -559,9 +558,9 @@ func Recip(U PS) PS{ // integrate to get Z func Exp(U PS) PS{ - ZZ := mkPS2(); - split(Integ(one,Mul(ZZ[0],Diff(U))),ZZ); - return ZZ[1]; + 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 @@ -571,69 +570,69 @@ func Exp(U PS) PS{ // bug: a nonzero constant term is ignored func Subst(U, V PS) PS { - Z:= mkPS(); + Z:= mkPS() go func(U, V, Z PS) { - VV := Split(V); - <-Z.req; - u := get(U); - Z.dat <- u; + VV := Split(V) + <-Z.req + u := get(U) + Z.dat <- u if end(u) == 0 { if end(get(VV[0])) != 0 { - put(finis,Z); + put(finis,Z) } else { - copy(Mul(VV[0],Subst(U,VV[1])),Z); + copy(Mul(VV[0],Subst(U,VV[1])),Z) } } - }(U, V, Z); - return Z; + }(U, V, 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(); + Z:= mkPS() go func(U, Z PS, c0 *rat, n int) { - c := one; + c := one for { - <-Z.req; - u := get(U); - Z.dat <- mul(u, c); - c = mul(c, c0); + <-Z.req + u := get(U) + Z.dat <- mul(u, c) + c = mul(c, c0) if end(u) != 0 { - Z.dat <- finis; - break; + Z.dat <- finis + break } for i := 1; i < n; i++ { - <-Z.req; - Z.dat <- zero; + <-Z.req + Z.dat <- zero } } - }(U, Z, c0, n); - return Z; + }(U, Z, c0, n) + 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)); + 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); + r := get(U) if !r.eq(c) { - print("got: "); - r.pr(); - print("should get "); - c.pr(); - print("\n"); + print("got: ") + r.pr() + print("should get ") + c.pr() + print("\n") panic(str) } } @@ -642,82 +641,82 @@ func check(U PS, c *rat, count int, str string) { const N=10 func checka(U PS, a []*rat, str string) { for i := 0; i < N; i++ { - check(U, a[i], 1, str); + check(U, a[i], 1, str) } } func main() { - Init(); + 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); + 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); + 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 + 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); + 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)); + 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)); + 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 + 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 */ } } |