1 ! Copyright (C) 2004, 2010 Slava Pestov.
2 ! See https://factorcode.org/license.txt for BSD license.
3 USING: combinators kernel kernel.private math math.bits
4 math.constants math.libm math.order math.private sequences
8 GENERIC: sqrt ( x -- y ) foldable
12 [ neg fsqrt [ 0.0 ] dip rect> ] [ fsqrt ] if ; inline
14 : factor-2s ( n -- r s )
15 ! factor an integer into 2^r * s
17 [ 0 ] dip [ dup even? ] [ [ 1 + ] [ 2/ ] bi* ] while
22 : (^fixnum) ( z w -- z^w )
26 [ [ * ] keep ] [ 1 - ] bi*
27 ] when [ sq ] [ 2/ ] bi*
28 ] until 2drop ; inline
30 : (^bignum) ( z w -- z^w )
31 make-bits 1 [ [ over * ] when [ sq ] dip ] reduce nip ; inline
34 dup fixnum? [ (^fixnum) ] [ (^bignum) ] if ; inline
36 GENERIC#: ^n 1 ( z w -- z^w ) foldable
41 [ factor-2s ] dip [ (^n) ] keep rot * shift ;
44 [ >fraction ] dip '[ _ ^n ] bi@ / ;
46 M: float ^n [ >float fpow ] unless-zero ;
50 : ^integer ( x y -- z )
51 dup 0 >= [ ^n ] [ [ recip ] dip neg ^n ] if ; inline
55 : >float-rect ( z -- x y )
56 >rect [ >float ] bi@ ; inline
58 : >polar ( z -- abs arg )
59 >float-rect [ [ sq ] bi@ + fsqrt ] [ swap fatan2 ] 2bi ; inline
61 : cis ( arg -- z ) >float [ fcos ] [ fsin ] bi rect> ; inline
63 : polar> ( abs arg -- z ) cis * ; inline
65 GENERIC: e^ ( x -- e^x )
67 M: float e^ fexp ; inline
69 M: real e^ >float e^ ; inline
71 M: complex e^ >rect [ e^ ] dip polar> ; inline
75 : ^mag ( w abs arg -- magnitude )
77 [ >float swap >float fpow ]
81 : ^theta ( w abs arg -- theta )
82 [ >float-rect ] [ flog * swap ] [ * + ] tri* ; inline
84 : ^complex ( x y -- z )
85 swap >polar [ ^mag ] [ ^theta ] 3bi polar> ; inline
88 2dup [ real? ] both? [ drop 0 >= ] [ 2drop f ] if ; inline
91 swap [ 0/0. ] swap '[ 0 < 1/0. _ ? ] if-zero ; inline
93 : (^mod) ( x y n -- z )
94 [ make-bits 1 ] dip dup
95 '[ [ over * _ mod ] when [ sq _ mod ] dip ] reduce nip ; inline
101 { [ over zero? ] [ 0^ ] }
102 { [ dup integer? ] [ ^integer ] }
103 { [ 2dup real^? ] [ [ >float ] bi@ fpow ] }
107 : nth-root ( n x -- y ) swap recip ^ ; inline
109 : divisor? ( m n -- ? ) mod zero? ; inline
111 ERROR: non-trivial-divisor n ;
113 : mod-inv ( x n -- y )
114 [ nip ] [ gcd 1 = ] 2bi
115 [ dup 0 < [ + ] [ nip ] if ]
116 [ non-trivial-divisor ] if ; foldable
118 : ^mod ( x y n -- z )
120 [ [ [ neg ] dip ^mod ] keep mod-inv ] [ (^mod) ] if ; foldable
122 GENERIC: absq ( x -- y ) foldable
124 M: real absq sq ; inline
126 : ~abs ( x y epsilon -- ? )
129 : ~rel ( x y epsilon -- ? )
130 [ [ - abs ] 2keep [ abs ] bi@ + ] dip * <= ;
132 : ~ ( x y epsilon -- ? )
134 { [ dup zero? ] [ drop number= ] }
135 { [ dup 0 < ] [ neg ~rel ] }
139 : conjugate ( z -- z* ) >rect neg rect> ; inline
141 : arg ( z -- arg ) >float-rect swap fatan2 ; inline
144 dup complex? [ drop f ] [ abs 1 <= ] if ; inline
147 dup complex? [ drop f ] [ 1 >= ] if ; inline
149 GENERIC: frexp ( x -- y exp )
152 dup fp-special? [ dup zero? ] unless* [ 0 ] [
154 [ 0x800f,ffff,ffff,ffff bitand 0.5 double>bits bitor bits>double ]
155 [ -52 shift 0x7ff bitand 1022 - ] bi
160 dup 0 > [ 1 ] [ abs -1 ] if swap dup log2 [
161 52 swap - shift 0x000f,ffff,ffff,ffff bitand
162 0.5 double>bits bitor bits>double
163 ] [ 1 + ] bi [ * ] dip
168 GENERIC#: ldexp 1 ( x exp -- y )
171 over fp-special? [ over zero? ] unless* [ drop ] [
172 [ double>bits dup -52 shift 0x7ff bitand 1023 - ] dip +
174 { [ dup -1074 < ] [ drop 0 copysign ] }
175 { [ dup 1023 > ] [ drop 0 < -1/0. 1/0. ? ] }
177 dup -1022 < [ 52 + -52 2^ ] [ 1 ] if
178 [ -0x7ff0,0000,0000,0001 bitand ]
179 [ 1023 + 52 shift bitor bits>double ]
186 2dup [ zero? ] either? [ 2drop 0 ] [ shift ] if ;
188 GENERIC: log ( x -- y )
190 M: float log dup 0.0 >= [ flog ] [ 0.0 rect> log ] if ; inline
192 M: real log >float log ; inline
194 M: complex log >polar [ flog ] dip rect> ; inline
196 : logn ( x n -- y ) [ log ] bi@ / ;
198 GENERIC: lgamma ( x -- y )
200 M: float lgamma flgamma ;
202 M: real lgamma >float lgamma ;
206 : most-negative-finite-float ( -- x )
207 -0x1.ffff,ffff,ffff,fp1023 >integer ; inline
209 : most-positive-finite-float ( -- x )
210 0x1.ffff,ffff,ffff,fp1023 >integer ; inline
212 CONSTANT: log-2 0x1.62e42fefa39efp-1
213 CONSTANT: log10-2 0x1.34413509f79ffp-2
215 : representable-as-float? ( x -- ? )
216 most-negative-finite-float
217 most-positive-finite-float between? ; inline
219 : (bignum-log) ( n log-quot: ( x -- y ) log-2 -- log )
221 dup representable-as-float?
222 [ >float @ ] [ frexp _ [ _ * ] bi* + ] if
227 M: bignum log [ log ] log-2 (bignum-log) ;
229 GENERIC: log1+ ( x -- y )
231 M: object log1+ 1 + log ; inline
233 M: float log1+ dup -1.0 >= [ flog1+ ] [ 1.0 + 0.0 rect> log ] if ; inline
235 : 10^ ( x -- 10^x ) 10 swap ^ ; inline
237 GENERIC: log10 ( x -- y ) foldable
239 M: real log10 >float flog10 ; inline
241 M: complex log10 log 10 log / ; inline
243 M: bignum log10 [ log10 ] log10-2 (bignum-log) ;
245 GENERIC: e^-1 ( x -- e^x-1 )
252 [ 1.0 - * ] [ log / ] bi
254 ] [ e^ 1.0 - ] if ; inline
256 M: real e^-1 >float e^-1 ; inline
258 GENERIC: cos ( x -- y ) foldable
262 [ [ fcos ] [ fcosh ] bi* * ]
263 [ [ fsin neg ] [ fsinh ] bi* * ] 2bi rect> ;
265 M: float cos fcos ; inline
267 M: real cos >float cos ; inline
269 : sec ( x -- y ) cos recip ; inline
271 GENERIC: cosh ( x -- y ) foldable
275 [ [ fcosh ] [ fcos ] bi* * ]
276 [ [ fsinh ] [ fsin ] bi* * ] 2bi rect> ;
278 M: float cosh fcosh ; inline
280 M: real cosh >float cosh ; inline
282 : sech ( x -- y ) cosh recip ; inline
284 GENERIC: sin ( x -- y ) foldable
288 [ [ fsin ] [ fcosh ] bi* * ]
289 [ [ fcos ] [ fsinh ] bi* * ] 2bi rect> ;
291 M: float sin fsin ; inline
293 M: real sin >float sin ; inline
295 : cosec ( x -- y ) sin recip ; inline
297 GENERIC: sinh ( x -- y ) foldable
301 [ [ fsinh ] [ fcos ] bi* * ]
302 [ [ fcosh ] [ fsin ] bi* * ] 2bi rect> ;
304 M: float sinh fsinh ; inline
306 M: real sinh >float sinh ; inline
308 : cosech ( x -- y ) sinh recip ; inline
310 GENERIC: tan ( x -- y ) foldable
312 M: complex tan [ sin ] [ cos ] bi / ;
314 M: float tan ftan ; inline
316 M: real tan >float tan ; inline
318 GENERIC: tanh ( x -- y ) foldable
320 M: complex tanh [ sinh ] [ cosh ] bi / ;
322 M: float tanh ftanh ; inline
324 M: real tanh >float tanh ; inline
326 : cot ( x -- y ) tan recip ; inline
328 : coth ( x -- y ) tanh recip ; inline
331 dup sq 1 - sqrt + log ; inline
333 : asech ( x -- y ) recip acosh ; inline
336 dup sq 1 + sqrt + log ; inline
338 : acosech ( x -- y ) recip asinh ; inline
341 [ 1 + ] [ 1 - neg ] bi / log 2 / ; inline
343 : acoth ( x -- y ) recip atanh ; inline
345 : i* ( x -- y ) >rect neg swap rect> ;
347 : -i* ( x -- y ) >rect swap neg rect> ;
350 dup [-1,1]? [ >float fasin ] [ i* asinh -i* ] if ; inline
353 dup [-1,1]? [ >float facos ] [ asin pi 2 / swap - ] if ; inline
355 GENERIC: atan ( x -- y ) foldable
357 M: complex atan i* atanh i* ; inline
359 M: float atan fatan ; inline
361 M: real atan >float atan ; inline
363 : asec ( x -- y ) recip acos ; inline
365 : acosec ( x -- y ) recip asin ; inline
367 : acot ( x -- y ) recip atan ; inline
369 : deg>rad ( x -- y ) pi * 180 / ; inline
371 : rad>deg ( x -- y ) 180 * pi / ; inline
373 GENERIC: truncate ( x -- y )
375 M: real truncate dup 1 mod - ;
379 dup -52 shift 0x7ff bitand 0x3ff -
380 ! check for floats without fractional part (>= 2^52)
384 ! the float is between -1.0 and 1.0,
385 ! the result could be +/-0.0, but we will
386 ! return 0.0 instead similar to other
388 2drop 0.0 ! -63 shift zero? 0.0 -0.0 ?
390 ! Put zeroes in the correct part of the mantissa
391 0x000fffffffffffff swap neg shift bitnot bitand
395 ! check for nans and infinities and do an operation on them
396 ! to trigger fp exceptions if necessary
397 nip 0x400 = [ dup + ] when
400 GENERIC: round ( x -- y )
402 GENERIC: round-to-even ( x -- y )
404 GENERIC: round-to-odd ( x -- y )
406 M: integer round ; inline
408 M: integer round-to-even ; inline
410 M: integer round-to-odd ; inline
412 : (round-tiebreak?) ( quotient rem denom tiebreak-quot -- q ? )
413 [ [ > ] ] dip [ 2dip = and ] curry 3bi or ; inline
415 : (round-to-even?) ( quotient rem denom -- quotient ? )
416 [ >integer odd? ] (round-tiebreak?) ; inline
418 : (round-to-odd?) ( quotient rem denom -- quotient ? )
419 [ >integer even? ] (round-tiebreak?) ; inline
421 : (ratio-round) ( x round-quot -- y )
422 [ >fraction [ /mod dup swapd abs 2 * ] keep ] [ call ] bi*
423 [ swap 0 < -1 1 ? + ] [ nip ] if ; inline
425 : (float-round) ( x round-quot -- y )
426 [ dup 1 mod [ - ] keep dup swapd abs 0.5 ] [ call ] bi*
427 [ swap 0.0 < -1.0 1.0 ? + ] [ nip ] if ; inline
429 M: ratio round [ >= ] (ratio-round) ;
431 M: ratio round-to-even [ (round-to-even?) ] (ratio-round) ;
433 M: ratio round-to-odd [ (round-to-odd?) ] (ratio-round) ;
435 M: float round dup sgn 2 /f + truncate ;
437 M: float round-to-even [ (round-to-even?) ] (float-round) ;
439 M: float round-to-odd [ (round-to-odd?) ] (float-round) ;
443 [ dup 0 < [ - 1 - ] [ - ] if ] unless-zero ; foldable
445 : ceiling ( x -- y ) neg floor neg ; foldable
447 : floor-to ( x step -- y )
448 [ [ / floor ] [ * ] bi ] unless-zero ;
450 : lerp ( a b t -- a_t ) [ over - ] dip * + ; inline
452 : roots ( x t -- seq )
453 [ [ log ] [ recip ] bi* * e^ ]
454 [ recip 2pi * 0 swap complex boa e^ ]
455 [ <iota> [ ^ * ] 2with map ] tri ;
458 : sigmoid ( x -- y ) neg e^ 1 + recip ; inline
460 : logit ( x -- y ) [ ] [ 1 swap - ] bi /f log ; inline
463 GENERIC: signum ( x -- y )
467 M: complex signum dup abs / ;
469 MATH: copysign ( x y -- x' )
471 M: real copysign >float copysign ;
474 [ double>bits ] [ fp-sign ] bi*
475 [ 63 2^ bitor ] [ 63 2^ bitnot bitand ] if
478 :: integer-sqrt ( x -- n )
481 bit-length 1 - 2 /i :> c
484 c bit-length <iota> <reversed> [| s |
488 x 2 c * e - d - 1 + neg shift a /i + a!
490 a a sq x > [ 1 - ] when
495 GENERIC: (integer-log10) ( x -- n ) foldable
497 ! For 32 bits systems, we could reduce
498 ! this to the first 27 elements..
499 CONSTANT: log10-guesses {
500 0 0 0 0 1 1 1 2 2 2 3 3 3 3
501 4 4 4 5 5 5 6 6 6 6 7 7 7 8
502 8 8 9 9 9 9 10 10 10 11 11 11
503 12 12 12 12 13 13 13 14 14 14
504 15 15 15 15 16 16 16 17 17
507 ! This table will hold a few unused bignums on 32 bits systems...
508 ! It could be reduced to the first 8 elements
509 ! Note that even though the 64 bits most-positive-fixnum
510 ! is hardcoded here this table also works (by chance) for 32bit systems.
511 ! This is because there is only one power of 2 greater than the
512 ! greatest power of 10 for 27 bit unsigned integers so we don't
513 ! need to hardcode the 32 bits most-positive-fixnum. See the
514 ! table below for powers of 2 and powers of 10 around the
515 ! most-positive-fixnum.
517 ! 67108864 2^26 | 72057594037927936 2^56
518 ! 99999999 10^8 | 99999999999999999 10^17
519 ! 134217727 2^27-1 | 144115188075855872 2^57
520 ! | 288230376151711744 2^58
521 ! | 576460752303423487 2^59-1
522 CONSTANT: log10-thresholds {
523 9 99 999 9999 99999 999999
524 9999999 99999999 999999999
525 9999999999 99999999999
526 999999999999 9999999999999
527 99999999999999 999999999999999
528 9999999999999999 99999999999999999
532 : fixnum-integer-log10 ( n -- x )
533 dup (log2) { array-capacity } declare
534 log10-guesses nth-unsafe { array-capacity } declare
535 dup log10-thresholds nth-unsafe { fixnum } declare
536 rot < [ 1 + ] when ; inline
538 ! bignum-integer-log10-find-down and bignum-integer-log10-find-up
539 ! work with very bad guesses, but in practice they will never loop
541 : bignum-integer-log10-find-down ( guess 10^guess n -- log10 )
542 [ 2dup > ] [ [ [ 1 - ] [ 10 / ] bi* ] dip ] do while 2drop ;
544 : bignum-integer-log10-find-up ( guess 10^guess n -- log10 )
546 [ 2dup <= ] [ [ [ 1 + ] [ 10 * ] bi* ] dip ] while 2drop ;
548 : bignum-integer-log10-guess ( n -- guess 10^guess )
549 (log2) >integer log10-2 * >integer dup 10^ ;
551 : bignum-integer-log10 ( n -- x )
552 [ bignum-integer-log10-guess ] keep 2dup >
553 [ bignum-integer-log10-find-down ]
554 [ bignum-integer-log10-find-up ] if ; inline
556 M: fixnum (integer-log10) fixnum-integer-log10 { fixnum } declare ; inline
558 M: bignum (integer-log10) bignum-integer-log10 ; inline
564 GENERIC: (integer-log2) ( x -- n ) foldable
566 M: integer (integer-log2) (log2) ; inline
568 : ((ratio-integer-log)) ( ratio quot -- log )
569 [ >integer ] dip call ; inline
571 : (ratio-integer-log) ( ratio quot base -- log )
573 [ drop ((ratio-integer-log)) ] [
575 [ drop ((ratio-integer-log)) ] [ nip pick ^ = ] 3bi
579 M: ratio (integer-log2) [ (integer-log2) ] 2 (ratio-integer-log) ;
581 M: ratio (integer-log10) [ (integer-log10) ] 10 (ratio-integer-log) ;
585 : integer-log10 ( x -- n )
586 assert-positive (integer-log10) ; inline
588 : integer-log2 ( x -- n )
589 assert-positive (integer-log2) ; inline