gcc/testsuite/go.test/test/chan/powser1.go

   1 // $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<n; 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<n; 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<j; i=i+1) put(a[i],Z)
 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 = u*v + x*(u*VV+v*UU) + x*x*UU*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+x*UU)*(z+x*ZZ) = 1
 523 //      z = 1/u
 524 //      u*ZZ + z*UU +x*UU*ZZ = 0
 525 //      ZZ = -UU*(z+x*ZZ)/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 }