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
  15
  16 import kernel
  17 import collection
  18
  19 in "C header" `{
  20         #include <stdlib.h>
  21         #include <math.h>
  22         #include <time.h>
  23 `}
  24
  25 redef class Int
  26         # Returns a random `Int` in `[0 .. self[`.
  27         fun rand: Int `{
  28                 return (long)(((double)self)*rand()/(RAND_MAX+1.0));
  29         `}
  30
  31         # Returns the result of a binary AND operation on `self` and `i`
  32         #
  33         #     assert 0x10.bin_and(0x01) == 0
  34         fun bin_and(i: Int): Int `{ return self & i; `}
  35
  36         # Returns the result of a binary OR operation on `self` and `i`
  37         #
  38         #     assert 0x10.bin_or(0x01) == 0x11
  39         fun bin_or(i: Int): Int `{ return self | i; `}
  40
  41         # Returns the result of a binary XOR operation on `self` and `i`
  42         #
  43         #     assert 0x101.bin_xor(0x110) == 0x11
  44         fun bin_xor(i: Int): Int `{ return self ^ i; `}
  45
  46         # Returns the 1's complement of `self`
  47         #
  48         #     assert 0x2F.bin_not == -48
  49         fun bin_not: Int `{ return ~self; `}
  50
  51         # Returns the square root of `self`
  52         #
  53         #     assert 16.sqrt == 4
  54         fun sqrt: Int `{ return sqrt(self); `}
  55
  56         # Returns the greatest common divisor of `self` and `o`
  57         #
  58         #     assert 54.gcd(24)   == 6
  59         #     assert -54.gcd(-24) == 6
  60         #     assert 54.gcd(-24)  == -6
  61         #     assert -54.gcd(24)  == -6
  62         #     assert 12.gcd(6)    == 6
  63         fun gcd(o: Int): Int
  64         do
  65                 if self < 0 then return -(-self).gcd(o)
  66                 if o < 0 then return -(self.gcd(-o))
  67                 if self == 0 or o == self then return o
  68                 if o == 0 then return self
  69                 if self.bin_and(1) == 0 then
  70                         if o.bin_and(1) == 1 then
  71                                 return self.rshift(1).gcd(o)
  72                         else
  73                                 return self.rshift(1).gcd(o.rshift(1)).lshift(1)
  74                         end
  75                 end
  76                 if o.bin_and(1) == 0 then return self.gcd(o.rshift(1))
  77                 if self > o then return (self - o).rshift(1).gcd(o)
  78                 return (o - self).rshift(1).gcd(self)
  79         end
  80
  81         # Is `self` even ?
  82         #
  83         #     assert 12.is_even
  84         fun is_even: Bool do return self % 2 == 0
  85
  86         # Is `self` odd ?
  87         #
  88         #     assert not 13.is_even
  89         fun is_odd: Bool do return not is_even
  90
  91         # Returns the `self` raised to the power of `e`.
  92         #
  93         #     assert 2 ** 3 == 8
  94         fun **(e: Int): Int
  95         do
  96                 return self.to_f.pow(e.to_f).to_i
  97         end
  98
  99         # The factorial of `self` (aka `self!`)
 100         #
 101         # Returns `1 * 2 * 3 * ... * self-1 * self`
 102         #
 103         #     assert 0.factorial == 1  # by convention for an empty product
 104         #     assert 1.factorial == 1
 105         #     assert 4.factorial == 24
 106         #     assert 9.factorial == 362880
 107         fun factorial: Int
 108         do
 109                 assert self >= 0
 110                 var res = 1
 111                 var n = self
 112                 while n > 0 do
 113                         res = res * n
 114                         n -= 1
 115                 end
 116                 return res
 117         end
 118 end
 119
 120 redef class Float
 121
 122         # Returns the non-negative square root of `self`.
 123         #
 124         #     assert 9.0.sqrt == 3.0
 125         #     #assert 3.0.sqrt == 1.732
 126         #     assert 1.0.sqrt == 1.0
 127         #     assert 0.0.sqrt == 0.0
 128         fun sqrt: Float `{ return sqrt(self); `}
 129
 130         # Computes the cosine of `self` (expressed in radians).
 131         #
 132         #     #assert pi.cos == -1.0
 133         fun cos: Float `{ return cos(self); `}
 134
 135         # Computes the sine of `self` (expressed in radians).
 136         #
 137         #     #assert pi.sin == 0.0
 138         fun sin: Float `{ return sin(self); `}
 139
 140         # Computes the cosine of x (expressed in radians).
 141         #
 142         #     #assert 0.0.tan == 0.0
 143         fun tan: Float `{ return tan(self); `}
 144
 145         # Computes the arc cosine of `self`.
 146         #
 147         #     #assert 0.0.acos == pi / 2.0
 148         fun acos: Float `{ return acos(self); `}
 149
 150         # Computes the arc sine of `self`.
 151         #
 152         #     #assert 1.0.asin == pi / 2.0
 153         fun asin: Float `{ return asin(self); `}
 154
 155         # Computes the arc tangent of `self`.
 156         #
 157         #     #assert 0.0.tan == 0.0
 158         fun atan: Float `{ return atan(self); `}
 159
 160         # Returns the absolute value of `self`.
 161         #
 162         #     assert 12.0.abs == 12.0
 163         #     assert (-34.56).abs == 34.56
 164         #     assert -34.56.abs == -34.56
 165         fun abs: Float `{ return fabs(self); `}
 166
 167         # Returns `self` raised at `e` power.
 168         #
 169         #     #assert 2.0.pow(0.0) == 1.0
 170         #     #assert 2.0.pow(3.0) == 8.0
 171         #     #assert 0.0.pow(9.0) == 0.0
 172         fun pow(e: Float): Float `{ return pow(self, e); `}
 173
 174         # Natural logarithm of `self`.
 175         #
 176         #     assert 0.0.log.is_inf == -1
 177         #     #assert 1.0.log == 0.0
 178         fun log: Float `{ return log(self); `}
 179
 180         # Logarithm of `self` to base `base`.
 181         #
 182         #     assert 100.0.log_base(10.0) == 2.0
 183         #     assert 256.0.log_base(2.0) == 8.0
 184         fun log_base(base: Float): Float do return log/base.log
 185
 186         # Returns *e* raised to `self`.
 187         fun exp: Float `{ return exp(self); `}
 188
 189         #     assert 1.1.ceil == 2.0
 190         #     assert 1.9.ceil == 2.0
 191         #     assert 2.0.ceil == 2.0
 192         #     assert (-1.5).ceil == -1.0
 193         fun ceil: Float `{ return ceil(self); `}
 194
 195         #     assert 1.1.floor == 1.0
 196         #     assert 1.9.floor == 1.0
 197         #     assert 2.0.floor == 2.0
 198         #     assert (-1.5).floor == -2.0
 199         fun floor: Float `{ return floor(self); `}
 200
 201         # Rounds the value of a float to its nearest integer value
 202         #
 203         #     assert 1.67.round == 2.0
 204         #     assert 1.34.round == 1.0
 205         #     assert -1.34.round == -1.0
 206         #     assert -1.67.round == -2.0
 207         fun round: Float `{ return round(self); `}
 208
 209         # Returns a random `Float` in `[0.0 .. self[`.
 210         fun rand: Float `{ return ((self)*rand())/(RAND_MAX+1.0); `}
 211
 212         # Returns the euclidean distance from `b`.
 213         fun hypot_with(b: Float): Float `{ return hypotf(self, b); `}
 214
 215         # Returns true is self is not a number.
 216         fun is_nan: Bool `{ return isnan(self); `}
 217
 218         # Is the float an infinite value
 219         # this function returns:
 220         #
 221         #  * 1 if self is positive infinity
 222         #  * -1 if self is negative infinity
 223         #  * 0 otherwise
 224         fun is_inf: Int do
 225                 if native_is_inf then
 226                         if self < 0.0 then return -1
 227                         return 1
 228                 end
 229                 return 0
 230         end
 231
 232         private fun native_is_inf: Bool `{ return isinf(self); `}
 233
 234         # Linear interpolation between `a` and `b` using `self` as weight
 235         #
 236         # ~~~
 237         # assert  0.0.lerp(0.0, 128.0) == 0.0
 238         # assert  0.5.lerp(0.0, 128.0) == 64.0
 239         # assert  1.0.lerp(0.0, 128.0) == 128.0
 240         # assert -0.5.lerp(0.0, 128.0) == -64.0
 241         # ~~~
 242         fun lerp(a, b: Float): Float do return (1.0 - self) * a + self * b
 243 end
 244
 245 redef class Collection[ E ]
 246         # Return a random element form the collection
 247         # There must be at least one element in the collection
 248         #
 249         # ~~~
 250         # var x = [1,2,3].rand
 251         # assert x == 1 or x == 2 or x == 3
 252         # ~~~
 253         fun rand: E
 254         do
 255                 if is_empty then abort
 256                 var rand_index = length.rand
 257
 258                 for e in self do
 259                         if rand_index == 0 then return e
 260                         rand_index -= 1
 261                 end
 262                 abort
 263         end
 264
 265         # Return a new array made of elements in a random order.
 266         #
 267         # ~~~
 268         # var a = [1,2,1].to_shuffle
 269         # assert a == [1,1,2] or a == [1,2,1] or a == [2,1,1]
 270         # ~~~
 271         fun to_shuffle: Array[E]
 272         do
 273                 var res = self.to_a
 274                 res.shuffle
 275                 return res
 276         end
 277 end
 278
 279 redef class SequenceRead[E]
 280         # Optimized for large collections using `[]`
 281         redef fun rand
 282         do
 283                 assert not is_empty
 284                 return self[length.rand]
 285         end
 286 end
 287
 288 redef class AbstractArray[E]
 289         # Reorder randomly the elements in self.
 290         #
 291         # ~~~
 292         # var a = new Array[Int]
 293         #
 294         # a.shuffle
 295         # assert a.is_empty
 296         #
 297         # a.add 1
 298         # a.shuffle
 299         # assert a == [1]
 300         #
 301         # a.add 2
 302         # a.shuffle
 303         # assert a == [1,2] or a == [2,1]
 304         # ~~~
 305         #
 306         # ENSURE self.shuffle.has_exactly(old(self))
 307         fun shuffle
 308         do
 309                 for i in [0..length[ do
 310                         var j = i + (length-i).rand
 311                         var tmp = self[i]
 312                         self[i] = self[j]
 313                         self[j] = tmp
 314                 end
 315         end
 316 end
 317
 318 redef class Sys
 319         init
 320         do
 321                 srand
 322         end
 323 end
 324
 325 # Computes the arc tangent given `x` and `y`.
 326 #
 327 #     assert atan2(-0.0, 1.0) == -0.0
 328 #     assert atan2(0.0, 1.0) == 0.0
 329 fun atan2(x: Float, y: Float): Float `{ return atan2(x, y); `}
 330
 331 # Approximate value of **pi**.
 332 fun pi: Float do return 3.14159265
 333
 334 # Initialize the pseudo-random generator with the given seed.
 335 # The pseudo-random generator is used by the method `rand` and other to generate sequence of numbers.
 336 # These sequences are repeatable by calling `srand_from` with a same seed value.
 337 #
 338 # ~~~~
 339 # srand_from(0)
 340 # var a = 10.rand
 341 # var b = 100.rand
 342 # srand_from(0)
 343 # assert 10.rand == a
 344 # assert 100.rand == b
 345 # ~~~~
 346 fun srand_from(x: Int) `{ srand(x); `}
 347
 348 # Reinitialize the pseudo-random generator used by the method `rand` and other.
 349 # This method is automatically invoked at the begin of the program, so usually, there is no need to manually invoke it.
 350 # The only exception is in conjunction with `srand_from` to reset the pseudo-random generator.
 351 fun srand `{ srand(time(NULL)); `}