core/math/integers/integers.factor

   1 ! Copyright (C) 2004, 2009 Slava Pestov.
   2 ! Copyright (C) 2008, Doug Coleman.
   3 ! See http://factorcode.org/license.txt for BSD license.
   4 USING: kernel kernel.private sequences
   5 sequences.private math math.private combinators ;
   6 IN: math.integers.private
   7
   8 : fixnum-min ( x y -- z ) [ fixnum< ] most ; foldable
   9 : fixnum-max ( x y -- z ) [ fixnum> ] most ; foldable
  10
  11 M: integer numerator ; inline
  12 M: integer denominator drop 1 ; inline
  13
  14 M: fixnum >fixnum ; inline
  15 M: fixnum >bignum fixnum>bignum ; inline
  16 M: fixnum >integer ; inline
  17
  18 M: fixnum hashcode* nip ; inline
  19 M: fixnum equal? over bignum? [ >bignum bignum= ] [ 2drop f ] if ; inline
  20 M: fixnum number= eq? ; inline
  21
  22 M: fixnum < fixnum< ; inline
  23 M: fixnum <= fixnum<= ; inline
  24 M: fixnum > fixnum> ; inline
  25 M: fixnum >= fixnum>= ; inline
  26
  27 M: fixnum u< fixnum< ; inline
  28 M: fixnum u<= fixnum<= ; inline
  29 M: fixnum u> fixnum> ; inline
  30 M: fixnum u>= fixnum>= ; inline
  31
  32 M: fixnum + fixnum+ ; inline
  33 M: fixnum - fixnum- ; inline
  34 M: fixnum * fixnum* ; inline
  35 M: fixnum /i fixnum/i ; inline
  36 M: fixnum /f [ >float ] dip >float float/f ; inline
  37
  38 M: fixnum mod fixnum-mod ; inline
  39
  40 M: fixnum /mod fixnum/mod ; inline
  41
  42 M: fixnum bitand fixnum-bitand ; inline
  43 M: fixnum bitor fixnum-bitor ; inline
  44 M: fixnum bitxor fixnum-bitxor ; inline
  45 M: fixnum shift >fixnum fixnum-shift ; inline
  46
  47 M: fixnum bitnot fixnum-bitnot ; inline
  48
  49 M: fixnum bit? neg shift 1 bitand 0 > ; inline
  50
  51 : fixnum-log2 ( x -- n )
  52     0 swap [ dup 1 eq? ] [ [ 1 + ] [ 2/ ] bi* ] until drop ;
  53
  54 M: fixnum (log2) fixnum-log2 ; inline
  55
  56 M: bignum >fixnum bignum>fixnum ; inline
  57 M: bignum >bignum ; inline
  58
  59 M: bignum hashcode* nip >fixnum ;
  60
  61 M: bignum equal?
  62     over bignum? [ bignum= ] [
  63         swap dup fixnum? [ >bignum bignum= ] [ 2drop f ] if
  64     ] if ; inline
  65
  66 M: bignum number= bignum= ; inline
  67
  68 M: bignum < bignum< ; inline
  69 M: bignum <= bignum<= ; inline
  70 M: bignum > bignum> ; inline
  71 M: bignum >= bignum>= ; inline
  72
  73 M: bignum u< bignum< ; inline
  74 M: bignum u<= bignum<= ; inline
  75 M: bignum u> bignum> ; inline
  76 M: bignum u>= bignum>= ; inline
  77
  78 M: bignum + bignum+ ; inline
  79 M: bignum - bignum- ; inline
  80 M: bignum * bignum* ; inline
  81 M: bignum /i bignum/i ; inline
  82 M: bignum mod bignum-mod ; inline
  83
  84 M: bignum /mod bignum/mod ; inline
  85
  86 M: bignum bitand bignum-bitand ; inline
  87 M: bignum bitor bignum-bitor ; inline
  88 M: bignum bitxor bignum-bitxor ; inline
  89 M: bignum shift >fixnum bignum-shift ; inline
  90
  91 M: bignum bitnot bignum-bitnot ; inline
  92 M: bignum bit? bignum-bit? ; inline
  93 M: bignum (log2) bignum-log2 ; inline
  94
  95 ! Converting ratios to floats. Based on FLOAT-RATIO from
  96 ! sbcl/src/code/float.lisp, which has the following license:
  97
  98 ! "The software is in the public domain and is
  99 ! provided with absolutely no warranty."
 100
 101 ! First step: pre-scaling
 102 : twos ( x -- y ) dup 1 - bitxor log2 ; inline
 103
 104 : scale-denonimator ( den -- scaled-den scale' )
 105     dup twos neg [ shift ] keep ; inline
 106
 107 : pre-scale ( num den -- scale shifted-num scaled-den )
 108     2dup [ log2 ] bi@ -
 109     [ neg 54 + shift ] [ [ scale-denonimator ] dip + ] bi-curry bi*
 110     -rot ; inline
 111
 112 ! Second step: loop
 113 : shift-mantissa ( scale mantissa -- scale' mantissa' )
 114     [ 1 + ] [ 2/ ] bi* ; inline
 115
 116 : /f-loop ( scale mantissa den -- scale' fraction-and-guard rem )
 117     [ 2dup /i log2 53 > ]
 118     [ [ shift-mantissa ] dip ]
 119     while /mod ; inline
 120
 121 ! Third step: post-scaling
 122 : unscaled-float ( mantissa -- n )
 123     52 2^ 1 - bitand 1022 52 shift bitor bits>double ; inline
 124
 125 : scale-float ( scale mantissa -- float' )
 126     [ dup 0 < [ neg 2^ recip ] [ 2^ ] if ] dip * ; inline
 127
 128 : post-scale ( scale mantissa -- n )
 129     2/ dup log2 52 > [ shift-mantissa ] when
 130     unscaled-float scale-float ; inline
 131
 132 ! Main word
 133 : /f-abs ( m n -- f )
 134     over zero? [
 135         2drop 0.0
 136     ] [
 137         [
 138             drop 1/0.
 139         ] [
 140             pre-scale
 141             /f-loop over odd?
 142             [ zero? [ 1 + ] unless ] [ drop ] if
 143             post-scale
 144         ] if-zero
 145     ] if ; inline
 146
 147 M: bignum /f ( m n -- f )
 148     [ [ abs ] bi@ /f-abs ] [ [ 0 < ] bi@ xor ] 2bi [ neg ] when ;