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