File src/pkg/math/big/nat.go (right):
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1251
src/pkg/math/big/nat.go:1251: // If the exponent is large and the base
is non-trivial, we use a
On 2012/10/16 21:24:30, gri wrote:
s/we use a/we use/
Done.s/we use a/we use/
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1256
src/pkg/math/big/nat.go:1256: if len(y) > 1 && len(x) > 1 && len(m) > 0
{
On 2012/10/16 21:24:30, gri wrote:
perhaps check the values in the order they appear in the signature:
if len(x) > 1 && len(y) > 1 && len(m) > 0 ...
and adjust the comment accordingly:
If the base is non-trivial and the exponent large, we use
Done.perhaps check the values in the order they appear in the signature:
if len(x) > 1 && len(y) > 1 && len(m) > 0 ...
and adjust the comment accordingly:
If the base is non-trivial and the exponent large, we use
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1321
src/pkg/math/big/nat.go:1321:
On 2012/10/16 21:24:30, gri wrote:
Can we make 4 a constant?
const n = 4
Done.Can we make 4 a constant?
const n = 4
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1323
src/pkg/math/big/nat.go:1323: var powers [16]nat
On 2012/10/16 21:24:30, gri wrote:
s/16/1<<n/
Done.s/16/1<<n/
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1324
src/pkg/math/big/nat.go:1324: powers[0] = powers[0].make(1)
On 2012/10/16 21:24:30, gri wrote:
powers[0] = natOne
Done.powers[0] = natOne
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1325
src/pkg/math/big/nat.go:1325: powers[0][0] = 1
On 2012/10/16 21:24:30, gri wrote:
get rid of this line
Done.get rid of this line
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1327
src/pkg/math/big/nat.go:1327: for i := 2; i < 16; i += 2 {
On 2012/10/16 21:24:30, gri wrote:
s/16/1<<n/
Done.s/16/1<<n/
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1328
src/pkg/math/big/nat.go:1328: powers[i] = powers[i].mul(powers[i/2],
powers[i/2])
On 2012/10/16 21:24:30, gri wrote:
for i := 2; i < 1<<n; i += 2 {
p2, p, p1 := &powers[i/2], &powers[i], &powers[i+1]
*p = p.mul(*p2, *p2)
zz, r = zz.div(r, *p, m)
*p, r = r, *p
*p1 = p1.mul(*p, x)
zz, r = zz.div(r, *p1, m)
*p1, r = r, *p1
}
Done.for i := 2; i < 1<<n; i += 2 {
p2, p, p1 := &powers[i/2], &powers[i], &powers[i+1]
*p = p.mul(*p2, *p2)
zz, r = zz.div(r, *p, m)
*p, r = r, *p
*p1 = p1.mul(*p, x)
zz, r = zz.div(r, *p1, m)
*p1, r = r, *p1
}
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1336
src/pkg/math/big/nat.go:1336: z = z.make(1)
On 2012/10/16 21:24:30, gri wrote:
z = z.setWord(1)
Done.z = z.setWord(1)
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1337
src/pkg/math/big/nat.go:1337: z[0] = 1
On 2012/10/16 21:24:30, gri wrote:
get rid of this line
Done.get rid of this line
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1340
src/pkg/math/big/nat.go:1340: word := y[i]
On 2012/10/16 21:24:30, gri wrote:
s/word/yi/
word is almost Word and yi is saying more and shorter
Done.s/word/yi/
word is almost Word and yi is saying more and shorter
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1343
src/pkg/math/big/nat.go:1343: // Manually unrolling this speeds the code
up by ~15%.
On 2012/10/16 21:24:30, gri wrote:
Really?
for k := 0; k < n; k++ {
zz = zz.mul(z, z)
zz, z = z, zz
zz, r = zz.div(r, z, m)
z, r = r, z
}
The loop overhead should be neglible compared to the mul/div stuff
Yea, I know. And yet, when I put it in a loop as you've written:Really?
for k := 0; k < n; k++ {
zz = zz.mul(z, z)
zz, z = z, zz
zz, r = zz.div(r, z, m)
z, r = r, z
}
The loop overhead should be neglible compared to the mul/div stuff
benchmark old ns/op new ns/op delta
BenchmarkRSA2048Decrypt 11243420 13158090 +17.03%
Benchmark3PrimeRSA2048Decrypt 7870770 10122080 +28.60%
Maybe inlining is kicking in and doing more than we expect?
https://codereview.appspot.com/6716048/
