libgo/go/math/big/rat_test.go

   1 // Copyright 2010 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package big
   6
   7 import (
   8         "bytes"
   9         "encoding/gob"
  10         "fmt"
  11         "math"
  12         "strconv"
  13         "strings"
  14         "testing"
  15 )
  16
  17 func TestZeroRat(t *testing.T) {
  18         var x, y, z Rat
  19         y.SetFrac64(0, 42)
  20
  21         if x.Cmp(&y) != 0 {
  22                 t.Errorf("x and y should be both equal and zero")
  23         }
  24
  25         if s := x.String(); s != "0/1" {
  26                 t.Errorf("got x = %s, want 0/1", s)
  27         }
  28
  29         if s := x.RatString(); s != "0" {
  30                 t.Errorf("got x = %s, want 0", s)
  31         }
  32
  33         z.Add(&x, &y)
  34         if s := z.RatString(); s != "0" {
  35                 t.Errorf("got x+y = %s, want 0", s)
  36         }
  37
  38         z.Sub(&x, &y)
  39         if s := z.RatString(); s != "0" {
  40                 t.Errorf("got x-y = %s, want 0", s)
  41         }
  42
  43         z.Mul(&x, &y)
  44         if s := z.RatString(); s != "0" {
  45                 t.Errorf("got x*y = %s, want 0", s)
  46         }
  47
  48         // check for division by zero
  49         defer func() {
  50                 if s := recover(); s == nil || s.(string) != "division by zero" {
  51                         panic(s)
  52                 }
  53         }()
  54         z.Quo(&x, &y)
  55 }
  56
  57 var setStringTests = []struct {
  58         in, out string
  59         ok      bool
  60 }{
  61         {"0", "0", true},
  62         {"-0", "0", true},
  63         {"1", "1", true},
  64         {"-1", "-1", true},
  65         {"1.", "1", true},
  66         {"1e0", "1", true},
  67         {"1.e1", "10", true},
  68         {in: "1e", ok: false},
  69         {in: "1.e", ok: false},
  70         {in: "1e+14e-5", ok: false},
  71         {in: "1e4.5", ok: false},
  72         {in: "r", ok: false},
  73         {in: "a/b", ok: false},
  74         {in: "a.b", ok: false},
  75         {"-0.1", "-1/10", true},
  76         {"-.1", "-1/10", true},
  77         {"2/4", "1/2", true},
  78         {".25", "1/4", true},
  79         {"-1/5", "-1/5", true},
  80         {"8129567.7690E14", "812956776900000000000", true},
  81         {"78189e+4", "781890000", true},
  82         {"553019.8935e+8", "55301989350000", true},
  83         {"98765432109876543210987654321e-10", "98765432109876543210987654321/10000000000", true},
  84         {"9877861857500000E-7", "3951144743/4", true},
  85         {"2169378.417e-3", "2169378417/1000000", true},
  86         {"884243222337379604041632732738665534", "884243222337379604041632732738665534", true},
  87         {"53/70893980658822810696", "53/70893980658822810696", true},
  88         {"106/141787961317645621392", "53/70893980658822810696", true},
  89         {"204211327800791583.81095", "4084226556015831676219/20000", true},
  90 }
  91
  92 func TestRatSetString(t *testing.T) {
  93         for i, test := range setStringTests {
  94                 x, ok := new(Rat).SetString(test.in)
  95
  96                 if ok {
  97                         if !test.ok {
  98                                 t.Errorf("#%d SetString(%q) expected failure", i, test.in)
  99                         } else if x.RatString() != test.out {
 100                                 t.Errorf("#%d SetString(%q) got %s want %s", i, test.in, x.RatString(), test.out)
 101                         }
 102                 } else if x != nil {
 103                         t.Errorf("#%d SetString(%q) got %p want nil", i, test.in, x)
 104                 }
 105         }
 106 }
 107
 108 func TestRatScan(t *testing.T) {
 109         var buf bytes.Buffer
 110         for i, test := range setStringTests {
 111                 x := new(Rat)
 112                 buf.Reset()
 113                 buf.WriteString(test.in)
 114
 115                 _, err := fmt.Fscanf(&buf, "%v", x)
 116                 if err == nil != test.ok {
 117                         if test.ok {
 118                                 t.Errorf("#%d error: %s", i, err)
 119                         } else {
 120                                 t.Errorf("#%d expected error", i)
 121                         }
 122                         continue
 123                 }
 124                 if err == nil && x.RatString() != test.out {
 125                         t.Errorf("#%d got %s want %s", i, x.RatString(), test.out)
 126                 }
 127         }
 128 }
 129
 130 var floatStringTests = []struct {
 131         in   string
 132         prec int
 133         out  string
 134 }{
 135         {"0", 0, "0"},
 136         {"0", 4, "0.0000"},
 137         {"1", 0, "1"},
 138         {"1", 2, "1.00"},
 139         {"-1", 0, "-1"},
 140         {".25", 2, "0.25"},
 141         {".25", 1, "0.3"},
 142         {".25", 3, "0.250"},
 143         {"-1/3", 3, "-0.333"},
 144         {"-2/3", 4, "-0.6667"},
 145         {"0.96", 1, "1.0"},
 146         {"0.999", 2, "1.00"},
 147         {"0.9", 0, "1"},
 148         {".25", -1, "0"},
 149         {".55", -1, "1"},
 150 }
 151
 152 func TestFloatString(t *testing.T) {
 153         for i, test := range floatStringTests {
 154                 x, _ := new(Rat).SetString(test.in)
 155
 156                 if x.FloatString(test.prec) != test.out {
 157                         t.Errorf("#%d got %s want %s", i, x.FloatString(test.prec), test.out)
 158                 }
 159         }
 160 }
 161
 162 func TestRatSign(t *testing.T) {
 163         zero := NewRat(0, 1)
 164         for _, a := range setStringTests {
 165                 x, ok := new(Rat).SetString(a.in)
 166                 if !ok {
 167                         continue
 168                 }
 169                 s := x.Sign()
 170                 e := x.Cmp(zero)
 171                 if s != e {
 172                         t.Errorf("got %d; want %d for z = %v", s, e, &x)
 173                 }
 174         }
 175 }
 176
 177 var ratCmpTests = []struct {
 178         rat1, rat2 string
 179         out        int
 180 }{
 181         {"0", "0/1", 0},
 182         {"1/1", "1", 0},
 183         {"-1", "-2/2", 0},
 184         {"1", "0", 1},
 185         {"0/1", "1/1", -1},
 186         {"-5/1434770811533343057144", "-5/1434770811533343057145", -1},
 187         {"49832350382626108453/8964749413", "49832350382626108454/8964749413", -1},
 188         {"-37414950961700930/7204075375675961", "37414950961700930/7204075375675961", -1},
 189         {"37414950961700930/7204075375675961", "74829901923401860/14408150751351922", 0},
 190 }
 191
 192 func TestRatCmp(t *testing.T) {
 193         for i, test := range ratCmpTests {
 194                 x, _ := new(Rat).SetString(test.rat1)
 195                 y, _ := new(Rat).SetString(test.rat2)
 196
 197                 out := x.Cmp(y)
 198                 if out != test.out {
 199                         t.Errorf("#%d got out = %v; want %v", i, out, test.out)
 200                 }
 201         }
 202 }
 203
 204 func TestIsInt(t *testing.T) {
 205         one := NewInt(1)
 206         for _, a := range setStringTests {
 207                 x, ok := new(Rat).SetString(a.in)
 208                 if !ok {
 209                         continue
 210                 }
 211                 i := x.IsInt()
 212                 e := x.Denom().Cmp(one) == 0
 213                 if i != e {
 214                         t.Errorf("got IsInt(%v) == %v; want %v", x, i, e)
 215                 }
 216         }
 217 }
 218
 219 func TestRatAbs(t *testing.T) {
 220         zero := new(Rat)
 221         for _, a := range setStringTests {
 222                 x, ok := new(Rat).SetString(a.in)
 223                 if !ok {
 224                         continue
 225                 }
 226                 e := new(Rat).Set(x)
 227                 if e.Cmp(zero) < 0 {
 228                         e.Sub(zero, e)
 229                 }
 230                 z := new(Rat).Abs(x)
 231                 if z.Cmp(e) != 0 {
 232                         t.Errorf("got Abs(%v) = %v; want %v", x, z, e)
 233                 }
 234         }
 235 }
 236
 237 func TestRatNeg(t *testing.T) {
 238         zero := new(Rat)
 239         for _, a := range setStringTests {
 240                 x, ok := new(Rat).SetString(a.in)
 241                 if !ok {
 242                         continue
 243                 }
 244                 e := new(Rat).Sub(zero, x)
 245                 z := new(Rat).Neg(x)
 246                 if z.Cmp(e) != 0 {
 247                         t.Errorf("got Neg(%v) = %v; want %v", x, z, e)
 248                 }
 249         }
 250 }
 251
 252 func TestRatInv(t *testing.T) {
 253         zero := new(Rat)
 254         for _, a := range setStringTests {
 255                 x, ok := new(Rat).SetString(a.in)
 256                 if !ok {
 257                         continue
 258                 }
 259                 if x.Cmp(zero) == 0 {
 260                         continue // avoid division by zero
 261                 }
 262                 e := new(Rat).SetFrac(x.Denom(), x.Num())
 263                 z := new(Rat).Inv(x)
 264                 if z.Cmp(e) != 0 {
 265                         t.Errorf("got Inv(%v) = %v; want %v", x, z, e)
 266                 }
 267         }
 268 }
 269
 270 type ratBinFun func(z, x, y *Rat) *Rat
 271 type ratBinArg struct {
 272         x, y, z string
 273 }
 274
 275 func testRatBin(t *testing.T, i int, name string, f ratBinFun, a ratBinArg) {
 276         x, _ := new(Rat).SetString(a.x)
 277         y, _ := new(Rat).SetString(a.y)
 278         z, _ := new(Rat).SetString(a.z)
 279         out := f(new(Rat), x, y)
 280
 281         if out.Cmp(z) != 0 {
 282                 t.Errorf("%s #%d got %s want %s", name, i, out, z)
 283         }
 284 }
 285
 286 var ratBinTests = []struct {
 287         x, y      string
 288         sum, prod string
 289 }{
 290         {"0", "0", "0", "0"},
 291         {"0", "1", "1", "0"},
 292         {"-1", "0", "-1", "0"},
 293         {"-1", "1", "0", "-1"},
 294         {"1", "1", "2", "1"},
 295         {"1/2", "1/2", "1", "1/4"},
 296         {"1/4", "1/3", "7/12", "1/12"},
 297         {"2/5", "-14/3", "-64/15", "-28/15"},
 298         {"4707/49292519774798173060", "-3367/70976135186689855734", "84058377121001851123459/1749296273614329067191168098769082663020", "-1760941/388732505247628681598037355282018369560"},
 299         {"-61204110018146728334/3", "-31052192278051565633/2", "-215564796870448153567/6", "950260896245257153059642991192710872711/3"},
 300         {"-854857841473707320655/4237645934602118692642972629634714039", "-18/31750379913563777419", "-27/133467566250814981", "15387441146526731771790/134546868362786310073779084329032722548987800600710485341"},
 301         {"618575745270541348005638912139/19198433543745179392300736", "-19948846211000086/637313996471", "27674141753240653/30123979153216", "-6169936206128396568797607742807090270137721977/6117715203873571641674006593837351328"},
 302         {"-3/26206484091896184128", "5/2848423294177090248", "15310893822118706237/9330894968229805033368778458685147968", "-5/24882386581946146755650075889827061248"},
 303         {"26946729/330400702820", "41563965/225583428284", "1238218672302860271/4658307703098666660055", "224002580204097/14906584649915733312176"},
 304         {"-8259900599013409474/7", "-84829337473700364773/56707961321161574960", "-468402123685491748914621885145127724451/396955729248131024720", "350340947706464153265156004876107029701/198477864624065512360"},
 305         {"575775209696864/1320203974639986246357", "29/712593081308", "410331716733912717985762465/940768218243776489278275419794956", "808/45524274987585732633"},
 306         {"1786597389946320496771/2066653520653241", "6269770/1992362624741777", "3559549865190272133656109052308126637/4117523232840525481453983149257", "8967230/3296219033"},
 307         {"-36459180403360509753/32150500941194292113930", "9381566963714/9633539", "301622077145533298008420642898530153/309723104686531919656937098270", "-3784609207827/3426986245"},
 308 }
 309
 310 func TestRatBin(t *testing.T) {
 311         for i, test := range ratBinTests {
 312                 arg := ratBinArg{test.x, test.y, test.sum}
 313                 testRatBin(t, i, "Add", (*Rat).Add, arg)
 314
 315                 arg = ratBinArg{test.y, test.x, test.sum}
 316                 testRatBin(t, i, "Add symmetric", (*Rat).Add, arg)
 317
 318                 arg = ratBinArg{test.sum, test.x, test.y}
 319                 testRatBin(t, i, "Sub", (*Rat).Sub, arg)
 320
 321                 arg = ratBinArg{test.sum, test.y, test.x}
 322                 testRatBin(t, i, "Sub symmetric", (*Rat).Sub, arg)
 323
 324                 arg = ratBinArg{test.x, test.y, test.prod}
 325                 testRatBin(t, i, "Mul", (*Rat).Mul, arg)
 326
 327                 arg = ratBinArg{test.y, test.x, test.prod}
 328                 testRatBin(t, i, "Mul symmetric", (*Rat).Mul, arg)
 329
 330                 if test.x != "0" {
 331                         arg = ratBinArg{test.prod, test.x, test.y}
 332                         testRatBin(t, i, "Quo", (*Rat).Quo, arg)
 333                 }
 334
 335                 if test.y != "0" {
 336                         arg = ratBinArg{test.prod, test.y, test.x}
 337                         testRatBin(t, i, "Quo symmetric", (*Rat).Quo, arg)
 338                 }
 339         }
 340 }
 341
 342 func TestIssue820(t *testing.T) {
 343         x := NewRat(3, 1)
 344         y := NewRat(2, 1)
 345         z := y.Quo(x, y)
 346         q := NewRat(3, 2)
 347         if z.Cmp(q) != 0 {
 348                 t.Errorf("got %s want %s", z, q)
 349         }
 350
 351         y = NewRat(3, 1)
 352         x = NewRat(2, 1)
 353         z = y.Quo(x, y)
 354         q = NewRat(2, 3)
 355         if z.Cmp(q) != 0 {
 356                 t.Errorf("got %s want %s", z, q)
 357         }
 358
 359         x = NewRat(3, 1)
 360         z = x.Quo(x, x)
 361         q = NewRat(3, 3)
 362         if z.Cmp(q) != 0 {
 363                 t.Errorf("got %s want %s", z, q)
 364         }
 365 }
 366
 367 var setFrac64Tests = []struct {
 368         a, b int64
 369         out  string
 370 }{
 371         {0, 1, "0"},
 372         {0, -1, "0"},
 373         {1, 1, "1"},
 374         {-1, 1, "-1"},
 375         {1, -1, "-1"},
 376         {-1, -1, "1"},
 377         {-9223372036854775808, -9223372036854775808, "1"},
 378 }
 379
 380 func TestRatSetFrac64Rat(t *testing.T) {
 381         for i, test := range setFrac64Tests {
 382                 x := new(Rat).SetFrac64(test.a, test.b)
 383                 if x.RatString() != test.out {
 384                         t.Errorf("#%d got %s want %s", i, x.RatString(), test.out)
 385                 }
 386         }
 387 }
 388
 389 func TestRatGobEncoding(t *testing.T) {
 390         var medium bytes.Buffer
 391         enc := gob.NewEncoder(&medium)
 392         dec := gob.NewDecoder(&medium)
 393         for _, test := range encodingTests {
 394                 medium.Reset() // empty buffer for each test case (in case of failures)
 395                 var tx Rat
 396                 tx.SetString(test + ".14159265")
 397                 if err := enc.Encode(&tx); err != nil {
 398                         t.Errorf("encoding of %s failed: %s", &tx, err)
 399                 }
 400                 var rx Rat
 401                 if err := dec.Decode(&rx); err != nil {
 402                         t.Errorf("decoding of %s failed: %s", &tx, err)
 403                 }
 404                 if rx.Cmp(&tx) != 0 {
 405                         t.Errorf("transmission of %s failed: got %s want %s", &tx, &rx, &tx)
 406                 }
 407         }
 408 }
 409
 410 // Sending a nil Rat pointer (inside a slice) on a round trip through gob should yield a zero.
 411 // TODO: top-level nils.
 412 func TestGobEncodingNilRatInSlice(t *testing.T) {
 413         buf := new(bytes.Buffer)
 414         enc := gob.NewEncoder(buf)
 415         dec := gob.NewDecoder(buf)
 416
 417         var in = make([]*Rat, 1)
 418         err := enc.Encode(&in)
 419         if err != nil {
 420                 t.Errorf("gob encode failed: %q", err)
 421         }
 422         var out []*Rat
 423         err = dec.Decode(&out)
 424         if err != nil {
 425                 t.Fatalf("gob decode failed: %q", err)
 426         }
 427         if len(out) != 1 {
 428                 t.Fatalf("wrong len; want 1 got %d", len(out))
 429         }
 430         var zero Rat
 431         if out[0].Cmp(&zero) != 0 {
 432                 t.Errorf("transmission of (*Int)(nill) failed: got %s want 0", out)
 433         }
 434 }
 435
 436 func TestIssue2379(t *testing.T) {
 437         // 1) no aliasing
 438         q := NewRat(3, 2)
 439         x := new(Rat)
 440         x.SetFrac(NewInt(3), NewInt(2))
 441         if x.Cmp(q) != 0 {
 442                 t.Errorf("1) got %s want %s", x, q)
 443         }
 444
 445         // 2) aliasing of numerator
 446         x = NewRat(2, 3)
 447         x.SetFrac(NewInt(3), x.Num())
 448         if x.Cmp(q) != 0 {
 449                 t.Errorf("2) got %s want %s", x, q)
 450         }
 451
 452         // 3) aliasing of denominator
 453         x = NewRat(2, 3)
 454         x.SetFrac(x.Denom(), NewInt(2))
 455         if x.Cmp(q) != 0 {
 456                 t.Errorf("3) got %s want %s", x, q)
 457         }
 458
 459         // 4) aliasing of numerator and denominator
 460         x = NewRat(2, 3)
 461         x.SetFrac(x.Denom(), x.Num())
 462         if x.Cmp(q) != 0 {
 463                 t.Errorf("4) got %s want %s", x, q)
 464         }
 465
 466         // 5) numerator and denominator are the same
 467         q = NewRat(1, 1)
 468         x = new(Rat)
 469         n := NewInt(7)
 470         x.SetFrac(n, n)
 471         if x.Cmp(q) != 0 {
 472                 t.Errorf("5) got %s want %s", x, q)
 473         }
 474 }
 475
 476 func TestIssue3521(t *testing.T) {
 477         a := new(Int)
 478         b := new(Int)
 479         a.SetString("64375784358435883458348587", 0)
 480         b.SetString("4789759874531", 0)
 481
 482         // 0) a raw zero value has 1 as denominator
 483         zero := new(Rat)
 484         one := NewInt(1)
 485         if zero.Denom().Cmp(one) != 0 {
 486                 t.Errorf("0) got %s want %s", zero.Denom(), one)
 487         }
 488
 489         // 1a) a zero value remains zero independent of denominator
 490         x := new(Rat)
 491         x.Denom().Set(new(Int).Neg(b))
 492         if x.Cmp(zero) != 0 {
 493                 t.Errorf("1a) got %s want %s", x, zero)
 494         }
 495
 496         // 1b) a zero value may have a denominator != 0 and != 1
 497         x.Num().Set(a)
 498         qab := new(Rat).SetFrac(a, b)
 499         if x.Cmp(qab) != 0 {
 500                 t.Errorf("1b) got %s want %s", x, qab)
 501         }
 502
 503         // 2a) an integral value becomes a fraction depending on denominator
 504         x.SetFrac64(10, 2)
 505         x.Denom().SetInt64(3)
 506         q53 := NewRat(5, 3)
 507         if x.Cmp(q53) != 0 {
 508                 t.Errorf("2a) got %s want %s", x, q53)
 509         }
 510
 511         // 2b) an integral value becomes a fraction depending on denominator
 512         x = NewRat(10, 2)
 513         x.Denom().SetInt64(3)
 514         if x.Cmp(q53) != 0 {
 515                 t.Errorf("2b) got %s want %s", x, q53)
 516         }
 517
 518         // 3) changing the numerator/denominator of a Rat changes the Rat
 519         x.SetFrac(a, b)
 520         a = x.Num()
 521         b = x.Denom()
 522         a.SetInt64(5)
 523         b.SetInt64(3)
 524         if x.Cmp(q53) != 0 {
 525                 t.Errorf("3) got %s want %s", x, q53)
 526         }
 527 }
 528
 529 // Test inputs to Rat.SetString.  The prefix "long:" causes the test
 530 // to be skipped in --test.short mode.  (The threshold is about 500us.)
 531 var float64inputs = []string{
 532         // Constants plundered from strconv/testfp.txt.
 533
 534         // Table 1: Stress Inputs for Conversion to 53-bit Binary, < 1/2 ULP
 535         "5e+125",
 536         "69e+267",
 537         "999e-026",
 538         "7861e-034",
 539         "75569e-254",
 540         "928609e-261",
 541         "9210917e+080",
 542         "84863171e+114",
 543         "653777767e+273",
 544         "5232604057e-298",
 545         "27235667517e-109",
 546         "653532977297e-123",
 547         "3142213164987e-294",
 548         "46202199371337e-072",
 549         "231010996856685e-073",
 550         "9324754620109615e+212",
 551         "78459735791271921e+049",
 552         "272104041512242479e+200",
 553         "6802601037806061975e+198",
 554         "20505426358836677347e-221",
 555         "836168422905420598437e-234",
 556         "4891559871276714924261e+222",
 557
 558         // Table 2: Stress Inputs for Conversion to 53-bit Binary, > 1/2 ULP
 559         "9e-265",
 560         "85e-037",
 561         "623e+100",
 562         "3571e+263",
 563         "81661e+153",
 564         "920657e-023",
 565         "4603285e-024",
 566         "87575437e-309",
 567         "245540327e+122",
 568         "6138508175e+120",
 569         "83356057653e+193",
 570         "619534293513e+124",
 571         "2335141086879e+218",
 572         "36167929443327e-159",
 573         "609610927149051e-255",
 574         "3743626360493413e-165",
 575         "94080055902682397e-242",
 576         "899810892172646163e+283",
 577         "7120190517612959703e+120",
 578         "25188282901709339043e-252",
 579         "308984926168550152811e-052",
 580         "6372891218502368041059e+064",
 581
 582         // Table 14: Stress Inputs for Conversion to 24-bit Binary, <1/2 ULP
 583         "5e-20",
 584         "67e+14",
 585         "985e+15",
 586         "7693e-42",
 587         "55895e-16",
 588         "996622e-44",
 589         "7038531e-32",
 590         "60419369e-46",
 591         "702990899e-20",
 592         "6930161142e-48",
 593         "25933168707e+13",
 594         "596428896559e+20",
 595
 596         // Table 15: Stress Inputs for Conversion to 24-bit Binary, >1/2 ULP
 597         "3e-23",
 598         "57e+18",
 599         "789e-35",
 600         "2539e-18",
 601         "76173e+28",
 602         "887745e-11",
 603         "5382571e-37",
 604         "82381273e-35",
 605         "750486563e-38",
 606         "3752432815e-39",
 607         "75224575729e-45",
 608         "459926601011e+15",
 609
 610         // Constants plundered from strconv/atof_test.go.
 611
 612         "0",
 613         "1",
 614         "+1",
 615         "1e23",
 616         "1E23",
 617         "100000000000000000000000",
 618         "1e-100",
 619         "123456700",
 620         "99999999999999974834176",
 621         "100000000000000000000001",
 622         "100000000000000008388608",
 623         "100000000000000016777215",
 624         "100000000000000016777216",
 625         "-1",
 626         "-0.1",
 627         "-0", // NB: exception made for this input
 628         "1e-20",
 629         "625e-3",
 630
 631         // largest float64
 632         "1.7976931348623157e308",
 633         "-1.7976931348623157e308",
 634         // next float64 - too large
 635         "1.7976931348623159e308",
 636         "-1.7976931348623159e308",
 637         // the border is ...158079
 638         // borderline - okay
 639         "1.7976931348623158e308",
 640         "-1.7976931348623158e308",
 641         // borderline - too large
 642         "1.797693134862315808e308",
 643         "-1.797693134862315808e308",
 644
 645         // a little too large
 646         "1e308",
 647         "2e308",
 648         "1e309",
 649
 650         // way too large
 651         "1e310",
 652         "-1e310",
 653         "1e400",
 654         "-1e400",
 655         "long:1e400000",
 656         "long:-1e400000",
 657
 658         // denormalized
 659         "1e-305",
 660         "1e-306",
 661         "1e-307",
 662         "1e-308",
 663         "1e-309",
 664         "1e-310",
 665         "1e-322",
 666         // smallest denormal
 667         "5e-324",
 668         "4e-324",
 669         "3e-324",
 670         // too small
 671         "2e-324",
 672         // way too small
 673         "1e-350",
 674         "long:1e-400000",
 675         // way too small, negative
 676         "-1e-350",
 677         "long:-1e-400000",
 678
 679         // try to overflow exponent
 680         // [Disabled: too slow and memory-hungry with rationals.]
 681         // "1e-4294967296",
 682         // "1e+4294967296",
 683         // "1e-18446744073709551616",
 684         // "1e+18446744073709551616",
 685
 686         // http://www.exploringbinary.com/java-hangs-when-converting-2-2250738585072012e-308/
 687         "2.2250738585072012e-308",
 688         // http://www.exploringbinary.com/php-hangs-on-numeric-value-2-2250738585072011e-308/
 689
 690         "2.2250738585072011e-308",
 691
 692         // A very large number (initially wrongly parsed by the fast algorithm).
 693         "4.630813248087435e+307",
 694
 695         // A different kind of very large number.
 696         "22.222222222222222",
 697         "long:2." + strings.Repeat("2", 4000) + "e+1",
 698
 699         // Exactly halfway between 1 and math.Nextafter(1, 2).
 700         // Round to even (down).
 701         "1.00000000000000011102230246251565404236316680908203125",
 702         // Slightly lower; still round down.
 703         "1.00000000000000011102230246251565404236316680908203124",
 704         // Slightly higher; round up.
 705         "1.00000000000000011102230246251565404236316680908203126",
 706         // Slightly higher, but you have to read all the way to the end.
 707         "long:1.00000000000000011102230246251565404236316680908203125" + strings.Repeat("0", 10000) + "1",
 708
 709         // Smallest denormal, 2^(-1022-52)
 710         "4.940656458412465441765687928682213723651e-324",
 711         // Half of smallest denormal, 2^(-1022-53)
 712         "2.470328229206232720882843964341106861825e-324",
 713         // A little more than the exact half of smallest denormal
 714         // 2^-1075 + 2^-1100.  (Rounds to 1p-1074.)
 715         "2.470328302827751011111470718709768633275e-324",
 716         // The exact halfway between smallest normal and largest denormal:
 717         // 2^-1022 - 2^-1075.  (Rounds to 2^-1022.)
 718         "2.225073858507201136057409796709131975935e-308",
 719
 720         "1152921504606846975",  //   1<<60 - 1
 721         "-1152921504606846975", // -(1<<60 - 1)
 722         "1152921504606846977",  //   1<<60 + 1
 723         "-1152921504606846977", // -(1<<60 + 1)
 724
 725         "1/3",
 726 }
 727
 728 func TestFloat64SpecialCases(t *testing.T) {
 729         for _, input := range float64inputs {
 730                 if strings.HasPrefix(input, "long:") {
 731                         if testing.Short() {
 732                                 continue
 733                         }
 734                         input = input[len("long:"):]
 735                 }
 736
 737                 r, ok := new(Rat).SetString(input)
 738                 if !ok {
 739                         t.Errorf("Rat.SetString(%q) failed", input)
 740                         continue
 741                 }
 742                 f, exact := r.Float64()
 743
 744                 // 1. Check string -> Rat -> float64 conversions are
 745                 // consistent with strconv.ParseFloat.
 746                 // Skip this check if the input uses "a/b" rational syntax.
 747                 if !strings.Contains(input, "/") {
 748                         e, _ := strconv.ParseFloat(input, 64)
 749
 750                         // Careful: negative Rats too small for
 751                         // float64 become -0, but Rat obviously cannot
 752                         // preserve the sign from SetString("-0").
 753                         switch {
 754                         case math.Float64bits(e) == math.Float64bits(f):
 755                                 // Ok: bitwise equal.
 756                         case f == 0 && r.Num().BitLen() == 0:
 757                                 // Ok: Rat(0) is equivalent to both +/- float64(0).
 758                         default:
 759                                 t.Errorf("strconv.ParseFloat(%q) = %g (%b), want %g (%b); delta = %g", input, e, e, f, f, f-e)
 760                         }
 761                 }
 762
 763                 if !isFinite(f) {
 764                         continue
 765                 }
 766
 767                 // 2. Check f is best approximation to r.
 768                 if !checkIsBestApprox(t, f, r) {
 769                         // Append context information.
 770                         t.Errorf("(input was %q)", input)
 771                 }
 772
 773                 // 3. Check f->R->f roundtrip is non-lossy.
 774                 checkNonLossyRoundtrip(t, f)
 775
 776                 // 4. Check exactness using slow algorithm.
 777                 if wasExact := new(Rat).SetFloat64(f).Cmp(r) == 0; wasExact != exact {
 778                         t.Errorf("Rat.SetString(%q).Float64().exact = %t, want %t", input, exact, wasExact)
 779                 }
 780         }
 781 }
 782
 783 func TestFloat64Distribution(t *testing.T) {
 784         // Generate a distribution of (sign, mantissa, exp) values
 785         // broader than the float64 range, and check Rat.Float64()
 786         // always picks the closest float64 approximation.
 787         var add = []int64{
 788                 0,
 789                 1,
 790                 3,
 791                 5,
 792                 7,
 793                 9,
 794                 11,
 795         }
 796         var winc, einc = uint64(1), int(1) // soak test (~75s on x86-64)
 797         if testing.Short() {
 798                 winc, einc = 10, 500 // quick test (~12ms on x86-64)
 799         }
 800
 801         for _, sign := range "+-" {
 802                 for _, a := range add {
 803                         for wid := uint64(0); wid < 60; wid += winc {
 804                                 b := int64(1<<wid + a)
 805                                 if sign == '-' {
 806                                         b = -b
 807                                 }
 808                                 for exp := -1100; exp < 1100; exp += einc {
 809                                         num, den := NewInt(b), NewInt(1)
 810                                         if exp > 0 {
 811                                                 num.Lsh(num, uint(exp))
 812                                         } else {
 813                                                 den.Lsh(den, uint(-exp))
 814                                         }
 815                                         r := new(Rat).SetFrac(num, den)
 816                                         f, _ := r.Float64()
 817
 818                                         if !checkIsBestApprox(t, f, r) {
 819                                                 // Append context information.
 820                                                 t.Errorf("(input was mantissa %#x, exp %d; f = %g (%b); f ~ %g; r = %v)",
 821                                                         b, exp, f, f, math.Ldexp(float64(b), exp), r)
 822                                         }
 823
 824                                         checkNonLossyRoundtrip(t, f)
 825                                 }
 826                         }
 827                 }
 828         }
 829 }
 830
 831 // TestFloat64NonFinite checks that SetFloat64 of a non-finite value
 832 // returns nil.
 833 func TestSetFloat64NonFinite(t *testing.T) {
 834         for _, f := range []float64{math.NaN(), math.Inf(+1), math.Inf(-1)} {
 835                 var r Rat
 836                 if r2 := r.SetFloat64(f); r2 != nil {
 837                         t.Errorf("SetFloat64(%g) was %v, want nil", f, r2)
 838                 }
 839         }
 840 }
 841
 842 // checkNonLossyRoundtrip checks that a float->Rat->float roundtrip is
 843 // non-lossy for finite f.
 844 func checkNonLossyRoundtrip(t *testing.T, f float64) {
 845         if !isFinite(f) {
 846                 return
 847         }
 848         r := new(Rat).SetFloat64(f)
 849         if r == nil {
 850                 t.Errorf("Rat.SetFloat64(%g (%b)) == nil", f, f)
 851                 return
 852         }
 853         f2, exact := r.Float64()
 854         if f != f2 || !exact {
 855                 t.Errorf("Rat.SetFloat64(%g).Float64() = %g (%b), %v, want %g (%b), %v; delta = %b",
 856                         f, f2, f2, exact, f, f, true, f2-f)
 857         }
 858 }
 859
 860 // delta returns the absolute difference between r and f.
 861 func delta(r *Rat, f float64) *Rat {
 862         d := new(Rat).Sub(r, new(Rat).SetFloat64(f))
 863         return d.Abs(d)
 864 }
 865
 866 // checkIsBestApprox checks that f is the best possible float64
 867 // approximation of r.
 868 // Returns true on success.
 869 func checkIsBestApprox(t *testing.T, f float64, r *Rat) bool {
 870         if math.Abs(f) >= math.MaxFloat64 {
 871                 // Cannot check +Inf, -Inf, nor the float next to them (MaxFloat64).
 872                 // But we have tests for these special cases.
 873                 return true
 874         }
 875
 876         // r must be strictly between f0 and f1, the floats bracketing f.
 877         f0 := math.Nextafter(f, math.Inf(-1))
 878         f1 := math.Nextafter(f, math.Inf(+1))
 879
 880         // For f to be correct, r must be closer to f than to f0 or f1.
 881         df := delta(r, f)
 882         df0 := delta(r, f0)
 883         df1 := delta(r, f1)
 884         if df.Cmp(df0) > 0 {
 885                 t.Errorf("Rat(%v).Float64() = %g (%b), but previous float64 %g (%b) is closer", r, f, f, f0, f0)
 886                 return false
 887         }
 888         if df.Cmp(df1) > 0 {
 889                 t.Errorf("Rat(%v).Float64() = %g (%b), but next float64 %g (%b) is closer", r, f, f, f1, f1)
 890                 return false
 891         }
 892         if df.Cmp(df0) == 0 && !isEven(f) {
 893                 t.Errorf("Rat(%v).Float64() = %g (%b); halfway should have rounded to %g (%b) instead", r, f, f, f0, f0)
 894                 return false
 895         }
 896         if df.Cmp(df1) == 0 && !isEven(f) {
 897                 t.Errorf("Rat(%v).Float64() = %g (%b); halfway should have rounded to %g (%b) instead", r, f, f, f1, f1)
 898                 return false
 899         }
 900         return true
 901 }
 902
 903 func isEven(f float64) bool { return math.Float64bits(f)&1 == 0 }
 904
 905 func TestIsFinite(t *testing.T) {
 906         finites := []float64{
 907                 1.0 / 3,
 908                 4891559871276714924261e+222,
 909                 math.MaxFloat64,
 910                 math.SmallestNonzeroFloat64,
 911                 -math.MaxFloat64,
 912                 -math.SmallestNonzeroFloat64,
 913         }
 914         for _, f := range finites {
 915                 if !isFinite(f) {
 916                         t.Errorf("!IsFinite(%g (%b))", f, f)
 917                 }
 918         }
 919         nonfinites := []float64{
 920                 math.NaN(),
 921                 math.Inf(-1),
 922                 math.Inf(+1),
 923         }
 924         for _, f := range nonfinites {
 925                 if isFinite(f) {
 926                         t.Errorf("IsFinite(%g, (%b))", f, f)
 927                 }
 928         }
 929 }