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 <stdlib.h>
  21         #include <math.h>
  22         #include <time.h>
  23 `}
  24
  25 in "C" `{
  26         /* Is rand shortcut? */
  27         static int nit_rand_seeded;
  28         /* Current rand seed if seeded */
  29         static unsigned int nit_rand_seed;
  30
  31         #define NIT_RAND_MAX 0x7fffffff
  32
  33         /* This algorithm is mentioned in the ISO C standard, here extended
  34         for 32 bits.  */
  35         static int
  36         nit_rand(void) {
  37                 unsigned int next = nit_rand_seed;
  38                 int result;
  39
  40                 next *= 1103515245;
  41                 next += 12345;
  42                 result = (unsigned int) (next / 65536) % 2048;
  43
  44                 next *= 1103515245;
  45                 next += 12345;
  46                 result <<= 10;
  47                 result ^= (unsigned int) (next / 65536) % 1024;
  48
  49                 next *= 1103515245;
  50                 next += 12345;
  51                 result <<= 10;
  52                 result ^= (unsigned int) (next / 65536) % 1024;
  53
  54                 nit_rand_seed = next;
  55
  56                 return result;
  57         }
  58 `}
  59
  60 redef class Int
  61         # Returns a random `Int` in `[0 .. self[`.
  62         fun rand: Int `{
  63                 if (nit_rand_seeded) return (long)(((double)self)*nit_rand()/(NIT_RAND_MAX+1.0));
  64                 return (long)(((double)self)*rand()/(RAND_MAX+1.0));
  65         `}
  66
  67         # Returns the result of a binary AND operation on `self` and `i`
  68         #
  69         #     assert 0x10.bin_and(0x01) == 0
  70         fun bin_and(i: Int): Int `{ return self & i; `}
  71
  72         # Alias of `bin_and`
  73         fun &(i: Int): Int do return bin_and(i)
  74
  75         # Returns the result of a binary OR operation on `self` and `i`
  76         #
  77         #     assert 0x10.bin_or(0x01) == 0x11
  78         fun bin_or(i: Int): Int `{ return self | i; `}
  79
  80         # Alias of `bin_or`
  81         fun |(i: Int): Int do return bin_or(i)
  82
  83         # Returns the result of a binary XOR operation on `self` and `i`
  84         #
  85         #     assert 0x101.bin_xor(0x110) == 0x11
  86         fun bin_xor(i: Int): Int `{ return self ^ i; `}
  87
  88         # Alias of `bin_xor`
  89         fun ^(i: Int): Int do return bin_xor(i)
  90
  91         # Returns the 1's complement of `self`
  92         #
  93         #     assert 0x2F.bin_not == -48
  94         fun bin_not: Int `{ return ~self; `}
  95
  96         # Alias of `bin_not`
  97         fun ~: Int do return bin_not
  98
  99         # Returns the square root of `self`
 100         #
 101         #     assert 16.sqrt == 4
 102         fun sqrt: Int `{ return sqrt(self); `}
 103
 104         # Returns the greatest common divisor of `self` and `o`
 105         #
 106         #     assert 54.gcd(24)   == 6
 107         #     assert -54.gcd(-24) == 6
 108         #     assert 54.gcd(-24)  == -6
 109         #     assert -54.gcd(24)  == -6
 110         #     assert 12.gcd(6)    == 6
 111         fun gcd(o: Int): Int
 112         do
 113                 if self < 0 then return -(-self).gcd(o)
 114                 if o < 0 then return -(self.gcd(-o))
 115                 if self == 0 or o == self then return o
 116                 if o == 0 then return self
 117                 if self.bin_and(1) == 0 then
 118                         if o.bin_and(1) == 1 then
 119                                 return (self >> 1).gcd(o)
 120                         else
 121                                 return (self >> 1).gcd(o >> 1) << 1
 122                         end
 123                 end
 124                 if o & 1 == 0 then return self.gcd(o >> 1)
 125                 if self > o then return ((self - o) >> 1).gcd(o)
 126                 return ((o - self) >> 1).gcd(self)
 127         end
 128
 129         # Is `self` even ?
 130         #
 131         #     assert 12.is_even
 132         fun is_even: Bool do return self % 2 == 0
 133
 134         # Is `self` odd ?
 135         #
 136         #     assert not 13.is_even
 137         fun is_odd: Bool do return not is_even
 138
 139         # Is self a prime number ?
 140         #
 141         # assert 3.is_prime
 142         # assert not 1.is_prime
 143         # assert not 12.is_prime
 144         fun is_prime: Bool
 145         do
 146                 if self == 2 then
 147                         return true
 148                 else if self <= 1 or self.is_even then
 149                         return false
 150                 end
 151                 for i in [3..self.sqrt[ do
 152                         if self % i == 0 then return false
 153                 end
 154                 return true
 155         end
 156
 157         # Returns the `self` raised to the power of `e`.
 158         #
 159         #     assert 2 ** 3 == 8
 160         fun **(e: Int): Int
 161         do
 162                 return self.to_f.pow(e.to_f).to_i
 163         end
 164
 165         # The factorial of `self` (aka `self!`)
 166         #
 167         # Returns `1 * 2 * 3 * ... * self-1 * self`
 168         #
 169         #     assert 0.factorial == 1  # by convention for an empty product
 170         #     assert 1.factorial == 1
 171         #     assert 4.factorial == 24
 172         #     assert 9.factorial == 362880
 173         fun factorial: Int
 174         do
 175                 assert self >= 0
 176                 var res = 1
 177                 var n = self
 178                 while n > 0 do
 179                         res = res * n
 180                         n -= 1
 181                 end
 182                 return res
 183         end
 184 end
 185
 186 redef class Byte
 187         # Returns the result of a binary AND operation on `self` and `i`
 188         #
 189         #     assert 0x10.bin_and(0x01) == 0
 190         fun bin_and(i: Byte): Byte `{ return self & i; `}
 191
 192         # Alias of `bin_and`
 193         fun &(i: Byte): Byte do return bin_and(i)
 194
 195         # Returns the result of a binary OR operation on `self` and `i`
 196         #
 197         #     assert 0x10.bin_or(0x01) == 0x11
 198         fun bin_or(i: Byte): Byte `{ return self | i; `}
 199
 200         # Alias of `bin_or`
 201         fun |(i: Byte): Byte do return bin_or(i)
 202
 203         # Returns the result of a binary XOR operation on `self` and `i`
 204         #
 205         #     assert 0x101.bin_xor(0x110) == 0x11
 206         fun bin_xor(i: Byte): Byte `{ return self ^ i; `}
 207
 208         # Alias of `bin_xor`
 209         fun ^(i: Byte): Byte do return bin_xor(i)
 210
 211         # Returns the 1's complement of `self`
 212         #
 213         #     assert 0x2F.bin_not == -48
 214         fun bin_not: Byte `{ return ~self; `}
 215
 216         # Alias of `bin_not`
 217         fun ~: Byte do return bin_not
 218 end
 219
 220 redef class Float
 221
 222         # Returns the non-negative square root of `self`.
 223         #
 224         #     assert 9.0.sqrt == 3.0
 225         #     #assert 3.0.sqrt == 1.732
 226         #     assert 1.0.sqrt == 1.0
 227         #     assert 0.0.sqrt == 0.0
 228         fun sqrt: Float `{ return sqrt(self); `}
 229
 230         # Computes the cosine of `self` (expressed in radians).
 231         #
 232         #     #assert pi.cos == -1.0
 233         fun cos: Float `{ return cos(self); `}
 234
 235         # Computes the sine of `self` (expressed in radians).
 236         #
 237         #     #assert pi.sin == 0.0
 238         fun sin: Float `{ return sin(self); `}
 239
 240         # Computes the cosine of x (expressed in radians).
 241         #
 242         #     #assert 0.0.tan == 0.0
 243         fun tan: Float `{ return tan(self); `}
 244
 245         # Computes the arc cosine of `self`.
 246         #
 247         #     #assert 0.0.acos == pi / 2.0
 248         fun acos: Float `{ return acos(self); `}
 249
 250         # Computes the arc sine of `self`.
 251         #
 252         #     #assert 1.0.asin == pi / 2.0
 253         fun asin: Float `{ return asin(self); `}
 254
 255         # Computes the arc tangent of `self`.
 256         #
 257         #     #assert 0.0.tan == 0.0
 258         fun atan: Float `{ return atan(self); `}
 259
 260         # Returns the absolute value of `self`.
 261         #
 262         #     assert 12.0.abs == 12.0
 263         #     assert (-34.56).abs == 34.56
 264         #     assert -34.56.abs == -34.56
 265         fun abs: Float `{ return fabs(self); `}
 266
 267         # Returns `self` raised at `e` power.
 268         #
 269         #     #assert 2.0.pow(0.0) == 1.0
 270         #     #assert 2.0.pow(3.0) == 8.0
 271         #     #assert 0.0.pow(9.0) == 0.0
 272         fun pow(e: Float): Float `{ return pow(self, e); `}
 273
 274         # Natural logarithm of `self`.
 275         #
 276         #     assert 0.0.log.is_inf == -1
 277         #     #assert 1.0.log == 0.0
 278         fun log: Float `{ return log(self); `}
 279
 280         # Logarithm of `self` to base `base`.
 281         #
 282         #     assert 100.0.log_base(10.0) == 2.0
 283         #     assert 256.0.log_base(2.0) == 8.0
 284         fun log_base(base: Float): Float do return log/base.log
 285
 286         # Returns *e* raised to `self`.
 287         fun exp: Float `{ return exp(self); `}
 288
 289         #     assert 1.1.ceil == 2.0
 290         #     assert 1.9.ceil == 2.0
 291         #     assert 2.0.ceil == 2.0
 292         #     assert (-1.5).ceil == -1.0
 293         fun ceil: Float `{ return ceil(self); `}
 294
 295         #     assert 1.1.floor == 1.0
 296         #     assert 1.9.floor == 1.0
 297         #     assert 2.0.floor == 2.0
 298         #     assert (-1.5).floor == -2.0
 299         fun floor: Float `{ return floor(self); `}
 300
 301         # Rounds the value of a float to its nearest integer value
 302         #
 303         #     assert 1.67.round == 2.0
 304         #     assert 1.34.round == 1.0
 305         #     assert -1.34.round == -1.0
 306         #     assert -1.67.round == -2.0
 307         fun round: Float `{ return round(self); `}
 308
 309         # Returns a random `Float` in `[0.0 .. self[`.
 310         fun rand: Float `{
 311                 if (nit_rand_seeded) return ((self)*nit_rand())/(NIT_RAND_MAX+1.0);
 312                 return ((self)*rand())/(RAND_MAX+1.0);
 313         `}
 314
 315         # Returns the euclidean distance from `b`.
 316         fun hypot_with(b: Float): Float `{ return hypotf(self, b); `}
 317
 318         # Returns true is self is not a number.
 319         #
 320         # As `nan != nan`, `is_nan` should be used to test if a float is the special *not a number* value.
 321         #
 322         # ~~~
 323         # assert nan != nan # By IEEE 754
 324         # assert nan.is_nan
 325         # assert not 10.0.is_nan
 326         # ~~~
 327         fun is_nan: Bool `{ return isnan(self); `}
 328
 329         # Is the float an infinite value
 330         # this function returns:
 331         #
 332         #  * 1 if self is positive infinity
 333         #  * -1 if self is negative infinity
 334         #  * 0 otherwise
 335         #
 336         # ~~~
 337         # assert 10.0.is_inf == 0
 338         # assert inf.is_inf == 1
 339         # assert (-inf).is_inf == -1
 340         # ~~~
 341         fun is_inf: Int do
 342                 if native_is_inf then
 343                         if self < 0.0 then return -1
 344                         return 1
 345                 end
 346                 return 0
 347         end
 348
 349         private fun native_is_inf: Bool `{ return isinf(self); `}
 350
 351         # Linear interpolation between `a` and `b` using `self` as weight
 352         #
 353         # ~~~
 354         # assert  0.0.lerp(0.0, 128.0) == 0.0
 355         # assert  0.5.lerp(0.0, 128.0) == 64.0
 356         # assert  1.0.lerp(0.0, 128.0) == 128.0
 357         # assert -0.5.lerp(0.0, 128.0) == -64.0
 358         # ~~~
 359         fun lerp(a, b: Float): Float do return (1.0 - self) * a + self * b
 360 end
 361
 362 # Positive float infinite (IEEE 754)
 363 #
 364 #     assert inf > 10.0
 365 #     assert inf.is_inf == 1
 366 #
 367 # `inf` follows the arithmetic of infinites
 368 #
 369 #     assert (inf - 1.0) == inf
 370 #     assert (inf - inf).is_nan
 371 #
 372 # The negative infinite can be used as `-inf`.
 373 #
 374 #     assert -inf < -10.0
 375 #     assert (-inf).is_inf == -1
 376 fun inf: Float do return 1.0 / 0.0
 377
 378 # Not a Number, representation of an undefined or unrepresentable float (IEEE 754).
 379 #
 380 # `nan` is not comparable with itself, you should use `Float::is_nan` to test it.
 381 #
 382 # ~~~
 383 # assert nan.is_nan
 384 # assert nan != nan # By IEEE 754
 385 # ~~~
 386 #
 387 # `nan` is the quiet result of some undefined operations.
 388 #
 389 # ~~~
 390 # assert (1.0 + nan).is_nan
 391 # assert (0.0 / 0.0).is_nan
 392 # assert (inf - inf).is_nan
 393 # assert (inf / inf).is_nan
 394 # assert (-1.0).sqrt.is_nan
 395 # ~~~
 396 fun nan: Float do return 0.0 / 0.0
 397
 398 redef class Collection[ E ]
 399         # Return a random element form the collection
 400         # There must be at least one element in the collection
 401         #
 402         # ~~~
 403         # var x = [1,2,3].rand
 404         # assert x == 1 or x == 2 or x == 3
 405         # ~~~
 406         fun rand: E
 407         do
 408                 if is_empty then abort
 409                 var rand_index = length.rand
 410
 411                 for e in self do
 412                         if rand_index == 0 then return e
 413                         rand_index -= 1
 414                 end
 415                 abort
 416         end
 417
 418         # Return a new array made of elements in a random order.
 419         #
 420         # ~~~
 421         # var a = [1,2,1].to_shuffle
 422         # assert a == [1,1,2] or a == [1,2,1] or a == [2,1,1]
 423         # ~~~
 424         fun to_shuffle: Array[E]
 425         do
 426                 var res = self.to_a
 427                 res.shuffle
 428                 return res
 429         end
 430 end
 431
 432 redef class SequenceRead[E]
 433         # Optimized for large collections using `[]`
 434         redef fun rand
 435         do
 436                 assert not is_empty
 437                 return self[length.rand]
 438         end
 439 end
 440
 441 redef class AbstractArray[E]
 442         # Reorder randomly the elements in self.
 443         #
 444         # ~~~
 445         # var a = new Array[Int]
 446         #
 447         # a.shuffle
 448         # assert a.is_empty
 449         #
 450         # a.add 1
 451         # a.shuffle
 452         # assert a == [1]
 453         #
 454         # a.add 2
 455         # a.shuffle
 456         # assert a == [1,2] or a == [2,1]
 457         # ~~~
 458         #
 459         # ENSURE self.shuffle.has_exactly(old(self))
 460         fun shuffle
 461         do
 462                 for i in [0..length[ do
 463                         var j = i + (length-i).rand
 464                         var tmp = self[i]
 465                         self[i] = self[j]
 466                         self[j] = tmp
 467                 end
 468         end
 469 end
 470
 471 redef class Sys
 472         init
 473         do
 474                 srand
 475         end
 476 end
 477
 478 # Computes the arc tangent given `x` and `y`.
 479 #
 480 #     assert atan2(-0.0, 1.0) == -0.0
 481 #     assert atan2(0.0, 1.0) == 0.0
 482 fun atan2(x: Float, y: Float): Float `{ return atan2(x, y); `}
 483
 484 # Approximate value of **pi**.
 485 fun pi: Float do return 3.14159265
 486
 487 # Initialize the pseudo-random generator with the given seed.
 488 # The pseudo-random generator is used by the method `rand` and other to generate sequence of numbers.
 489 # These sequences are repeatable by calling `srand_from` with a same seed value.
 490 #
 491 # ~~~~
 492 # srand_from(0)
 493 # var a = 10.rand
 494 # var b = 100.rand
 495 # srand_from(0)
 496 # assert 10.rand == a
 497 # assert 100.rand == b
 498 # ~~~~
 499 fun srand_from(x: Int) `{ nit_rand_seeded = 1; nit_rand_seed = x; `}
 500
 501 # Reinitialize the pseudo-random generator used by the method `rand` and other.
 502 # This method is automatically invoked at the begin of the program, so usually, there is no need to manually invoke it.
 503 # The only exception is in conjunction with `srand_from` to reset the pseudo-random generator.
 504 fun srand `{ nit_rand_seeded = 0; srand(time(NULL)); `}