delta/go-git.git/src/math, branch dev.typealias

crypto/*: document use or non-use of constant-time algorithms

2016-12-07T16:34:50+00:00

Fixes #16821.

Change-Id: I63d5f3d7cfba1c76259912d754025c5f3cbe4a56
Reviewed-on: https://go-review.googlesource.com/31573
Run-TryBot: Russ Cox 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick

math/rand: export Source64, mainly for documentation value

2016-11-23T04:29:25+00:00

There is some code value too: types intending to implement
Source64 can write a conversion confirming that.

For #4254 and the Go 1.8 release notes.

Change-Id: I7fc350a84f3a963e4dab317ad228fa340dda5c66
Reviewed-on: https://go-review.googlesource.com/33456
Run-TryBot: Russ Cox 
Reviewed-by: Brad Fitzpatrick

math/big: add Baillie-PSW test to (*Int).ProbablyPrime

2016-11-22T02:05:47+00:00

After x.ProbablyPrime(n) passes the n Miller-Rabin rounds,
add a Baillie-PSW test before declaring x probably prime.

Although the provable error bounds are unchanged, the empirical
error bounds drop dramatically: there are no known inputs
for which Baillie-PSW gives the wrong answer. For example,
before this CL, big.NewInt(443*1327).ProbablyPrime(1) == true.
Now it is (correctly) false.

The new Baillie-PSW test is two pieces: an added Miller-Rabin
round with base 2, and a so-called extra strong Lucas test.
(See the references listed in prime.go for more details.)
The Lucas test takes about 3.5x as long as the Miller-Rabin round,
which is close to theoretical expectations.

name                              time/op
ProbablyPrime/Lucas             2.91ms ± 2%
ProbablyPrime/MillerRabinBase2   850µs ± 1%
ProbablyPrime/n=0               3.75ms ± 3%

The speed of prime testing for a prime input does get slower:

name                  old time/op  new time/op   delta
ProbablyPrime/n=1    849µs ± 1%   4521µs ± 1%  +432.31%   (p=0.000 n=10+9)
ProbablyPrime/n=5   4.31ms ± 3%   7.87ms ± 1%   +82.70%  (p=0.000 n=10+10)
ProbablyPrime/n=10  8.52ms ± 3%  12.28ms ± 1%   +44.11%  (p=0.000 n=10+10)
ProbablyPrime/n=20  16.9ms ± 2%   21.4ms ± 2%   +26.35%   (p=0.000 n=9+10)

However, because the Baillie-PSW test is only added when the old
ProbablyPrime(n) would return true, testing composites runs at
the same speed as before, except in the case where the result
would have been incorrect and is now correct.

In particular, the most important use of this code is for
generating random primes in crypto/rand. That use spends
essentially all its time testing composites, so it is not
slowed down by the new Baillie-PSW check:

name                  old time/op  new time/op   delta
Prime                104ms ±22%    111ms ±16%      ~     (p=0.165 n=10+10)

Thanks to Serhat Şevki Dinçer for CL 20170, which this CL builds on.

Fixes #13229.

Change-Id: Id26dde9b012c7637c85f2e96355d029b6382812a
Reviewed-on: https://go-review.googlesource.com/30770
Run-TryBot: Russ Cox 
TryBot-Result: Gobot Gobot 
Reviewed-by: Robert Griesemer

math/rand: make floating point tests shorter on mips and mipsle

2016-11-16T19:22:53+00:00

Like GOARM=5 does.

Fixes #17944

Change-Id: Ica2a54a90fbd4a29471d1c6009ace2fcc5e82a73
Reviewed-on: https://go-review.googlesource.com/33326
Reviewed-by: Cherry Zhang

all: spell "marshal" and "unmarshal" consistently

2016-11-12T00:13:35+00:00

The tree is inconsistent about single l vs double l in those
words in documentation, test messages, and one error value text.

	$ git grep -E '[Mm]arshall(|s|er|ers|ed|ing)' | wc -l
	      42
	$ git grep -E '[Mm]arshal(|s|er|ers|ed|ing)' | wc -l
	    1694

Make it consistently a single l, per earlier decisions. This means
contributors won't be confused by misleading precedence, and it helps
consistency.

Change the spelling in one error value text in newRawAttributes of
crypto/x509 package to be consistent.

This change was generated with:

	perl -i -npe 's,([Mm]arshal)l(|s|er|ers|ed|ing),$1$2,' $(git grep -l -E '[Mm]arshall' | grep -v AUTHORS | grep -v CONTRIBUTORS)

Updates #12431.
Follows https://golang.org/cl/14150.

Change-Id: I85d28a2d7692862ccb02d6a09f5d18538b6049a2
Reviewed-on: https://go-review.googlesource.com/33017
Run-TryBot: Minux Ma 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick

math: use SIMD to accelerate some scalar math functions on s390x

2016-11-11T20:20:23+00:00

Note, most math functions are structured to use stubs, so that they can
be accelerated with assembly on any platform.
Sinh, cosh, and tanh were not structued with stubs, so this CL does
that. This set of routines was chosen as likely to produce good speedups
with assembly on any platform.

Technique used was minimax polynomial approximation using tables of
polynomial coefficients, with argument range reduction.
A table of scaling factors was also used for cosh and log10.

                     before       after      speedup
BenchmarkCos         22.1 ns/op   6.79 ns/op  3.25x
BenchmarkCosh       125   ns/op  11.7  ns/op 10.68x
BenchmarkLog10       48.4 ns/op  12.5  ns/op  3.87x
BenchmarkSin         22.2 ns/op   6.55 ns/op  3.39x
BenchmarkSinh       125   ns/op  14.2  ns/op  8.80x
BenchmarkTanh        65.0 ns/op  15.1  ns/op  4.30x

Accuracy was tested against a high precision
reference function to determine maximum error.
Approximately 4,000,000 points were tested for each function,
producing the following result.
Note: ulperr is error in "units in the last place"

       max
      ulperr
sin    1.43 (returns NaN beyond +-2^50)
cos    1.79 (returns NaN beyond +-2^50)
cosh   1.05
sinh   3.02
tanh   3.69
log10  1.75

Also includes a set of tests to test non-vector functions even
when SIMD is enabled

Change-Id: Icb45f14d00864ee19ed973d209c3af21e4df4edc
Reviewed-on: https://go-review.googlesource.com/32352
Run-TryBot: Michael Munday 
TryBot-Result: Gobot Gobot 
Reviewed-by: Michael Munday

math, math/big: add support for GOARCH=mips{,le}

2016-11-03T22:55:06+00:00

Change-Id: I54e100cced5b49674937fb87d1e0f585f962aeb7
Reviewed-on: https://go-review.googlesource.com/31484
Reviewed-by: Cherry Zhang

math/big: flip long/short flag on TestFloat32Distribution

2016-10-27T21:44:37+00:00

It looks like a typo in CL 30707.

Change-Id: Ia2d013567dbd1a49901d9be0cd2d5a103e6e38cf
Reviewed-on: https://go-review.googlesource.com/32187
Run-TryBot: Cherry Zhang 
TryBot-Result: Gobot Gobot 
Reviewed-by: Russ Cox

math/big: uses SIMD for some math big functions on s390x

2016-10-26T23:52:10+00:00

The following benchmarks are improved by the amounts shown
(Others unaffected beyond the level of noise.)
Also adds a test to confirm non-SIMD implementation still correct,
even when run on SIMD-capable machine

Benchmark                   old            new
BenchmarkAddVV/100-18    66148.08 MB/s 117546.19 MB/s 1.8x
BenchmarkAddVV/1000-18   70168.27 MB/s 133478.96 MB/s 1.9x
BenchmarkAddVV/10000-18  67489.80 MB/s 100010.79 MB/s 1.5x
BenchmarkAddVV/100000-18 54329.99 MB/s  69232.45 MB/s 1.3x
BenchmarkAddVW/100-18     9929.10 MB/s  14841.31 MB/s 1.5x
BenchmarkAddVW/1000-18   10583.31 MB/s  18674.44 MB/s 1.76x
BenchmarkAddVW/10000-18  10521.15 MB/s  17484.10 MB/s 1.66x
BenchmarkAddVW/100000-18 10616.56 MB/s  18084.27 MB/s 1.7x

Change-Id: Ic9234c41a43f6c5e9d0e9377de8b4deeefc428a7
Reviewed-on: https://go-review.googlesource.com/32211
Reviewed-by: Brad Fitzpatrick 
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot

math/cmplx: prevent infinite loop in tanSeries

2016-10-25T18:32:22+00:00

The condition to determine if any further iterations are needed is
evaluated to false in case it encounters a NaN. Instead, flip the
condition to keep looping until the factor is greater than the machine
roundoff error.

Updates #17577

Change-Id: I058abe73fcd49d3ae4e2f7b33020437cc8f290c3
Reviewed-on: https://go-review.googlesource.com/31952
Reviewed-by: Robert Griesemer