LEFT | RIGHT |
(no file at all) | |
1 // Copyright 2010 The Go Authors. All rights reserved. | 1 // Copyright 2010 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 package big | 5 package big |
6 | 6 |
7 import ( | 7 import ( |
8 "bytes" | 8 "bytes" |
9 "encoding/gob" | 9 "encoding/gob" |
10 "fmt" | 10 "fmt" |
| 11 "math" |
| 12 "strconv" |
| 13 "strings" |
11 "testing" | 14 "testing" |
12 ) | 15 ) |
13 | 16 |
14 func TestZeroRat(t *testing.T) { | 17 func TestZeroRat(t *testing.T) { |
15 var x, y, z Rat | 18 var x, y, z Rat |
16 y.SetFrac64(0, 42) | 19 y.SetFrac64(0, 42) |
17 | 20 |
18 if x.Cmp(&y) != 0 { | 21 if x.Cmp(&y) != 0 { |
19 t.Errorf("x and y should be both equal and zero") | 22 t.Errorf("x and y should be both equal and zero") |
20 } | 23 } |
(...skipping 468 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
489 // 3) changing the numerator/denominator of a Rat changes the Rat | 492 // 3) changing the numerator/denominator of a Rat changes the Rat |
490 x.SetFrac(a, b) | 493 x.SetFrac(a, b) |
491 a = x.Num() | 494 a = x.Num() |
492 b = x.Denom() | 495 b = x.Denom() |
493 a.SetInt64(5) | 496 a.SetInt64(5) |
494 b.SetInt64(3) | 497 b.SetInt64(3) |
495 if x.Cmp(q53) != 0 { | 498 if x.Cmp(q53) != 0 { |
496 t.Errorf("3) got %s want %s", x, q53) | 499 t.Errorf("3) got %s want %s", x, q53) |
497 } | 500 } |
498 } | 501 } |
| 502 |
| 503 // Test inputs to Rat.SetString. The optional prefix "slow:" skips |
| 504 // checks found to be slow for certain large rationals. |
| 505 var float64inputs = []string{ |
| 506 // |
| 507 // Constants plundered from strconv/testfp.txt. |
| 508 // |
| 509 |
| 510 // Table 1: Stress Inputs for Conversion to 53-bit Binary, < 1/2 ULP |
| 511 "5e+125", |
| 512 "69e+267", |
| 513 "999e-026", |
| 514 "7861e-034", |
| 515 "75569e-254", |
| 516 "928609e-261", |
| 517 "9210917e+080", |
| 518 "84863171e+114", |
| 519 "653777767e+273", |
| 520 "5232604057e-298", |
| 521 "27235667517e-109", |
| 522 "653532977297e-123", |
| 523 "3142213164987e-294", |
| 524 "46202199371337e-072", |
| 525 "231010996856685e-073", |
| 526 "9324754620109615e+212", |
| 527 "78459735791271921e+049", |
| 528 "272104041512242479e+200", |
| 529 "6802601037806061975e+198", |
| 530 "20505426358836677347e-221", |
| 531 "836168422905420598437e-234", |
| 532 "4891559871276714924261e+222", |
| 533 |
| 534 // Table 2: Stress Inputs for Conversion to 53-bit Binary, > 1/2 ULP |
| 535 "9e-265", |
| 536 "85e-037", |
| 537 "623e+100", |
| 538 "3571e+263", |
| 539 "81661e+153", |
| 540 "920657e-023", |
| 541 "4603285e-024", |
| 542 "87575437e-309", |
| 543 "245540327e+122", |
| 544 "6138508175e+120", |
| 545 "83356057653e+193", |
| 546 "619534293513e+124", |
| 547 "2335141086879e+218", |
| 548 "36167929443327e-159", |
| 549 "609610927149051e-255", |
| 550 "3743626360493413e-165", |
| 551 "94080055902682397e-242", |
| 552 "899810892172646163e+283", |
| 553 "7120190517612959703e+120", |
| 554 "25188282901709339043e-252", |
| 555 "308984926168550152811e-052", |
| 556 "6372891218502368041059e+064", |
| 557 |
| 558 // Table 14: Stress Inputs for Conversion to 24-bit Binary, <1/2 ULP |
| 559 "5e-20", |
| 560 "67e+14", |
| 561 "985e+15", |
| 562 "7693e-42", |
| 563 "55895e-16", |
| 564 "996622e-44", |
| 565 "7038531e-32", |
| 566 "60419369e-46", |
| 567 "702990899e-20", |
| 568 "6930161142e-48", |
| 569 "25933168707e+13", |
| 570 "596428896559e+20", |
| 571 |
| 572 // Table 15: Stress Inputs for Conversion to 24-bit Binary, >1/2 ULP |
| 573 "3e-23", |
| 574 "57e+18", |
| 575 "789e-35", |
| 576 "2539e-18", |
| 577 "76173e+28", |
| 578 "887745e-11", |
| 579 "5382571e-37", |
| 580 "82381273e-35", |
| 581 "750486563e-38", |
| 582 "3752432815e-39", |
| 583 "75224575729e-45", |
| 584 "459926601011e+15", |
| 585 |
| 586 // |
| 587 // Constants plundered from strconv/atof_test.go. |
| 588 // |
| 589 |
| 590 "0", |
| 591 "1", |
| 592 "+1", |
| 593 "1e23", |
| 594 "1E23", |
| 595 "100000000000000000000000", |
| 596 "1e-100", |
| 597 "123456700", |
| 598 "99999999999999974834176", |
| 599 "100000000000000000000001", |
| 600 "100000000000000008388608", |
| 601 "100000000000000016777215", |
| 602 "100000000000000016777216", |
| 603 "-1", |
| 604 "-0.1", |
| 605 "-0", // NB: exception made for this input |
| 606 "1e-20", |
| 607 "625e-3", |
| 608 |
| 609 // largest float64 |
| 610 "1.7976931348623157e308", |
| 611 "-1.7976931348623157e308", |
| 612 // next float64 - too large |
| 613 "1.7976931348623159e308", |
| 614 "-1.7976931348623159e308", |
| 615 // the border is ...158079 |
| 616 // borderline - okay |
| 617 "1.7976931348623158e308", |
| 618 "-1.7976931348623158e308", |
| 619 // borderline - too large |
| 620 "1.797693134862315808e308", |
| 621 "-1.797693134862315808e308", |
| 622 |
| 623 // a little too large |
| 624 "1e308", |
| 625 "2e308", |
| 626 "1e309", |
| 627 |
| 628 // way too large |
| 629 "1e310", |
| 630 "-1e310", |
| 631 "1e400", |
| 632 "-1e400", |
| 633 "1e400000", |
| 634 "-1e400000", |
| 635 |
| 636 // denormalized |
| 637 "1e-305", |
| 638 "1e-306", |
| 639 "1e-307", |
| 640 "1e-308", |
| 641 "1e-309", |
| 642 "1e-310", |
| 643 "1e-322", |
| 644 // smallest denormal |
| 645 "5e-324", |
| 646 "4e-324", |
| 647 "3e-324", |
| 648 // too small |
| 649 "2e-324", |
| 650 // way too small |
| 651 "1e-350", |
| 652 "slow:1e-400000", |
| 653 // way too small, negative |
| 654 "-1e-350", |
| 655 "slow:-1e-400000", |
| 656 |
| 657 // try to overflow exponent |
| 658 // [Disabled: too slow and memory-hungry with rationals.] |
| 659 // "1e-4294967296", |
| 660 // "1e+4294967296", |
| 661 // "1e-18446744073709551616", |
| 662 // "1e+18446744073709551616", |
| 663 |
| 664 // http://www.exploringbinary.com/java-hangs-when-converting-2-225073858
5072012e-308/ |
| 665 "2.2250738585072012e-308", |
| 666 // http://www.exploringbinary.com/php-hangs-on-numeric-value-2-225073858
5072011e-308/ |
| 667 |
| 668 "2.2250738585072011e-308", |
| 669 |
| 670 // A very large number (initially wrongly parsed by the fast algorithm). |
| 671 "4.630813248087435e+307", |
| 672 |
| 673 // A different kind of very large number. |
| 674 "22.222222222222222", |
| 675 "2." + strings.Repeat("2", 4000) + "e+1", |
| 676 |
| 677 // Exactly halfway between 1 and math.Nextafter(1, 2). |
| 678 // Round to even (down). |
| 679 "1.00000000000000011102230246251565404236316680908203125", |
| 680 // Slightly lower; still round down. |
| 681 "1.00000000000000011102230246251565404236316680908203124", |
| 682 // Slightly higher; round up. |
| 683 "1.00000000000000011102230246251565404236316680908203126", |
| 684 // Slightly higher, but you have to read all the way to the end. |
| 685 "slow:1.00000000000000011102230246251565404236316680908203125" + strings
.Repeat("0", 10000) + "1", |
| 686 |
| 687 // Smallest denormal, 2^(-1022-52) |
| 688 "4.940656458412465441765687928682213723651e-324", |
| 689 // Half of smallest denormal, 2^(-1022-53) |
| 690 "2.470328229206232720882843964341106861825e-324", |
| 691 // A little more than the exact half of smallest denormal |
| 692 // 2^-1075 + 2^-1100. (Rounds to 1p-1074.) |
| 693 "2.470328302827751011111470718709768633275e-324", |
| 694 // The exact halfway between smallest normal and largest denormal: |
| 695 // 2^-1022 - 2^-1075. (Rounds to 2^-1022.) |
| 696 "2.225073858507201136057409796709131975935e-308", |
| 697 |
| 698 "1152921504606846975", // 1<<60 - 1 |
| 699 "-1152921504606846975", // -(1<<60 - 1) |
| 700 "1152921504606846977", // 1<<60 + 1 |
| 701 "-1152921504606846977", // -(1<<60 + 1) |
| 702 |
| 703 "1/3", |
| 704 } |
| 705 |
| 706 func TestFloat64SpecialCases(t *testing.T) { |
| 707 for _, input := range float64inputs { |
| 708 slow := strings.HasPrefix(input, "slow:") |
| 709 if slow { |
| 710 input = input[len("slow:"):] |
| 711 } |
| 712 |
| 713 r, ok := new(Rat).SetString(input) |
| 714 if !ok { |
| 715 t.Errorf("Rat.SetString(%q) failed", input) |
| 716 continue |
| 717 } |
| 718 f, exact := r.Float64() |
| 719 |
| 720 // 1. Check string -> Rat -> float64 conversions are |
| 721 // consistent with strconv.ParseFloat. |
| 722 // Skip this check if the input uses "a/b" rational syntax. |
| 723 if !strings.Contains(input, "/") { |
| 724 e, _ := strconv.ParseFloat(input, 64) |
| 725 |
| 726 // Careful: negative Rats too small for |
| 727 // float64 become -0, but Rat obviously cannot |
| 728 // preserve the sign from SetString("-0"). |
| 729 switch { |
| 730 case math.Float64bits(e) == math.Float64bits(f): |
| 731 // Ok: bitwise equal. |
| 732 case f == 0 && r.Num().BitLen() == 0: |
| 733 // Ok: Rat(0) is equivalent to both +/- float64(
0). |
| 734 default: |
| 735 t.Errorf("strconv.ParseFloat(%q) = %g (%b), want
%g (%b); delta=%g", input, e, e, f, f, f-e) |
| 736 } |
| 737 } |
| 738 |
| 739 if !isFinite(f) || slow { |
| 740 continue |
| 741 } |
| 742 |
| 743 // 2. Check f is best approximation to r. |
| 744 if !checkIsBestApprox(t, f, r) { |
| 745 // Append context information. |
| 746 t.Errorf("(input was %q)", input) |
| 747 } |
| 748 |
| 749 // 3. Check f->R->f roundtrip is non-lossy. |
| 750 checkNonLossyRoundtrip(t, f) |
| 751 |
| 752 // 4. Check exactness using slow algorithm. |
| 753 if wasExact := new(Rat).SetFloat64(f).Cmp(r) == 0; wasExact != e
xact { |
| 754 t.Errorf("Rat.SetString(%q).Float64().exact = %b, want %
b", input, exact, wasExact) |
| 755 } |
| 756 } |
| 757 } |
| 758 |
| 759 func TestFloat64Distribution(t *testing.T) { |
| 760 // Generate a distribution of (sign, mantissa, exp) values |
| 761 // broader than the float64 range, and check Rat.Float64() |
| 762 // always picks the closest float64 approximation. |
| 763 var add = []int64{ |
| 764 0, |
| 765 1, |
| 766 3, |
| 767 5, |
| 768 7, |
| 769 9, |
| 770 11, |
| 771 } |
| 772 const winc, einc = 5, 100 // quick test (<1s) |
| 773 //const winc, einc = 1, 1 // soak test (~75s) |
| 774 for _, sign := range "+-" { |
| 775 for _, a := range add { |
| 776 for wid := uint64(0); wid < 60; wid += winc { |
| 777 b := int64(1<<wid + a) |
| 778 if sign == '-' { |
| 779 b = -b |
| 780 } |
| 781 for exp := -1100; exp < 1100; exp += einc { |
| 782 num, den := NewInt(b), NewInt(1) |
| 783 if exp > 0 { |
| 784 num.Lsh(num, uint(exp)) |
| 785 } else { |
| 786 den.Lsh(den, uint(-exp)) |
| 787 } |
| 788 r := new(Rat).SetFrac(num, den) |
| 789 f, _ := r.Float64() |
| 790 |
| 791 if !checkIsBestApprox(t, f, r) { |
| 792 // Append context information. |
| 793 t.Errorf("(input was mantissa %#
x, exp %d; f=%g (%b); f~%g; r=%v)", |
| 794 b, exp, f, f, math.Ldexp
(float64(b), exp), r) |
| 795 } |
| 796 |
| 797 checkNonLossyRoundtrip(t, f) |
| 798 } |
| 799 } |
| 800 } |
| 801 } |
| 802 } |
| 803 |
| 804 // TestFloat64NonFinite checks that SetFloat64 of a non-finite value |
| 805 // returns nil. |
| 806 func TestSetFloat64NonFinite(t *testing.T) { |
| 807 for _, f := range []float64{math.NaN(), math.Inf(+1), math.Inf(-1)} { |
| 808 var r Rat |
| 809 if r2 := r.SetFloat64(f); r2 != nil { |
| 810 t.Errorf("SetFloat64(%g) was %v, want nil", f, r2) |
| 811 } |
| 812 } |
| 813 } |
| 814 |
| 815 // checkNonLossyRoundtrip checks that a float->Rat->float roundtrip is |
| 816 // non-lossy for finite f. |
| 817 func checkNonLossyRoundtrip(t *testing.T, f float64) { |
| 818 if !isFinite(f) { |
| 819 return |
| 820 } |
| 821 r := new(Rat).SetFloat64(f) |
| 822 if r == nil { |
| 823 t.Errorf("Rat.SetFloat64(%g (%b)) == nil", f, f) |
| 824 return |
| 825 } |
| 826 f2, exact := r.Float64() |
| 827 if f != f2 || !exact { |
| 828 t.Errorf("Rat.SetFloat64(%g).Float64() = %g (%b), %v, want %g (%
b), %v; delta=%b", |
| 829 f, f2, f2, exact, f, f, true, f2-f) |
| 830 } |
| 831 } |
| 832 |
| 833 // delta returns the absolute difference between r and f. |
| 834 func delta(r *Rat, f float64) *Rat { |
| 835 d := new(Rat).Sub(r, new(Rat).SetFloat64(f)) |
| 836 return d.Abs(d) |
| 837 } |
| 838 |
| 839 // checkIsBestApprox checks that f is the best possible float64 |
| 840 // approximation of r. |
| 841 // Returns true on success. |
| 842 func checkIsBestApprox(t *testing.T, f float64, r *Rat) bool { |
| 843 if math.Abs(f) >= math.MaxFloat64 { |
| 844 // Cannot check +Inf, -Inf, nor the float next to them (MaxFloat
64). |
| 845 // But we have tests for these special cases. |
| 846 return true |
| 847 } |
| 848 |
| 849 // r must be strictly between f0 and f1, the floats bracketing f. |
| 850 f0 := math.Nextafter(f, math.Inf(-1)) |
| 851 f1 := math.Nextafter(f, math.Inf(+1)) |
| 852 |
| 853 // For f to be correct, r must be closer to f than to f0 or f1. |
| 854 df := delta(r, f) |
| 855 df0 := delta(r, f0) |
| 856 df1 := delta(r, f1) |
| 857 if df.Cmp(df0) > 0 { |
| 858 t.Errorf("Rat(%v).Float64() = %g (%b), but previous float64 %g (
%b) is closer", r, f, f, f0, f0) |
| 859 return false |
| 860 } |
| 861 if df.Cmp(df1) > 0 { |
| 862 t.Errorf("Rat(%v).Float64() = %g (%b), but next float64 %g (%b)
is closer", r, f, f, f1, f1) |
| 863 return false |
| 864 } |
| 865 if df.Cmp(df0) == 0 && !isEven(f) { |
| 866 t.Errorf("Rat(%v).Float64() = %g (%b); halfway should have round
ed to %g (%b) instead", r, f, f, f0, f0) |
| 867 return false |
| 868 } |
| 869 if df.Cmp(df1) == 0 && !isEven(f) { |
| 870 t.Errorf("Rat(%v).Float64() = %g (%b); halfway should have round
ed to %g (%b) instead", r, f, f, f1, f1) |
| 871 return false |
| 872 } |
| 873 return true |
| 874 } |
| 875 |
| 876 func isEven(f float64) bool { return math.Float64bits(f)&1 == 0 } |
| 877 |
| 878 func TestIsFinite(t *testing.T) { |
| 879 finites := []float64{ |
| 880 1.0 / 3, |
| 881 4891559871276714924261e+222, |
| 882 math.MaxFloat64, |
| 883 math.SmallestNonzeroFloat64, |
| 884 -math.MaxFloat64, |
| 885 -math.SmallestNonzeroFloat64, |
| 886 } |
| 887 for _, f := range finites { |
| 888 if !isFinite(f) { |
| 889 t.Errorf("!IsFinite(%g (%b))", f, f) |
| 890 } |
| 891 } |
| 892 nonfinites := []float64{ |
| 893 math.NaN(), |
| 894 math.Inf(-1), |
| 895 math.Inf(+1), |
| 896 } |
| 897 for _, f := range nonfinites { |
| 898 if isFinite(f) { |
| 899 t.Errorf("IsFinite(%g, (%b))", f, f) |
| 900 } |
| 901 } |
| 902 } |
LEFT | RIGHT |