1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
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
13 # Mathematical operations
14 module math
is ldflags
"-lm"
26 /* Is rand shortcut? */
27 static int nit_rand_seeded;
28 /* Current rand seed if seeded */
29 static unsigned int nit_rand_seed;
31 #define NIT_RAND_MAX 0x7fffffff
33 /* This algorithm is mentioned in the ISO C standard, here extended
37 unsigned int next = nit_rand_seed;
42 result = (unsigned int) (next / 65536) % 2048;
47 result ^= (unsigned int) (next / 65536) % 1024;
52 result ^= (unsigned int) (next / 65536) % 1024;
61 # Returns a random `Int` in `[0 .. self[`.
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));
67 # Returns the result of a binary AND operation on `self` and `i`
69 # assert 0x10 & 0x01 == 0
70 fun &(i
: Int): Int is intern `{ return self & i; `}
72 # Returns the result of a binary OR operation on `self` and `i
`
74 # assert 0x10 | 0x01 == 0x11
75 fun |(i: Int): Int is intern `{ return self | i; `}
77 # Returns the result of a binary XOR operation on `self` and `i`
79 # assert 0x101 ^ 0x110 == 0x11
80 fun ^
(i
: Int): Int `{ return self ^ i; `}
82 # Returns the 1's complement of `self`
85 fun ~: Int `{ return ~self; `}
87 # Returns the square root of `self`
90 fun sqrt
: Int `{ return sqrt(self); `}
92 # Returns the greatest common divisor of `self` and `o
`
94 # assert 54.gcd(24) == 6
95 # assert -54.gcd(-24) == 6
96 # assert 54.gcd(-24) == -6
97 # assert -54.gcd(24) == -6
98 # assert 12.gcd(6) == 6
101 if self < 0 then return -(-self).gcd(o)
102 if o < 0 then return -(self.gcd(-o))
103 if self == 0 or o == self then return o
104 if o == 0 then return self
105 if self & 1 == 0 then
107 return (self >> 1).gcd(o)
109 return (self >> 1).gcd(o >> 1) << 1
112 if o & 1 == 0 then return self.gcd(o >> 1)
113 if self > o then return ((self - o) >> 1).gcd(o)
114 return ((o - self) >> 1).gcd(self)
120 fun is_even: Bool do return self % 2 == 0
124 # assert not 13.is_even
125 fun is_odd: Bool do return not is_even
127 # Is self a prime number ?
130 # assert not 1.is_prime
131 # assert not 12.is_prime
136 else if self <= 1 or self.is_even then
139 for i in [3..self.sqrt[ do
140 if self % i == 0 then return false
145 # Returns the `self` raised to the power of `e
`.
150 return self.to_f.pow(e.to_f).to_i
153 # The factorial of `self` (aka `self!`)
155 # Returns `1 * 2 * 3 * ... * self-1
* self`
157 # assert 0.factorial == 1 # by convention for an empty product
158 # assert 1.factorial == 1
159 # assert 4.factorial == 24
160 # assert 9.factorial == 362880
175 # Returns the result of a binary AND operation on `self` and `i
`
177 # assert 0x10u8 & 0x01u8 == 0u8
178 fun &(i: Byte): Byte is intern `{ return self & i; `}
180 # Returns the result of a binary OR operation on `self` and `i`
182 # assert 0x10u8 | 0x01u8 == 0x11u8
183 fun |(i
: Byte): Byte `{ return self | i; `}
185 # Returns the result of a binary XOR operation on `self` and `i
`
187 # assert 0x101u8 ^ 0x110u8 == 0x11u8
188 fun ^(i: Byte): Byte `{ return self ^ i; `}
190 # Returns the 1's complement of `self`
192 # assert ~0x2Fu8 == 0xD0u8
193 fun ~
: Byte `{ return ~self; `}
198 # Returns the non-negative square root of `self`.
200 # assert 9.0.sqrt == 3.0
201 # #assert 3.0.sqrt == 1.732
202 # assert 1.0.sqrt == 1.0
203 # assert 0.0.sqrt == 0.0
204 fun sqrt: Float `{ return sqrt(self); `}
206 # Computes the cosine of `self` (expressed in radians).
208 # #assert pi.cos == -1.0
209 fun cos
: Float `{ return cos(self); `}
211 # Computes the sine of `self` (expressed in radians).
213 # #assert pi.sin == 0.0
214 fun sin: Float `{ return sin(self); `}
216 # Computes the cosine of x (expressed in radians).
218 # #assert 0.0.tan == 0.0
219 fun tan
: Float `{ return tan(self); `}
221 # Computes the arc cosine of `self`.
223 # #assert 0.0.acos == pi / 2.0
224 fun acos: Float `{ return acos(self); `}
226 # Computes the arc sine of `self`.
228 # #assert 1.0.asin == pi / 2.0
229 fun asin
: Float `{ return asin(self); `}
231 # Computes the arc tangent of `self`.
233 # #assert 0.0.tan == 0.0
234 fun atan: Float `{ return atan(self); `}
236 # Returns the absolute value of `self`.
238 # assert 12.0.abs == 12.0
239 # assert (-34.56).abs == 34.56
240 # assert -34.56.abs == -34.56
241 fun abs
: Float `{ return fabs(self); `}
243 # Returns `self` raised at `e
` power.
245 # #assert 2.0.pow(0.0) == 1.0
246 # #assert 2.0.pow(3.0) == 8.0
247 # #assert 0.0.pow(9.0) == 0.0
248 fun pow(e: Float): Float `{ return pow(self, e); `}
250 # Natural logarithm of `self`.
252 # assert 0.0.log.is_inf == -1
253 # #assert 1.0.log == 0.0
254 fun log
: Float `{ return log(self); `}
256 # Logarithm of `self` to base `base
`.
258 # assert 100.0.log_base(10.0) == 2.0
259 # assert 256.0.log_base(2.0) == 8.0
260 fun log_base(base: Float): Float do return log/base.log
262 # Returns *e* raised to `self`.
263 fun exp: Float `{ return exp(self); `}
265 # assert 1.1.ceil == 2.0
266 # assert 1.9.ceil == 2.0
267 # assert 2.0.ceil == 2.0
268 # assert (-1.5).ceil == -1.0
269 fun ceil
: Float `{ return ceil(self); `}
271 # assert 1.1.floor == 1.0
272 # assert 1.9.floor == 1.0
273 # assert 2.0.floor == 2.0
274 # assert (-1.5).floor == -2.0
275 fun floor: Float `{ return floor(self); `}
277 # Rounds the value of a float to its nearest integer value
279 # assert 1.67.round == 2.0
280 # assert 1.34.round == 1.0
281 # assert -1.34.round == -1.0
282 # assert -1.67.round == -2.0
283 fun round
: Float `{ return round(self); `}
285 # Returns a random `Float` in `[0.0 .. self[`.
287 if (nit_rand_seeded
) return ((self)*nit_rand
())/(NIT_RAND_MAX+1.0);
288 return ((self)*rand
())/(RAND_MAX+1.0);
291 # Returns the euclidean distance from `b
`.
292 fun hypot_with(b: Float): Float `{ return hypotf(self, b); `}
294 # Returns true is self is not a number.
296 # As `nan != nan`, `is_nan` should be used to test if a float is the special *not a number* value.
299 # assert nan != nan # By IEEE 754
301 # assert not 10.0.is_nan
303 fun is_nan
: Bool `{ return isnan(self); `}
305 # Is the float an infinite value
306 # this function returns:
308 # * 1 if self is positive infinity
309 # * -1 if self is negative infinity
313 # assert 10.0.is_inf == 0
314 # assert inf.is_inf == 1
315 # assert (-inf).is_inf == -1
318 if native_is_inf then
319 if self < 0.0 then return -1
325 private fun native_is_inf: Bool `{ return isinf(self); `}
327 # Linear interpolation between `a` and `b` using `self` as weight
330 # assert 0.0.lerp(0.0, 128.0) == 0.0
331 # assert 0.5.lerp(0.0, 128.0) == 64.0
332 # assert 1.0.lerp(0.0, 128.0) == 128.0
333 # assert -0.5.lerp(0.0, 128.0) == -64.0
335 fun lerp
(a
, b
: Float): Float do return (1.0 - self) * a
+ self * b
337 # Quadratic Bézier interpolation between `a` and `b` with an `handle` using `self` as weight
340 # assert 0.00.qerp(0.0, 32.0, 128.0) == 0.0
341 # assert 0.25.qerp(0.0, 32.0, 128.0) == 20.0
342 # assert 0.50.qerp(0.0, 32.0, 128.0) == 48.0
343 # assert 0.75.qerp(0.0, 32.0, 128.0) == 84.0
344 # assert 1.00.qerp(0.0, 32.0, 128.0) == 128.0
346 fun qerp
(a
, handle
, b
: Float): Float do
355 # Cubic Bézier interpolation between `a` and `b` with two handles using `self` as weight
357 # The Cubic Bézier interpolation is the most common one and use two control points.
360 # assert 0.00.cerp(0.0, 32.0, 128.0, 64.0) == 0.0
361 # assert 0.25.cerp(0.0, 32.0, 128.0, 64.0) == 32.5
362 # assert 0.50.cerp(0.0, 32.0, 128.0, 64.0) == 68.0
363 # assert 0.75.cerp(0.0, 32.0, 128.0, 64.0) == 85.5
364 # assert 1.00.cerp(0.0, 32.0, 128.0, 64.0) == 64.0
366 fun cerp
(a
, a_handle
, b_handle
, b
: Float): Float do
370 3.0*i
*i
*p
* a_handle
+
371 3.0*i
*p
*p
* b_handle
+
377 # Positive float infinite (IEEE 754)
380 # assert inf.is_inf == 1
382 # `inf` follows the arithmetic of infinites
384 # assert (inf - 1.0) == inf
385 # assert (inf - inf).is_nan
387 # The negative infinite can be used as `-inf`.
389 # assert -inf < -10.0
390 # assert (-inf).is_inf == -1
391 fun inf
: Float do return 1.0 / 0.0
393 # Not a Number, representation of an undefined or unrepresentable float (IEEE 754).
395 # `nan` is not comparable with itself, you should use `Float::is_nan` to test it.
399 # assert nan != nan # By IEEE 754
402 # `nan` is the quiet result of some undefined operations.
405 # assert (1.0 + nan).is_nan
406 # assert (0.0 / 0.0).is_nan
407 # assert (inf - inf).is_nan
408 # assert (inf / inf).is_nan
409 # assert (-1.0).sqrt.is_nan
411 fun nan
: Float do return 0.0 / 0.0
413 redef class Collection[ E
]
414 # Return a random element form the collection
415 # There must be at least one element in the collection
418 # var x = [1,2,3].rand
419 # assert x == 1 or x == 2 or x == 3
423 if is_empty
then abort
424 var rand_index
= length
.rand
427 if rand_index
== 0 then return e
433 # Return a new array made of elements in a random order.
436 # var a = [1,2,1].to_shuffle
437 # assert a == [1,1,2] or a == [1,2,1] or a == [2,1,1]
439 fun to_shuffle
: Array[E
]
446 # Return a new array made of (at most) `length` elements randomly chosen.
449 # var a = [1,2,1].sample(2)
450 # assert a == [1,1] or a == [1,2] or a == [2,1]
453 # If there is not enough elements, then the result only contains them in a random order.
456 # ENSURE `result.length == self.length.min(length)`
458 # Note: the default implementation uses the Reservoir Algorithm
459 fun sample
(length
: Int): Array[E
]
461 if length
>= self.length
then return to_shuffle
463 var res
= new Array[E
].with_capacity
(length
)
465 for i
in [0..length
[ do
470 for i
in [length
+1..self.length
] do
481 redef class SequenceRead[E
]
482 # Optimized for large collections using `[]`
486 return self[length
.rand
]
490 redef class AbstractArray[E
]
491 # Reorder randomly the elements in self.
494 # var a = new Array[Int]
505 # assert a == [1,2] or a == [2,1]
508 # ENSURE self.shuffle.has_exactly(old(self))
511 for i
in [0..length
[ do
512 var j
= i
+ (length-i
).rand
527 # Computes the arc tangent given `x` and `y`.
529 # assert atan2(-0.0, 1.0) == -0.0
530 # assert atan2(0.0, 1.0) == 0.0
531 fun atan2
(x
: Float, y
: Float): Float `{ return atan2(x, y); `}
533 # Approximate value of **pi**.
534 fun pi: Float do return 3.14159265
536 # Initialize the pseudo-random generator with the given seed.
537 # The pseudo-random generator is used by the method `rand
` and other to generate sequence of numbers.
538 # These sequences are repeatable by calling `srand_from
` with a same seed value.
545 # assert 10.rand == a
546 # assert 100.rand == b
548 fun srand_from(x: Int) `{ nit_rand_seeded = 1; nit_rand_seed = (unsigned int)x; `}
550 # Reinitialize the pseudo-random generator used by the method `rand` and other.
551 # This method is automatically invoked at the begin of the program, so usually, there is no need to manually invoke it.
552 # The only exception is in conjunction with `srand_from` to reset the pseudo-random generator.
553 fun srand
`{ nit_rand_seeded = 0; srand((unsigned int)time(NULL)); `}