Debian Codegraph @

math/math.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 // Sections of the code below, in particular log() and exp(), are based on Go's
5 // implementation, which is, in turn, based on FreeBSD's. The original C code,
6 // as well as the respective comments and constants are from
7 // /usr/src/lib/msun/src/{e_log,e_exp}.c.
8 //
9 // The FreeBSD copyright notice:
10 // ====================================================
11 // Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved.
12 //
13 // Developed at SunPro, a Sun Microsystems, Inc. business.
14 // Permission to use, copy, modify, and distribute this
15 // software is freely granted, provided that this notice
16 // is preserved.
17 // ====================================================
18 //
19 // The Go copyright notice:
20 // ====================================================
21 // Copyright (c) 2009 The Go Authors. All rights reserved.
22 //
23 // Redistribution and use in source and binary forms, with or without
24 // modification, are permitted provided that the following conditions are
25 // met:
26 //
27 // * Redistributions of source code must retain the above copyright
28 // notice, this list of conditions and the following disclaimer.
29 // * Redistributions in binary form must reproduce the above
30 // copyright notice, this list of conditions and the following disclaimer
31 // in the documentation and/or other materials provided with the
32 // distribution.
33 // * Neither the name of Google Inc. nor the names of its
34 // contributors may be used to endorse or promote products derived from
35 // this software without specific prior written permission.
36 //
37 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
38 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
39 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
40 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
41 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
43 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
44 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
45 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
46 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
47 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
48 // ====================================================
49
50 use types;
51
52 // The standard tolerance used by [[isclosef32]] and [[isclosef64]], which is
53 // just an arbitrary way to measure whether two floating-point numbers are
54 // "sufficiently" close to each other.
55 export def STANDARD_TOL = 1e-14;
56
57 // Returns whether x and y are within tol of each other.
58 export fn isclosef64(x: f64, y: f64, tol: f64 = STANDARD_TOL) bool = {
59 if (isnan(x) || isnan(y) || isnan(tol)) {
60 return false;
61 };
62 return absf64(x - y) < tol;
63 };
64
65 // Returns whether x and y are within tol of each other.
66 export fn isclosef32(x: f32, y: f32, tol: f32 = STANDARD_TOL) bool = {
67 if (isnan(x) || isnan(y) || isnan(tol)) {
68 return false;
69 };
70 return absf32(x - y) < tol;
71 };
72
73 // e - https://oeis.org/A001113
74 export def E: f64 = 2.71828182845904523536028747135266249775724709369995957496696763;
75 // pi - https://oeis.org/A000796
76 export def PI: f64 = 3.14159265358979323846264338327950288419716939937510582097494459;
77 // tau - https://oeis.org/A019692
78 export def TAU: f64 = 6.2831853071795864769252867665590057683943387987502116419498892;
79 // phi - https://oeis.org/A001622
80 export def PHI: f64 = 1.61803398874989484820458683436563811772030917980576286213544862;
81 // sqrt(2) - https://oeis.org/A002193
82 export def SQRT_2: f64 = 1.41421356237309504880168872420969807856967187537694807317667974;
83 // sqrt(e) - https://oeis.org/A019774
84 export def SQRT_E: f64 = 1.64872127070012814684865078781416357165377610071014801157507931;
85 // sqrt(pi) - https://oeis.org/A002161
86 export def SQRT_PI: f64 = 1.77245385090551602729816748334114518279754945612238712821380779;
87 // sqrt(phi) - https://oeis.org/A139339
88 export def SQRT_PHI: f64 = 1.27201964951406896425242246173749149171560804184009624861664038;
89 // ln(2) - https://oeis.org/A002162
90 export def LN_2: f64 = 0.693147180559945309417232121458176568075500134360255254120680009;
91 // ln(2) - https://oeis.org/A002162
92 export def LN2_HI: f64 = 6.93147180369123816490e-01;
93 // ln(2) - https://oeis.org/A002162
94 export def LN2_LO: f64 = 1.90821492927058770002e-10;
95 // log_{2}(e)
96 export def LOG2_E: f64 = 1f64 / LN_2;
97 // ln(10) - https://oeis.org/A002392
98 export def LN_10: f64 = 2.30258509299404568401799145468436420760110148862877297603332790;
99 // log_{10}(e)
100 export def LOG10_E: f64 = 1f64 / LN_10;
101
102 // __ieee754_log(x)
103 // Return the logarithm of x
104 //
105 // Method :
106 // 1. Argument Reduction: find k and f such that
107 // x = 2**k * (1+f),
108 // where sqrt(2)/2 < 1+f < sqrt(2) .
109 //
110 // 2. Approximation of log(1+f).
111 // Let s = f/(2+f) ; based on log(1+f) = log(1+s) - log(1-s)
112 // = 2s + 2/3 s**3 + 2/5 s**5 + .....,
113 // = 2s + s*R
114 // We use a special Reme algorithm on [0,0.1716] to generate
115 // a polynomial of degree 14 to approximate R. The maximum error
116 // of this polynomial approximation is bounded by 2**-58.45. In
117 // other words,
118 // 2 4 6 8 10 12 14
119 // R(z) ~ L1*s +L2*s +L3*s +L4*s +L5*s +L6*s +L7*s
120 // (the values of L1 to L7 are listed in the program) and
121 // | 2 14 | -58.45
122 // | L1*s +...+L7*s - R(z) | <= 2
123 // | |
124 // Note that 2s = f - s*f = f - hfsq + s*hfsq, where hfsq = f*f/2.
125 // In order to guarantee error in log below 1ulp, we compute log by
126 // log(1+f) = f - s*(f - R) (if f is not too large)
127 // log(1+f) = f - (hfsq - s*(hfsq+R)). (better accuracy)
128 //
129 // 3. Finally, log(x) = k*Ln2 + log(1+f).
130 // = k*Ln2_hi+(f-(hfsq-(s*(hfsq+R)+k*Ln2_lo)))
131 // Here Ln2 is split into two floating point number:
132 // Ln2_hi + Ln2_lo,
133 // where n*Ln2_hi is always exact for |n| < 2000.
134 //
135 // Special cases:
136 // log(x) is NaN with signal if x < 0 (including -INF) ;
137 // log(+INF) is +INF; log(0) is -INF with signal;
138 // log(NaN) is that NaN with no signal.
139 //
140 // Accuracy:
141 // according to an error analysis, the error is always less than
142 // 1 ulp (unit in the last place).
143 //
144 // Constants:
145 // The hexadecimal values are the intended ones for the following
146 // constants. The decimal values may be used, provided that the
147 // compiler will convert from decimal to binary accurately enough
148 // to produce the hexadecimal values shown.
149
150 // Returns the natural logarithm of x.
151 export fn logf64(x: f64) f64 = {
152 const L1 = 6.666666666666735130e-01; // 3fe55555 55555593
153 const L2 = 3.999999999940941908e-01; // 3fd99999 9997fa04
154 const L3 = 2.857142874366239149e-01; // 3fd24924 94229359
155 const L4 = 2.222219843214978396e-01; // 3fcc71c5 1d8e78af
156 const L5 = 1.818357216161805012e-01; // 3fc74664 96cb03de
157 const L6 = 1.531383769920937332e-01; // 3fc39a09 d078c69f
158 const L7 = 1.479819860511658591e-01; // 3fc2f112 df3e5244
159
160 // special cases
161 if (isnan(x) || x == INF) {
162 return x;
163 } else if (x < 0f64) {
164 return NAN;
165 } else if (x == 0f64) {
166 return -INF;
167 };
168
169 // Reduce
170 const (f1, ki) = frexpf64(x);
171 if (f1 < (SQRT_2 / 2f64)) {
172 f1 *= 2f64;
173 ki -= 1i64;
174 };
175 let f = f1 - 1f64;
176 let k = (ki: f64);
177
178 // Compute
179 const s = f / (2f64 + f);
180 const s2 = s * s;
181 const s4 = s2 * s2;
182 const t1 = s2 * (L1 + s4 * (L3 + s4 * (L5 + s4 * L7)));
183 const t2 = s4 * (L2 + s4 * (L4 + s4 * L6));
184 const R = t1 + t2;
185 const hfsq = 0.5f64 * f * f;
186 return k * LN2_HI - ((hfsq - (s * (hfsq + R) + k * LN2_LO)) - f);
187 };
188
189 // Returns the decimal logarithm of x.
190 export fn log10f64(x: f64) f64 = {
191 return logf64(x) * (1f64 / LN_10);
192 };
193
194 // Returns the binary logarithm of x.
195 export fn log2f64(x: f64) f64 = {
196 const (frac, exp) = frexpf64(x);
197 // Make sure exact powers of two give an exact answer.
198 // Don't depend on log(0.5) * (1 / LN_2) + exp being exactly exp - 1.
199 if (frac == 0.5f64) {
200 return ((exp - 1): f64);
201 };
202 return logf64(frac) * (1f64 / LN_2) + (exp: f64);
203 };
204
205 // double log1p(double x)
206 //
207 // Method :
208 // 1. Argument Reduction: find k and f such that
209 // 1+x = 2**k * (1+f),
210 // where sqrt(2)/2 < 1+f < sqrt(2) .
211 //
212 // Note. If k=0, then f=x is exact. However, if k!=0, then f
213 // may not be representable exactly. In that case, a correction
214 // term is need. Let u=1+x rounded. Let c = (1+x)-u, then
215 // log(1+x) - log(u) ~ c/u. Thus, we proceed to compute log(u),
216 // and add back the correction term c/u.
217 // (Note: when x > 2**53, one can simply return log(x))
218 //
219 // 2. Approximation of log1p(f).
220 // Let s = f/(2+f) ; based on log(1+f) = log(1+s) - log(1-s)
221 // = 2s + 2/3 s**3 + 2/5 s**5 + .....,
222 // = 2s + s*R
223 // We use a special Reme algorithm on [0,0.1716] to generate
224 // a polynomial of degree 14 to approximate R The maximum error
225 // of this polynomial approximation is bounded by 2**-58.45. In
226 // other words,
227 // 2 4 6 8 10 12 14
228 // R(z) ~ LP1*s +LP2*s +LP3*s +LP4*s +LP5*s +LP6*s +LP7*s
229 // (the values of LP1 to LP7 are listed in the program)
230 // and
231 // | 2 14 | -58.45
232 // | LP1*s +...+LP7*s - R(z) | <= 2
233 // | |
234 // Note that 2s = f - s*f = f - hfsq + s*hfsq, where hfsq = f*f/2.
235 // In order to guarantee error in log below 1ulp, we compute log
236 // by
237 // log1p(f) = f - (hfsq - s*(hfsq+R)).
238 //
239 // 3. Finally, log1p(x) = k*ln2 + log1p(f).
240 // = k*ln2_hi+(f-(hfsq-(s*(hfsq+R)+k*ln2_lo)))
241 // Here ln2 is split into two floating point number:
242 // ln2_hi + ln2_lo,
243 // where n*ln2_hi is always exact for |n| < 2000.
244 //
245 // Special cases:
246 // log1p(x) is NaN with signal if x < -1 (including -INF) ;
247 // log1p(+INF) is +INF; log1p(-1) is -INF with signal;
248 // log1p(NaN) is that NaN with no signal.
249 //
250 // Accuracy:
251 // according to an error analysis, the error is always less than
252 // 1 ulp (unit in the last place).
253 //
254 // Constants:
255 // The hexadecimal values are the intended ones for the following
256 // constants. The decimal values may be used, provided that the
257 // compiler will convert from decimal to binary accurately enough
258 // to produce the hexadecimal values shown.
259 //
260 // Note: Assuming log() return accurate answer, the following
261 // algorithm can be used to compute log1p(x) to within a few ULP:
262 //
263 // u = 1+x;
264 // if(u==1.0) return x ; else
265 // return log(u)*(x/(u-1.0));
266 //
267 // See HP-15C Advanced Functions Handbook, p.193.
268
269 // Returns the natural logarithm of 1 plus its argument x.
270 // It is more accurate than log(1 + x) when x is near zero.
271 export fn log1pf64(x: f64) f64 = {
272 // sqrt(2) - 1
273 const SQRT2M1 = 4.142135623730950488017e-01; // 0x3fda827999fcef34
274 // sqrt(2) / 2 - 1
275 const SQRT2HALFM1 = -2.928932188134524755992e-01; // 0xbfd2bec333018866
276 const SMALL = 1f64 / ((1i64 << 29): f64); // 2**-29
277 const TINY = 1f64 / ((1i64 << 54): f64); // 2**-54
278 const TWO53 = ((1i64 << 53): f64); // 2**53
279 const LN2HI = 6.93147180369123816490e-01; // 3fe62e42fee00000
280 const LN2LO = 1.90821492927058770002e-10; // 3dea39ef35793c76
281 const LP1 = 6.666666666666735130e-01; // 3fe5555555555593
282 const LP2 = 3.999999999940941908e-01; // 3fd999999997fa04
283 const LP3 = 2.857142874366239149e-01; // 3fd2492494229359
284 const LP4 = 2.222219843214978396e-01; // 3fcc71c51d8e78af
285 const LP5 = 1.818357216161805012e-01; // 3fc7466496cb03de
286 const LP6 = 1.531383769920937332e-01; // 3fc39a09d078c69f
287 const LP7 = 1.479819860511658591e-01; // 3fc2f112df3e5244
288
289 if (x < -1f64 || isnan(x)) {
290 return NAN;
291 } else if (x == -1f64) {
292 return -INF;
293 } else if (x == INF) {
294 return INF;
295 };
296
297 const absx = absf64(x);
298
299 let f = 0f64;
300 let iu = 0u64;
301 let k = 1i64;
302 if (absx < SQRT2M1) { // |x| < Sqrt(2)-1
303 if (absx < SMALL) { // |x| < 2**-29
304 if (absx < TINY) { // |x| < 2**-54
305 return x;
306 };
307 return x - (x * x * 0.5f64);
308 };
309 if (x > SQRT2HALFM1) { // Sqrt(2)/2-1 < x
310 // (Sqrt(2)/2-1) < x < (Sqrt(2)-1)
311 k = 0;
312 f = x;
313 iu = 1;
314 };
315 };
316 let c = 0f64;
317 if (k != 0) {
318 let u = 0f64;
319 if (absx < TWO53) { // 1<<53
320 u = 1.0 + x;
321 iu = f64bits(u);
322 k = (((iu >> 52) - 1023): i64);
323 // Correction term
324 if (k > 0) {
325 c = 1f64 - (u - x);
326 } else {
327 c = x - (u - 1f64);
328 };
329 c /= u;
330 } else {
331 u = x;
332 iu = f64bits(u);
333 k = (((iu >> 52) - 1023): i64);
334 c = 0f64;
335 };
336 iu &= 0x000fffffffffffff;
337 if (iu < 0x0006a09e667f3bcd) { // Mantissa of Sqrt(2)
338 // Normalize u
339 u = f64frombits(iu | 0x3ff0000000000000);
340 } else {
341 k += 1;
342 // Normalize u/2
343 u = f64frombits(iu | 0x3fe0000000000000);
344 iu = (0x0010000000000000 - iu) >> 2;
345 };
346 f = u - 1f64; // Sqrt(2)/2 < u < Sqrt(2)
347 };
348 const hfsq = 0.5 * f * f;
349 let s = 0f64;
350 let R = 0f64;
351 let z = 0f64;
352 if (iu == 0) { // |f| < 2**-20
353 if (f == 0f64) {
354 if (k == 0) {
355 return 0f64;
356 };
357 c += (k: f64) * LN2LO;
358 return (k: f64) * LN2HI + c;
359 };
360 R = hfsq * (1.0 - 0.66666666666666666 * f); // Avoid division
361 if (k == 0) {
362 return f - R;
363 };
364 return (k: f64) * LN2HI - ((R - ((k: f64) * LN2LO + c)) - f);
365 };
366 s = f / (2f64 + f);
367 z = s * s;
368 R = z * (LP1 +
369 z * (LP2 +
370 z * (LP3 +
371 z * (LP4 +
372 z * (LP5 +
373 z * (LP6 +
374 z * LP7))))));
375 if (k == 0) {
376 return f - (hfsq - s * (hfsq + R));
377 };
378 return (k: f64) * LN2HI -
379 ((hfsq - (s * (hfsq + R) + ((k: f64) * LN2LO + c))) - f);
380 };
381
382 // exp(x)
383 // Returns the exponential of x.
384 //
385 // Method
386 // 1. Argument reduction:
387 // Reduce x to an r so that |r| <= 0.5*ln2 ~ 0.34658.
388 // Given x, find r and integer k such that
389 //
390 // x = k*ln2 + r, |r| <= 0.5*ln2.
391 //
392 // Here r will be represented as r = hi-lo for better
393 // accuracy.
394 //
395 // 2. Approximation of exp(r) by a special rational function on
396 // the interval [0,0.34658]:
397 // Write
398 // R(r**2) = r*(exp(r)+1)/(exp(r)-1) = 2 + r*r/6 - r**4/360 + ...
399 // We use a special Remez algorithm on [0,0.34658] to generate
400 // a polynomial of degree 5 to approximate R. The maximum error
401 // of this polynomial approximation is bounded by 2**-59. In
402 // other words,
403 // R(z) ~ 2.0 + P1*z + P2*z**2 + P3*z**3 + P4*z**4 + P5*z**5
404 // (where z=r*r, and the values of P1 to P5 are listed below)
405 // and
406 // | 5 | -59
407 // | 2.0+P1*z+...+P5*z - R(z) | <= 2
408 // | |
409 // The computation of exp(r) thus becomes
410 // 2*r
411 // exp(r) = 1 + -------
412 // R - r
413 // r*R1(r)
414 // = 1 + r + ----------- (for better accuracy)
415 // 2 - R1(r)
416 // where
417 // 2 4 10
418 // R1(r) = r - (P1*r + P2*r + ... + P5*r ).
419 //
420 // 3. Scale back to obtain exp(x):
421 // From step 1, we have
422 // exp(x) = 2**k * exp(r)
423 //
424 // Special cases:
425 // exp(INF) is INF, exp(NaN) is NaN;
426 // exp(-INF) is 0, and
427 // for finite argument, only exp(0)=1 is exact.
428 //
429 // Accuracy:
430 // according to an error analysis, the error is always less than
431 // 1 ulp (unit in the last place).
432 //
433 // Misc. info.
434 // For IEEE double
435 // if x > 7.09782712893383973096e+02 then exp(x) overflow
436 // if x < -7.45133219101941108420e+02 then exp(x) underflow
437 //
438 // Constants:
439 // The hexadecimal values are the intended ones for the following
440 // constants. The decimal values may be used, provided that the
441 // compiler will convert from decimal to binary accurately enough
442 // to produce the hexadecimal values shown.
443
444 // Returns e^r * 2^k where r = hi - lo and |r| <= (ln(2) / 2).
445 export fn expmultif64(hi: f64, lo: f64, k: i64) f64 = {
446 const P1 = 1.66666666666666657415e-01; // 0x3fc55555; 0x55555555
447 const P2 = -2.77777777770155933842e-03; // 0xbf66c16c; 0X16bebd9n
448 const P3 = 6.61375632143793436117e-05; // 0x3f11566a; 0Xaf25de2c
449 const P4 = -1.65339022054652515390e-06; // 0xbebbbd41; 0Xc5d26bf1
450 const P5 = 4.13813679705723846039e-08; // 0x3e663769; 0X72bea4d0
451
452 let r = hi - lo;
453 let t = r * r;
454 let c = r - t * (P1 + t * (P2 + t * (P3 + t * (P4 + t * P5))));
455 const y = 1f64 - ((lo - (r * c) / (2f64 - c)) - hi);
456 return ldexpf64(y, k);
457 };
458
459 // Returns e^x.
460 export fn expf64(x: f64) f64 = {
461 const overflow = 7.09782712893383973096e+02;
462 const underflow = -7.45133219101941108420e+02;
463 const near_zero = 1f64 / ((1i64 << 28i64): f64);
464
465 if (isnan(x) || x == INF) {
466 return x;
467 } else if (x == -INF) {
468 return 0f64;
469 } else if (x > overflow) {
470 return INF;
471 } else if (x < underflow) {
472 return 0f64;
473 } else if (-near_zero < x && x < near_zero) {
474 return 1f64 + x;
475 };
476
477 // Reduce; computed as r = hi - lo for extra precision.
478 let k = 0i64;
479 if (x < 0f64) {
480 k = (((LOG2_E * x) - 0.5): i64);
481 } else if (x > 0f64) {
482 k = (((LOG2_E * x) + 0.5): i64);
483 };
484 const hi = x - ((k: f64) * LN2_HI);
485 const lo = (k: f64) * LN2_LO;
486
487 // Compute
488 return expmultif64(hi, lo, k);
489 };
490
491 // Returns 2^x.
492 export fn exp2f64(x: f64) f64 = {
493 const overflow = 1.0239999999999999e+03;
494 const underflow = -1.0740e+03;
495
496 if (isnan(x) || x == INF) {
497 return x;
498 } else if (x == -INF) {
499 return 0f64;
500 } else if (x > overflow) {
501 return INF;
502 } else if (x < underflow) {
503 return 0f64;
504 };
505
506 // Argument reduction; x = r×lg(e) + k with |r| ≤ ln(2)/2.
507 // Computed as r = hi - lo for extra precision.
508 let k = 0i64;
509 if (x > 0f64) {
510 k = ((x + 0.5): i64);
511 } else if (x < 0f64) {
512 k = ((x - 0.5): i64);
513 };
514 const t = x - (k: f64);
515 const hi = t * LN2_HI;
516 const lo = -t * LN2_LO;
517
518 // Compute
519 return expmultif64(hi, lo, k);
520 };
521
522 // __ieee754_sqrt(x)
523 // Return correctly rounded sqrt.
524 // -----------------------------------------
525 // | Use the hardware sqrt if you have one |
526 // -----------------------------------------
527 // Method:
528 // Bit by bit method using integer arithmetic. (Slow, but portable)
529 // 1. Normalization
530 // Scale x to y in [1,4) with even powers of 2:
531 // find an integer k such that 1 <= (y=x*2**(2k)) < 4, then
532 // sqrt(x) = 2**k * sqrt(y)
533 // 2. Bit by bit computation
534 // Let q = sqrt(y) truncated to i bit after binary point (q = 1),
535 // i 0
536 // i+1 2
537 // s = 2*q , and y = 2 * ( y - q ). (1)
538 // i i i i
539 //
540 // To compute q from q , one checks whether
541 // i+1 i
542 //
543 // -(i+1) 2
544 // (q + 2 ) <= y. (2)
545 // i
546 // -(i+1)
547 // If (2) is false, then q = q ; otherwise q = q + 2 .
548 // i+1 i i+1 i
549 //
550 // With some algebraic manipulation, it is not difficult to see
551 // that (2) is equivalent to
552 // -(i+1)
553 // s + 2 <= y (3)
554 // i i
555 //
556 // The advantage of (3) is that s and y can be computed by
557 // i i
558 // the following recurrence formula:
559 // if (3) is false
560 //
561 // s = s , y = y ; (4)
562 // i+1 i i+1 i
563 //
564 // otherwise,
565 // -i -(i+1)
566 // s = s + 2 , y = y - s - 2 (5)
567 // i+1 i i+1 i i
568 //
569 // One may easily use induction to prove (4) and (5).
570 // Note. Since the left hand side of (3) contain only i+2 bits,
571 // it is not necessary to do a full (53-bit) comparison
572 // in (3).
573 // 3. Final rounding
574 // After generating the 53 bits result, we compute one more bit.
575 // Together with the remainder, we can decide whether the
576 // result is exact, bigger than 1/2ulp, or less than 1/2ulp
577 // (it will never equal to 1/2ulp).
578 // The rounding mode can be detected by checking whether
579 // huge + tiny is equal to huge, and whether huge - tiny is
580 // equal to huge for some floating point number "huge" and "tiny".
581
582 // Returns the square root of x.
583 export fn sqrtf64(x: f64) f64 = {
584 if (x == 0f64) {
585 return x;
586 } else if (isnan(x) || x == INF) {
587 return x;
588 } else if (x < 0f64) {
589 return NAN;
590 };
591
592 let bits = f64bits(x);
593
594 // Normalize x
595 let exp = (((bits >> F64_MANTISSA_BITS) & F64_EXPONENT_MASK): i64);
596 if (exp == 0i64) {
597 // Subnormal x
598 for (bits & (1 << F64_MANTISSA_BITS) == 0) {
599 bits <<= 1;
600 exp -= 1;
601 };
602 exp += 1;
603 };
604 // Unbias exponent
605 exp -= (F64_EXPONENT_BIAS: i64);
606 bits = bits & ~(F64_EXPONENT_MASK << F64_MANTISSA_BITS);
607 bits = bits | (1u64 << (F64_MANTISSA_BITS: u64));
608 // Odd exp, double x to make it even
609 if (exp & 1i64 == 1i64) {
610 bits <<= 1;
611 };
612 // exp = exp/2, exponent of square root
613 exp >>= 1;
614 // Generate sqrt(x) bit by bit
615 bits <<= 1;
616 // q = sqrt(x)
617 let q = 0u64;
618 let s = 0u64;
619 // r = moving bit from MSB to LSB
620 let r = ((1u64 << (F64_MANTISSA_BITS + 1u64)): u64);
621 for (r != 0) {
622 const t = s + r;
623 if (t <= bits) {
624 s = t + r;
625 bits -= t;
626 q += r;
627 };
628 bits <<= 1u64;
629 r >>= 1u64;
630 };
631 // Final rounding
632 if (bits != 0) {
633 // Remainder, result not exact
634 // Round according to extra bit
635 q += q & 1;
636 };
637 // significand + biased exponent
638 bits = (q >> 1) + (
639 ((exp - 1i64 + (F64_EXPONENT_BIAS: i64)): u64) <<
640 F64_MANTISSA_BITS);
641 return f64frombits(bits);
642 };
643
644 fn is_f64_odd_int(x: f64) bool = {
645 const (x_int, x_frac) = modfracf64(x);
646 const has_no_frac = (x_frac == 0f64);
647 const is_odd = ((x_int: i64 & 1i64) == 1i64);
648 return has_no_frac && is_odd;
649 };
650
651 // Returns x^p.
652 export fn powf64(x: f64, p: f64) f64 = {
653 if (x == 1f64 || p == 0f64) {
654 return 1f64;
655 } else if (p == 1f64) {
656 return x;
657 } else if (isnan(x)) {
658 return NAN;
659 } else if (isnan(p)) {
660 return NAN;
661 } else if (x == 0f64) {
662 if (p < 0f64) {
663 if (is_f64_odd_int(p)) {
664 return copysignf64(INF, x);
665 } else {
666 return INF;
667 };
668 } else if (p > 0f64) {
669 if (is_f64_odd_int(p)) {
670 return x;
671 } else {
672 return 0f64;
673 };
674 };
675 } else if (isinf(p)) {
676 if (x == -1f64) {
677 return 1f64;
678 } else if ((absf64(x) < 1f64) == (p == INF)) {
679 return 0f64;
680 };
681 return INF;
682 } else if (isinf(x)) {
683 if (x == -INF) {
684 return powf64(-0f64, -p);
685 } else if (p < 0f64) {
686 return 0f64;
687 } else if (p > 0f64) {
688 return INF;
689 };
690 } else if (p == 0.5f64) {
691 return sqrtf64(x);
692 } else if (p == -0.5f64) {
693 return 1f64 / sqrtf64(x);
694 };
695
696 let (p_int, p_frac) = modfracf64(absf64(p));
697 if (p_frac != 0f64 && x < 0f64) {
698 return NAN;
699 };
700 if (p_int > types::I64_MAX: f64) {
701 if (x == -1f64) {
702 return 1f64;
703 } else if ((absf64(x) < 1f64) == (p > 0f64)) {
704 return 0f64;
705 } else {
706 return INF;
707 };
708 };
709
710 let res_mantissa = 1f64;
711 let res_exp = 0i64;
712
713 // The method used later in this function doesn't apply to fractional
714 // powers, so we have to handle these separately with
715 // x^p = e^{p * ln(x)}
716 if (p_frac != 0f64) {
717 if (p_frac > 0.5f64) {
718 p_frac -= 1f64;
719 p_int += 1f64;
720 };
721 res_mantissa = expf64(p_frac * logf64(x));
722 };
723
724 // Repeatedly square our number x, for each bit in our power p.
725 // If the current bit is 1 in p, add the respective power of x to our
726 // result.
727 let (x_mantissa, x_exp) = frexpf64(x);
728 for (let i = p_int: i64; i != 0; i >>= 1) {
729 // Check for over/underflow.
730 if (x_exp <= -1i64 << (F64_EXPONENT_BITS: i64)) {
731 return 0f64;
732 };
733 if (x_exp >= 1i64 << (F64_EXPONENT_BITS: i64)) {
734 return INF;
735 };
736 // Perform squaring.
737 if (i & 1i64 == 1i64) {
738 res_mantissa *= x_mantissa;
739 res_exp += x_exp;
740 };
741 x_mantissa *= x_mantissa;
742 x_exp <<= 1;
743 // Correct mantisa to be in [0.5, 1).
744 if (x_mantissa < 0.5f64) {
745 x_mantissa += x_mantissa;
746 x_exp -= 1;
747 };
748 };
749
750 if (p < 0f64) {
751 res_mantissa = 1f64 / res_mantissa;
752 res_exp = -res_exp;
753 };
754
755 return ldexpf64(res_mantissa, res_exp);
756 };
757
758 // Returns the greatest integer value less than or equal to x.
759 export fn floorf64(x: f64) f64 = {
760 if (x == 0f64 || isnan(x) || isinf(x)) {
761 return x;
762 };
763 if (x < 0f64) {
764 let (int_part, frac_part) = modfracf64(-x);
765 if (frac_part != 0f64) {
766 int_part += 1f64;
767 };
768 return -int_part;
769 };
770 return modfracf64(x).0;
771 };
772
773 // Returns the least integer value greater than or equal to x.
774 export fn ceilf64(x: f64) f64 = -floorf64(-x);
775
776 // Returns the integer value of x.
777 export fn truncf64(x: f64) f64 = {
778 if (x == 0f64 || isnan(x) || isinf(x)) {
779 return x;
780 };
781 return modfracf64(x).0;
782 };
783
784 // Returns the nearest integer, rounding half away from zero.
785 export fn roundf64(x: f64) f64 = {
786 let bits = f64bits(x);
787 let e = (bits >> F64_MANTISSA_BITS) & F64_EXPONENT_MASK;
788 if (e < F64_EXPONENT_BIAS) {
789 // Round abs(x) < 1 including denormals.
790 bits &= F64_SIGN_MASK; // +-0
791 if (e == F64_EXPONENT_BIAS - 1) {
792 bits |= F64_ONE; // +-1
793 };
794 } else if (e < F64_EXPONENT_BIAS + F64_MANTISSA_BITS) {
795 // Round any abs(x) >= 1 containing a fractional component
796 // [0,1).
797 // Numbers with larger exponents are returned unchanged since
798 // they must be either an integer, infinity, or NaN.
799 const half = 1u64 << (F64_MANTISSA_BITS - 1);
800 e -= F64_EXPONENT_BIAS;
801 bits += half >> e;
802 bits = bits & ~(F64_MANTISSA_MASK >> e);
803 };
804 return f64frombits(bits);
805 };
806
807 // Returns the floating-point remainder of x / y. The magnitude of the result
808 // is less than y and its sign agrees with that of x.
809 export fn modf64(x: f64, y: f64) f64 = {
810 if (y == 0f64) {
811 return NAN;
812 };
813 if (isinf(x) || isnan(x) || isnan(y)) {
814 return NAN;
815 };
816
817 y = absf64(y);
818
819 const (y_frac, y_exp) = frexpf64(y);
820 let r = x;
821 if (x < 0f64) {
822 r = -x;
823 };
824
825 for (r >= y) {
826 const (r_frac, r_exp) = frexpf64(r);
827 if (r_frac < y_frac) {
828 r_exp -= 1i64;
829 };
830 r = r - ldexpf64(y, r_exp - y_exp);
831 };
832 if (x < 0f64) {
833 r = -r;
834 };
835 return r;
836 };