core/math/integers/integers.factor

   1 ! Copyright (C) 2004, 2010 Slava Pestov.
   2 ! Copyright (C) 2008, Doug Coleman.
   3 ! See http://factorcode.org/license.txt for BSD license.
   4 USING: combinators kernel kernel.private math math.order
   5 math.private ;
   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 M: fixnum >float fixnum>float ; inline
  18 M: fixnum integer>fixnum ; inline
  19 M: fixnum integer>fixnum-strict ; inline
  20
  21 M: fixnum hashcode* nip ; inline
  22 M: fixnum equal? over bignum? [ >bignum bignum= ] [ 2drop f ] if ; inline
  23 M: fixnum number= eq? ; inline
  24
  25 M: fixnum < fixnum< ; inline
  26 M: fixnum <= fixnum<= ; inline
  27 M: fixnum > fixnum> ; inline
  28 M: fixnum >= fixnum>= ; inline
  29
  30 M: fixnum u< fixnum< ; inline
  31 M: fixnum u<= fixnum<= ; inline
  32 M: fixnum u> fixnum> ; inline
  33 M: fixnum u>= fixnum>= ; inline
  34
  35 M: fixnum min over fixnum? [ fixnum-min ] [ call-next-method ] if ; inline
  36 M: fixnum max over fixnum? [ fixnum-max ] [ call-next-method ] if ; inline
  37
  38 M: fixnum + fixnum+ ; inline
  39 M: fixnum - fixnum- ; inline
  40 M: fixnum * fixnum* ; inline
  41 M: fixnum /i fixnum/i ; inline
  42
  43 M: fixnum mod fixnum-mod ; inline
  44
  45 M: fixnum /mod fixnum/mod ; inline
  46
  47 M: fixnum bitand fixnum-bitand ; inline
  48 M: fixnum bitor fixnum-bitor ; inline
  49 M: fixnum bitxor fixnum-bitxor ; inline
  50 M: fixnum shift integer>fixnum fixnum-shift ; inline
  51
  52 M: fixnum bitnot fixnum-bitnot ; inline
  53
  54 : fixnum-bit? ( n m -- b )
  55     neg shift 1 bitand zero? not ; inline
  56
  57 M: fixnum bit? fixnum-bit? ; inline
  58
  59 : fixnum-log2 ( x -- n )
  60     { fixnum } declare
  61     0 swap [ dup 1 eq? ] [
  62         [ 1 fixnum+fast ] [ 2/ ] bi*
  63     ] until drop ;
  64
  65 M: fixnum (log2) fixnum-log2 { fixnum } declare ; inline
  66
  67 M: bignum >fixnum bignum>fixnum ; inline
  68 M: bignum >bignum ; inline
  69 M: bignum integer>fixnum bignum>fixnum ; inline
  70
  71 M: bignum integer>fixnum-strict
  72     dup bignum>fixnum
  73     2dup number= [ nip ] [ drop out-of-fixnum-range ] if ; inline
  74
  75 M: bignum hashcode* nip bignum>fixnum ;
  76
  77 M: bignum equal?
  78     over bignum? [ bignum= ] [
  79         swap dup fixnum? [ >bignum bignum= ] [ 2drop f ] if
  80     ] if ; inline
  81
  82 M: bignum number= bignum= ; inline
  83
  84 M: bignum < bignum< ; inline
  85 M: bignum <= bignum<= ; inline
  86 M: bignum > bignum> ; inline
  87 M: bignum >= bignum>= ; inline
  88
  89 M: bignum u< bignum< ; inline
  90 M: bignum u<= bignum<= ; inline
  91 M: bignum u> bignum> ; inline
  92 M: bignum u>= bignum>= ; inline
  93
  94 M: bignum + bignum+ ; inline
  95 M: bignum - bignum- ; inline
  96 M: bignum * bignum* ; inline
  97 M: bignum /i bignum/i ; inline
  98 M: bignum mod bignum-mod ; inline
  99
 100 M: bignum /mod bignum/mod ; inline
 101
 102 M: bignum bitand bignum-bitand ; inline
 103 M: bignum bitor bignum-bitor ; inline
 104 M: bignum bitxor bignum-bitxor ; inline
 105 M: bignum shift integer>fixnum bignum-shift ; inline
 106
 107 M: bignum bitnot bignum-bitnot ; inline
 108 M: bignum bit? bignum-bit? ; inline
 109 M: bignum (log2) bignum-log2 ; inline
 110
 111 ! Converting ratios to floats. Based on FLOAT-RATIO from
 112 ! sbcl/src/code/float.lisp, which has the following license:
 113
 114 ! "The software is in the public domain and is
 115 ! provided with absolutely no warranty."
 116
 117 ! First step: pre-scaling
 118 : twos ( x -- y ) dup 1 - bitxor log2 ; inline
 119
 120 : scale-denonimator ( den -- scaled-den scale' )
 121     dup twos neg [ shift ] keep ; inline
 122
 123 : (epsilon?) ( num shift -- ? )
 124     dup neg? [ neg 2^ 1 - bitand zero? not ] [ 2drop f ] if ; inline
 125
 126 : pre-scale ( num den -- epsilon? mantissa den' scale )
 127     2dup [ log2 ] bi@ -
 128     [ neg 54 + [ (epsilon?) ] [ shift ] 2bi ]
 129     [ [ scale-denonimator ] dip + ] bi-curry bi* ; inline
 130
 131 ! Second step: loop
 132 : (2/-with-epsilon) ( epsilon? num -- epsilon?' num' )
 133     [ 1 bitand zero? not or ] [ 2/ ] bi ; inline
 134
 135 : /f-loop ( epsilon? mantissa den scale -- epsilon?' fraction-and-guard rem scale' )
 136     [ 2over /i log2 53 > ]
 137     [ [ (2/-with-epsilon) ] [ ] [ 1 + ] tri* ] while
 138     [ /mod ] dip ; inline
 139
 140 ! Third step: post-scaling
 141 : scale-float ( mantissa scale -- float' )
 142     {
 143         { [ dup 1024 > ] [ 2drop 1/0. ] }
 144         { [ dup -1023 < ] [ 1021 + shift bits>double ] }
 145         [ [ 52 2^ 1 - bitand ] dip 1022 + 52 shift bitor bits>double ]
 146     } cond ; inline
 147
 148 : post-scale ( mantissa scale -- n )
 149     [ 2/ ] dip over log2 52 > [ [ 2/ ] [ 1 + ] bi* ] when
 150     scale-float ; inline
 151
 152 : round-to-nearest ( epsilon? fraction-and-guard rem -- fraction-and-guard' )
 153     over odd?
 154     [
 155         zero? [
 156             dup 2 bitand zero? not rot or [ 1 + ] when
 157         ] [ nip 1 + ] if
 158     ] [ drop nip ] if ;
 159     inline
 160
 161 ! Main word
 162 : /f-abs ( m n -- f )
 163     over zero? [ nip zero? 0/0. 0.0 ? ] [
 164         [ drop 1/0. ] [
 165             pre-scale
 166             /f-loop
 167             [ round-to-nearest ] dip
 168             post-scale
 169         ] if-zero
 170     ] if ; inline
 171
 172 : bignum/f ( m n -- f )
 173     [ [ abs ] bi@ /f-abs ] [ [ 0 < ] bi@ xor ] 2bi [ neg ] when ; inline
 174
 175 M: bignum /f ( m n -- f ) { bignum bignum } declare bignum/f ;
 176
 177 CONSTANT: bignum/f-threshold 0x20,0000,0000,0000
 178
 179 : fixnum/f ( m n -- m/n )
 180     [ >float ] bi@ float/f ; inline
 181
 182 M: fixnum /f
 183     { fixnum fixnum } declare
 184     2dup [ abs bignum/f-threshold >= ] either?
 185     [ bignum/f ] [ fixnum/f ] if ; inline
 186
 187 : bignum>float ( bignum -- float )
 188     { bignum } declare 1 >bignum bignum/f ;
 189
 190 M: bignum >float bignum>float ; inline