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 15.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
173 # Is `self` a power of two ?
176 # assert not 3.is_pow2
179 # assert not 0.is_pow2
181 fun is_pow2: Bool do return self != 0 and (self & self - 1) == 0
185 # Returns the result of a binary AND operation on `self` and `i
`
187 # assert 0x10u8 & 0x01u8 == 0u8
188 fun &(i: Byte): Byte is intern `{ return self & i; `}
190 # Returns the result of a binary OR operation on `self` and `i`
192 # assert 0x10u8 | 0x01u8 == 0x11u8
193 fun |(i
: Byte): Byte `{ return self | i; `}
195 # Returns the result of a binary XOR operation on `self` and `i
`
197 # assert 0x101u8 ^ 0x110u8 == 0x11u8
198 fun ^(i: Byte): Byte `{ return self ^ i; `}
200 # Returns the 1's complement of `self`
202 # assert ~0x2Fu8 == 0xD0u8
203 fun ~
: Byte `{ return ~self; `}
208 # Returns the non-negative square root of `self`.
210 # assert 9.0.sqrt == 3.0
211 # #assert 3.0.sqrt == 1.732
212 # assert 1.0.sqrt == 1.0
213 # assert 0.0.sqrt == 0.0
214 fun sqrt: Float `{ return sqrt(self); `}
216 # Computes the cosine of `self` (expressed in radians).
218 # #assert pi.cos == -1.0
219 fun cos
: Float `{ return cos(self); `}
221 # Computes the sine of `self` (expressed in radians).
223 # #assert pi.sin == 0.0
224 fun sin: Float `{ return sin(self); `}
226 # Computes the cosine of x (expressed in radians).
228 # #assert 0.0.tan == 0.0
229 fun tan
: Float `{ return tan(self); `}
231 # Computes the arc cosine of `self`.
233 # #assert 0.0.acos == pi / 2.0
234 fun acos: Float `{ return acos(self); `}
236 # Computes the arc sine of `self`.
238 # #assert 1.0.asin == pi / 2.0
239 fun asin
: Float `{ return asin(self); `}
241 # Computes the arc tangent of `self`.
243 # #assert 0.0.tan == 0.0
244 fun atan: Float `{ return atan(self); `}
246 # Returns the absolute value of `self`.
248 # assert 12.0.abs == 12.0
249 # assert (-34.56).abs == 34.56
250 # assert -34.56.abs == -34.56
251 fun abs
: Float `{ return fabs(self); `}
253 # Returns `self` raised at `e
` power.
255 # assert 2.0.pow(0.0) == 1.0
256 # assert 2.0.pow(3.0) == 8.0
257 # assert 0.0.pow(9.0) == 0.0
258 fun pow(e: Float): Float `{ return pow(self, e); `}
260 # Natural logarithm of `self`.
262 # assert 0.0.log.is_inf == -1
263 # assert 1.0.log == 0.0
264 fun log
: Float `{ return log(self); `}
266 # Logarithm of `self` to base `base
`.
268 # assert 100.0.log_base(10.0) == 2.0
269 # assert 256.0.log_base(2.0) == 8.0
270 fun log_base(base: Float): Float do return log/base.log
272 # Returns *e* raised to `self`.
273 fun exp: Float `{ return exp(self); `}
275 # assert 1.1.ceil == 2.0
276 # assert 1.9.ceil == 2.0
277 # assert 2.0.ceil == 2.0
278 # assert (-1.5).ceil == -1.0
279 fun ceil
: Float `{ return ceil(self); `}
281 # assert 1.1.floor == 1.0
282 # assert 1.9.floor == 1.0
283 # assert 2.0.floor == 2.0
284 # assert (-1.5).floor == -2.0
285 fun floor: Float `{ return floor(self); `}
287 # Rounds the value of a float to its nearest integer value
289 # assert 1.67.round == 2.0
290 # assert 1.34.round == 1.0
291 # assert -1.34.round == -1.0
292 # assert -1.67.round == -2.0
293 fun round
: Float `{ return round(self); `}
295 # Returns a random `Float` in `[0.0 .. self[`.
297 if (nit_rand_seeded
) return ((self)*nit_rand
())/(NIT_RAND_MAX+1.0);
298 return ((self)*rand
())/(RAND_MAX+1.0);
301 # Returns the euclidean distance from `b
`.
302 fun hypot_with(b: Float): Float `{ return hypotf(self, b); `}
304 # Returns true is self is not a number.
306 # As `nan != nan`, `is_nan` should be used to test if a float is the special *not a number* value.
309 # assert nan != nan # By IEEE 754
311 # assert not 10.0.is_nan
313 fun is_nan
: Bool `{ return isnan(self); `}
315 # Is the float an infinite value
316 # this function returns:
318 # * 1 if self is positive infinity
319 # * -1 if self is negative infinity
323 # assert 10.0.is_inf == 0
324 # assert inf.is_inf == 1
325 # assert (-inf).is_inf == -1
328 if native_is_inf then
329 if self < 0.0 then return -1
335 private fun native_is_inf: Bool `{ return isinf(self); `}
337 # Linear interpolation between `a` and `b` using `self` as weight
340 # assert 0.0.lerp(0.0, 128.0) == 0.0
341 # assert 0.5.lerp(0.0, 128.0) == 64.0
342 # assert 1.0.lerp(0.0, 128.0) == 128.0
343 # assert -0.5.lerp(0.0, 128.0) == -64.0
345 fun lerp
(a
, b
: Float): Float do return (1.0 - self) * a
+ self * b
347 # Quadratic Bézier interpolation between `a` and `b` with an `handle` using `self` as weight
350 # assert 0.00.qerp(0.0, 32.0, 128.0) == 0.0
351 # assert 0.25.qerp(0.0, 32.0, 128.0) == 20.0
352 # assert 0.50.qerp(0.0, 32.0, 128.0) == 48.0
353 # assert 0.75.qerp(0.0, 32.0, 128.0) == 84.0
354 # assert 1.00.qerp(0.0, 32.0, 128.0) == 128.0
356 fun qerp
(a
, handle
, b
: Float): Float do
365 # Cubic Bézier interpolation between `a` and `b` with two handles using `self` as weight
367 # The Cubic Bézier interpolation is the most common one and use two control points.
370 # assert 0.00.cerp(0.0, 32.0, 128.0, 64.0) == 0.0
371 # assert 0.25.cerp(0.0, 32.0, 128.0, 64.0) == 32.5
372 # assert 0.50.cerp(0.0, 32.0, 128.0, 64.0) == 68.0
373 # assert 0.75.cerp(0.0, 32.0, 128.0, 64.0) == 85.5
374 # assert 1.00.cerp(0.0, 32.0, 128.0, 64.0) == 64.0
376 fun cerp
(a
, a_handle
, b_handle
, b
: Float): Float do
380 3.0*i
*i
*p
* a_handle
+
381 3.0*i
*p
*p
* b_handle
+
387 # Positive float infinite (IEEE 754)
390 # assert inf.is_inf == 1
392 # `inf` follows the arithmetic of infinites
394 # assert (inf - 1.0) == inf
395 # assert (inf - inf).is_nan
397 # The negative infinite can be used as `-inf`.
399 # assert -inf < -10.0
400 # assert (-inf).is_inf == -1
401 fun inf
: Float do return 1.0 / 0.0
403 # Not a Number, representation of an undefined or unrepresentable float (IEEE 754).
405 # `nan` is not comparable with itself, you should use `Float::is_nan` to test it.
409 # assert nan != nan # By IEEE 754
412 # `nan` is the quiet result of some undefined operations.
415 # assert (1.0 + nan).is_nan
416 # assert (0.0 / 0.0).is_nan
417 # assert (inf - inf).is_nan
418 # assert (inf / inf).is_nan
419 # assert (-1.0).sqrt.is_nan
421 fun nan
: Float do return 0.0 / 0.0
423 redef class Comparable
424 # Constraint `self` within `[min..max]`
426 # assert 1.clamp(5, 10) == 5
427 # assert 7.clamp(5, 10) == 7
428 # assert 15.clamp(5, 10) == 10
429 # assert 1.5.clamp(1.0, 2.0) == 1.5
430 # assert "a".clamp("b", "c") == "b"
431 fun clamp
(min
, max
: OTHER): OTHER do return self.max
(min
).min
(max
)
434 redef class Collection[ E
]
435 # Return a random element form the collection
436 # There must be at least one element in the collection
439 # var x = [1,2,3].rand
440 # assert x == 1 or x == 2 or x == 3
444 if is_empty
then abort
445 var rand_index
= length
.rand
448 if rand_index
== 0 then return e
454 # Return a new array made of elements in a random order.
457 # var a = [1,2,1].to_shuffle
458 # assert a == [1,1,2] or a == [1,2,1] or a == [2,1,1]
460 fun to_shuffle
: Array[E
]
467 # Return a new array made of (at most) `length` elements randomly chosen.
470 # var a = [1,2,1].sample(2)
471 # assert a == [1,1] or a == [1,2] or a == [2,1]
474 # If there is not enough elements, then the result only contains them in a random order.
477 # ENSURE `result.length == self.length.min(length)`
479 # Note: the default implementation uses the Reservoir Algorithm
480 fun sample
(length
: Int): Array[E
]
482 if length
>= self.length
then return to_shuffle
484 var res
= new Array[E
].with_capacity
(length
)
486 for i
in [0..length
[ do
491 for i
in [length
+1..self.length
] do
502 redef class SequenceRead[E
]
503 # Optimized for large collections using `[]`
507 return self[length
.rand
]
511 redef class AbstractArray[E
]
512 # Reorder randomly the elements in self.
515 # var a = new Array[Int]
526 # assert a == [1,2] or a == [2,1]
529 # ENSURE self.shuffle.has_exactly(old(self))
532 for i
in [0..length
[ do
533 var j
= i
+ (length-i
).rand
548 # Computes the arc tangent given `y` and `x`.
550 # assert atan2(-0.0, 1.0) == -0.0
551 # assert atan2(0.0, 1.0) == 0.0
552 fun atan2
(y
: Float, x
: Float): Float `{ return atan2(y, x); `}
554 # Approximate value of **pi**.
555 fun pi: Float do return 3.14159265
557 # Initialize the pseudo-random generator with the given seed.
558 # The pseudo-random generator is used by the method `rand
` and other to generate sequence of numbers.
559 # These sequences are repeatable by calling `srand_from
` with a same seed value.
566 # assert 10.rand == a
567 # assert 100.rand == b
569 fun srand_from(x: Int) `{ nit_rand_seeded = 1; nit_rand_seed = (unsigned int)x; `}
571 # Reinitialize the pseudo-random generator used by the method `rand` and other.
572 # This method is automatically invoked at the begin of the program, so usually, there is no need to manually invoke it.
573 # The only exception is in conjunction with `srand_from` to reset the pseudo-random generator.
574 fun srand
`{ nit_rand_seeded = 0; srand((unsigned int)time(NULL)); `}