lib/gmp/gmp.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Multi precision integer and rational number using gmp lib
  16 module gmp
  17
  18 private import native_gmp
  19
  20 redef class Numeric
  21
  22     # The BigInt equivalent of `self`
  23     fun to_bi: BigInt do return self.to_i.to_bi
  24
  25     # The Ratio equivalent of `self`
  26     fun to_r: Ratio do return self.to_f.to_r
  27
  28 end
  29
  30 redef class Text
  31
  32     # Is `self` a well-formed BigInt (i.e. parsable via `to_bi`)
  33     #
  34     #     assert "123".is_bi
  35     #     assert "-123".is_bi
  36     #     assert not "0b1011".is_bi
  37     #     assert not "123u8".is_bi
  38     #     assert not "Not a BigInt".is_bi
  39     fun is_bi: Bool do
  40         var pre = prefix("-")
  41         if pre != null then
  42             return pre.text_after.is_dec
  43         else
  44             return is_dec
  45         end
  46     end
  47
  48     # Is `self` a well-formed Ratio (i.e. parsable via `to_r`)
  49     #
  50     #     assert "123".is_r
  51     #     assert "-123".is_r
  52     #     assert "1/2".is_r
  53     #     assert "-1/2".is_r
  54     #     assert not "-1/-2".is_r
  55     #     assert not "0b1011".is_r
  56     #     assert not "123u8".is_r
  57     #     assert not "Not an Ratio".is_r
  58     fun is_r: Bool do
  59         var frac = split_once_on('/')
  60         if frac.length == 2 then
  61             return frac[0].is_bi and frac[1].is_dec
  62         else
  63             return is_bi
  64         end
  65     end
  66
  67     # If `self` contains a BigInt, return the corresponding BigInt
  68     #
  69     #     assert("123".to_bi == 123.to_bi)
  70     #     assert("-123".to_bi == -123.to_bi)
  71     fun to_bi: BigInt do
  72         assert is_bi
  73         var tmp = new NativeMPZ
  74         tmp.set_str(self.to_cstring, 10i32)
  75         return new BigInt(tmp)
  76     end
  77
  78     # If `self` contains a Ratio, return the corresponding Ratio
  79     #
  80     #     assert("123".to_r == 123.to_r)
  81     #     assert("-123".to_r == -123.to_r)
  82     #     assert("1/2".to_r == 0.5.to_r)
  83     #     assert("-1/2".to_r == -0.5.to_r)
  84     fun to_r: Ratio do
  85         assert is_r
  86         var tmp = new NativeMPQ
  87         tmp.set_str self.to_cstring
  88         return new Ratio(tmp)
  89     end
  90 end
  91
  92 redef class Float
  93     redef fun to_bi do
  94         var tmp = new NativeMPZ
  95         tmp.set_d self
  96         return new BigInt(tmp)
  97     end
  98
  99     redef fun to_r do
 100         var tmp = new NativeMPQ
 101         tmp.set_d self
 102         return new Ratio(tmp)
 103     end
 104 end
 105
 106 redef class Int
 107     redef fun to_bi do
 108         var tmp = new NativeMPZ
 109         tmp.set_si self
 110         return new BigInt(tmp)
 111     end
 112
 113     redef fun to_r do
 114         var tmp = new NativeMPQ
 115         tmp.set_si(self, 1)
 116         return new Ratio(tmp)
 117     end
 118 end
 119
 120 # Multi precision Integer numbers.
 121 class BigInt
 122     super Discrete
 123     super Numeric
 124     super FinalizableOnce
 125
 126     redef type OTHER: BigInt
 127
 128     private var val: NativeMPZ
 129
 130     redef fun successor(i) do return self + i.to_bi
 131     redef fun predecessor(i) do return self - i.to_bi
 132
 133     redef fun hash do return self.to_i
 134
 135     redef fun <=>(i) do
 136         var res = val.cmp(i.val)
 137         if (res) < 0 then
 138             return -1
 139         else if (res) > 0 then
 140             return 1
 141         else
 142             return 0
 143         end
 144     end
 145
 146     redef fun ==(i) do return i isa BigInt and (self <=> i) == 0
 147     redef fun <=(i) do return (self <=> i) <= 0
 148     redef fun <(i) do return (self <=> i) < 0
 149     redef fun >=(i) do return (self <=> i) >= 0
 150     redef fun >(i) do return (self <=> i) > 0
 151
 152
 153     #     assert(2.to_bi + 2.to_bi == 4.to_bi)
 154     redef fun +(i) do
 155         var res = new NativeMPZ
 156         val.add(res, i.val)
 157         return new BigInt(res)
 158     end
 159
 160     #     assert(-(2.to_bi) == (-2).to_bi)
 161     redef fun - do
 162         var res = new NativeMPZ
 163         val.neg res
 164         return new BigInt(res)
 165     end
 166
 167     #     assert(2.to_bi - 2.to_bi == 0.to_bi)
 168     redef fun -(i) do
 169         var res = new NativeMPZ
 170         val.sub(res, i.val)
 171         return new BigInt(res)
 172     end
 173
 174     #     assert(2.to_bi * 2.to_bi == 4.to_bi)
 175     redef fun *(i) do
 176         var res = new NativeMPZ
 177         val.mul(res, i.val)
 178         return new BigInt(res)
 179     end
 180
 181     #     assert(3.to_bi / 2.to_bi == 1.to_bi)
 182     redef fun /(i) do
 183         var res = new NativeMPZ
 184         val.tdiv_q(res, i.val)
 185         return new BigInt(res)
 186     end
 187
 188     # Modulo of `self` with `i`.
 189     #
 190     # Finds the remainder of the division of `self` by `i`.
 191     #
 192     #     assert(5.to_bi % 2.to_bi == 1.to_bi)
 193     fun %(i: BigInt): BigInt do
 194         var res = new NativeMPZ
 195         val.mod(res, i.val)
 196         return new BigInt(res)
 197     end
 198
 199     # Returns `self` raised to the power of `e`.
 200     #
 201     #     assert(3.to_bi ** 2 == 9.to_bi)
 202     fun **(e: Int): BigInt do
 203         var res = new NativeMPZ
 204         var pow = new UInt64
 205         pow.set_si e
 206         val.pow_ui(res, pow)
 207         pow.free
 208         return new BigInt(res)
 209     end
 210
 211     # The absolute value of `self`.
 212     #
 213     #     assert((-3).to_bi.abs == 3.to_bi)
 214     fun abs: BigInt do
 215         var res = new NativeMPZ
 216         val.abs res
 217         return new BigInt(res)
 218     end
 219
 220     # Returns the greatest common divisor of `self` and `i`
 221     #
 222     #     assert(15.to_bi.gcd(10.to_bi) == 5.to_bi)
 223     fun gcd(i: BigInt): BigInt do
 224         var res = new NativeMPZ
 225         val.gcd(res, i.val)
 226         return new BigInt(res)
 227     end
 228
 229     # Determine if `self` is a prime number.
 230     # Return 2 if `self` is prime, return 1 if `self` is probably prime and
 231     # return 0 if `self` is definitely not a prime number.
 232     #
 233     # This function begins by trying some divisions with small number to find if
 234     # there is other factors then `self` and one. After that, it uses the
 235     # Miller-Rabin probabilistic primality tests. The probability of a non-prime
 236     # being identified as probably prime with that test is less than
 237     # `4^(-reps)`. It is recommended to use a `reps` value between 15 and 50.
 238     #
 239     #     assert((0x10001).to_bi.probab_prime(15) == 2)
 240     fun probab_prime(reps: Int): Int do
 241         return val.probab_prime_p(reps.to_i32)
 242     end
 243
 244     # Return the next prime number greater than `self`.
 245     # This fonction uses a probabilistic algorithm.
 246     #
 247     #     assert(11.to_bi.next_prime == 13.to_bi)
 248     fun next_prime: BigInt do
 249         var res = new NativeMPZ
 250         val.nextprime res
 251         return new BigInt(res)
 252     end
 253
 254     #     assert(11.to_bi.zero == 0.to_bi)
 255     redef fun zero do return new BigInt(new NativeMPZ)
 256
 257     #     assert(11.to_bi.value_of(4) == 4.to_bi)
 258     redef fun value_of(i) do return i.to_bi
 259
 260     #     assert(11.to_bi.to_i == 11)
 261     redef fun to_i do return val.get_si
 262
 263     #     assert(11.to_bi.to_f == 11.0)
 264     redef fun to_f do return val.get_d
 265
 266     #     assert(11.to_bi.to_s == "11")
 267     redef fun to_s do
 268         var cstr = val.get_str(10.to_i32)
 269         var str = cstr.to_s
 270         cstr.free
 271         return str
 272     end
 273
 274     redef fun to_bi do return self
 275
 276     #     assert(123.to_bi.to_r == 123.to_r)
 277     redef fun to_r do
 278         var tmp = new NativeMPQ
 279         tmp.set_z val
 280         return new Ratio(tmp)
 281     end
 282
 283     #     assert(3.to_bi.distance(6.to_bi) == -3)
 284     redef fun distance(i) do return (self - i).to_i
 285
 286     redef fun finalize_once do val.finalize
 287 end
 288
 289 # Multi precision Rational numbers.
 290 #
 291 #     assert((0.2 + 0.1) == 0.30000000000000004)
 292 #     assert(("1/5".to_r + "1/10".to_r) == "3/10".to_r)
 293 class Ratio
 294     super Numeric
 295     super FinalizableOnce
 296
 297     redef type OTHER: Ratio
 298
 299     private var val: NativeMPQ
 300
 301     redef fun hash do return self.to_i
 302
 303     redef fun <=>(r) do
 304         var res = val.cmp(r.val)
 305         if (res) < 0 then
 306             return -1
 307         else if (res) > 0 then
 308             return 1
 309         else
 310             return 0
 311         end
 312     end
 313
 314     redef fun ==(r) do return r isa Ratio and (self <=> r) == 0
 315     redef fun <=(r) do return (self <=> r) <= 0
 316     redef fun <(r) do return (self <=> r) < 0
 317     redef fun >=(r) do return (self <=> r) >= 0
 318     redef fun >(r) do return (self <=> r) > 0
 319
 320     #     assert("3/2".to_r + "5/2".to_r == 4.to_r)
 321     redef fun +(r) do
 322         var res = new NativeMPQ
 323         val.add(res, r.val)
 324         return new Ratio(res)
 325     end
 326
 327     #     assert( -("1/2".to_r) == ("-1/2").to_r)
 328     redef fun - do
 329         var res = new NativeMPQ
 330         val.neg res
 331         return new Ratio(res)
 332     end
 333
 334     #     assert("5/2".to_r - "3/2".to_r == 1.to_r)
 335     redef fun -(r) do
 336         var res = new NativeMPQ
 337         val.sub(res, r.val)
 338         return new Ratio(res)
 339     end
 340
 341     #     assert("3/2".to_r * 2.to_r == 3.to_r)
 342     redef fun *(r) do
 343         var res = new NativeMPQ
 344         val.mul(res, r.val)
 345         return new Ratio(res)
 346     end
 347
 348     #     assert(3.to_r / 2.to_r == "3/2".to_r)
 349     redef fun /(r) do
 350         var res = new NativeMPQ
 351         val.div(res, r.val)
 352         return new Ratio(res)
 353     end
 354
 355     # The absolute value of `self`.
 356     #
 357     #     assert((-3.to_r).abs == 3.to_r)
 358     #     assert(3.to_r.abs == 3.to_r)
 359     fun abs: Ratio do
 360         var res = new NativeMPQ
 361         val.abs res
 362         return new Ratio(res)
 363     end
 364
 365     #     assert((3.to_r).zero == 0.to_r)
 366     redef fun zero do return new Ratio(new NativeMPQ)
 367
 368     #     assert((3.to_r).value_of(2) == 2.to_r)
 369     redef fun value_of(n) do return n.to_r
 370
 371     #     assert("7/2".to_r.to_i == 3)
 372     redef fun to_i do
 373         var res = new NativeMPZ
 374         val.numref.tdiv_q(res, val.denref)
 375         return res.get_si
 376     end
 377
 378     #     assert(3.to_r.to_f == 3.0)
 379     redef fun to_f do return val.get_d
 380
 381     #     assert(3.to_r.to_s == "3")
 382     redef fun to_s do
 383         var cstr = val.get_str(10i32)
 384         var str = cstr.to_s
 385         cstr.free
 386         return str
 387     end
 388
 389     #     assert("7/2".to_r.to_bi == 3.to_bi)
 390     redef fun to_bi do
 391         var res = new NativeMPZ
 392         val.numref.tdiv_q(res, val.denref)
 393         return new BigInt(res)
 394     end
 395
 396     redef fun to_r do return self
 397
 398     redef fun finalize_once do val.finalize
 399 end