lib/standard/math.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
   4 #
   5 # This file is free software, which comes along with NIT.  This software is
   6 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   7 # without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
   8 # PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
   9 # is kept unaltered, and a notification of the changes is added.
  10 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
  11 # another product.
  12
  13 # Mathematical operations
  14 module math is ldflags "-lm"
  15
  16 import kernel
  17 import collection
  18
  19 in "C header" `{
  20 #include <math.h>
  21 `}
  22
  23 redef class Int
  24         # Returns a random `Int` in `[0 .. self[`.
  25         fun rand: Int is extern "kernel_Int_Int_rand_0"
  26
  27         # Returns the result of a binary AND operation on `self` and `i`
  28         #
  29         #     assert 0x10.bin_and(0x01) == 0
  30         fun bin_and(i: Int): Int is extern "kernel_Int_Int_binand_0"
  31
  32         # Alias of `bin_and`
  33         fun &(i: Int): Int do return bin_and(i)
  34
  35         # Returns the result of a binary OR operation on `self` and `i`
  36         #
  37         #     assert 0x10.bin_or(0x01) == 0x11
  38         fun bin_or(i: Int): Int is extern "kernel_Int_Int_binor_0"
  39
  40         # Alias of `bin_or`
  41         fun |(i: Int): Int do return bin_or(i)
  42
  43         # Returns the result of a binary XOR operation on `self` and `i`
  44         #
  45         #     assert 0x101.bin_xor(0x110) == 0x11
  46         fun bin_xor(i: Int): Int is extern "kernel_Int_Int_binxor_0"
  47
  48         # Alias of `bin_xor`
  49         fun ^(i: Int): Int do return bin_xor(i)
  50
  51         # Returns the 1's complement of `self`
  52         #
  53         #     assert 0x2F.bin_not == -48
  54         fun bin_not: Int is extern "kernel_Int_Int_binnot_0"
  55
  56         # Alias of `bin_not`
  57         fun ~: Int do return bin_not
  58
  59         # Returns the square root of `self`
  60         #
  61         #     assert 16.sqrt == 4
  62         fun sqrt: Int `{ return sqrt(self); `}
  63
  64         # Returns the greatest common divisor of `self` and `o`
  65         #
  66         #     assert 54.gcd(24)   == 6
  67         #     assert -54.gcd(-24) == 6
  68         #     assert 54.gcd(-24)  == -6
  69         #     assert -54.gcd(24)  == -6
  70         #     assert 12.gcd(6)    == 6
  71         fun gcd(o: Int): Int
  72         do
  73                 if self < 0 then return -(-self).gcd(o)
  74                 if o < 0 then return -(self.gcd(-o))
  75                 if self == 0 or o == self then return o
  76                 if o == 0 then return self
  77                 if self.bin_and(1) == 0 then
  78                         if o.bin_and(1) == 1 then
  79                                 return self.rshift(1).gcd(o)
  80                         else
  81                                 return self.rshift(1).gcd(o.rshift(1)).lshift(1)
  82                         end
  83                 end
  84                 if o.bin_and(1) == 0 then return self.gcd(o.rshift(1))
  85                 if self > o then return (self - o).rshift(1).gcd(o)
  86                 return (o - self).rshift(1).gcd(self)
  87         end
  88
  89         # Is `self` even ?
  90         #
  91         #     assert 12.is_even
  92         fun is_even: Bool do return self % 2 == 0
  93
  94         # Is `self` odd ?
  95         #
  96         #     assert not 13.is_even
  97         fun is_odd: Bool do return not is_even
  98
  99         # Is self a prime number ?
 100         #
 101         # assert 3.is_prime
 102         # assert not 1.is_prime
 103         # assert not 12.is_prime
 104         fun is_prime: Bool
 105         do
 106                 if self == 2 then
 107                         return true
 108                 else if self <= 1 or self.is_even then
 109                         return false
 110                 end
 111                 for i in [3..self.sqrt[ do
 112                         if self % i == 0 then return false
 113                 end
 114                 return true
 115         end
 116
 117         # Returns the `self` raised to the power of `e`.
 118         #
 119         #     assert 2 ** 3 == 8
 120         fun **(e: Int): Int
 121         do
 122                 return self.to_f.pow(e.to_f).to_i
 123         end
 124
 125         # The factorial of `self` (aka `self!`)
 126         #
 127         # Returns `1 * 2 * 3 * ... * self-1 * self`
 128         #
 129         #     assert 0.factorial == 1  # by convention for an empty product
 130         #     assert 1.factorial == 1
 131         #     assert 4.factorial == 24
 132         #     assert 9.factorial == 362880
 133         fun factorial: Int
 134         do
 135                 assert self >= 0
 136                 var res = 1
 137                 var n = self
 138                 while n > 0 do
 139                         res = res * n
 140                         n -= 1
 141                 end
 142                 return res
 143         end
 144 end
 145
 146 redef class Byte
 147         # Returns the result of a binary AND operation on `self` and `i`
 148         #
 149         #     assert 0x10.bin_and(0x01) == 0
 150         fun bin_and(i: Byte): Byte `{ return self & i; `}
 151
 152         # Alias of `bin_and`
 153         fun &(i: Byte): Byte do return bin_and(i)
 154
 155         # Returns the result of a binary OR operation on `self` and `i`
 156         #
 157         #     assert 0x10.bin_or(0x01) == 0x11
 158         fun bin_or(i: Byte): Byte `{ return self | i; `}
 159
 160         # Alias of `bin_or`
 161         fun |(i: Byte): Byte do return bin_or(i)
 162
 163         # Returns the result of a binary XOR operation on `self` and `i`
 164         #
 165         #     assert 0x101.bin_xor(0x110) == 0x11
 166         fun bin_xor(i: Byte): Byte `{ return self ^ i; `}
 167
 168         # Alias of `bin_xor`
 169         fun ^(i: Byte): Byte do return bin_xor(i)
 170
 171         # Returns the 1's complement of `self`
 172         #
 173         #     assert 0x2F.bin_not == -48
 174         fun bin_not: Byte `{ return ~self; `}
 175
 176         # Alias of `bin_not`
 177         fun ~: Byte do return bin_not
 178 end
 179
 180 redef class Float
 181
 182         # Returns the non-negative square root of `self`.
 183         #
 184         #     assert 9.0.sqrt == 3.0
 185         #     #assert 3.0.sqrt == 1.732
 186         #     assert 1.0.sqrt == 1.0
 187         #     assert 0.0.sqrt == 0.0
 188         fun sqrt: Float is extern "kernel_Float_Float_sqrt_0"
 189
 190         # Computes the cosine of `self` (expressed in radians).
 191         #
 192         #     #assert pi.cos == -1.0
 193         fun cos: Float is extern "kernel_Float_Float_cos_0"
 194
 195         # Computes the sine of `self` (expressed in radians).
 196         #
 197         #     #assert pi.sin == 0.0
 198         fun sin: Float is extern "kernel_Float_Float_sin_0"
 199
 200         # Computes the cosine of x (expressed in radians).
 201         #
 202         #     #assert 0.0.tan == 0.0
 203         fun tan: Float is extern "kernel_Float_Float_tan_0"
 204
 205         # Computes the arc cosine of `self`.
 206         #
 207         #     #assert 0.0.acos == pi / 2.0
 208         fun acos: Float is extern "kernel_Float_Float_acos_0"
 209
 210         # Computes the arc sine of `self`.
 211         #
 212         #     #assert 1.0.asin == pi / 2.0
 213         fun asin: Float is extern "kernel_Float_Float_asin_0"
 214
 215         # Computes the arc tangent of `self`.
 216         #
 217         #     #assert 0.0.tan == 0.0
 218         fun atan: Float is extern "kernel_Float_Float_atan_0"
 219
 220         # Returns the absolute value of `self`.
 221         #
 222         #     assert 12.0.abs == 12.0
 223         #     assert (-34.56).abs == 34.56
 224         #     assert -34.56.abs == -34.56
 225         fun abs: Float `{ return fabs(self); `}
 226
 227         # Returns `self` raised at `e` power.
 228         #
 229         #     #assert 2.0.pow(0.0) == 1.0
 230         #     #assert 2.0.pow(3.0) == 8.0
 231         #     #assert 0.0.pow(9.0) == 0.0
 232         fun pow(e: Float): Float is extern "kernel_Float_Float_pow_1"
 233
 234         # Natural logarithm of `self`.
 235         #
 236         #     assert 0.0.log.is_inf == -1
 237         #     #assert 1.0.log == 0.0
 238         fun log: Float is extern "kernel_Float_Float_log_0"
 239
 240         # Logarithm of `self` to base `base`.
 241         #
 242         #     assert 100.0.log_base(10.0) == 2.0
 243         #     assert 256.0.log_base(2.0) == 8.0
 244         fun log_base(base: Float): Float do return log/base.log
 245
 246         # Returns *e* raised to `self`.
 247         fun exp: Float is extern "kernel_Float_Float_exp_0"
 248
 249         #     assert 1.1.ceil == 2.0
 250         #     assert 1.9.ceil == 2.0
 251         #     assert 2.0.ceil == 2.0
 252         #     assert (-1.5).ceil == -1.0
 253         fun ceil: Float `{ return ceil(self); `}
 254
 255         #     assert 1.1.floor == 1.0
 256         #     assert 1.9.floor == 1.0
 257         #     assert 2.0.floor == 2.0
 258         #     assert (-1.5).floor == -2.0
 259         fun floor: Float `{ return floor(self); `}
 260
 261         # Rounds the value of a float to its nearest integer value
 262         #
 263         #     assert 1.67.round == 2.0
 264         #     assert 1.34.round == 1.0
 265         #     assert -1.34.round == -1.0
 266         #     assert -1.67.round == -2.0
 267         fun round: Float is extern "round"
 268
 269         # Returns a random `Float` in `[0.0 .. self[`.
 270         fun rand: Float is extern "kernel_Float_Float_rand_0"
 271
 272         # Returns the euclidean distance from `b`.
 273         fun hypot_with(b : Float): Float is extern "hypotf"
 274
 275         # Returns true is self is not a number.
 276         fun is_nan: Bool is extern "isnan"
 277
 278         # Is the float an infinite value
 279         # this function returns:
 280         #
 281         #  * 1 if self is positive infinity
 282         #  * -1 if self is negative infinity
 283         #  * 0 otherwise
 284         fun is_inf: Int do
 285                 if is_inf_extern then
 286                         if self < 0.0 then return -1
 287                         return 1
 288                 end
 289                 return 0
 290         end
 291
 292         private fun is_inf_extern: Bool is extern "isinf"
 293
 294         # Linear interpolation between `a` and `b` using `self` as weight
 295         #
 296         # ~~~
 297         # assert  0.0.lerp(0.0, 128.0) == 0.0
 298         # assert  0.5.lerp(0.0, 128.0) == 64.0
 299         # assert  1.0.lerp(0.0, 128.0) == 128.0
 300         # assert -0.5.lerp(0.0, 128.0) == -64.0
 301         # ~~~
 302         fun lerp(a, b: Float): Float do return (1.0 - self) * a + self * b
 303 end
 304
 305 redef class Collection[ E ]
 306         # Return a random element form the collection
 307         # There must be at least one element in the collection
 308         #
 309         # ~~~
 310         # var x = [1,2,3].rand
 311         # assert x == 1 or x == 2 or x == 3
 312         # ~~~
 313         fun rand: E
 314         do
 315                 if is_empty then abort
 316                 var rand_index = length.rand
 317
 318                 for e in self do
 319                         if rand_index == 0 then return e
 320                         rand_index -= 1
 321                 end
 322                 abort
 323         end
 324
 325         # Return a new array made of elements in a random order.
 326         #
 327         # ~~~
 328         # var a = [1,2,1].to_shuffle
 329         # assert a == [1,1,2] or a == [1,2,1] or a == [2,1,1]
 330         # ~~~
 331         fun to_shuffle: Array[E]
 332         do
 333                 var res = self.to_a
 334                 res.shuffle
 335                 return res
 336         end
 337 end
 338
 339 redef class SequenceRead[E]
 340         # Optimized for large collections using `[]`
 341         redef fun rand
 342         do
 343                 assert not is_empty
 344                 return self[length.rand]
 345         end
 346 end
 347
 348 redef class AbstractArray[E]
 349         # Reorder randomly the elements in self.
 350         #
 351         # ~~~
 352         # var a = new Array[Int]
 353         #
 354         # a.shuffle
 355         # assert a.is_empty
 356         #
 357         # a.add 1
 358         # a.shuffle
 359         # assert a == [1]
 360         #
 361         # a.add 2
 362         # a.shuffle
 363         # assert a == [1,2] or a == [2,1]
 364         # ~~~
 365         #
 366         # ENSURE self.shuffle.has_exactly(old(self))
 367         fun shuffle
 368         do
 369                 for i in [0..length[ do
 370                         var j = i + (length-i).rand
 371                         var tmp = self[i]
 372                         self[i] = self[j]
 373                         self[j] = tmp
 374                 end
 375         end
 376 end
 377
 378 redef class Sys
 379         init
 380         do
 381                 srand
 382         end
 383 end
 384
 385 # Computes the arc tangent given `x` and `y`.
 386 #
 387 #     assert atan2(-0.0, 1.0) == -0.0
 388 #     assert atan2(0.0, 1.0) == 0.0
 389 fun atan2(x: Float, y: Float): Float is extern "kernel_Any_Any_atan2_2"
 390
 391 # Approximate value of **pi**.
 392 fun pi: Float is extern "kernel_Any_Any_pi_0"
 393
 394 # Initialize the pseudo-random generator with the given seed.
 395 # The pseudo-random generator is used by the method `rand` and other to generate sequence of numbers.
 396 # These sequences are repeatable by calling `srand_from` with a same seed value.
 397 #
 398 # ~~~~
 399 # srand_from(0)
 400 # var a = 10.rand
 401 # var b = 100.rand
 402 # srand_from(0)
 403 # assert 10.rand == a
 404 # assert 100.rand == b
 405 # ~~~~
 406 fun srand_from(x: Int) is extern "kernel_Any_Any_srand_from_1"
 407
 408 # Reinitialize the pseudo-random generator used by the method `rand` and other.
 409 # This method is automatically invoked at the begin of the program, so usually, there is no need to manually invoke it.
 410 # The only exception is in conjunction with `srand_from` to reset the pseudo-random generator.
 411 fun srand is extern "kernel_Any_Any_srand_0"