summaryrefslogtreecommitdiff
path: root/libgo/go/math/big/int_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'libgo/go/math/big/int_test.go')
-rw-r--r--libgo/go/math/big/int_test.go173
1 files changed, 94 insertions, 79 deletions
diff --git a/libgo/go/math/big/int_test.go b/libgo/go/math/big/int_test.go
index 45a3765d3ee..b8e0778ca32 100644
--- a/libgo/go/math/big/int_test.go
+++ b/libgo/go/math/big/int_test.go
@@ -9,6 +9,7 @@ import (
"encoding/hex"
"fmt"
"math/rand"
+ "strings"
"testing"
"testing/quick"
)
@@ -478,6 +479,18 @@ func TestQuoStepD6(t *testing.T) {
}
}
+func BenchmarkQuoRem(b *testing.B) {
+ x, _ := new(Int).SetString("153980389784927331788354528594524332344709972855165340650588877572729725338415474372475094155672066328274535240275856844648695200875763869073572078279316458648124537905600131008790701752441155668003033945258023841165089852359980273279085783159654751552359397986180318708491098942831252291841441726305535546071", 0)
+ y, _ := new(Int).SetString("7746362281539803897849273317883545285945243323447099728551653406505888775727297253384154743724750941556720663282745352402758568446486952008757638690735720782793164586481245379056001310087907017524411556680030339452580238411650898523599802732790857831596547515523593979861803187084910989428312522918414417263055355460715745539358014631136245887418412633787074173796862711588221766398229333338511838891484974940633857861775630560092874987828057333663969469797013996401149696897591265769095952887917296740109742927689053276850469671231961384715398038978492733178835452859452433234470997285516534065058887757272972533841547437247509415567206632827453524027585684464869520087576386907357207827931645864812453790560013100879070175244115566800303394525802384116508985235998027327908578315965475155235939798618031870849109894283125229184144172630553554607112725169432413343763989564437170644270643461665184965150423819594083121075825", 0)
+ q := new(Int)
+ r := new(Int)
+
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ q.QuoRem(y, x, r)
+ }
+}
+
var bitLenTests = []struct {
in string
out int
@@ -572,6 +585,19 @@ var expTests = []struct {
{"0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0"},
{"0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0"},
{"0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0"},
+
+ {
+ "2",
+ "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
+ "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", // odd
+ "0x6AADD3E3E424D5B713FCAA8D8945B1E055166132038C57BBD2D51C833F0C5EA2007A2324CE514F8E8C2F008A2F36F44005A4039CB55830986F734C93DAF0EB4BAB54A6A8C7081864F44346E9BC6F0A3EB9F2C0146A00C6A05187D0C101E1F2D038CDB70CB5E9E05A2D188AB6CBB46286624D4415E7D4DBFAD3BCC6009D915C406EED38F468B940F41E6BEDC0430DD78E6F19A7DA3A27498A4181E24D738B0072D8F6ADB8C9809A5B033A09785814FD9919F6EF9F83EEA519BEC593855C4C10CBEEC582D4AE0792158823B0275E6AEC35242740468FAF3D5C60FD1E376362B6322F78B7ED0CA1C5BBCD2B49734A56C0967A1D01A100932C837B91D592CE08ABFF",
+ },
+ {
+ "2",
+ "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
+ "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", // even
+ "0x7858794B5897C29F4ED0B40913416AB6C48588484E6A45F2ED3E26C941D878E923575AAC434EE2750E6439A6976F9BB4D64CEDB2A53CE8D04DD48CADCDF8E46F22747C6B81C6CEA86C0D873FBF7CEF262BAAC43A522BD7F32F3CDAC52B9337C77B3DCFB3DB3EDD80476331E82F4B1DF8EFDC1220C92656DFC9197BDC1877804E28D928A2A284B8DED506CBA304435C9D0133C246C98A7D890D1DE60CBC53A024361DA83A9B8775019083D22AC6820ED7C3C68F8E801DD4EC779EE0A05C6EB682EF9840D285B838369BA7E148FA27691D524FAEAF7C6ECE2A4B99A294B9F2C241857B5B90CC8BFFCFCF18DFA7D676131D5CD3855A5A3E8EBFA0CDFADB4D198B4A",
+ },
}
func TestExp(t *testing.T) {
@@ -614,6 +640,26 @@ func TestExp(t *testing.T) {
}
}
+func BenchmarkExp(b *testing.B) {
+ x, _ := new(Int).SetString("11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865", 0)
+ y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
+ n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
+ out := new(Int)
+ for i := 0; i < b.N; i++ {
+ out.Exp(x, y, n)
+ }
+}
+
+func BenchmarkExp2(b *testing.B) {
+ x, _ := new(Int).SetString("2", 0)
+ y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
+ n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
+ out := new(Int)
+ for i := 0; i < b.N; i++ {
+ out.Exp(x, y, n)
+ }
+}
+
func checkGcd(aBytes, bBytes []byte) bool {
x := new(Int)
y := new(Int)
@@ -715,85 +761,6 @@ func TestGcd(t *testing.T) {
}
}
-var primes = []string{
- "2",
- "3",
- "5",
- "7",
- "11",
-
- "13756265695458089029",
- "13496181268022124907",
- "10953742525620032441",
- "17908251027575790097",
-
- // https://golang.org/issue/638
- "18699199384836356663",
-
- "98920366548084643601728869055592650835572950932266967461790948584315647051443",
- "94560208308847015747498523884063394671606671904944666360068158221458669711639",
-
- // http://primes.utm.edu/lists/small/small3.html
- "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
- "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
- "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
- "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
-
- // ECC primes: http://tools.ietf.org/html/draft-ladd-safecurves-02
- "3618502788666131106986593281521497120414687020801267626233049500247285301239", // Curve1174: 2^251-9
- "57896044618658097711785492504343953926634992332820282019728792003956564819949", // Curve25519: 2^255-19
- "9850501549098619803069760025035903451269934817616361666987073351061430442874302652853566563721228910201656997576599", // E-382: 2^382-105
- "42307582002575910332922579714097346549017899709713998034217522897561970639123926132812109468141778230245837569601494931472367", // Curve41417: 2^414-17
- "6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", // E-521: 2^521-1
-}
-
-var composites = []string{
- "0",
- "1",
- "21284175091214687912771199898307297748211672914763848041968395774954376176754",
- "6084766654921918907427900243509372380954290099172559290432744450051395395951",
- "84594350493221918389213352992032324280367711247940675652888030554255915464401",
- "82793403787388584738507275144194252681",
-}
-
-func TestProbablyPrime(t *testing.T) {
- nreps := 20
- if testing.Short() {
- nreps = 1
- }
- for i, s := range primes {
- p, _ := new(Int).SetString(s, 10)
- if !p.ProbablyPrime(nreps) {
- t.Errorf("#%d prime found to be non-prime (%s)", i, s)
- }
- }
-
- for i, s := range composites {
- c, _ := new(Int).SetString(s, 10)
- if c.ProbablyPrime(nreps) {
- t.Errorf("#%d composite found to be prime (%s)", i, s)
- }
- if testing.Short() {
- break
- }
- }
-
- // check that ProbablyPrime panics if n <= 0
- c := NewInt(11) // a prime
- for _, n := range []int{-1, 0, 1} {
- func() {
- defer func() {
- if n <= 0 && recover() == nil {
- t.Fatalf("expected panic from ProbablyPrime(%d)", n)
- }
- }()
- if !c.ProbablyPrime(n) {
- t.Fatalf("%v should be a prime", c)
- }
- }()
- }
-}
-
type intShiftTest struct {
in string
shift uint
@@ -1229,6 +1196,9 @@ func BenchmarkModSqrt224_3Mod4(b *testing.B) {
}
func BenchmarkModSqrt5430_Tonelli(b *testing.B) {
+ if isRaceBuilder {
+ b.Skip("skipping on race builder")
+ }
p := tri(5430)
x := new(Int).SetUint64(2)
for i := 0; i < b.N; i++ {
@@ -1238,6 +1208,9 @@ func BenchmarkModSqrt5430_Tonelli(b *testing.B) {
}
func BenchmarkModSqrt5430_3Mod4(b *testing.B) {
+ if isRaceBuilder {
+ b.Skip("skipping on race builder")
+ }
p := tri(5430)
x := new(Int).SetUint64(2)
for i := 0; i < b.N; i++ {
@@ -1303,6 +1276,7 @@ var modInverseTests = []struct {
}{
{"1234567", "458948883992"},
{"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
+ {"-10", "13"}, // issue #16984
}
func TestModInverse(t *testing.T) {
@@ -1480,3 +1454,44 @@ func TestIssue2607(t *testing.T) {
n := NewInt(10)
n.Rand(rand.New(rand.NewSource(9)), n)
}
+
+func TestSqrt(t *testing.T) {
+ root := 0
+ r := new(Int)
+ for i := 0; i < 10000; i++ {
+ if (root+1)*(root+1) <= i {
+ root++
+ }
+ n := NewInt(int64(i))
+ r.SetInt64(-2)
+ r.Sqrt(n)
+ if r.Cmp(NewInt(int64(root))) != 0 {
+ t.Errorf("Sqrt(%v) = %v, want %v", n, r, root)
+ }
+ }
+
+ for i := 0; i < 1000; i += 10 {
+ n, _ := new(Int).SetString("1"+strings.Repeat("0", i), 10)
+ r := new(Int).Sqrt(n)
+ root, _ := new(Int).SetString("1"+strings.Repeat("0", i/2), 10)
+ if r.Cmp(root) != 0 {
+ t.Errorf("Sqrt(1e%d) = %v, want 1e%d", i, r, i/2)
+ }
+ }
+
+ // Test aliasing.
+ r.SetInt64(100)
+ r.Sqrt(r)
+ if r.Int64() != 10 {
+ t.Errorf("Sqrt(100) = %v, want 10 (aliased output)", r.Int64())
+ }
+}
+
+func BenchmarkSqrt(b *testing.B) {
+ n, _ := new(Int).SetString("1"+strings.Repeat("0", 1001), 10)
+ b.ResetTimer()
+ t := new(Int)
+ for i := 0; i < b.N; i++ {
+ t.Sqrt(n)
+ }
+}