codekingpro/portable-devtools

1// Copyright 2018 The Go Authors. All rights reserved.2// Use of this source code is governed by a BSD-style3// license that can be found in the LICENSE file.4 5package math6 7import (8	"math/bits"9)10 11// reduceThreshold is the maximum value of x where the reduction using Pi/412// in 3 float64 parts still gives accurate results. This threshold13// is set by y*C being representable as a float64 without error14// where y is given by y = floor(x * (4 / Pi)) and C is the leading partial15// terms of 4/Pi. Since the leading terms (PI4A and PI4B in sin.go) have 3016// and 32 trailing zero bits, y should have less than 30 significant bits.17//18//	y < 1<<30  -> floor(x*4/Pi) < 1<<30 -> x < (1<<30 - 1) * Pi/419//20// So, conservatively we can take x < 1<<29.21// Above this threshold Payne-Hanek range reduction must be used.22const reduceThreshold = 1 << 2923 24// trigReduce implements Payne-Hanek range reduction by Pi/425// for x > 0. It returns the integer part mod 8 (j) and26// the fractional part (z) of x / (Pi/4).27// The implementation is based on:28// "ARGUMENT REDUCTION FOR HUGE ARGUMENTS: Good to the Last Bit"29// K. C. Ng et al, March 24, 199230// The simulated multi-precision calculation of x*B uses 64-bit integer arithmetic.31func trigReduce(x float64) (j uint64, z float64) {32	const PI4 = Pi / 433	if x < PI4 {34		return 0, x35	}36	// Extract out the integer and exponent such that,37	// x = ix * 2 ** exp.38	ix := Float64bits(x)39	exp := int(ix>>shift&mask) - bias - shift40	ix &^= mask << shift41	ix |= 1 << shift42	// Use the exponent to extract the 3 appropriate uint64 digits from mPi4,43	// B ~ (z0, z1, z2), such that the product leading digit has the exponent -61.44	// Note, exp >= -53 since x >= PI4 and exp < 971 for maximum float64.45	digit, bitshift := uint(exp+61)/64, uint(exp+61)%6446	z0 := (mPi4[digit] << bitshift) | (mPi4[digit+1] >> (64 - bitshift))47	z1 := (mPi4[digit+1] << bitshift) | (mPi4[digit+2] >> (64 - bitshift))48	z2 := (mPi4[digit+2] << bitshift) | (mPi4[digit+3] >> (64 - bitshift))49	// Multiply mantissa by the digits and extract the upper two digits (hi, lo).50	z2hi, _ := bits.Mul64(z2, ix)51	z1hi, z1lo := bits.Mul64(z1, ix)52	z0lo := z0 * ix53	lo, c := bits.Add64(z1lo, z2hi, 0)54	hi, _ := bits.Add64(z0lo, z1hi, c)55	// The top 3 bits are j.56	j = hi >> 6157	// Extract the fraction and find its magnitude.58	hi = hi<<3 | lo>>6159	lz := uint(bits.LeadingZeros64(hi))60	e := uint64(bias - (lz + 1))61	// Clear implicit mantissa bit and shift into place.62	hi = (hi << (lz + 1)) | (lo >> (64 - (lz + 1)))63	hi >>= 64 - shift64	// Include the exponent and convert to a float.65	hi |= e << shift66	z = Float64frombits(hi)67	// Map zeros to origin.68	if j&1 == 1 {69		j++70		j &= 771		z--72	}73	// Multiply the fractional part by pi/4.74	return j, z * PI475}76 77// mPi4 is the binary digits of 4/pi as a uint64 array,78// that is, 4/pi = Sum mPi4[i]*2^(-64*i)79// 19 64-bit digits and the leading one bit give 1217 bits80// of precision to handle the largest possible float64 exponent.81var mPi4 = [...]uint64{82	0x0000000000000001,83	0x45f306dc9c882a53,84	0xf84eafa3ea69bb81,85	0xb6c52b3278872083,86	0xfca2c757bd778ac3,87	0x6e48dc74849ba5c0,88	0x0c925dd413a32439,89	0xfc3bd63962534e7d,90	0xd1046bea5d768909,91	0xd338e04d68befc82,92	0x7323ac7306a673e9,93	0x3908bf177bf25076,94	0x3ff12fffbc0b301f,95	0xde5e2316b414da3e,96	0xda6cfd9e4f96136e,97	0x9e8c7ecd3cbfd45a,98	0xea4f758fd7cbe2f6,99	0x7a0e73ef14a525d4,100	0xd7f6bf623f1aba10,101	0xac06608df8f6d757,102}103