The Newton sqrtInverse procedure we use to compute Float.Sqrt should
not allocate a number of times proportional to the number of Newton
iterations we need to reach the desired precision.
At the beginning the function the target precision is known, so even
if we do want to perform the early steps at low precisions (to save
time), it's still possible to pre-allocate larger backing arrays, both
for the temp variables in the loop and the variable that'll hold the
final result.
There's one complication. At the following line:
u.Sub(three, u)
the Sub method will allocate, because the receiver aliases one of the
arguments, and the large backing array we initially allocated for u
will be replaced by a smaller one allocated by Sub. We can work around
this by introducing a second temp variable u2 that we use to hold the
Sub call result.
Overall, the sqrtInverse procedure still allocates a number of times
proportional to the number of Newton steps, because unfortunately a
few of the Mul calls in the Newton function allocate; but at least we
allocate less in the function itself.
FloatSqrt/256-4 1.97µs ± 1% 1.84µs ± 1% -6.61% (p=0.000 n=8+8)
FloatSqrt/1000-4 4.80µs ± 3% 4.28µs ± 1% -10.78% (p=0.000 n=8+8)
FloatSqrt/10000-4 40.0µs ± 1% 38.3µs ± 1% -4.15% (p=0.000 n=8+8)
FloatSqrt/100000-4 955µs ± 1% 932µs ± 0% -2.49% (p=0.000 n=8+7)
FloatSqrt/1000000-4 79.8ms ± 1% 79.4ms ± 1% ~ (p=0.105 n=8+8)
name old alloc/op new alloc/op delta
FloatSqrt/256-4 816B ± 0% 512B ± 0% -37.25% (p=0.000 n=8+8)
FloatSqrt/1000-4 2.50kB ± 0% 1.47kB ± 0% -41.03% (p=0.000 n=8+8)
FloatSqrt/10000-4 23.5kB ± 0% 18.2kB ± 0% -22.62% (p=0.000 n=8+8)
FloatSqrt/100000-4 251kB ± 0% 173kB ± 0% -31.26% (p=0.000 n=8+8)
FloatSqrt/1000000-4 4.61MB ± 0% 2.86MB ± 0% -37.90% (p=0.000 n=8+8)
name old allocs/op new allocs/op delta
FloatSqrt/256-4 12.0 ± 0% 8.0 ± 0% -33.33% (p=0.000 n=8+8)
FloatSqrt/1000-4 19.0 ± 0% 9.0 ± 0% -52.63% (p=0.000 n=8+8)
FloatSqrt/10000-4 35.0 ± 0% 14.0 ± 0% -60.00% (p=0.000 n=8+8)
FloatSqrt/100000-4 55.0 ± 0% 23.0 ± 0% -58.18% (p=0.000 n=8+8)
FloatSqrt/1000000-4 122 ± 0% 75 ± 0% -38.52% (p=0.000 n=8+8)
Change-Id: I950dbf61a40267a6cca82ae72524c3024bcb149c
Reviewed-on: https://go-review.googlesource.com/87659
Reviewed-by: Robert Griesemer <gri@golang.org>
useSSE41 was used inside asm implementation of floor to select between base and ss4 code path.
We intrinsified floor and left asm functions as a backup for non-sse4 systems.
This made variable unused, so remove it.
Change-Id: Ia2633de7c7cb1ef1d5b15a2366b523e481b722d9
Reviewed-on: https://go-review.googlesource.com/97935
Run-TryBot: Ilya Tocar <ilya.tocar@intel.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Fatalf calls in two Float tests use the %s verb with Floats values,
which is not allowed and results in failure messages that look like
this:
float_test.go:1385: i = 0, prec = 1, ToZero:
%!s(*big.Float=1) [0]
/ %!s(*big.Float=1) [0]
= %!s(*big.Float=0.0625)
want %!s(*big.Float=1)
Switch to %v.
Change-Id: Ifdc80bf19c91ca1b190f6551a6d0a51b42ed5919
Reviewed-on: https://go-review.googlesource.com/87199
Run-TryBot: Alberto Donizetti <alb.donizetti@gmail.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
In the comment of seedPost, the word: condiiton was changed to: condition
Change-Id: I8967cc0e9f5d37776bada96cc1443c8bf46e1117
Reviewed-on: https://go-review.googlesource.com/86156
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Fixes#23224
The previous Pow code had an optimization for
powers equal to ±0.5 that used Sqrt for
increased accuracy/speed. This caused special
cases involving powers of ±0.5 to disagree with
the Pow spec. This change places the Sqrt optimization
after all of the special case handling.
Change-Id: I6bf757f6248256b29cc21725a84e27705d855369
Reviewed-on: https://go-review.googlesource.com/85660
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Dim performance has regressed by 14% vs 1.9 on amd64.
Current pure go version of Dim is faster and,
what is even more important for performance, is inlinable, so
instead of tweaking asm implementation, just remove it.
I had to update BenchmarkDim, because it was simply reloading
constant(answer) in a loop.
Perf data below:
name old time/op new time/op delta
Dim-6 6.79ns ± 0% 1.60ns ± 1% -76.39% (p=0.000 n=7+10)
If I modify benchmark to be the same as in this CL results are even better:
name old time/op new time/op delta
Dim-6 10.2ns ± 0% 1.6ns ± 1% -84.27% (p=0.000 n=8+10)
Updates #21913
Change-Id: I00e23c8affc293531e1d9f0e0e49f3a525634f53
Reviewed-on: https://go-review.googlesource.com/80695
Run-TryBot: Ilya Tocar <ilya.tocar@intel.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
In nat.divLarge (having signature (z nat).divLarge(u, uIn, v nat)),
we check whether z aliases uIn or v, but aliasing is currently not
checked for the u parameter.
Unfortunately, z and u aliasing each other can in some cases cause
errors in the computation.
The q return parameter (which will hold the result's quotient), is
unconditionally initialized as
q = z.make(m + 1)
When cap(z) ≥ m+1, z.make() will reuse z's backing array, causing q
and z to share the same backing array. If then z aliases u, setting q
during the quotient computation will then corrupt u, which at that
point already holds computation state.
To fix this, we add an alias(z, u) check at the beginning of the
function, taking care of aliasing the same way we already do for uIn
and v.
Fixes#22830
Change-Id: I3ab81120d5af6db7772a062bb1dfc011de91f7ad
Reviewed-on: https://go-review.googlesource.com/78995
Run-TryBot: Alberto Donizetti <alb.donizetti@gmail.com>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Branch cuts for the elementary complex functions along real or imaginary axes
should be resolved in floating point calculations by one-sided continuity with
signed zero as described in:
"Branch Cuts for Complex Elementary Functions or Much Ado About Nothing's Sign Bit"
W. Kahan
Available at: https://people.freebsd.org/~das/kahan86branch.pdf
And as described in the C99 standard which is claimed as the original cephes source.
Sqrt did not return the correct branch when imag(x) == 0. The branch is now
determined by sign(imag(x)). This incorrect branch choice was affecting the behavior
of the Trigonometric/Hyperbolic functions that use Sqrt in intermediate calculations.
Asin, Asinh and Atan had spurious domain checks, whereas the functions should be valid
over the whole complex plane with appropriate branch cuts.
Fixes#6888
Change-Id: I9b1278af54f54bfb4208276ae345bbd3ddf3ec83
Reviewed-on: https://go-review.googlesource.com/46492
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>
This reverts CL 55972.
Reason for revert: this changes Perm's behavior unnecessarily.
I asked for this change originally but I now regret it.
Reverting so that I don't have to justify it in Go 1.10 release notes.
Edited to keep the change to rand_test.go, which seems to have
been mostly unrelated.
Fixes#22744.
Change-Id: If8bb1bcde3ced0db2fdcd0aa65ab128613686c66
Reviewed-on: https://go-review.googlesource.com/78195
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Emmanuel Odeke <emm.odeke@gmail.com>
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Joe Tsai <thebrokentoaster@gmail.com>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
If a composite literal contains any comments on their own lines without
any elements, the printer would unindent the comments.
The comments in this edge case are written when the closing '}' is
written. Indent and outdent first so that the indentation is
interspersed before the comment is written.
Also note that the go/printer golden tests don't show the exact same
behaviour that gofmt does. Added a TODO to figure this out in a separate
CL.
While at it, ensure that the tree conforms to gofmt. The changes are
unrelated to this indentation fix, however.
Fixes#22355.
Change-Id: I5ac25ac6de95a236f1e123479127cc4dd71e93fe
Reviewed-on: https://go-review.googlesource.com/74232
Run-TryBot: Daniel Martí <mvdan@mvdan.cc>
Reviewed-by: Robert Griesemer <gri@golang.org>
A clarifying comment was added to indicate that overflow of a
single Word is not possible in the single digit calculation.
Lehmer's paper includes a proof of the bounds on the size of the
cosequences (u0, u1, u2, v0, v1, v2).
Change-Id: I98127a07aa8f8fe44814b74b2bc6ff720805194b
Reviewed-on: https://go-review.googlesource.com/77451
Reviewed-by: Robert Griesemer <gri@golang.org>
Right rotation is achieved using negative k in RotateLeft*(x, k). Add
examples demonstrating that functionality.
Change-Id: I15dab159accd2937cb18d3fa8ca32da8501567d3
Reviewed-on: https://go-review.googlesource.com/75371
Run-TryBot: Tobias Klauser <tobias.klauser@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
An initial draft of the Newton code for Float.Sqrt was structured like
this:
for condition
// do Newton iteration..
prec *= 2
since prec, at the end of the loop, was double the precision used in
the last Newton iteration, the termination condition was set to
2*limit. The code was later rewritten in the form
for condition
prec *= 2
// do Newton iteration..
but condition was not updated, and it's still 2*limit, which is about
double what we actually need, and is triggering the execution of an
additional, and unnecessary, Newton iteration.
This change adjusts the Newton termination condition to the (correct)
value of z.prec, plus 32 guard bits as a safety margin.
name old time/op new time/op delta
FloatSqrt/64-4 798ns ± 3% 802ns ± 3% ~ (p=0.458 n=8+8)
FloatSqrt/128-4 1.65µs ± 1% 1.65µs ± 1% ~ (p=0.290 n=8+8)
FloatSqrt/256-4 3.10µs ± 1% 2.10µs ± 0% -32.32% (p=0.000 n=8+7)
FloatSqrt/1000-4 8.83µs ± 1% 4.91µs ± 2% -44.39% (p=0.000 n=8+8)
FloatSqrt/10000-4 107µs ± 1% 40µs ± 1% -62.68% (p=0.000 n=8+8)
FloatSqrt/100000-4 2.91ms ± 1% 0.96ms ± 1% -67.13% (p=0.000 n=8+8)
FloatSqrt/1000000-4 240ms ± 1% 80ms ± 1% -66.66% (p=0.000 n=8+8)
name old alloc/op new alloc/op delta
FloatSqrt/64-4 416B ± 0% 416B ± 0% ~ (all equal)
FloatSqrt/128-4 720B ± 0% 720B ± 0% ~ (all equal)
FloatSqrt/256-4 1.34kB ± 0% 0.82kB ± 0% -39.29% (p=0.000 n=8+8)
FloatSqrt/1000-4 5.09kB ± 0% 2.50kB ± 0% -50.94% (p=0.000 n=8+8)
FloatSqrt/10000-4 45.9kB ± 0% 23.5kB ± 0% -48.81% (p=0.000 n=8+8)
FloatSqrt/100000-4 533kB ± 0% 251kB ± 0% -52.90% (p=0.000 n=8+8)
FloatSqrt/1000000-4 9.21MB ± 0% 4.61MB ± 0% -49.98% (p=0.000 n=8+8)
name old allocs/op new allocs/op delta
FloatSqrt/64-4 9.00 ± 0% 9.00 ± 0% ~ (all equal)
FloatSqrt/128-4 13.0 ± 0% 13.0 ± 0% ~ (all equal)
FloatSqrt/256-4 15.0 ± 0% 12.0 ± 0% -20.00% (p=0.000 n=8+8)
FloatSqrt/1000-4 24.0 ± 0% 19.0 ± 0% -20.83% (p=0.000 n=8+8)
FloatSqrt/10000-4 40.0 ± 0% 35.0 ± 0% -12.50% (p=0.000 n=8+8)
FloatSqrt/100000-4 66.0 ± 0% 55.0 ± 0% -16.67% (p=0.000 n=8+8)
FloatSqrt/1000000-4 143 ± 0% 122 ± 0% -14.69% (p=0.000 n=8+8)
Change-Id: I4868adb7f8960f2ca20e7792734c2e6211669fc0
Reviewed-on: https://go-review.googlesource.com/75010
Reviewed-by: Robert Griesemer <gri@golang.org>
Adds the following s390x test under mask (immediate) instructions:
TMHH
TMHL
TMLH
TMLL
These are useful for testing bits and are already used in the math package.
Change-Id: Idffb3f83b238dba76ac1e42ac6b0bf7f1d11bea2
Reviewed-on: https://go-review.googlesource.com/41092
Run-TryBot: Michael Munday <mike.munday@ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
By calculating dim directly, rather than calling max, we can simplify
the generated code significantly. The compiler now reports that dim
is easily inlineable, but it can't be inlined because there is still
an assembly stub for Dim.
Since dim is now very simple I no longer think it is worth having
assembly implementations of it. I have therefore removed the s390x
assembly. Removing the other assembly for Dim is #21913.
name old time/op new time/op delta
Dim 4.29ns ± 0% 3.53ns ± 0% -17.62% (p=0.000 n=9+8)
Change-Id: Ic38a6b51603cbc661dcdb868ecf2b1947e9f399e
Reviewed-on: https://go-review.googlesource.com/64194
Run-TryBot: Michael Munday <mike.munday@ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
This change adds a Square root method to the big.Float type, with
signature
(z *Float) Sqrt(x *Float) *Float
Fixes#20460
Change-Id: I050aaed0615fe0894e11c800744600648343c223
Reviewed-on: https://go-review.googlesource.com/67830
Run-TryBot: Alberto Donizetti <alb.donizetti@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Rounding ties to even is statistically useful for some applications.
This implementation completes IEEE float64 rounding mode support (in
addition to Round, Ceil, Floor, Trunc).
This function avoids subtle faults found in ad-hoc implementations, and
is simple enough to be inlined by the compiler.
Fixes#21748
Change-Id: I09415df2e42435f9e7dabe3bdc0148e9b9ebd609
Reviewed-on: https://go-review.googlesource.com/61211
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Increase MaxBase from 36 to 62 and extend the conversion
alphabet with the upper-case letters 'A' to 'Z'. For int
conversions with bases <= 36, the letters 'A' to 'Z' have
the same values (10 to 35) as the corresponding lower-case
letters. For conversion bases > 36 up to 62, the upper-case
letters have the values 36 to 61.
Added MaxBase to api/except.txt: Clients should not make
assumptions about the value of MaxBase being constant.
The core of the change is in natconv.go. The remaining
changes are adjusted tests and documentation.
Fixes#21558.
Change-Id: I5f74da633caafca03993e13f32ac9546c572cc84
Reviewed-on: https://go-review.googlesource.com/65970
Reviewed-by: Martin Möhrmann <moehrmann@google.com>
This removes some of the []byte/string conversions currently
existing in the (un)marshaling methods of Int and Rat.
For Int we introduce a new function (*Int).setFromScanner() essentially
implementing the SetString method being given an io.ByteScanner instead
of a string. So we can handle the string case in (*Int).SetString with
a *strings.Reader and the []byte case in (*Int).UnmarshalText() with a
*bytes.Reader now avoiding the []byte/string conversion here.
For Rat we introduce a new function (*Rat).marshal() essentially
implementing the String method outputting []byte instead of string.
Using this new function and the same formatting rules as in
(*Rat).RatString we can implement (*Rat).MarshalText() without
the []byte/string conversion it used to have.
Change-Id: Ic5ef246c1582c428a40f214b95a16671ef0a06d9
Reviewed-on: https://go-review.googlesource.com/65950
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
strings.IndexByte was introduced in go1.2 and it can be used
effectively wherever the second argument to strings.Index is
exactly one byte long.
This avoids generating unnecessary string symbols and saves
a few calls to strings.Index.
Change-Id: I1ab5edb7c4ee9058084cfa57cbcc267c2597e793
Reviewed-on: https://go-review.googlesource.com/65930
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
- using FMA and AVX instructions if available to speed-up
Exp calculation on amd64
- using a data table instead of #define'ed constants because
these instructions do not support loading floating point immediates.
One has to use a memory operand / register.
- Benchmark results on Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz:
Original vs New (non-FMA path)
name old time/op new time/op delta
Exp 16.0ns ± 1% 16.1ns ± 3% ~ (p=0.308 n=9+10)
Original vs New (FMA path)
name old time/op new time/op delta
Exp 16.0ns ± 1% 13.7ns ± 2% -14.80% (p=0.000 n=9+10)
Change-Id: I3d8986925d82b39b95ee979ae06f59d7e591d02e
Reviewed-on: https://go-review.googlesource.com/62590
Reviewed-by: Ilya Tocar <ilya.tocar@intel.com>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Shuffle panics if n < 0, not n <= 0. The comment for the (*Rand).Shuffle
function is already accurate.
Change-Id: I073049310bca9632e50e9ca3ff79eec402122793
Reviewed-on: https://go-review.googlesource.com/63750
Reviewed-by: Ian Lance Taylor <iant@golang.org>
CL 62250 makes constant folding a bit more aggressive and these
benchmarks were optimized away. This CL adds some indirection to
the function arguments to stop them being folded.
The Copysign benchmark is a bit faster because I've left one
argument as a constant and it can be partially folded.
old CL 62250 this CL
Copysign 1.24ns ± 0% 0.34ns ± 2% 1.02ns ± 2%
Abs 0.67ns ± 0% 0.35ns ± 3% 0.67ns ± 0%
Signbit 0.87ns ± 0% 0.35ns ± 2% 0.87ns ± 1%
Change-Id: I9604465a87d7aa29f4bd6009839c8ee354be3cd7
Reviewed-on: https://go-review.googlesource.com/62450
Run-TryBot: Michael Munday <mike.munday@ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Perm and Shuffle are fundamentally doing the same work.
This change makes Perm's algorithm match Shuffle's.
In addition to allowing developers to switch more
easily between the two methods, it affords a nice speed-up:
name old time/op new time/op delta
Perm3-8 75.7ns ± 1% 51.8ns ± 1% -31.59% (p=0.000 n=9+8)
Perm30-8 610ns ± 1% 405ns ± 1% -33.67% (p=0.000 n=9+9)
This change alters the output from Perm,
given the same Source and seed.
This is a change from Go 1.0 behavior.
This necessitates updating the regression test.
This also changes the number of calls made to the Source
during Perm, which changes the output of the math/rand examples.
This also slightly perturbs the output of Perm,
nudging it out of the range currently accepted by TestUniformFactorial.
However, it is complete unclear that the helpers relied on
by TestUniformFactorial are correct. That is #21211.
This change updates checkSimilarDistribution to respect
closeEnough for standard deviations, which makes the test pass.
The whole situation is muddy; see #21211 for details.
There is an alternative implementation of Perm
that avoids initializing m, which is more similar
to the existing implementation, plus some optimizations:
func (r *Rand) Perm(n int) []int {
m := make([]int, n)
max31 := n
if n > 1<<31-1-1 {
max31 = 1<<31 - 1 - 1
}
i := 1
for ; i < max31; i++ {
j := r.int31n(int32(i + 1))
m[i] = m[j]
m[j] = i
}
for ; i < n; i++ {
j := r.Int63n(int64(i + 1))
m[i] = m[j]
m[j] = i
}
return m
}
This is a tiny bit faster than the implementation
actually used in this change:
name old time/op new time/op delta
Perm3-8 51.8ns ± 1% 50.3ns ± 1% -2.83% (p=0.000 n=8+9)
Perm30-8 405ns ± 1% 394ns ± 1% -2.66% (p=0.000 n=9+8)
However, 3% in performance doesn't seem worth
having the two algorithms diverge,
nor the reduced readability of this alternative.
Updates #16213.
Change-Id: I11a7441ff8837ee9c241b4c88f7aa905348be781
Reviewed-on: https://go-review.googlesource.com/55972
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
Shuffle uses the Fisher-Yates algorithm.
Since this is new API, it affords us the opportunity
to use a much faster Int31n implementation that mostly avoids division.
As a result, BenchmarkPerm30ViaShuffle is
about 30% faster than BenchmarkPerm30,
despite requiring a separate initialization loop
and using function calls to swap elements.
Fixes#20480
Updates #16213
Updates #21211
Change-Id: Ib8956c4bebed9d84f193eb98282ec16ee7c2b2d5
Reviewed-on: https://go-review.googlesource.com/51891
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
This function avoids subtle faults found in many ad-hoc implementations,
and is simple enough to be inlined by the compiler.
Fixes#20100
Change-Id: Ib320254e9b1f1f798c6ef906b116f63bc29e8d08
Reviewed-on: https://go-review.googlesource.com/43652
Reviewed-by: Robert Griesemer <gri@golang.org>
Change-Id: Ic3ce2f3c055f2636ec8fc9cec8592e596b18dc05
Reviewed-on: https://go-review.googlesource.com/54771
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Implement int reg <-> fp reg moves on amd64.
If we see a load to int reg followed by an int->fp move, then we can just
load to the fp reg instead. Same for stores.
math.Abs is now:
MOVQ "".x+8(SP), AX
SHLQ $1, AX
SHRQ $1, AX
MOVQ AX, "".~r1+16(SP)
math.Copysign is now:
MOVQ "".x+8(SP), AX
SHLQ $1, AX
SHRQ $1, AX
MOVQ "".y+16(SP), CX
SHRQ $63, CX
SHLQ $63, CX
ORQ CX, AX
MOVQ AX, "".~r2+24(SP)
math.Float64bits is now:
MOVSD "".x+8(SP), X0
MOVSD X0, "".~r1+16(SP)
(it would be nicer to use a non-SSE reg for this, nothing is perfect)
And due to the fix for #21440, the inlined version of these improve as well.
name old time/op new time/op delta
Abs 1.38ns ± 5% 0.89ns ±10% -35.54% (p=0.000 n=10+10)
Copysign 1.56ns ± 7% 1.35ns ± 6% -13.77% (p=0.000 n=9+10)
Fixes#13095
Change-Id: Ibd7f2792412a6668608780b0688a77062e1f1499
Reviewed-on: https://go-review.googlesource.com/58732
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
Reviewed-by: Ilya Tocar <ilya.tocar@intel.com>
This commit defines the inverse of error function (erfinv) in the
math package. The function is based on the rational approximation
of percentage points of normal distribution available at
https://www.jstor.org/stable/pdf/2347330.pdf.
Fixes#6359
Change-Id: Icfe4508f623e0574c7fffdbf7aa929540fd4c944
Reviewed-on: https://go-review.googlesource.com/46990
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Updates #13745
Recognize z.Mul(x, x) as squaring for Floats and use
the internal z.sqr(x) method for nat on the mantissa.
Change-Id: I0f792157bad93a13cae1aecc4c10bd20c6397693
Reviewed-on: https://go-review.googlesource.com/56774
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
updates #13745
A squared rational is always positive and can not
be reduced since the numerator and denominator had
no previous common factors. The nat multiplication
can be performed using the internal sqr method.
Change-Id: I558f5b38e379bfd26ff163c9489006d7e5a9cfaa
Reviewed-on: https://go-review.googlesource.com/56776
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Found with mvdan.cc/unindent. Prioritized the ones with the biggest wins
for now.
Change-Id: I2b032e45cdd559fc9ed5b1ee4c4de42c4c92e07b
Reviewed-on: https://go-review.googlesource.com/56470
Run-TryBot: Daniel Martí <mvdan@mvdan.cc>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
The existing implementation is translated from C, which uses a
polynomial coefficient very close to 1/6. If the function uses
1/6 as this coeffient, the result of Exp(1) will be more accurate.
And this change doesn't introduce more error to Exp function.
Fixes#20319
Change-Id: I94c236a18cf95570ebb69f7fb99884b0d7cf5f6e
Reviewed-on: https://go-review.googlesource.com/49294
Reviewed-by: Robert Griesemer <gri@golang.org>
updates #13745
Multiprecision squaring can be done in a straightforward manner
with about half the multiplications of a basic multiplication
due to the symmetry of the operands. This change implements
basic squaring for nat types and uses it for Int multiplication
when the same variable is supplied to both arguments of
z.Mul(x, x). This has some overhead to allocate a temporary
variable to hold the cross products, shift them to double and
add them to the diagonal terms. There is a speed benefit in
the intermediate range when the overhead is neglible and the
asymptotic performance of karatsuba multiplication has not been
reached.
basicSqrThreshold = 20
karatsubaSqrThreshold = 400
Were set by running calibrate_test.go to measure timing differences
between the algorithms. Benchmarks for squaring:
name old time/op new time/op delta
IntSqr/1-4 51.5ns ±25% 25.1ns ± 7% -51.38% (p=0.008 n=5+5)
IntSqr/2-4 79.1ns ± 4% 72.4ns ± 2% -8.47% (p=0.008 n=5+5)
IntSqr/3-4 102ns ± 4% 97ns ± 5% ~ (p=0.056 n=5+5)
IntSqr/5-4 161ns ± 4% 163ns ± 7% ~ (p=0.952 n=5+5)
IntSqr/8-4 277ns ± 5% 267ns ± 6% ~ (p=0.087 n=5+5)
IntSqr/10-4 358ns ± 3% 360ns ± 4% ~ (p=0.730 n=5+5)
IntSqr/20-4 1.07µs ± 3% 1.01µs ± 6% ~ (p=0.056 n=5+5)
IntSqr/30-4 2.36µs ± 4% 1.72µs ± 2% -27.03% (p=0.008 n=5+5)
IntSqr/50-4 5.19µs ± 3% 3.88µs ± 4% -25.37% (p=0.008 n=5+5)
IntSqr/80-4 11.3µs ± 4% 8.6µs ± 3% -23.78% (p=0.008 n=5+5)
IntSqr/100-4 16.2µs ± 4% 12.8µs ± 3% -21.49% (p=0.008 n=5+5)
IntSqr/200-4 50.1µs ± 5% 44.7µs ± 3% -10.65% (p=0.008 n=5+5)
IntSqr/300-4 105µs ±11% 95µs ± 3% -9.50% (p=0.008 n=5+5)
IntSqr/500-4 231µs ± 5% 227µs ± 2% ~ (p=0.310 n=5+5)
IntSqr/800-4 496µs ± 9% 459µs ± 3% -7.40% (p=0.016 n=5+5)
IntSqr/1000-4 700µs ± 3% 710µs ± 5% ~ (p=0.841 n=5+5)
Show a speed up of 10-25% in the range where basicSqr is optimal,
improved single word squaring and no significant difference when
the fallback to standard multiplication is used.
Change-Id: Iae2c82ca91cf890823f91e5c83bbe9a2c534b72b
Reviewed-on: https://go-review.googlesource.com/53638
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
The current implementation of the extended Euclidean GCD algorithm
calculates both cosequences x and y inside the division loop. This
is unneccessary since the second Bezout coefficient can be obtained
at the end of calculation via a multiplication, subtraction and a
division. In case only one coefficient is needed, e.g. ModInverse
this calculation can be skipped entirely. This is a standard
optimization, see e.g.
"Handbook of Elliptic and Hyperelliptic Curve Cryptography"
Cohen et al pp 191
Available at:
http://cs.ucsb.edu/~koc/ccs130h/2013/EllipticHyperelliptic-CohenFrey.pdf
Updates #15833
Change-Id: I1e0d2e63567cfed97fd955048fe6373d36f22757
Reviewed-on: https://go-review.googlesource.com/50530
Reviewed-by: Robert Griesemer <gri@golang.org>
The current implementation uses a shift and add
loop to compute the product of x's exponent xe and
the integer part of y (yi) for yi up to 1<<63.
Since xe is an 11-bit exponent, this product can be
up to 74-bits and overflow both 32 and 64-bit int.
This change checks whether the accumulated exponent
will fit in the 11-bit float exponent of the output
and breaks out of the loop early if overflow is detected.
The current handling of yi >= 1<<63 uses Exp(y * Log(x))
which incorrectly returns Nan for x<0. In addition,
for y this large, Exp(y * Log(x)) can be enumerated
to only overflow except when x == -1 since the
boundary cases computed exactly:
Pow(NextAfter(1.0, Inf(1)), 1<<63) == 2.72332... * 10^889
Pow(NextAfter(1.0, Inf(-1)), 1<<63) == 1.91624... * 10^-445
exceed the range of float64. So, the call can be
replaced with a simple case statement analgous to
y == Inf that correctly handles x < 0 as well.
Fixes#7394
Change-Id: I6f50dc951f3693697f9669697599860604323102
Reviewed-on: https://go-review.googlesource.com/48290
Reviewed-by: Robert Griesemer <gri@golang.org>
As noted in the TODO comment, the sticky bit is only used
when the rounding bit is zero or the rounding mode is
ToNearestEven. This change makes that check explicit and
will eliminate half the sticky bit calculations on average
when rounding mode is not ToNearestEven.
Change-Id: Ia4709f08f46e682bf97dabe5eb2a10e8e3d7af43
Reviewed-on: https://go-review.googlesource.com/54111
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Add test cases to verify behavior for Ldexp with exponents outside the
range of Minint32/Maxint32, for a gccgo bug.
Test for issue #21323.
Change-Id: Iea67bc6fcfafdfddf515cf7075bdac59360c277a
Reviewed-on: https://go-review.googlesource.com/54230
Run-TryBot: Than McIntosh <thanm@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
The standard deviation of a uniform distribution is size / √12.
The size of the interval [0, 255] is 256, not 255.
While we're here, simplify the expression.
The tests previously passed only because the error margin was large enough.
Sample observed standard deviations while running tests:
73.7893634666819
73.9221651548294
73.8077961697150
73.9084236069471
73.8968446814785
73.8684209136244
73.9774618960282
73.9523483202549
255 / √12 == 73.6121593216772
256 / √12 == 73.9008344562721
Change-Id: I7bc6cdc11e5d098951f2f2133036f62489275979
Reviewed-on: https://go-review.googlesource.com/51310
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Regular HTTP is insecure, oeis.org supports HTTPS and it is actually
used in some other places in the codebase. This changes these final urls
to use HTTPS.
Change-Id: Ia46410a9c7ce67238a10cb6bfffaceca46112f58
Reviewed-on: https://go-review.googlesource.com/52072
Reviewed-by: Alberto Donizetti <alb.donizetti@gmail.com>
Manual hyphenation doesn't work well when text gets reflown,
for example by godoc.
There are a few other manual hyphenations in the tree,
but they are in local comments or comments for unexported functions.
Change-Id: I17c9b1fee1def650da48903b3aae2fa1e1119a65
Reviewed-on: https://go-review.googlesource.com/53510
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Erroneously called OnesCount instead of OnesCount64
Change-Id: Ie877e43f213253e45d31f64931c4a15915849586
Reviewed-on: https://go-review.googlesource.com/53410
Reviewed-by: Chris Broadfoot <cbro@golang.org>
Go doesn't guarantee that the result of floating point operations will
be the same on different architectures. It was not stated in the
documentation, that can lead to confusion.
Fixes#18354
Change-Id: Idb1b4c256fb9a7158a74256136eca3b8ce44476f
Reviewed-on: https://go-review.googlesource.com/34938
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Implements detection of x86 cpu features that
are used in the go standard library.
Changes all standard library packages to use the new cpu package
instead of using runtime internal variables to check x86 cpu features.
Updates: #15403
Change-Id: I2999a10cb4d9ec4863ffbed72f4e021a1dbc4bb9
Reviewed-on: https://go-review.googlesource.com/41476
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
This adds math/bits intrinsics for OnesCount, Len, TrailingZeros on
ppc64x.
benchmark old ns/op new ns/op delta
BenchmarkLeadingZeros-16 4.26 1.71 -59.86%
BenchmarkLeadingZeros16-16 3.04 1.83 -39.80%
BenchmarkLeadingZeros32-16 3.31 1.82 -45.02%
BenchmarkLeadingZeros64-16 3.69 1.71 -53.66%
BenchmarkTrailingZeros-16 2.55 1.62 -36.47%
BenchmarkTrailingZeros32-16 2.55 1.77 -30.59%
BenchmarkTrailingZeros64-16 2.78 1.62 -41.73%
BenchmarkOnesCount-16 3.19 0.93 -70.85%
BenchmarkOnesCount32-16 2.55 1.18 -53.73%
BenchmarkOnesCount64-16 3.22 0.93 -71.12%
Update #18616
I also made a change to bits_test.go because when debugging some failures
the output was not quite providing the right argument information.
Change-Id: Ia58d31d1777cf4582a4505f85b11a1202ca07d3e
Reviewed-on: https://go-review.googlesource.com/41630
Run-TryBot: Lynn Boger <laboger@linux.vnet.ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Carlos Eduardo Seo <cseo@linux.vnet.ibm.com>
Reviewed-by: Keith Randall <khr@golang.org>
As necessary, math functions were structured to use stubs, so that they can
be accelerated with assembly on any platform.
Technique used was minimax polynomial approximation using tables of
polynomial coefficients, with argument range reduction.
Benchmark New Old Speedup
BenchmarkAcos 12.2 47.5 3.89
BenchmarkAcosh 18.5 56.2 3.04
BenchmarkAsin 13.1 40.6 3.10
BenchmarkAsinh 19.4 62.8 3.24
BenchmarkAtan 10.1 23 2.28
BenchmarkAtanh 19.1 53.2 2.79
BenchmarkAtan2 16.5 33.9 2.05
BenchmarkCbrt 14.8 58 3.92
BenchmarkErf 10.8 20.1 1.86
BenchmarkErfc 11.2 23.5 2.10
BenchmarkExp 8.77 53.8 6.13
BenchmarkExpm1 10.1 38.3 3.79
BenchmarkLog 13.1 40.1 3.06
BenchmarkLog1p 12.7 38.3 3.02
BenchmarkPowInt 31.7 40.5 1.28
BenchmarkPowFrac 33.1 141 4.26
BenchmarkTan 11.5 30 2.61
Accuracy was tested against a high precision
reference function to determine maximum error.
Note: ulperr is error in "units in the last place"
max
ulperr
Acos 1.15
Acosh 1.07
Asin 2.22
Asinh 1.72
Atan 1.41
Atanh 3.00
Atan2 1.45
Cbrt 1.18
Erf 1.29
Erfc 4.82
Exp 1.00
Expm1 2.26
Log 0.94
Log1p 2.39
Tan 3.14
Pow will have 99.99% correctly rounded results with reasonable inputs
producing numeric (non Inf or NaN) results
Change-Id: I850e8cf7b70426e8b54ec49d74acd4cddc8c6cb2
Reviewed-on: https://go-review.googlesource.com/38585
Reviewed-by: Michael Munday <munday@ca.ibm.com>
Run-TryBot: Michael Munday <munday@ca.ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
We have dedicated asm implementation of sincos only on 386 and amd64,
on everything else we are just jumping to generic version.
However amd64 version is actually slower than generic one:
Sincos-6 34.4ns ± 0% 24.8ns ± 0% -27.79% (p=0.000 n=8+10)
So remove all sincos*.s and keep only generic and 386.
Updates #19819
Change-Id: I7eefab35743729578264f52f6d23ee2c227c92a5
Reviewed-on: https://go-review.googlesource.com/41200
Run-TryBot: Ilya Tocar <ilya.tocar@intel.com>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
The instructions allow moves between floating point and general
purpose registers without any conversion taking place.
Change-Id: I82c6f3ad9c841a83783b5be80dcf5cd538ff49e6
Reviewed-on: https://go-review.googlesource.com/38777
Run-TryBot: Michael Munday <munday@ca.ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
Starting in go1.9, the minimum processor requirement for ppc64 is POWER8. So it
may now use the same divWW implementation as ppc64le.
Updates #19074
Change-Id: If1a85f175cda89eee06a1024ccd468da6124c844
Reviewed-on: https://go-review.googlesource.com/39010
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Lynn Boger <laboger@linux.vnet.ibm.com>
After https://golang.org/cl/31490 we break false
output dependency for CVTS.. in compiler generated code.
I've looked through asm code, which uses CVTS..
and added XOR to the only case where it affected performance.
Log-6 21.6ns ± 0% 19.9ns ± 0% -7.87% (p=0.000 n=10+10)
Change-Id: I25d9b405e3041a3839b40f9f9a52e708034bb347
Reviewed-on: https://go-review.googlesource.com/38771
Run-TryBot: Ilya Tocar <ilya.tocar@intel.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Verified that BenchmarkBitLen time went down from 2.25 ns/op to 0.65 ns/op
an a 2.3 GHz Intel Core i7, before removing that benchmark (now covered by
math/bits benchmarks).
Change-Id: I3890bb7d1889e95b9a94bd68f0bdf06f1885adeb
Reviewed-on: https://go-review.googlesource.com/38464
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
A -0 constant is the same as 0. Use explicit negative zero
for float64 -0.0. Also, fix two test cases that were wrong.
Fixes#19673.
Change-Id: Ic09775f29d9bc2ee7814172e59c4a693441ea730
Reviewed-on: https://go-review.googlesource.com/38463
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
nat.setUint64 is nicely generic.
By assuming 32- or 64-bit words, however,
we can write simpler code,
and eliminate some shifts
in dead code that vet complains about.
Generated code for 64 bit systems is unaltered.
Generated code for 32 bit systems is much better.
For 386, the routine length drops from 325
bytes of code to 271 bytes of code, with fewer loops.
Change-Id: I1bc14c06272dee37a7fcb48d33dd1e621eba945d
Reviewed-on: https://go-review.googlesource.com/38070
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Change-Id: I6343c162e27e2e492547c96f1fc504909b1c03c0
Reviewed-on: https://go-review.googlesource.com/37793
Reviewed-by: Daniel Martí <mvdan@mvdan.cc>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Removes an extra function call for TrailingZeroes and thus may
increase chances for inlining.
Change-Id: Iefd8d4402dc89b64baf4e5c865eb3dadade623af
Reviewed-on: https://go-review.googlesource.com/37613
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
This change adds math/bits as a new dependency of math/big.
- use bits.LeadingZeroes instead of local implementation
(they are identical, so there's no performance loss here)
- leave other functionality local (ntz, bitLen) since there's
faster implementations in math/big at the moment
Change-Id: I1218aa8a1df0cc9783583b090a4bb5a8a145c4a2
Reviewed-on: https://go-review.googlesource.com/37141
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Removes init function from the math package.
Allows stripping of arrays with pre-computed values
used for Pow10 from binaries if Pow10 is not used.
cmd/go shrinks by 128 bytes.
Fixed small values like 10**-323 being 0 instead of 1e-323.
Overall precision is increased but still not as good as
predefined constants for some inputs.
Samples:
Pow10(208)
before: 1.0000000000000006662e+208
after: 1.0000000000000000959e+208
Pow10(202)
before 1.0000000000000009895e+202
after 1.0000000000000001193e+202
Pow10(60)
before 1.0000000000000001278e+60
after 0.9999999999999999494e+60
Pow10(-100)
before 0.99999999999999938551e-100
after 0.99999999999999989309e-100
Pow10(-200)
before 0.9999999999999988218e-200
after 1.0000000000000001271e-200
name old time/op new time/op delta
Pow10Pos-4 44.6ns ± 2% 1.2ns ± 1% -97.39% (p=0.000 n=19+17)
Pow10Neg-4 50.8ns ± 1% 4.1ns ± 2% -92.02% (p=0.000 n=17+19)
Change-Id: If094034286b8ac64be3a95fd9e8ffa3d4ad39b31
Reviewed-on: https://go-review.googlesource.com/36331
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Martin Möhrmann <moehrmann@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Test finite negative x with Y0(-1), Y1(-1), Yn(2,-1), Yn(-3,-1).
Also test the special case Yn(0,0).
Fixes#19130.
Change-Id: I95f05a72e1c455ed8ddf202c56f4266f03f370fd
Reviewed-on: https://go-review.googlesource.com/37310
Reviewed-by: Robert Griesemer <gri@golang.org>
For compatibility with math/bits uint operations.
When math/big was written originally, the Go compiler used 32bit
int/uint values even on a 64bit machine. uintptr was the type that
represented the machine register size. Now, the int/uint types are
sized to the native machine register size, so they are the natural
machine Word type.
On most machines, the size of int/uint correspond to the size of
uintptr. On platforms where uint and uintptr have different sizes,
this change may lead to performance differences (e.g., amd64p32).
Change-Id: Ief249c160b707b6441848f20041e32e9e9d8d8ca
Reviewed-on: https://go-review.googlesource.com/37372
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Add exported global variables and store the results of benchmarked
functions in them. This prevents the current compiler optimizations
from removing the instructions that are needed to compute the return
values of the benchmarked functions.
Change-Id: If8b08424e85f3796bb6dd73e761c653abbabcc5e
Reviewed-on: https://go-review.googlesource.com/37195
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
- moved from: x&m>>k | x&^m<<k to: x&m>>k | x<<k&m
This permits use of the same constant m twice (*) which may be
better for machines that can't use large immediate constants
directly with an AND instruction and have to load them explicitly.
*) CPUs don't usually have a &^ instruction, so x&^m becomes x&(^m)
- simplified returns
This improves the generated code because the compiler recognizes
x>>k | x<<k as ROT when k is the bitsize of x.
The 8-bit versions of these instructions can be significantly faster
still if they are replaced with table lookups, as long as the table
is in cache. If the table is not in cache, table-lookup is probably
slower, hence the choice of an explicit register-only implementation
for now.
BenchmarkReverse-8 8.50 6.86 -19.29%
BenchmarkReverse8-8 2.17 1.74 -19.82%
BenchmarkReverse16-8 2.89 2.34 -19.03%
BenchmarkReverse32-8 3.55 2.95 -16.90%
BenchmarkReverse64-8 6.81 5.57 -18.21%
BenchmarkReverseBytes-8 3.49 2.48 -28.94%
BenchmarkReverseBytes16-8 0.93 0.62 -33.33%
BenchmarkReverseBytes32-8 1.55 1.13 -27.10%
BenchmarkReverseBytes64-8 2.47 2.47 +0.00%
Reverse-8 8.50ns ± 0% 6.86ns ± 0% ~ (p=1.000 n=1+1)
Reverse8-8 2.17ns ± 0% 1.74ns ± 0% ~ (p=1.000 n=1+1)
Reverse16-8 2.89ns ± 0% 2.34ns ± 0% ~ (p=1.000 n=1+1)
Reverse32-8 3.55ns ± 0% 2.95ns ± 0% ~ (p=1.000 n=1+1)
Reverse64-8 6.81ns ± 0% 5.57ns ± 0% ~ (p=1.000 n=1+1)
ReverseBytes-8 3.49ns ± 0% 2.48ns ± 0% ~ (p=1.000 n=1+1)
ReverseBytes16-8 0.93ns ± 0% 0.62ns ± 0% ~ (p=1.000 n=1+1)
ReverseBytes32-8 1.55ns ± 0% 1.13ns ± 0% ~ (p=1.000 n=1+1)
ReverseBytes64-8 2.47ns ± 0% 2.47ns ± 0% ~ (all samples are equal)
Change-Id: I0064de8c7e0e568ca7885d6f7064344bef91a06d
Reviewed-on: https://go-review.googlesource.com/37215
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Change-Id: I280c53be455f2fe0474ad577c0f7b7908a4eccb2
Reviewed-on: https://go-review.googlesource.com/36993
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
The tests failed to compile when using the math_big_pure_go tag on
s390x.
Change-Id: I2a09f53ff6562ab9bc9b886cffc0f6205bbfcfbb
Reviewed-on: https://go-review.googlesource.com/36956
Run-TryBot: Michael Munday <munday@ca.ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
The s390x port was based on the ppc64 port and, because of the way the
port was done, inherited some instructions from it. ppc64 supports
3-operand (4-operand for FMADD etc.) floating point instructions
but s390x doesn't (the destination register is always an input) and
so these were emulated.
There is a bug in the emulation of FMADD whereby if the destination
register is also a source for the multiplication it will be
clobbered. This doesn't break any assembly code in the std lib but
could affect future work.
To fix this I have gone through the floating point instructions and
removed all unnecessary 3-/4-operand emulation. The compiler doesn't
need it and assembly writers don't need it, it's just a source of
bugs.
I've also deleted the FNMADD family of emulated instructions. They
aren't used anywhere.
Change-Id: Ic07cedcf141a6a3b43a0c84895460f6cfbf56c04
Reviewed-on: https://go-review.googlesource.com/33350
Run-TryBot: Michael Munday <munday@ca.ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
Unlike the pure go implementation used by every other architecture,
the amd64 asm implementation of Exp does not fail early if the
argument is known to overflow. Make it fail early.
Cost of the check is < 1ns (on an old Sandy Bridge machine):
name old time/op new time/op delta
Exp-4 18.3ns ± 1% 18.7ns ± 1% +2.08% (p=0.000 n=18+20)
Fixes#14932Fixes#18912
Change-Id: I04b3f9b4ee853822cbdc97feade726fbe2907289
Reviewed-on: https://go-review.googlesource.com/36271
Run-TryBot: Alberto Donizetti <alb.donizetti@gmail.com>
Reviewed-by: Russ Cox <rsc@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
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 <rsc@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
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 <rsc@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
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 <minux@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
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 <munday@ca.ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Michael Munday <munday@ca.ibm.com>
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 <gri@golang.org>
Implements Float.Scan which satisfies fmt.Scanner interface.
Also enforces docs' interface implementation claims with compile time
type assertions, that is:
+ Float always implements fmt.Formatter and fmt.Scanner
+ Int always implements fmt.Formatter and fmt.Scanner
+ Rat always implements fmt.Formatter
which will ensure that the API claims are strictly matched.
Also note that Float.Scan doesn't handle ±Inf.
Fixes#17391
Change-Id: I3d3dfbe7f602066975c7a7794fe25b4c645440ce
Reviewed-on: https://go-review.googlesource.com/30723
Reviewed-by: Robert Griesemer <gri@golang.org>
Add special case for Gamma(+∞) which speeds it up:
benchmark old ns/op new ns/op delta
BenchmarkGamma-4 14.5 7.44 -48.69%
The documentation for math.Gamma already specifies it as a special
case:
Gamma(+Inf) = +Inf
The original C code that has been used as the reference implementation
(as mentioned in the comments in gamma.go) also treats Gamma(+∞) as a
special case:
if( x == INFINITY )
return(x);
Change-Id: Idac36e19192b440475aec0796faa2d2c7f8abe0b
Reviewed-on: https://go-review.googlesource.com/31370
Reviewed-by: Robert Griesemer <gri@golang.org>
In addition to the DecimalConversion benchmark, that exercises the
String method of the internal decimal type on a range of small shifts,
add a few benchmarks for the big.Float String method. They can be used
to obtain more realistic data on the real-world performance of
big.Float printing.
Change-Id: I7ada324e7603cb1ce7492ccaf3382db0096223ba
Reviewed-on: https://go-review.googlesource.com/31275
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
This is needed for some of the more complex primality tests
(to filter out exact squares), and while the code is simple the
boundary conditions are not obvious, so it seems worth having
in the library.
Change-Id: Ica994a6b6c1e412a6f6d9c3cf823f9b653c6bcbd
Reviewed-on: https://go-review.googlesource.com/30706
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Inspired by Alberto Donizetti's observations in
https://go-review.googlesource.com/#/c/30099/.
name old time/op new time/op delta
DecimalConversion-8 138µs ± 1% 136µs ± 2% -1.85% (p=0.000 n=10+10)
10 runs each, measured on a Mac Mini, 2.3 GHz Intel Core i7.
Performance improvements varied between -1.25% to -4.4%; -1.85% is
about in the middle of the observed improvement. The generated code
is slightly shorter in the inner loops of the conversion code.
Change-Id: I10fb3b2843da527691c39ad5e5e5bd37ed63e2fa
Reviewed-on: https://go-review.googlesource.com/31250
Reviewed-by: Alan Donovan <adonovan@google.com>
1. Define behavior for Unmarshal of JSON null into Unmarshaler and
TextUnmarshaler. Specifically, an Unmarshaler will be given the
literal null and can decide what to do (because otherwise
json.RawMessage is impossible to implement), and a TextUnmarshaler
will be skipped over (because there is no text to unmarshal), like
most other inappropriate types. Document this in Unmarshal, with a
reminder in UnmarshalJSON about handling null.
2. Test all this.
3. Fix the TextUnmarshaler case, which was returning an unmarshalling
error, to match the definition.
4. Fix the error that had been used for the TextUnmarshaler, since it
was claiming that there was a JSON string when in fact the problem was
NOT having a string.
5. Adjust time.Time and big.Int's UnmarshalJSON to ignore null, as is
conventional.
Fixes#9037.
Change-Id: If78350414eb8dda712867dc8f4ca35a9db041b0c
Reviewed-on: https://go-review.googlesource.com/30944
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
A later CL will be adding more code here.
It will help to keep it separate from the other code.
Change-Id: I971ba53de819cd10991b51fdec665984939a5f9b
Reviewed-on: https://go-review.googlesource.com/30709
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
The Montgomery multiply code is applicable to this case
but was being bypassed. Don't do that.
The old test len(x) > 1 was really just a bad approximation to x > 1.
name old time/op new time/op delta
Exp-8 5.56ms ± 4% 5.73ms ± 3% ~ (p=0.095 n=5+5)
Exp2-8 7.59ms ± 1% 5.66ms ± 1% -25.40% (p=0.008 n=5+5)
This comes up especially when doing Fermat (Miller-Rabin)
primality tests with base 2.
Change-Id: I4cc02978db6dfa93f7f3c8f32718e25eedb4f5ed
Reviewed-on: https://go-review.googlesource.com/30708
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
This way you can still run 'go test' or 'go bench -run Foo'
without wondering why it is taking so very long.
Change-Id: Icfa097a6deb1d6682acb7be9f34729215c29eabb
Reviewed-on: https://go-review.googlesource.com/30707
Reviewed-by: Robert Griesemer <gri@golang.org>
- Add new BenchmarkQuoRem.
- Eliminate allocation in divLarge nat pool
- Unroll mulAddVWW body 4x
- Remove some redundant slice loads in divLarge
name old time/op new time/op delta
QuoRem-8 2.18µs ± 1% 1.93µs ± 1% -11.38% (p=0.000 n=19+18)
The starting point in the comparison here is Cherry's
pending CL to turn mulWW and divWW into intrinsics.
The optimizations in divLarge work best because all
the function calls are gone. The effect of this CL is not
as large if you don't assume Cherry's CL.
Change-Id: Ia6138907489c5b9168497912e43705634e163b35
Reviewed-on: https://go-review.googlesource.com/30613
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
Using 387 mode was computing it without underflow to zero,
apparently due to an 80-bit intermediate. Avoid underflow even
with 64-bit floats.
This eliminates the TODOs in the test suite.
Fixes linux-386-387 build and fixes#11441.
Change-Id: I8abaa63bfdf040438a95625d1cb61042f0302473
Reviewed-on: https://go-review.googlesource.com/30540
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
The 387 implementation is less accurate and slower.
name old time/op new time/op delta
Exp-8 29.7ns ± 2% 24.0ns ± 2% -19.08% (p=0.000 n=10+10)
This makes Gamma more accurate too.
Change-Id: Iad33b9cce0b087ccbce3e08ba7a6d285c4999d02
Reviewed-on: https://go-review.googlesource.com/30230
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Quentin Smith <quentin@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
This adds Uint64 methods to Rand and rngSource.
Rand.Uint64 uses Source.Uint64 directly if it is present.
rngSource.Uint64 provides access to all 64 bits generated by the
underlying ALFG. To ensure high seed quality a 64th bit has been added
to all elements of the array of "cooked" random numbers that are used
for seeding. gen_cooked.go generates both the 63 bit and 64 bit array.
Fixes#4254
Change-Id: I22855618ac69abae3d2799b3e7e59996d4c5a4b1
Reviewed-on: https://go-review.googlesource.com/27253
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
This makes function fit in 16 bytes, saving 16 bytes.
Change-Id: Iac5d2add42f6dae985b2a5cbe19ad4bd4bcc92ec
Reviewed-on: https://go-review.googlesource.com/29151
Run-TryBot: Ilya Tocar <ilya.tocar@intel.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
This adds the instructions frim, frip, and friz to the ppc64x
assembler for use in implementing the math.Floor, math.Ceil, and
math.Trunc functions to improve performance.
Fixes#17185
BenchmarkCeil-128 21.4 6.99 -67.34%
BenchmarkFloor-128 13.9 6.37 -54.17%
BenchmarkTrunc-128 12.7 6.33 -50.16%
Change-Id: I96131bd4e8c9c8dbafb25bfeb544cf9d2dbb4282
Reviewed-on: https://go-review.googlesource.com/29654
Run-TryBot: Lynn Boger <laboger@linux.vnet.ibm.com>
Reviewed-by: Michael Munday <munday@ca.ibm.com>
Also adds the 'find leftmost one' instruction (FLOGR) and replaces the
WORD-encoded use of FLOGR in math/big with it.
Change-Id: I18e7cd19e75b8501a6ae8bd925471f7e37ded206
Reviewed-on: https://go-review.googlesource.com/29372
Reviewed-by: Cherry Zhang <cherryyz@google.com>
Run-TryBot: Michael Munday <munday@ca.ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
No need to test so many sizes in race mode, especially for a package
which doesn't use goroutines.
Reduces test time from 2.5 minutes to 25 seconds.
Updates #17104
Change-Id: I7065b39273f82edece385c0d67b3f2d83d4934b8
Reviewed-on: https://go-review.googlesource.com/29163
Reviewed-by: David Crawshaw <crawshaw@golang.org>
The new SSA backend for s390x can use R0 as a general purpose register.
This change modifies assembly code to either avoid using R0 entirely
or explicitly set R0 to 0.
R0 can still be safely used as 0 in address calculations.
Change-Id: I3efa723e9ef322a91a408bd8c31768d7858526c8
Reviewed-on: https://go-review.googlesource.com/28976
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
1.7 introduced a significant regression compared to 1.6:
SqrtIndirect-4 2.32ns ± 0% 7.86ns ± 0% +238.79% (p=0.000 n=20+18)
This is caused by sqrtsd preserving upper part of destination register.
Which introduces dependency on previous value of X0.
In 1.6 benchmark loop didn't use X0 immediately after call:
callq *%rbx
movsd 0x8(%rsp),%xmm2
movsd 0x20(%rsp),%xmm1
addsd %xmm2,%xmm1
mov 0x18(%rsp),%rax
inc %rax
jmp loop
In 1.7 however xmm0 is used just after call:
callq *%rbx
mov 0x10(%rsp),%rcx
lea 0x1(%rcx),%rax
movsd 0x8(%rsp),%xmm0
movsd 0x18(%rsp),%xmm1
I've verified that this is caused by dependency, by inserting
XORPS X0,X0 in the beginning of math.Sqrt, which puts performance back on 1.6 level.
Splitting SQRTSD mem,reg into:
MOVSD mem,reg
SQRTSD reg,reg
Removes dependency, because MOVSD (load version)
doesn't need to preserve upper part of a register.
And reg,reg operation is solved by renamer in CPU.
As a result of this change regression is gone:
SqrtIndirect-4 7.86ns ± 0% 2.33ns ± 0% -70.36% (p=0.000 n=18+17)
This also removes old Sqrt benchmarks, in favor of benchmarks measuring latency.
Only SqrtIndirect is kept, to show impact of this patch.
Change-Id: Ic7eebe8866445adff5bc38192fa8d64c9a6b8872
Reviewed-on: https://go-review.googlesource.com/28392
Run-TryBot: Ilya Tocar <ilya.tocar@intel.com>
Reviewed-by: Keith Randall <khr@golang.org>
While it was previously explicitly documented that "the default Source"
is safe for concurrent use, a careless reader can interpret that as
meaning "the implementation of the Source interface created by functions
in this package" rather than "the default shared Source used by
top-level functions". Be explicit that the Source returned by NewSource
is not safe for use by multiple goroutines.
Fixes#3611.
Change-Id: Iae4bc04c3887ad6e2491e36e38feda40324022c5
Reviewed-on: https://go-review.googlesource.com/25501
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
The existing implementation used a pure go implementation, leading to slow
cryptographic performance.
Implemented mulWW, subVV, mulAddVWW, addMulVVW, and bitLen for
ppc64{le}.
Implemented divWW for ppc64le only, as the DIVDEU instruction is only
available on Power8 or newer.
benchcmp output:
benchmark old ns/op new ns/op delta
BenchmarkSignP384 28934360 10877330 -62.41%
BenchmarkRSA2048Decrypt 41261033 5139930 -87.54%
BenchmarkRSA2048Sign 45231300 7610985 -83.17%
Benchmark3PrimeRSA2048Decrypt 20487300 2481408 -87.89%
Fixes#16621
Change-Id: If8b68963bb49909bde832f2bda08a3791c4f5b7a
Reviewed-on: https://go-review.googlesource.com/26951
Run-TryBot: Michael Munday <munday@ca.ibm.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Michael Munday <munday@ca.ibm.com>
Add missing function prototypes.
Fix function prototypes.
Use FP references instead of SP references.
Fix variable names.
Update comments.
Clean up whitespace. (Not for vet.)
All fairly minor fixes to make vet happy.
Updates #11041
Change-Id: Ifab2cdf235ff61cdc226ab1d84b8467b5ac9446c
Reviewed-on: https://go-review.googlesource.com/27713
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
The Source provided by math/rand relies on an array of cooked
pseudo-random 63bit integers for seeding. The origin of these
numbers is undocumented.
Add a standalone program in math/rand folder that generates
the 63bit integer array as well as a 64bit version supporting
extension of the Source to 64bit pseudo-random number
generation while maintaining the current sequence in the
lower 63bit.
The code is largely based on the initial implementation of the
random number generator in the go repository by Ken Thompson
(revision 399).
Change-Id: Ib4192aea8127595027116a0f5a7be53f11dc110b
Reviewed-on: https://go-review.googlesource.com/22230
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
There are no synchronization points protecting the readVal and readPos
variables. This leads to a race when Read is called concurrently.
Fix this by adding methods to lockedSource, which is the case where
a race matters.
Fixes#16308.
Change-Id: Ic028909955700906b2d71e5c37c02da21b0f4ad9
Reviewed-on: https://go-review.googlesource.com/24852
Reviewed-by: Joe Tsai <thebrokentoaster@gmail.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Do not throw away the rest of Int63 value used for
generation random bytes. Save it in Rand struct and
re-use during the next Read call.
Fixes#16124
Change-Id: Ic70bd80c3c3a6590e60ac615e8b3c2324589bea3
Reviewed-on: https://go-review.googlesource.com/24251
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Joe Tsai <thebrokentoaster@gmail.com>
Run-TryBot: Joe Tsai <thebrokentoaster@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Fixes#15788
Change-Id: I5a1fd1e5992f1c16cf8d8437d742bf02e1653b9c
Reviewed-on: https://go-review.googlesource.com/23461
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Previously, a 0 mantissa was special-cased during big.Float
parsing, but not during big.Rat parsing. This meant that a value
like 0e9999999999 would parse successfully in big.Float.SetString,
but would hang in big.Rat.SetString. This discrepancy became an
issue in https://golang.org/src/go/constant/value.go?#L250,
where the big.Float would report an exponent of 0, so
big.Rat.SetString would be used and would subsequently hang.
A Go Playground example of this is https://play.golang.org/p/3fy28eUJuF
The solution is to special-case a zero mantissa during big.Rat
parsing as well, so that neither big.Rat nor big.Float will hang when
parsing a value with 0 mantissa but a large exponent.
This was discovered using go-fuzz on CockroachDB:
https://github.com/cockroachdb/go-fuzz/blob/master/examples/parser/main.goFixes#16176
Change-Id: I775558a8682adbeba1cc9d20ba10f8ed26259c56
Reviewed-on: https://go-review.googlesource.com/24430
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
shortens code and gives an example of the use of Run.
Change-Id: I75ffaf762218a589274b4b62e19022e31e805d1b
Reviewed-on: https://go-review.googlesource.com/23424
Reviewed-by: Russ Cox <rsc@golang.org>
Run-TryBot: Marcel van Lohuizen <mpvl@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Document the fact that the default Source uses only
the bottom 31 bits of the given seed.
Fixes#15788
Change-Id: If20d1ec44a55c793a4a0a388f84b9392c2102bd1
Reviewed-on: https://go-review.googlesource.com/23352
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Follow-up to https://golang.org/cl/21755.
This turned out to be a bit more than just a few nits
as originally expected in that CL.
1) The actual mantissa may be shorter than required for the
given precision (because of trailing 0's): no need to
allocate space for it (and transmit 0's). This can save
a lot of space when the precision is high: E.g., for
prec == 1000, 16 words or 128 bytes are required at the
most, but if the actual number is short, it may be much
less (for the test cases present, it's significantly less).
2) The actual mantissa may be longer than the number of
words required for the given precision: make sure to
not overflow when encoding in bytes.
3) Add more documentation.
4) Add more tests.
Change-Id: I9f40c408cfdd9183a8e81076d2f7d6c75e7a00e9
Reviewed-on: https://go-review.googlesource.com/22324
Reviewed-by: Alan Donovan <adonovan@google.com>
Added GobEncode/Decode and a test for them.
Fixes#14593
Change-Id: Ic8d3efd24d0313a1a66f01da293c4c1fd39764a8
Reviewed-on: https://go-review.googlesource.com/21755
Reviewed-by: Robert Griesemer <gri@golang.org>
cmd and runtime were handled separately, and I'm intentionally skipped
syscall. This is the rest of the standard library.
CL generated mechanically with github.com/mdempsky/unconvert.
Change-Id: I9e0eff886974dedc37adb93f602064b83e469122
Reviewed-on: https://go-review.googlesource.com/22104
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Converting a big.Float value x to a float32/64 value did not correctly
round x up to the smallest denormal float32/64 if x was smaller than the
smallest denormal float32/64, but larger than 0.5 of a smallest denormal
float32/64.
Handle this case explicitly and simplify some code in the turn.
For #14651.
Change-Id: I025e24bf8f0e671581a7de0abf7c1cd7e6403a6c
Reviewed-on: https://go-review.googlesource.com/20816
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Alan Donovan <adonovan@google.com>
'b' is a standard verb for floating point values. The runes like '+'
and '#' are called "flags" by package fmt's documentation. The flag
'-' controls left/right justification, not anything related to signs.
Change-Id: Ia9cf81b002df373f274ce635fe09b5bd0066aa1c
Reviewed-on: https://go-review.googlesource.com/20930
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
The existing implementation uses code written in Go to
implement Sqrt; this adds the assembler to use the sqrt
instruction for Power and makes the necessary changes to
allow it to be inlined.
The following tests showed this relative improvement:
benchmark delta
BenchmarkSqrt -97.91%
BenchmarkSqrtIndirect -96.65%
BenchmarkSqrtGo -35.93%
BenchmarkSqrtPrime -96.94%
Fixes#14349
Change-Id: I8074f4dc63486e756587564ceb320aca300bf5fa
Reviewed-on: https://go-review.googlesource.com/19515
Reviewed-by: Minux Ma <minux@golang.org>
Adds a type of output to Examples that allows tests to have unordered
output. This is intended to help clarify when the output of a command
will produce a fixed return, but that return might not be in an constant
order.
Examples where this is useful would be documenting the rand.Perm()
call, or perhaps the (os.File).Readdir(), both of which can not guarantee
order, but can guarantee the elements of the output.
Fixes#10149
Change-Id: Iaf0cf1580b686afebd79718ed67ea744f5ed9fc5
Reviewed-on: https://go-review.googlesource.com/19280
Reviewed-by: Andrew Gerrand <adg@golang.org>
When a big.Float is converted to a denormal float32/64, the rounding
precision depends on the size of the denormal. Rounding may round up
and thus change the size (exponent) of the denormal. Recompute the
correct precision again for correct placement of the mantissa.
Fixes#14553.
Change-Id: Iedab5810a2d2a405cc5da28c6de7be34cb035b86
Reviewed-on: https://go-review.googlesource.com/20198
Reviewed-by: Alan Donovan <adonovan@google.com>
It appears to be a trivial dreg. Unreferenced. Gone.
Change-Id: I4a5ceed48e84254bc8a07fdb04487a18a0edf965
Reviewed-on: https://go-review.googlesource.com/20122
Run-TryBot: Rob Pike <r@golang.org>
Reviewed-by: Dave Cheney <dave@cheney.net>
The tree's pretty inconsistent about single space vs double space
after a period in documentation. Make it consistently a single space,
per earlier decisions. This means contributors won't be confused by
misleading precedence.
This CL doesn't use go/doc to parse. It only addresses // comments.
It was generated with:
$ perl -i -npe 's,^(\s*// .+[a-z]\.) +([A-Z]),$1 $2,' $(git grep -l -E '^\s*//(.+\.) +([A-Z])')
$ go test go/doc -update
Change-Id: Iccdb99c37c797ef1f804a94b22ba5ee4b500c4f7
Reviewed-on: https://go-review.googlesource.com/20022
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Dave Day <djd@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
This is a subset of https://golang.org/cl/20022 with only the copyright
header lines, so the next CL will be smaller and more reviewable.
Go policy has been single space after periods in comments for some time.
The copyright header template at:
https://golang.org/doc/contribute.html#copyright
also uses a single space.
Make them all consistent.
Change-Id: Icc26c6b8495c3820da6b171ca96a74701b4a01b0
Reviewed-on: https://go-review.googlesource.com/20111
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Takes 3% off my all.bash run time.
For #10571.
Change-Id: I8f00f523d6919e87182d35722a669b0b96b8218b
Reviewed-on: https://go-review.googlesource.com/18087
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Also fix bug reported in CL 17510.
Found during fix of #13515 in CL 17672, but separate from the fix.
Change-Id: I4b1024569a98f5cfd2ebb442ec3d64356164d284
Reviewed-on: https://go-review.googlesource.com/17673
Reviewed-by: Robert Griesemer <gri@golang.org>
Replaced code that substituted 0 for rounded-up 1 with
code to try again. This has minimal effect on the existing
stream of random numbers, but restores uniformity.
Fixes#12290.
Change-Id: Ib68f0b0a4a173339bcd0274cc16509f7b0977de8
Reviewed-on: https://go-review.googlesource.com/17670
Reviewed-by: Russ Cox <rsc@golang.org>
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
ˆ (U+02C6) is a circumflex accent, not an exponentiation operator.
In the rest of the source code for this package, exponentation is
written as **, so do the same here.
Change-Id: I107b85be242ab79d152eb8a6fcf3ca2b197d7658
Reviewed-on: https://go-review.googlesource.com/17671
Reviewed-by: Robert Griesemer <gri@golang.org>
Found by github user asukakenji.
Change-Id: I4c76316b69e8a243fb6bf280283f3722e728d853
Reviewed-on: https://go-review.googlesource.com/17641
Reviewed-by: Robert Griesemer <gri@golang.org>
Noticed by cmd/vet.
Expected values array produced by Python instead of Keisan because:
1) Keisan's website calculator is painfully difficult to copy/paste
values into and out of, and
2) after tediously computing e^(vf[i] * 10) - 1 via Keisan I
discovered that Keisan computing vf[i]*10 in a higher precision was
giving substantially different output values.
Also, testing uses "close" instead of "veryclose" because 386's
assembly implementation produces values for some of the test cases
that fail "veryclose". Curiously, Expm1(vf[i]*10) is identical to
Exp(vf[i]*10)-1 on 386, whereas with the portable implementation
they're only "veryclose".
Investigating these questions is left to someone else. I just wanted
to fix the cmd/vet warning.
Fixes#13101.
Change-Id: Ica8f6c267d01aa4cc31f53593e95812746942fbc
Reviewed-on: https://go-review.googlesource.com/16505
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Klaus Post <klauspost@gmail.com>
Reviewed-by: Robert Griesemer <gri@golang.org>
The bug number was a typo, and I forgot to switch the implementation
back to if statements after the change from Float64bits in the first
patchset back to branching.
if statements can currently be inlined, but switch cannot (#13071)
Change-Id: I81d0cf64bda69186c3d747a07047f6a694f8fa70
Reviewed-on: https://go-review.googlesource.com/16446
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
The compiler can do a fine job, and can also inline it.
From Jeremy Jackins's observation and rsc's recommendation in thread:
"Pure Go math.Abs outperforms assembly version"
https://groups.google.com/forum/#!topic/golang-dev/nP5mWvwAXZo
Updates #13095
Change-Id: I3066f8eaa327bb403173b29791cc8661d7c0532c
Reviewed-on: https://go-review.googlesource.com/16444
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Copy math package CL 12230 to cmplx package.
Change-Id: I3345b782b84b5b98e2b6a60d8774c7e7cede2891
Reviewed-on: https://go-review.googlesource.com/15500
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
As akalin points out in the bug, the comment previously claimed that the
probability that the input is prime given that the function returned
true is 1 - ¼ⁿ. But that's wrong: the correct statement is that the
probability of the function returning false given a composite input is
1 - ¼ⁿ.
This is not nearly as helpful, but at least it's truthful. A number of
other (correct) expressions are suggested on the bug, but I think that
the simplier one is preferable.
This change also notes that the function is not suitable for
adversarial inputs since it's deterministic.
Fixes#12274.
Change-Id: I6a0871d103b126ee5a5a922a8c6993055cb7b1ed
Reviewed-on: https://go-review.googlesource.com/14052
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Good enough for now.
Fixes#11241.
Change-Id: Ieb50809f104d20bcbe14daecac503f72486bec92
Reviewed-on: https://go-review.googlesource.com/15111
Reviewed-by: Alan Donovan <adonovan@google.com>
- more uniform naming
- test sign more deliberately
- remove superfluous test (JSON encoder always uses the JSON marshaler if present)
Change-Id: I37b1e367c01fc8bae1e06adbdb72dd366c08d5ce
Reviewed-on: https://go-review.googlesource.com/15110
Reviewed-by: Alan Donovan <adonovan@google.com>
- moved existing package documentation from nat.go to doc.go
- expanded on it
For #11241.
Change-Id: Ie75a2b0178a8904a4154307a1f5080d7efc5489a
Reviewed-on: https://go-review.googlesource.com/15042
Reviewed-by: Alan Donovan <adonovan@google.com>
Like int/rat/float conversions, move this functionality into separate
implementation and test files.
No implementation changes besides the move.
Change-Id: If19c45f5a72a57b95cbce2329724693ae5a4807d
Reviewed-on: https://go-review.googlesource.com/14997
Reviewed-by: Alan Donovan <adonovan@google.com>
- renamed (nat) itoa to utoa (since that's what it is)
- added (nat) itoa that takes a sign parameter; this helps removing a few string copies
- used buffers instead of string+ in Rat conversions
Change-Id: I6b37a6b39557ae311cafdfe5c4a26e9246bde1a9
Reviewed-on: https://go-review.googlesource.com/14995
Reviewed-by: Alan Donovan <adonovan@google.com>
This makes the Int conversion routines match the respective strconv
and big.Float conversion routines.
Change-Id: I5cfcda1632ee52fe87c5bb75892bdda76cc3af15
Reviewed-on: https://go-review.googlesource.com/14994
Reviewed-by: Alan Donovan <adonovan@google.com>
Current result of DecimalConversion benchmark (for future reference):
BenchmarkDecimalConversion-8 10000 204770 ns/op
Measured on Mac Mini (late 2012) running OS X 10.10.5,
2.3 GHz Intel Core i7, 8 GB 1333 MHz DDR3.
Also: Removed comment suggesting to implement decimal by representing
digits as numbers 0..9 rather than ASCII chars '0'..'9' to avoid
repeated +/-'0' operations. Tried and it appears (per above benchmark)
that the +/-'0' operations are neglibile but the addition conversion
passes around it are not and that it makes things significantly slower.
Change-Id: I6ee033b1172043248093cc5d02abff5fc54c2e7a
Reviewed-on: https://go-review.googlesource.com/14857
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Alan Donovan <adonovan@google.com>
Enabled all but a handful of disabled Float formatting test cases.
Fixes#10991.
Change-Id: Id18e160e857be2743429a377000e996978015a1a
Reviewed-on: https://go-review.googlesource.com/14850
Reviewed-by: Alan Donovan <adonovan@google.com>
Instead of computing the final adjustment factor as a power of 10,
it's more efficient to split 10**e into 2**e * 5**e . Powers of 2
are trivially added to the Float exponent, and powers of 5 are
smaller and thus faster to compute.
Also, use a table of uint64 values rather than float64 values for
initial power value. uint64 values appear to be faster to convert
to Floats (useful for small exponents).
Added two small benchmarks to confirm that there's no regresssion.
benchmark old ns/op new ns/op delta
BenchmarkParseFloatSmallExp-8 17543 16220 -7.54%
BenchmarkParseFloatLargeExp-8 60865 59996 -1.43%
Change-Id: I3efd7556b023316f86f334137a67fe0c6d52f8ef
Reviewed-on: https://go-review.googlesource.com/14782
Reviewed-by: Alan Donovan <adonovan@google.com>
Add a Read function to Rand which reads random bytes into a buffer.
Fixes#8330
Change-Id: I85b90277b8be9287c6697def8dbefe0029b6ee06
Reviewed-on: https://go-review.googlesource.com/14522
Reviewed-by: Rob Pike <r@golang.org>
Block comments appear after a block in the HTML documentation generated by
godoc. Words like "following" should be avoided.
Change-Id: Iedfad67f4b8b9c84f128b98b9b06fa76919af388
Reviewed-on: https://go-review.googlesource.com/14357
Reviewed-by: Rob Pike <r@golang.org>
For primes which are 3 mod 4, using Tonelli-Shanks is slower
and more complicated than using the identity
a**((p+1)/4) mod p == sqrt(a)
For 2^450-2^225-1 and 2^10860-2^5430-1, which are 3 mod 4:
BenchmarkModSqrt225_TonelliTri 1000 1135375 ns/op
BenchmarkModSqrt225_3Mod4 10000 156009 ns/op
BenchmarkModSqrt5430_Tonelli 1 3448851386 ns/op
BenchmarkModSqrt5430_3Mod4 2 914616710 ns/op
~2.6x to 7x faster.
Fixes#11437 (which is a prime choice of issues to fix)
Change-Id: I813fb29454160483ec29825469e0370d517850c2
Reviewed-on: https://go-review.googlesource.com/11522
Reviewed-by: Adam Langley <agl@golang.org>
Even though the umul/uquo functions expect two valid, finite big.Floats
arguments, SetString was calling them with possibly Inf values, which
resulted in bogus return values.
Replace umul and udiv calls with Mul and Quo calls to fix this. Also,
fix two wrong tests.
See relevant issue on issue tracker for a detailed explanation.
Fixes#11341
Change-Id: Ie35222763a57a2d712a5f5f7baec75cab8189a53
Reviewed-on: https://go-review.googlesource.com/13778
Reviewed-by: Robert Griesemer <gri@golang.org>
This is not a functional change.
Also:
- minor cleanups, better comments
- uniform spelling of noun "zeros" (per OED)
Fixes#11277.
Change-Id: I1726f358ce15907bd2410f646b02cf8b11b919cd
Reviewed-on: https://go-review.googlesource.com/11267
Reviewed-by: Alan Donovan <adonovan@google.com>
Reviewed-by: Robert Griesemer <gri@golang.org>
Urge users of math/rand to consider using crypto/rand when doing
security-sensitive work.
Related to issue #11871. While we haven't reached consensus on how
to make the package inherently safer, everyone agrees that the docs
for math/rand can be improved.
Change-Id: I576a312e51b2a3445691da6b277c7b4717173197
Reviewed-on: https://go-review.googlesource.com/12900
Reviewed-by: Rob Pike <r@golang.org>
- Make Log2 exact for powers of two.
- Fix error tolerance function to make tolerance
a function of the correct (expected) value.
Fixes#9066.
Change-Id: I0320a93ce4130deed1c7b7685627d51acb7bc56d
Reviewed-on: https://go-review.googlesource.com/12230
Reviewed-by: Ian Lance Taylor <iant@golang.org>
The previous commit (git 2ae77376) just did golang.org. This one
includes golang.org subdomains like blog, play, and build.
Change-Id: I4469f7b307ae2a12ea89323422044e604c5133ae
Reviewed-on: https://go-review.googlesource.com/12071
Reviewed-by: Rob Pike <r@golang.org>
Alberto Donizetti
isharipo
erifan01
Vlad Krasnov
Cherry Zhang
Ilya Tocar
Shawn Smith
Thanabodee Charoenpiriyakij
Paul PISCUC
Brian Kessler
Vladimir Stefanovic
Russ Cox
Daniel Martí
Filippo Valsorda
Tobias Klauser
Lynn Boger
griesemer
Michael Munday
Michael Munday
Mark Pulford
Matthew Dempsky
Marvin Stenger
Agniva De Sarker
Burak Guven
Ian Lance Taylor
Josh Bleecher Snyder
jaredculp
Keith Randall
Lakshay Garg
crvv
Carlos Eduardo Seo
romanyx
Wembley G. Leach, Jr
Than McIntosh
Jelte Fennema
Francesc Campoy Flores
Francesc Campoy
Dylan Waits
Aditya Mukerjee
Martynas Budriūnas
gulyasm
Martin Möhrmann
Bill O'Farrell
Eric Lagergren
Eitan Adler
Alexander Döring
Shenghou Ma
Brad Fitzpatrick
Dmitri Shuralyov
Mohit Agarwal
Emmanuel Odeke
Florian Uekermann
Michal Bohuslávek
David Glasser
Ethan Miller
Dmitri Popov
Konstantin Shaposhnikov
Nathan VanBenschoten
Marcel van Lohuizen
Jeff R. Allen
OneOfOne
Aliaksandr Valialkin
Dominik Honnef
Brady Catherman
Rob Pike
Martin Möhrmann
David Chase
Jingguo Yao
Yao Zhang
Caleb Spare
David Crawshaw
Charlie Dorian
Damian Gryski
Adam Langley
Spencer Nelson
David Leon Gil
Tarmigan Casebolt
Andrey Petrov