basis/math/functions/functions.factor

   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
   5 sequences.private ;
   6 IN: math.functions
   7
   8 GENERIC: sqrt ( x -- y ) foldable
   9
  10 M: real sqrt
  11     >float dup 0.0 <
  12     [ neg fsqrt [ 0.0 ] dip rect> ] [ fsqrt ] if ; inline
  13
  14 : factor-2s ( n -- r s )
  15     ! factor an integer into 2^r * s
  16     dup 0 = [ 1 ] [
  17         [ 0 ] dip [ dup even? ] [ [ 1 + ] [ 2/ ] bi* ] while
  18     ] if ; inline
  19
  20 <PRIVATE
  21
  22 : (^fixnum) ( z w -- z^w )
  23     [ 1 ] 2dip
  24     [ dup zero? ] [
  25         dup odd? [
  26             [ [ * ] keep ] [ 1 - ] bi*
  27         ] when [ sq ] [ 2/ ] bi*
  28     ] until 2drop ; inline
  29
  30 : (^bignum) ( z w -- z^w )
  31     make-bits 1 [ [ over * ] when [ sq ] dip ] reduce nip ; inline
  32
  33 : (^n) ( z w -- z^w )
  34     dup fixnum? [ (^fixnum) ] [ (^bignum) ] if ; inline
  35
  36 GENERIC#: ^n 1 ( z w -- z^w ) foldable
  37
  38 M: fixnum ^n (^n) ;
  39
  40 M: bignum ^n
  41     [ factor-2s ] dip [ (^n) ] keep rot * shift ;
  42
  43 M: ratio ^n
  44     [ >fraction ] dip '[ _ ^n ] bi@ / ;
  45
  46 M: float ^n (^n) ;
  47
  48 M: complex ^n (^n) ;
  49
  50 : integer^ ( x y -- z )
  51     dup 0 >= [ ^n ] [ [ recip ] dip neg ^n ] if ; inline
  52
  53 PRIVATE>
  54
  55 : >float-rect ( z -- x y )
  56     >rect [ >float ] bi@ ; inline
  57
  58 : >polar ( z -- abs arg )
  59     >float-rect [ [ sq ] bi@ + fsqrt ] [ swap fatan2 ] 2bi ; inline
  60
  61 : cis ( arg -- z ) >float [ fcos ] [ fsin ] bi rect> ; inline
  62
  63 : polar> ( abs arg -- z ) cis * ; inline
  64
  65 GENERIC: e^ ( x -- e^x )
  66
  67 M: float e^ fexp ; inline
  68
  69 M: real e^ >float e^ ; inline
  70
  71 M: complex e^ >rect [ e^ ] dip polar> ; inline
  72
  73 <PRIVATE
  74
  75 : ^mag ( w abs arg -- magnitude )
  76     [ >float-rect swap ]
  77     [ >float swap >float fpow ]
  78     [ rot * e^ /f ]
  79     tri* ; inline
  80
  81 : ^theta ( w abs arg -- theta )
  82     [ >float-rect ] [ flog * swap ] [ * + ] tri* ; inline
  83
  84 : ^complex ( x y -- z )
  85     swap >polar [ ^mag ] [ ^theta ] 3bi polar> ; inline
  86
  87 : real^? ( x y -- ? )
  88     2dup [ real? ] both? [ drop 0 >= ] [ 2drop f ] if ; inline
  89
  90 : 0^ ( zero x -- z )
  91     swap [ 0/0. ] swap '[ 0 < 1/0. _ ? ] if-zero ; inline
  92
  93 : (^mod) ( x y n -- z )
  94     [ make-bits 1 ] dip dup
  95     '[ [ over * _ mod ] when [ sq _ mod ] dip ] reduce nip ; inline
  96
  97 PRIVATE>
  98
  99 : ^ ( x y -- x^y )
 100     {
 101         { [ over zero? ] [ 0^ ] }
 102         { [ dup integer? ] [ integer^ ] }
 103         { [ 2dup real^? ] [ [ >float ] bi@ fpow ] }
 104         [ ^complex ]
 105     } cond ; inline
 106
 107 : nth-root ( n x -- y ) swap recip ^ ; inline
 108
 109 : divisor? ( m n -- ? )
 110     mod 0 = ; inline
 111
 112 ERROR: non-trivial-divisor n ;
 113
 114 : mod-inv ( x n -- y )
 115     [ nip ] [ gcd 1 = ] 2bi
 116     [ dup 0 < [ + ] [ nip ] if ]
 117     [ non-trivial-divisor ] if ; foldable
 118
 119 : ^mod ( x y n -- z )
 120     over 0 <
 121     [ [ [ neg ] dip ^mod ] keep mod-inv ] [ (^mod) ] if ; foldable
 122
 123 GENERIC: absq ( x -- y ) foldable
 124
 125 M: real absq sq ; inline
 126
 127 : ~abs ( x y epsilon -- ? )
 128     [ - abs ] dip < ;
 129
 130 : ~rel ( x y epsilon -- ? )
 131     [ [ - abs ] 2keep [ abs ] bi@ + ] dip * <= ;
 132
 133 : ~ ( x y epsilon -- ? )
 134     {
 135         { [ dup zero? ] [ drop number= ] }
 136         { [ dup 0 < ] [ neg ~rel ] }
 137         [ ~abs ]
 138     } cond ;
 139
 140 : conjugate ( z -- z* ) >rect neg rect> ; inline
 141
 142 : arg ( z -- arg ) >float-rect swap fatan2 ; inline
 143
 144 : [-1,1]? ( x -- ? )
 145     dup complex? [ drop f ] [ abs 1 <= ] if ; inline
 146
 147 : >=1? ( x -- ? )
 148     dup complex? [ drop f ] [ 1 >= ] if ; inline
 149
 150 GENERIC: frexp ( x -- y exp )
 151
 152 M: float frexp
 153     dup fp-special? [ dup zero? ] unless* [ 0 ] [
 154         double>bits
 155         [ 0x800f,ffff,ffff,ffff bitand 0.5 double>bits bitor bits>double ]
 156         [ -52 shift 0x7ff bitand 1022 - ] bi
 157     ] if ; inline
 158
 159 M: integer frexp
 160     [ 0.0 0 ] [
 161         dup 0 > [ 1 ] [ abs -1 ] if swap dup log2 [
 162             52 swap - shift 0x000f,ffff,ffff,ffff bitand
 163             0.5 double>bits bitor bits>double
 164         ] [ 1 + ] bi [ * ] dip
 165     ] if-zero ; inline
 166
 167 DEFER: copysign
 168
 169 GENERIC#: ldexp 1 ( x exp -- y )
 170
 171 M: float ldexp
 172     over fp-special? [ over zero? ] unless* [ drop ] [
 173         [ double>bits dup -52 shift 0x7ff bitand 1023 - ] dip +
 174         {
 175             { [ dup -1074 < ] [ drop 0 copysign ] }
 176             { [ dup 1023 > ] [ drop 0 < -1/0. 1/0. ? ] }
 177             [
 178                 dup -1022 < [ 52 + -52 2^ ] [ 1 ] if
 179                 [ -0x7ff0,0000,0000,0001 bitand ]
 180                 [ 1023 + 52 shift bitor bits>double ]
 181                 [ * ] tri*
 182             ]
 183         } cond
 184     ] if ;
 185
 186 M: integer ldexp
 187     2dup [ zero? ] either? [ 2drop 0 ] [ shift ] if ;
 188
 189 GENERIC: log ( x -- y )
 190
 191 M: float log dup 0.0 >= [ flog ] [ 0.0 rect> log ] if ; inline
 192
 193 M: real log >float log ; inline
 194
 195 M: complex log >polar [ flog ] dip rect> ; inline
 196
 197 : logn ( x n -- y ) [ log ] bi@ / ;
 198
 199 GENERIC: lgamma ( x -- y )
 200
 201 M: float lgamma flgamma ;
 202
 203 M: real lgamma >float lgamma ;
 204
 205 <PRIVATE
 206
 207 : most-negative-finite-float ( -- x )
 208     -0x1.ffff,ffff,ffff,fp1023 >integer ; inline
 209
 210 : most-positive-finite-float ( -- x )
 211     0x1.ffff,ffff,ffff,fp1023 >integer ; inline
 212
 213 CONSTANT: log-2   0x1.62e42fefa39efp-1
 214 CONSTANT: log10-2 0x1.34413509f79ffp-2
 215
 216 : representable-as-float? ( x -- ? )
 217     most-negative-finite-float
 218     most-positive-finite-float between? ; inline
 219
 220 : (bignum-log) ( n log-quot: ( x -- y ) log-2 -- log )
 221     dupd '[
 222         dup representable-as-float?
 223         [ >float @ ] [ frexp _ [ _ * ] bi* + ] if
 224     ] call ; inline
 225
 226 PRIVATE>
 227
 228 M: bignum log [ log ] log-2 (bignum-log) ;
 229
 230 GENERIC: log1+ ( x -- y )
 231
 232 M: object log1+ 1 + log ; inline
 233
 234 M: float log1+ dup -1.0 >= [ flog1+ ] [ 1.0 + 0.0 rect> log ] if ; inline
 235
 236 : 10^ ( x -- 10^x ) 10 swap ^ ; inline
 237
 238 GENERIC: log10 ( x -- y ) foldable
 239
 240 M: real log10 >float flog10 ; inline
 241
 242 M: complex log10 log 10 log / ; inline
 243
 244 M: bignum log10 [ log10 ] log10-2 (bignum-log) ;
 245
 246 GENERIC: e^-1 ( x -- e^x-1 )
 247
 248 M: float e^-1
 249     dup abs 0.7 < [
 250         dup e^ dup 1.0 = [
 251             drop
 252         ] [
 253             [ 1.0 - * ] [ log / ] bi
 254         ] if
 255     ] [ e^ 1.0 - ] if ; inline
 256
 257 M: real e^-1 >float e^-1 ; inline
 258
 259 GENERIC: cos ( x -- y ) foldable
 260
 261 M: complex cos
 262     >float-rect
 263     [ [ fcos ] [ fcosh ] bi* * ]
 264     [ [ fsin neg ] [ fsinh ] bi* * ] 2bi rect> ;
 265
 266 M: float cos fcos ; inline
 267
 268 M: real cos >float cos ; inline
 269
 270 : sec ( x -- y ) cos recip ; inline
 271
 272 GENERIC: cosh ( x -- y ) foldable
 273
 274 M: complex cosh
 275     >float-rect
 276     [ [ fcosh ] [ fcos ] bi* * ]
 277     [ [ fsinh ] [ fsin ] bi* * ] 2bi rect> ;
 278
 279 M: float cosh fcosh ; inline
 280
 281 M: real cosh >float cosh ; inline
 282
 283 : sech ( x -- y ) cosh recip ; inline
 284
 285 GENERIC: sin ( x -- y ) foldable
 286
 287 M: complex sin
 288     >float-rect
 289     [ [ fsin ] [ fcosh ] bi* * ]
 290     [ [ fcos ] [ fsinh ] bi* * ] 2bi rect> ;
 291
 292 M: float sin fsin ; inline
 293
 294 M: real sin >float sin ; inline
 295
 296 : cosec ( x -- y ) sin recip ; inline
 297
 298 GENERIC: sinh ( x -- y ) foldable
 299
 300 M: complex sinh
 301     >float-rect
 302     [ [ fsinh ] [ fcos ] bi* * ]
 303     [ [ fcosh ] [ fsin ] bi* * ] 2bi rect> ;
 304
 305 M: float sinh fsinh ; inline
 306
 307 M: real sinh >float sinh ; inline
 308
 309 : cosech ( x -- y ) sinh recip ; inline
 310
 311 GENERIC: tan ( x -- y ) foldable
 312
 313 M: complex tan [ sin ] [ cos ] bi / ;
 314
 315 M: float tan ftan ; inline
 316
 317 M: real tan >float tan ; inline
 318
 319 GENERIC: tanh ( x -- y ) foldable
 320
 321 M: complex tanh [ sinh ] [ cosh ] bi / ;
 322
 323 M: float tanh ftanh ; inline
 324
 325 M: real tanh >float tanh ; inline
 326
 327 : cot ( x -- y ) tan recip ; inline
 328
 329 : coth ( x -- y ) tanh recip ; inline
 330
 331 : acosh ( x -- y )
 332     dup sq 1 - sqrt + log ; inline
 333
 334 : asech ( x -- y ) recip acosh ; inline
 335
 336 : asinh ( x -- y )
 337     dup sq 1 + sqrt + log ; inline
 338
 339 : acosech ( x -- y ) recip asinh ; inline
 340
 341 : atanh ( x -- y )
 342     [ 1 + ] [ 1 - neg ] bi / log 2 / ; inline
 343
 344 : acoth ( x -- y ) recip atanh ; inline
 345
 346 : i* ( x -- y ) >rect neg swap rect> ;
 347
 348 : -i* ( x -- y ) >rect swap neg rect> ;
 349
 350 : asin ( x -- y )
 351     dup [-1,1]? [ >float fasin ] [ i* asinh -i* ] if ; inline
 352
 353 : acos ( x -- y )
 354     dup [-1,1]? [ >float facos ] [ asin pi 2 / swap - ] if ; inline
 355
 356 GENERIC: atan ( x -- y ) foldable
 357
 358 M: complex atan i* atanh i* ; inline
 359
 360 M: float atan fatan ; inline
 361
 362 M: real atan >float atan ; inline
 363
 364 : asec ( x -- y ) recip acos ; inline
 365
 366 : acosec ( x -- y ) recip asin ; inline
 367
 368 : acot ( x -- y ) recip atan ; inline
 369
 370 : deg>rad ( x -- y ) pi * 180 / ; inline
 371
 372 : rad>deg ( x -- y ) 180 * pi / ; inline
 373
 374 GENERIC: truncate ( x -- y )
 375
 376 M: real truncate dup 1 mod - ;
 377
 378 M: float truncate
 379     dup double>bits
 380     dup -52 shift 0x7ff bitand 0x3ff -
 381     ! check for floats without fractional part (>= 2^52)
 382     dup 52 < [
 383         nipd
 384         dup 0 < [
 385             ! the float is between -1.0 and 1.0,
 386             ! the result could be +/-0.0, but we will
 387             ! return 0.0 instead similar to other
 388             ! languages
 389             2drop 0.0 ! -63 shift zero? 0.0 -0.0 ?
 390         ] [
 391             ! Put zeroes in the correct part of the mantissa
 392             0x000fffffffffffff swap neg shift bitnot bitand
 393             bits>double
 394         ] if
 395     ] [
 396         ! check for nans and infinities and do an operation on them
 397         ! to trigger fp exceptions if necessary
 398         nip 0x400 = [ dup + ] when
 399     ] if ; inline
 400
 401 GENERIC: round ( x -- y )
 402
 403 GENERIC: round-to-even ( x -- y )
 404
 405 GENERIC: round-to-odd ( x -- y )
 406
 407 M: integer round ; inline
 408
 409 M: integer round-to-even ; inline
 410
 411 M: integer round-to-odd ; inline
 412
 413 : (round-tiebreak?) ( quotient rem denom tiebreak-quot -- q ? )
 414     [ [ > ] ] dip [ 2dip = and ] curry 3bi or ; inline
 415
 416 : (round-to-even?) ( quotient rem denom -- quotient ? )
 417     [ >integer odd? ] (round-tiebreak?) ; inline
 418
 419 : (round-to-odd?) ( quotient rem denom -- quotient ? )
 420     [ >integer even? ] (round-tiebreak?) ; inline
 421
 422 : (ratio-round) ( x round-quot -- y )
 423     [ >fraction [ /mod dup swapd abs 2 * ] keep ] [ call ] bi*
 424     [ swap 0 < -1 1 ? + ] [ nip ] if ; inline
 425
 426 : (float-round) ( x round-quot -- y )
 427     [ dup 1 mod [ - ] keep dup swapd abs 0.5 ] [ call ] bi*
 428     [ swap 0.0 < -1.0 1.0 ? + ] [ nip ] if ; inline
 429
 430 M: ratio round [ >= ] (ratio-round) ;
 431
 432 M: ratio round-to-even [ (round-to-even?) ] (ratio-round) ;
 433
 434 M: ratio round-to-odd [ (round-to-odd?) ] (ratio-round) ;
 435
 436 M: float round dup sgn 2 /f + truncate ;
 437
 438 M: float round-to-even [ (round-to-even?) ] (float-round) ;
 439
 440 M: float round-to-odd [ (round-to-odd?) ] (float-round) ;
 441
 442 : floor ( x -- y )
 443     dup 1 mod
 444     [ dup 0 < [ - 1 - ] [ - ] if ] unless-zero ; foldable
 445
 446 : ceiling ( x -- y ) neg floor neg ; foldable
 447
 448 : floor-to ( x step -- y )
 449     [ [ / floor ] [ * ] bi ] unless-zero ;
 450
 451 : lerp ( a b t -- a_t ) [ over - ] dip * + ; inline
 452
 453 : roots ( x t -- seq )
 454     [ [ log ] [ recip ] bi* * e^ ]
 455     [ recip 2pi * 0 swap complex boa e^ ]
 456     [ <iota> [ ^ * ] 2with map ] tri ;
 457
 458 ! expit
 459 : sigmoid ( x -- y ) neg e^ 1 + recip ; inline
 460
 461 : logit ( x -- y ) [ ] [ 1 swap - ] bi /f log ; inline
 462
 463
 464 GENERIC: signum ( x -- y )
 465
 466 M: real signum sgn ;
 467
 468 M: complex signum dup abs / ;
 469
 470 MATH: copysign ( x y -- x' )
 471
 472 M: real copysign >float copysign ;
 473
 474 M: float copysign
 475     [ double>bits ] [ fp-sign ] bi*
 476     [ 63 2^ bitor ] [ 63 2^ bitnot bitand ] if
 477     bits>double ;
 478
 479 :: integer-sqrt ( x -- n )
 480     x [ 0 ] [
 481         assert-non-negative
 482         bit-length 1 - 2 /i :> c
 483         1 :> a!
 484         0 :> d!
 485         c bit-length <iota> <reversed> [| s |
 486             d :> e
 487             c s neg shift d!
 488             a d e - 1 - shift
 489             x 2 c * e - d - 1 + neg shift a /i + a!
 490         ] each
 491         a a sq x > [ 1 - ] when
 492     ] if-zero ;
 493
 494 <PRIVATE
 495
 496 GENERIC: (integer-log10) ( x -- n ) foldable
 497
 498 ! For 32 bits systems, we could reduce
 499 ! this to the first 27 elements..
 500 CONSTANT: log10-guesses {
 501     0 0 0 0 1 1 1 2 2 2 3 3 3 3
 502     4 4 4 5 5 5 6 6 6 6 7 7 7 8
 503     8 8 9 9 9 9 10 10 10 11 11 11
 504     12 12 12 12 13 13 13 14 14 14
 505     15 15 15 15 16 16 16 17 17
 506 }
 507
 508 ! This table will hold a few unused bignums on 32 bits systems...
 509 ! It could be reduced to the first 8 elements
 510 ! Note that even though the 64 bits most-positive-fixnum
 511 ! is hardcoded here this table also works (by chance) for 32bit systems.
 512 ! This is because there is only one power of 2 greater than the
 513 ! greatest power of 10 for 27 bit unsigned integers so we don't
 514 ! need to hardcode the 32 bits most-positive-fixnum. See the
 515 ! table below for powers of 2 and powers of 10 around the
 516 ! most-positive-fixnum.
 517 !
 518 ! 67108864  2^26    | 72057594037927936   2^56
 519 ! 99999999  10^8    | 99999999999999999  10^17
 520 ! 134217727 2^27-1  | 144115188075855872  2^57
 521 !                   | 288230376151711744  2^58
 522 !                   | 576460752303423487  2^59-1
 523 CONSTANT: log10-thresholds {
 524     9 99 999 9999 99999 999999
 525     9999999 99999999 999999999
 526     9999999999 99999999999
 527     999999999999 9999999999999
 528     99999999999999 999999999999999
 529     9999999999999999 99999999999999999
 530     576460752303423487
 531 }
 532
 533 : fixnum-integer-log10 ( n -- x )
 534     dup (log2) { array-capacity } declare
 535     log10-guesses nth-unsafe { array-capacity } declare
 536     dup log10-thresholds nth-unsafe { fixnum } declare
 537     rot < [ 1 + ] when ; inline
 538
 539 ! bignum-integer-log10-find-down and bignum-integer-log10-find-up
 540 ! work with very bad guesses, but in practice they will never loop
 541 ! more than once.
 542 : bignum-integer-log10-find-down ( guess 10^guess n -- log10 )
 543     [ 2dup > ] [ [ [ 1 - ] [ 10 / ] bi* ] dip ] do while 2drop ;
 544
 545 : bignum-integer-log10-find-up ( guess 10^guess n -- log10 )
 546     [ 10 * ] dip
 547     [ 2dup <= ] [ [ [ 1 + ] [ 10 * ] bi* ] dip ] while 2drop ;
 548
 549 : bignum-integer-log10-guess ( n -- guess 10^guess )
 550     (log2) >integer log10-2 * >integer dup 10^ ;
 551
 552 : bignum-integer-log10 ( n -- x )
 553     [ bignum-integer-log10-guess ] keep 2dup >
 554     [ bignum-integer-log10-find-down ]
 555     [ bignum-integer-log10-find-up ] if ; inline
 556
 557 M: fixnum (integer-log10) fixnum-integer-log10 { fixnum } declare ; inline
 558
 559 M: bignum (integer-log10) bignum-integer-log10 ; inline
 560
 561 PRIVATE>
 562
 563 <PRIVATE
 564
 565 GENERIC: (integer-log2) ( x -- n ) foldable
 566
 567 M: integer (integer-log2) (log2) ; inline
 568
 569 : ((ratio-integer-log)) ( ratio quot -- log )
 570     [ >integer ] dip call ; inline
 571
 572 : (ratio-integer-log) ( ratio quot base -- log )
 573     pick 1 >=
 574     [ drop ((ratio-integer-log)) ] [
 575         [ recip ] 2dip
 576         [ drop ((ratio-integer-log)) ] [ nip pick ^ = ] 3bi
 577         [ 1 + ] unless neg
 578     ] if ; inline
 579
 580 M: ratio (integer-log2) [ (integer-log2) ] 2 (ratio-integer-log) ;
 581
 582 M: ratio (integer-log10) [ (integer-log10) ] 10 (ratio-integer-log) ;
 583
 584 PRIVATE>
 585
 586 : integer-log10 ( x -- n )
 587     assert-positive (integer-log10) ; inline
 588
 589 : integer-log2 ( x -- n )
 590     assert-positive (integer-log2) ; inline