diff options
| author | Russ Cox <rsc@golang.org> | 2022-07-26 23:34:15 -0400 |
|---|---|---|
| committer | Gopher Robot <gobot@golang.org> | 2022-11-02 14:43:50 +0000 |
| commit | d8541aa8d5d09042cff39ba064b2e09b772f0ae0 (patch) | |
| tree | a0cb993d1207cd655216b6160d4be7c5265ceed5 /src | |
| parent | 0aeda5afe5972c1b5f76d5ee78cbc5c96474ca89 (diff) | |
| download | go-d8541aa8d5d09042cff39ba064b2e09b772f0ae0.tar.xz | |
math/big: add benchmark of Exp with large modulus
Setting up for improving even modulus.
name time/op
ExpMont/Odd-16 240µs ± 2%
ExpMont/Even1-16 757µs ± 3%
ExpMont/Even2-16 755µs ± 1%
ExpMont/Even3-16 771µs ± 3%
ExpMont/Even4-16 775µs ± 3%
ExpMont/Even8-16 779µs ± 2%
ExpMont/Even32-16 778µs ± 3%
ExpMont/Even64-16 774µs ± 6%
ExpMont/Even96-16 776µs ± 4%
ExpMont/Even128-16 764µs ± 2%
ExpMont/Even255-16 761µs ± 3%
ExpMont/SmallEven1-16 45.6µs ± 1%
ExpMont/SmallEven2-16 44.3µs ± 2%
ExpMont/SmallEven3-16 44.1µs ± 5%
ExpMont/SmallEven4-16 47.1µs ± 6%
name alloc/op
ExpMont/Odd-16 2.53kB ± 0%
ExpMont/Even1-16 2.57kB ± 0%
ExpMont/Even2-16 2.57kB ± 0%
ExpMont/Even3-16 2.57kB ± 0%
ExpMont/Even4-16 2.57kB ± 0%
ExpMont/Even8-16 2.57kB ± 0%
ExpMont/Even32-16 2.57kB ± 0%
ExpMont/Even64-16 2.57kB ± 0%
ExpMont/Even96-16 2.57kB ± 0%
ExpMont/Even128-16 2.57kB ± 0%
ExpMont/Even255-16 2.57kB ± 0%
ExpMont/SmallEven1-16 872B ± 0%
ExpMont/SmallEven2-16 872B ± 0%
ExpMont/SmallEven3-16 872B ± 0%
ExpMont/SmallEven4-16 872B ± 0%
name allocs/op
ExpMont/Odd-16 21.0 ± 0%
ExpMont/Even1-16 24.0 ± 0%
ExpMont/Even2-16 24.0 ± 0%
ExpMont/Even3-16 24.0 ± 0%
ExpMont/Even4-16 24.0 ± 0%
ExpMont/Even8-16 24.0 ± 0%
ExpMont/Even32-16 24.0 ± 0%
ExpMont/Even64-16 24.0 ± 0%
ExpMont/Even96-16 24.0 ± 0%
ExpMont/Even128-16 24.0 ± 0%
ExpMont/Even255-16 24.0 ± 0%
ExpMont/SmallEven1-16 16.0 ± 0%
ExpMont/SmallEven2-16 16.0 ± 0%
ExpMont/SmallEven3-16 16.0 ± 0%
ExpMont/SmallEven4-16 16.0 ± 0%
Change-Id: I5278378b4209a97b16273be581533310e0e4110b
Reviewed-on: https://go-review.googlesource.com/c/go/+/420896
Reviewed-by: Roland Shoemaker <roland@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Auto-Submit: Russ Cox <rsc@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Diffstat (limited to 'src')
| -rw-r--r-- | src/math/big/int_test.go | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go index 75831e5215..53cd399b1f 100644 --- a/src/math/big/int_test.go +++ b/src/math/big/int_test.go @@ -661,6 +661,41 @@ func BenchmarkExp(b *testing.B) { } } +func BenchmarkExpMont(b *testing.B) { + x, _ := new(Int).SetString("297778224889315382157302278696111964193", 0) + y, _ := new(Int).SetString("2548977943381019743024248146923164919440527843026415174732254534318292492375775985739511369575861449426580651447974311336267954477239437734832604782764979371984246675241012538135715981292390886872929238062252506842498360562303324154310849745753254532852868768268023732398278338025070694508489163836616810661033068070127919590264734220833816416141878688318329193389865030063416339367925710474801991305827284114894677717927892032165200876093838921477120036402410731159852999623461591709308405270748511350289172153076023215", 0) + var mods = []struct { + name string + val string + }{ + {"Odd", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF"}, + {"Even1", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FE"}, + {"Even2", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FC"}, + {"Even3", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281F8"}, + {"Even4", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281F0"}, + {"Even8", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B21828100"}, + {"Even32", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B00000000"}, + {"Even64", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FF0000000000000000"}, + {"Even96", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828283000000000000000000000000"}, + {"Even128", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF00000000000000000000000000000000"}, + {"Even255", "0x82828282828200FFFF28FF2B218281FF8000000000000000000000000000000000000000000000000000000000000000"}, + {"SmallEven1", "0x7E"}, + {"SmallEven2", "0x7C"}, + {"SmallEven3", "0x78"}, + {"SmallEven4", "0x70"}, + } + for _, mod := range mods { + n, _ := new(Int).SetString(mod.val, 0) + out := new(Int) + b.Run(mod.name, func(b *testing.B) { + b.ReportAllocs() + 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) |