Source file src/pkg/math/trig_reduce.go

     1	// Copyright 2018 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	package math
     6	
     7	import (
     8		"math/bits"
     9	)
    10	
    11	// reduceThreshold is the maximum value where the reduction using Pi/4
    12	// in 3 float64 parts still gives accurate results.  Above this
    13	// threshold Payne-Hanek range reduction must be used.
    14	const reduceThreshold = (1 << 52) / (4 / Pi)
    15	
    16	// trigReduce implements Payne-Hanek range reduction by Pi/4
    17	// for x > 0.  It returns the integer part mod 8 (j) and
    18	// the fractional part (z) of x / (Pi/4).
    19	// The implementation is based on:
    20	// "ARGUMENT REDUCTION FOR HUGE ARGUMENTS: Good to the Last Bit"
    21	// K. C. Ng et al, March 24, 1992
    22	// The simulated multi-precision calculation of x*B uses 64-bit integer arithmetic.
    23	func trigReduce(x float64) (j uint64, z float64) {
    24		const PI4 = Pi / 4
    25		if x < PI4 {
    26			return 0, x
    27		}
    28		// Extract out the integer and exponent such that,
    29		// x = ix * 2 ** exp.
    30		ix := Float64bits(x)
    31		exp := int(ix>>shift&mask) - bias - shift
    32		ix &^= mask << shift
    33		ix |= 1 << shift
    34		// Use the exponent to extract the 3 appropriate uint64 digits from mPi4,
    35		// B ~ (z0, z1, z2), such that the product leading digit has the exponent -61.
    36		// Note, exp >= -53 since x >= PI4 and exp < 971 for maximum float64.
    37		digit, bitshift := uint(exp+61)/64, uint(exp+61)%64
    38		z0 := (mPi4[digit] << bitshift) | (mPi4[digit+1] >> (64 - bitshift))
    39		z1 := (mPi4[digit+1] << bitshift) | (mPi4[digit+2] >> (64 - bitshift))
    40		z2 := (mPi4[digit+2] << bitshift) | (mPi4[digit+3] >> (64 - bitshift))
    41		// Multiply mantissa by the digits and extract the upper two digits (hi, lo).
    42		z2hi, _ := bits.Mul64(z2, ix)
    43		z1hi, z1lo := bits.Mul64(z1, ix)
    44		z0lo := z0 * ix
    45		lo, c := bits.Add64(z1lo, z2hi, 0)
    46		hi, _ := bits.Add64(z0lo, z1hi, c)
    47		// The top 3 bits are j.
    48		j = hi >> 61
    49		// Extract the fraction and find its magnitude.
    50		hi = hi<<3 | lo>>61
    51		lz := uint(bits.LeadingZeros64(hi))
    52		e := uint64(bias - (lz + 1))
    53		// Clear implicit mantissa bit and shift into place.
    54		hi = (hi << (lz + 1)) | (lo >> (64 - (lz + 1)))
    55		hi >>= 64 - shift
    56		// Include the exponent and convert to a float.
    57		hi |= e << shift
    58		z = Float64frombits(hi)
    59		// Map zeros to origin.
    60		if j&1 == 1 {
    61			j++
    62			j &= 7
    63			z--
    64		}
    65		// Multiply the fractional part by pi/4.
    66		return j, z * PI4
    67	}
    68	
    69	// mPi4 is the binary digits of 4/pi as a uint64 array,
    70	// that is, 4/pi = Sum mPi4[i]*2^(-64*i)
    71	// 19 64-bit digits and the leading one bit give 1217 bits
    72	// of precision to handle the largest possible float64 exponent.
    73	var mPi4 = [...]uint64{
    74		0x0000000000000001,
    75		0x45f306dc9c882a53,
    76		0xf84eafa3ea69bb81,
    77		0xb6c52b3278872083,
    78		0xfca2c757bd778ac3,
    79		0x6e48dc74849ba5c0,
    80		0x0c925dd413a32439,
    81		0xfc3bd63962534e7d,
    82		0xd1046bea5d768909,
    83		0xd338e04d68befc82,
    84		0x7323ac7306a673e9,
    85		0x3908bf177bf25076,
    86		0x3ff12fffbc0b301f,
    87		0xde5e2316b414da3e,
    88		0xda6cfd9e4f96136e,
    89		0x9e8c7ecd3cbfd45a,
    90		0xea4f758fd7cbe2f6,
    91		0x7a0e73ef14a525d4,
    92		0xd7f6bf623f1aba10,
    93		0xac06608df8f6d757,
    94	}
    95	

View as plain text