7f2ecd0dc5c319d9b935afa8ea4a8529a265f136
[ghc.git] / libraries / base / GHC / Real.hs
1 {-# LANGUAGE Trustworthy #-}
2 {-# LANGUAGE CPP, NoImplicitPrelude, MagicHash, UnboxedTuples, BangPatterns #-}
3 {-# OPTIONS_GHC -Wno-orphans #-}
4 {-# OPTIONS_HADDOCK hide #-}
5
6 -----------------------------------------------------------------------------
7 -- |
8 -- Module : GHC.Real
9 -- Copyright : (c) The University of Glasgow, 1994-2002
10 -- License : see libraries/base/LICENSE
11 --
12 -- Maintainer : cvs-ghc@haskell.org
13 -- Stability : internal
14 -- Portability : non-portable (GHC Extensions)
15 --
16 -- The types 'Ratio' and 'Rational', and the classes 'Real', 'Fractional',
17 -- 'Integral', and 'RealFrac'.
18 --
19 -----------------------------------------------------------------------------
20
21 module GHC.Real where
22
23 import GHC.Base
24 import GHC.Num
25 import GHC.List
26 import GHC.Enum
27 import GHC.Show
28 import {-# SOURCE #-} GHC.Exception( divZeroException, overflowException, ratioZeroDenomException )
29
30 #if defined(OPTIMISE_INTEGER_GCD_LCM)
31 # if defined(MIN_VERSION_integer_gmp)
32 import GHC.Integer.GMP.Internals
33 # else
34 # error unsupported OPTIMISE_INTEGER_GCD_LCM configuration
35 # endif
36 #endif
37
38 infixr 8 ^, ^^
39 infixl 7 /, `quot`, `rem`, `div`, `mod`
40 infixl 7 %
41
42 default () -- Double isn't available yet,
43 -- and we shouldn't be using defaults anyway
44
45 ------------------------------------------------------------------------
46 -- Divide by zero and arithmetic overflow
47 ------------------------------------------------------------------------
48
49 -- We put them here because they are needed relatively early
50 -- in the libraries before the Exception type has been defined yet.
51
52 {-# NOINLINE divZeroError #-}
53 divZeroError :: a
54 divZeroError = raise# divZeroException
55
56 {-# NOINLINE ratioZeroDenominatorError #-}
57 ratioZeroDenominatorError :: a
58 ratioZeroDenominatorError = raise# ratioZeroDenomException
59
60 {-# NOINLINE overflowError #-}
61 overflowError :: a
62 overflowError = raise# overflowException
63
64 --------------------------------------------------------------
65 -- The Ratio and Rational types
66 --------------------------------------------------------------
67
68 -- | Rational numbers, with numerator and denominator of some 'Integral' type.
69 data Ratio a = !a :% !a deriving Eq -- ^ @since 2.01
70
71 -- | Arbitrary-precision rational numbers, represented as a ratio of
72 -- two 'Integer' values. A rational number may be constructed using
73 -- the '%' operator.
74 type Rational = Ratio Integer
75
76 ratioPrec, ratioPrec1 :: Int
77 ratioPrec = 7 -- Precedence of ':%' constructor
78 ratioPrec1 = ratioPrec + 1
79
80 infinity, notANumber :: Rational
81 infinity = 1 :% 0
82 notANumber = 0 :% 0
83
84 -- Use :%, not % for Inf/NaN; the latter would
85 -- immediately lead to a runtime error, because it normalises.
86
87 -- | Forms the ratio of two integral numbers.
88 {-# SPECIALISE (%) :: Integer -> Integer -> Rational #-}
89 (%) :: (Integral a) => a -> a -> Ratio a
90
91 -- | Extract the numerator of the ratio in reduced form:
92 -- the numerator and denominator have no common factor and the denominator
93 -- is positive.
94 numerator :: Ratio a -> a
95
96 -- | Extract the denominator of the ratio in reduced form:
97 -- the numerator and denominator have no common factor and the denominator
98 -- is positive.
99 denominator :: Ratio a -> a
100
101
102 -- | 'reduce' is a subsidiary function used only in this module.
103 -- It normalises a ratio by dividing both numerator and denominator by
104 -- their greatest common divisor.
105 reduce :: (Integral a) => a -> a -> Ratio a
106 {-# SPECIALISE reduce :: Integer -> Integer -> Rational #-}
107 reduce _ 0 = ratioZeroDenominatorError
108 reduce x y = (x `quot` d) :% (y `quot` d)
109 where d = gcd x y
110
111 x % y = reduce (x * signum y) (abs y)
112
113 numerator (x :% _) = x
114 denominator (_ :% y) = y
115
116 --------------------------------------------------------------
117 -- Standard numeric classes
118 --------------------------------------------------------------
119
120 class (Num a, Ord a) => Real a where
121 -- | the rational equivalent of its real argument with full precision
122 toRational :: a -> Rational
123
124 -- | Integral numbers, supporting integer division.
125 class (Real a, Enum a) => Integral a where
126 -- | integer division truncated toward zero
127 quot :: a -> a -> a
128 -- | integer remainder, satisfying
129 --
130 -- > (x `quot` y)*y + (x `rem` y) == x
131 rem :: a -> a -> a
132 -- | integer division truncated toward negative infinity
133 div :: a -> a -> a
134 -- | integer modulus, satisfying
135 --
136 -- > (x `div` y)*y + (x `mod` y) == x
137 mod :: a -> a -> a
138 -- | simultaneous 'quot' and 'rem'
139 quotRem :: a -> a -> (a,a)
140 -- | simultaneous 'div' and 'mod'
141 divMod :: a -> a -> (a,a)
142 -- | conversion to 'Integer'
143 toInteger :: a -> Integer
144
145 {-# INLINE quot #-}
146 {-# INLINE rem #-}
147 {-# INLINE div #-}
148 {-# INLINE mod #-}
149 n `quot` d = q where (q,_) = quotRem n d
150 n `rem` d = r where (_,r) = quotRem n d
151 n `div` d = q where (q,_) = divMod n d
152 n `mod` d = r where (_,r) = divMod n d
153
154 divMod n d = if signum r == negate (signum d) then (q-1, r+d) else qr
155 where qr@(q,r) = quotRem n d
156
157 -- | Fractional numbers, supporting real division.
158 class (Num a) => Fractional a where
159 {-# MINIMAL fromRational, (recip | (/)) #-}
160
161 -- | fractional division
162 (/) :: a -> a -> a
163 -- | reciprocal fraction
164 recip :: a -> a
165 -- | Conversion from a 'Rational' (that is @'Ratio' 'Integer'@).
166 -- A floating literal stands for an application of 'fromRational'
167 -- to a value of type 'Rational', so such literals have type
168 -- @('Fractional' a) => a@.
169 fromRational :: Rational -> a
170
171 {-# INLINE recip #-}
172 {-# INLINE (/) #-}
173 recip x = 1 / x
174 x / y = x * recip y
175
176 -- | Extracting components of fractions.
177 class (Real a, Fractional a) => RealFrac a where
178 -- | The function 'properFraction' takes a real fractional number @x@
179 -- and returns a pair @(n,f)@ such that @x = n+f@, and:
180 --
181 -- * @n@ is an integral number with the same sign as @x@; and
182 --
183 -- * @f@ is a fraction with the same type and sign as @x@,
184 -- and with absolute value less than @1@.
185 --
186 -- The default definitions of the 'ceiling', 'floor', 'truncate'
187 -- and 'round' functions are in terms of 'properFraction'.
188 properFraction :: (Integral b) => a -> (b,a)
189 -- | @'truncate' x@ returns the integer nearest @x@ between zero and @x@
190 truncate :: (Integral b) => a -> b
191 -- | @'round' x@ returns the nearest integer to @x@;
192 -- the even integer if @x@ is equidistant between two integers
193 round :: (Integral b) => a -> b
194 -- | @'ceiling' x@ returns the least integer not less than @x@
195 ceiling :: (Integral b) => a -> b
196 -- | @'floor' x@ returns the greatest integer not greater than @x@
197 floor :: (Integral b) => a -> b
198
199 {-# INLINE truncate #-}
200 truncate x = m where (m,_) = properFraction x
201
202 round x = let (n,r) = properFraction x
203 m = if r < 0 then n - 1 else n + 1
204 in case signum (abs r - 0.5) of
205 -1 -> n
206 0 -> if even n then n else m
207 1 -> m
208 _ -> errorWithoutStackTrace "round default defn: Bad value"
209
210 ceiling x = if r > 0 then n + 1 else n
211 where (n,r) = properFraction x
212
213 floor x = if r < 0 then n - 1 else n
214 where (n,r) = properFraction x
215
216 -- These 'numeric' enumerations come straight from the Report
217
218 numericEnumFrom :: (Fractional a) => a -> [a]
219 numericEnumFrom n = go 0
220 where
221 -- See Note [Numeric Stability of Enumerating Floating Numbers]
222 go !k = let !n' = n + k
223 in n' : go (k + 1)
224
225 numericEnumFromThen :: (Fractional a) => a -> a -> [a]
226 numericEnumFromThen n m = go 0
227 where
228 step = m - n
229 -- See Note [Numeric Stability of Enumerating Floating Numbers]
230 go !k = let !n' = n + k * step
231 in n' : go (k + 1)
232
233 numericEnumFromTo :: (Ord a, Fractional a) => a -> a -> [a]
234 numericEnumFromTo n m = takeWhile (<= m + 1/2) (numericEnumFrom n)
235
236 numericEnumFromThenTo :: (Ord a, Fractional a) => a -> a -> a -> [a]
237 numericEnumFromThenTo e1 e2 e3
238 = takeWhile predicate (numericEnumFromThen e1 e2)
239 where
240 mid = (e2 - e1) / 2
241 predicate | e2 >= e1 = (<= e3 + mid)
242 | otherwise = (>= e3 + mid)
243
244 {- Note [Numeric Stability of Enumerating Floating Numbers]
245 -----------------------------------------------------------
246 When enumerate floating numbers, we could add the increment to the last number
247 at every run (as what we did previously):
248
249 numericEnumFrom n = n `seq` (n : numericEnumFrom (n + 1))
250
251 This approach is concise and really fast, only needs an addition operation.
252 However when a floating number is large enough, for `n`, `n` and `n+1` will
253 have the same binary representation. For example (all number has type
254 `Double`):
255
256 9007199254740990 is: 0x433ffffffffffffe
257 9007199254740990 + 1 is: 0x433fffffffffffff
258 (9007199254740990 + 1) + 1 is: 0x4340000000000000
259 ((9007199254740990 + 1) + 1) + 1 is: 0x4340000000000000
260
261 When we evaluate ([9007199254740990..9007199254740991] :: Double), we would
262 never reach the condition in `numericEnumFromTo`
263
264 9007199254740990 + 1 + 1 + ... > 9007199254740991 + 1/2
265
266 We would fall into infinite loop (as reported in Trac #15081).
267
268 To remedy the situation, we record the number of `1` that needed to be added
269 to the start number, rather than increasing `1` at every time. This approach
270 can improvement the numeric stability greatly at the cost of a multiplication.
271
272 Furthermore, we use the type of the enumerated number, `Fractional a => a`,
273 as the type of multiplier. In rare situations, the multiplier could be very
274 large and will lead to the enumeration to infinite loop, too, which should
275 be very rare. Consider the following example:
276
277 [1..9007199254740994]
278
279 We could fix that by using an Integer as multiplier but we don't do that.
280 The benchmark on T7954.hs shows that this approach leads to significant
281 degeneration on performance (33% increase allocation and 300% increase on
282 elapsed time).
283
284 See Trac #15081 and Phab:D4650 for the related discussion about this problem.
285 -}
286
287 --------------------------------------------------------------
288 -- Instances for Int
289 --------------------------------------------------------------
290
291 -- | @since 2.0.1
292 instance Real Int where
293 toRational x = toInteger x :% 1
294
295 -- | @since 2.0.1
296 instance Integral Int where
297 toInteger (I# i) = smallInteger i
298
299 a `quot` b
300 | b == 0 = divZeroError
301 | b == (-1) && a == minBound = overflowError -- Note [Order of tests]
302 -- in GHC.Int
303 | otherwise = a `quotInt` b
304
305 a `rem` b
306 | b == 0 = divZeroError
307 -- The quotRem CPU instruction fails for minBound `quotRem` -1,
308 -- but minBound `rem` -1 is well-defined (0). We therefore
309 -- special-case it.
310 | b == (-1) = 0
311 | otherwise = a `remInt` b
312
313 a `div` b
314 | b == 0 = divZeroError
315 | b == (-1) && a == minBound = overflowError -- Note [Order of tests]
316 -- in GHC.Int
317 | otherwise = a `divInt` b
318
319 a `mod` b
320 | b == 0 = divZeroError
321 -- The divMod CPU instruction fails for minBound `divMod` -1,
322 -- but minBound `mod` -1 is well-defined (0). We therefore
323 -- special-case it.
324 | b == (-1) = 0
325 | otherwise = a `modInt` b
326
327 a `quotRem` b
328 | b == 0 = divZeroError
329 -- Note [Order of tests] in GHC.Int
330 | b == (-1) && a == minBound = (overflowError, 0)
331 | otherwise = a `quotRemInt` b
332
333 a `divMod` b
334 | b == 0 = divZeroError
335 -- Note [Order of tests] in GHC.Int
336 | b == (-1) && a == minBound = (overflowError, 0)
337 | otherwise = a `divModInt` b
338
339 --------------------------------------------------------------
340 -- Instances for @Word@
341 --------------------------------------------------------------
342
343 -- | @since 2.01
344 instance Real Word where
345 toRational x = toInteger x % 1
346
347 -- | @since 2.01
348 instance Integral Word where
349 quot (W# x#) y@(W# y#)
350 | y /= 0 = W# (x# `quotWord#` y#)
351 | otherwise = divZeroError
352 rem (W# x#) y@(W# y#)
353 | y /= 0 = W# (x# `remWord#` y#)
354 | otherwise = divZeroError
355 div (W# x#) y@(W# y#)
356 | y /= 0 = W# (x# `quotWord#` y#)
357 | otherwise = divZeroError
358 mod (W# x#) y@(W# y#)
359 | y /= 0 = W# (x# `remWord#` y#)
360 | otherwise = divZeroError
361 quotRem (W# x#) y@(W# y#)
362 | y /= 0 = case x# `quotRemWord#` y# of
363 (# q, r #) ->
364 (W# q, W# r)
365 | otherwise = divZeroError
366 divMod (W# x#) y@(W# y#)
367 | y /= 0 = (W# (x# `quotWord#` y#), W# (x# `remWord#` y#))
368 | otherwise = divZeroError
369 toInteger (W# x#) = wordToInteger x#
370
371 --------------------------------------------------------------
372 -- Instances for Integer
373 --------------------------------------------------------------
374
375 -- | @since 2.0.1
376 instance Real Integer where
377 toRational x = x :% 1
378
379 -- Note [Integer division constant folding]
380 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
381 --
382 -- Constant folding of quot, rem, div, mod, divMod and quotRem for
383 -- Integer arguments depends crucially on inlining. Constant folding
384 -- rules defined in compiler/prelude/PrelRules.hs trigger for
385 -- quotInteger, remInteger and so on. So if calls to quot, rem and so on
386 -- were not inlined the rules would not fire. The rules would also not
387 -- fire if calls to quotInteger and so on were inlined, but this does not
388 -- happen because they are all marked with NOINLINE pragma - see documentation
389 -- of integer-gmp or integer-simple.
390
391 -- | @since 2.0.1
392 instance Integral Integer where
393 toInteger n = n
394
395 {-# INLINE quot #-}
396 _ `quot` 0 = divZeroError
397 n `quot` d = n `quotInteger` d
398
399 {-# INLINE rem #-}
400 _ `rem` 0 = divZeroError
401 n `rem` d = n `remInteger` d
402
403 {-# INLINE div #-}
404 _ `div` 0 = divZeroError
405 n `div` d = n `divInteger` d
406
407 {-# INLINE mod #-}
408 _ `mod` 0 = divZeroError
409 n `mod` d = n `modInteger` d
410
411 {-# INLINE divMod #-}
412 _ `divMod` 0 = divZeroError
413 n `divMod` d = case n `divModInteger` d of
414 (# x, y #) -> (x, y)
415
416 {-# INLINE quotRem #-}
417 _ `quotRem` 0 = divZeroError
418 n `quotRem` d = case n `quotRemInteger` d of
419 (# q, r #) -> (q, r)
420
421 --------------------------------------------------------------
422 -- Instances for @Ratio@
423 --------------------------------------------------------------
424
425 -- | @since 2.0.1
426 instance (Integral a) => Ord (Ratio a) where
427 {-# SPECIALIZE instance Ord Rational #-}
428 (x:%y) <= (x':%y') = x * y' <= x' * y
429 (x:%y) < (x':%y') = x * y' < x' * y
430
431 -- | @since 2.0.1
432 instance (Integral a) => Num (Ratio a) where
433 {-# SPECIALIZE instance Num Rational #-}
434 (x:%y) + (x':%y') = reduce (x*y' + x'*y) (y*y')
435 (x:%y) - (x':%y') = reduce (x*y' - x'*y) (y*y')
436 (x:%y) * (x':%y') = reduce (x * x') (y * y')
437 negate (x:%y) = (-x) :% y
438 abs (x:%y) = abs x :% y
439 signum (x:%_) = signum x :% 1
440 fromInteger x = fromInteger x :% 1
441
442 -- | @since 2.0.1
443 {-# RULES "fromRational/id" fromRational = id :: Rational -> Rational #-}
444 instance (Integral a) => Fractional (Ratio a) where
445 {-# SPECIALIZE instance Fractional Rational #-}
446 (x:%y) / (x':%y') = (x*y') % (y*x')
447 recip (0:%_) = ratioZeroDenominatorError
448 recip (x:%y)
449 | x < 0 = negate y :% negate x
450 | otherwise = y :% x
451 fromRational (x:%y) = fromInteger x % fromInteger y
452
453 -- | @since 2.0.1
454 instance (Integral a) => Real (Ratio a) where
455 {-# SPECIALIZE instance Real Rational #-}
456 toRational (x:%y) = toInteger x :% toInteger y
457
458 -- | @since 2.0.1
459 instance (Integral a) => RealFrac (Ratio a) where
460 {-# SPECIALIZE instance RealFrac Rational #-}
461 properFraction (x:%y) = (fromInteger (toInteger q), r:%y)
462 where (q,r) = quotRem x y
463
464 -- | @since 2.0.1
465 instance (Show a) => Show (Ratio a) where
466 {-# SPECIALIZE instance Show Rational #-}
467 showsPrec p (x:%y) = showParen (p > ratioPrec) $
468 showsPrec ratioPrec1 x .
469 showString " % " .
470 -- H98 report has spaces round the %
471 -- but we removed them [May 04]
472 -- and added them again for consistency with
473 -- Haskell 98 [Sep 08, #1920]
474 showsPrec ratioPrec1 y
475
476 -- | @since 2.0.1
477 instance (Integral a) => Enum (Ratio a) where
478 {-# SPECIALIZE instance Enum Rational #-}
479 succ x = x + 1
480 pred x = x - 1
481
482 toEnum n = fromIntegral n :% 1
483 fromEnum = fromInteger . truncate
484
485 enumFrom = numericEnumFrom
486 enumFromThen = numericEnumFromThen
487 enumFromTo = numericEnumFromTo
488 enumFromThenTo = numericEnumFromThenTo
489
490 --------------------------------------------------------------
491 -- Coercions
492 --------------------------------------------------------------
493
494 -- | general coercion from integral types
495 {-# NOINLINE [1] fromIntegral #-}
496 fromIntegral :: (Integral a, Num b) => a -> b
497 fromIntegral = fromInteger . toInteger
498
499 {-# RULES
500 "fromIntegral/Int->Int" fromIntegral = id :: Int -> Int
501 #-}
502
503 {-# RULES
504 "fromIntegral/Int->Word" fromIntegral = \(I# x#) -> W# (int2Word# x#)
505 "fromIntegral/Word->Int" fromIntegral = \(W# x#) -> I# (word2Int# x#)
506 "fromIntegral/Word->Word" fromIntegral = id :: Word -> Word
507 #-}
508
509 -- | general coercion to fractional types
510 realToFrac :: (Real a, Fractional b) => a -> b
511 {-# NOINLINE [1] realToFrac #-}
512 realToFrac = fromRational . toRational
513
514 --------------------------------------------------------------
515 -- Overloaded numeric functions
516 --------------------------------------------------------------
517
518 -- | Converts a possibly-negative 'Real' value to a string.
519 showSigned :: (Real a)
520 => (a -> ShowS) -- ^ a function that can show unsigned values
521 -> Int -- ^ the precedence of the enclosing context
522 -> a -- ^ the value to show
523 -> ShowS
524 showSigned showPos p x
525 | x < 0 = showParen (p > 6) (showChar '-' . showPos (-x))
526 | otherwise = showPos x
527
528 even, odd :: (Integral a) => a -> Bool
529 even n = n `rem` 2 == 0
530 odd = not . even
531 {-# INLINABLE even #-}
532 {-# INLINABLE odd #-}
533
534 -------------------------------------------------------
535 -- | raise a number to a non-negative integral power
536 {-# SPECIALISE [1] (^) ::
537 Integer -> Integer -> Integer,
538 Integer -> Int -> Integer,
539 Int -> Int -> Int #-}
540 {-# INLINABLE [1] (^) #-} -- See Note [Inlining (^)]
541 (^) :: (Num a, Integral b) => a -> b -> a
542 x0 ^ y0 | y0 < 0 = errorWithoutStackTrace "Negative exponent"
543 | y0 == 0 = 1
544 | otherwise = f x0 y0
545 where -- f : x0 ^ y0 = x ^ y
546 f x y | even y = f (x * x) (y `quot` 2)
547 | y == 1 = x
548 | otherwise = g (x * x) (y `quot` 2) x -- See Note [Half of y - 1]
549 -- g : x0 ^ y0 = (x ^ y) * z
550 g x y z | even y = g (x * x) (y `quot` 2) z
551 | y == 1 = x * z
552 | otherwise = g (x * x) (y `quot` 2) (x * z) -- See Note [Half of y - 1]
553
554 -- | raise a number to an integral power
555 (^^) :: (Fractional a, Integral b) => a -> b -> a
556 {-# INLINABLE [1] (^^) #-} -- See Note [Inlining (^)
557 x ^^ n = if n >= 0 then x^n else recip (x^(negate n))
558
559 {- Note [Half of y - 1]
560 ~~~~~~~~~~~~~~~~~~~~~
561 Since y is guaranteed to be odd and positive here,
562 half of y - 1 can be computed as y `quot` 2, optimising subtraction away.
563 -}
564
565 {- Note [Inlining (^)
566 ~~~~~~~~~~~~~~~~~~~~~
567 The INLINABLE pragma allows (^) to be specialised at its call sites.
568 If it is called repeatedly at the same type, that can make a huge
569 difference, because of those constants which can be repeatedly
570 calculated.
571
572 Currently the fromInteger calls are not floated because we get
573 \d1 d2 x y -> blah
574 after the gentle round of simplification. -}
575
576 {- Rules for powers with known small exponent
577 see #5237
578 For small exponents, (^) is inefficient compared to manually
579 expanding the multiplication tree.
580 Here, rules for the most common exponent types are given.
581 The range of exponents for which rules are given is quite
582 arbitrary and kept small to not unduly increase the number of rules.
583 0 and 1 are excluded based on the assumption that nobody would
584 write x^0 or x^1 in code and the cases where an exponent could
585 be statically resolved to 0 or 1 are rare.
586
587 It might be desirable to have corresponding rules also for
588 exponents of other types (e. g., Word), but it's doubtful they
589 would fire, since the exponents of other types tend to get
590 floated out before the rule has a chance to fire.
591
592 Also desirable would be rules for (^^), but I haven't managed
593 to get those to fire.
594
595 Note: Trying to save multiplications by sharing the square for
596 exponents 4 and 5 does not save time, indeed, for Double, it is
597 up to twice slower, so the rules contain flat sequences of
598 multiplications.
599 -}
600
601 {-# RULES
602 "^2/Int" forall x. x ^ (2 :: Int) = let u = x in u*u
603 "^3/Int" forall x. x ^ (3 :: Int) = let u = x in u*u*u
604 "^4/Int" forall x. x ^ (4 :: Int) = let u = x in u*u*u*u
605 "^5/Int" forall x. x ^ (5 :: Int) = let u = x in u*u*u*u*u
606 "^2/Integer" forall x. x ^ (2 :: Integer) = let u = x in u*u
607 "^3/Integer" forall x. x ^ (3 :: Integer) = let u = x in u*u*u
608 "^4/Integer" forall x. x ^ (4 :: Integer) = let u = x in u*u*u*u
609 "^5/Integer" forall x. x ^ (5 :: Integer) = let u = x in u*u*u*u*u
610 #-}
611
612 -------------------------------------------------------
613 -- Special power functions for Rational
614 --
615 -- see #4337
616 --
617 -- Rationale:
618 -- For a legitimate Rational (n :% d), the numerator and denominator are
619 -- coprime, i.e. they have no common prime factor.
620 -- Therefore all powers (n ^ a) and (d ^ b) are also coprime, so it is
621 -- not necessary to compute the greatest common divisor, which would be
622 -- done in the default implementation at each multiplication step.
623 -- Since exponentiation quickly leads to very large numbers and
624 -- calculation of gcds is generally very slow for large numbers,
625 -- avoiding the gcd leads to an order of magnitude speedup relatively
626 -- soon (and an asymptotic improvement overall).
627 --
628 -- Note:
629 -- We cannot use these functions for general Ratio a because that would
630 -- change results in a multitude of cases.
631 -- The cause is that if a and b are coprime, their remainders by any
632 -- positive modulus generally aren't, so in the default implementation
633 -- reduction occurs.
634 --
635 -- Example:
636 -- (17 % 3) ^ 3 :: Ratio Word8
637 -- Default:
638 -- (17 % 3) ^ 3 = ((17 % 3) ^ 2) * (17 % 3)
639 -- = ((289 `mod` 256) % 9) * (17 % 3)
640 -- = (33 % 9) * (17 % 3)
641 -- = (11 % 3) * (17 % 3)
642 -- = (187 % 9)
643 -- But:
644 -- ((17^3) `mod` 256) % (3^3) = (4913 `mod` 256) % 27
645 -- = 49 % 27
646 --
647 -- TODO:
648 -- Find out whether special-casing for numerator, denominator or
649 -- exponent = 1 (or -1, where that may apply) gains something.
650
651 -- Special version of (^) for Rational base
652 {-# RULES "(^)/Rational" (^) = (^%^) #-}
653 (^%^) :: Integral a => Rational -> a -> Rational
654 (n :% d) ^%^ e
655 | e < 0 = errorWithoutStackTrace "Negative exponent"
656 | e == 0 = 1 :% 1
657 | otherwise = (n ^ e) :% (d ^ e)
658
659 -- Special version of (^^) for Rational base
660 {-# RULES "(^^)/Rational" (^^) = (^^%^^) #-}
661 (^^%^^) :: Integral a => Rational -> a -> Rational
662 (n :% d) ^^%^^ e
663 | e > 0 = (n ^ e) :% (d ^ e)
664 | e == 0 = 1 :% 1
665 | n > 0 = (d ^ (negate e)) :% (n ^ (negate e))
666 | n == 0 = ratioZeroDenominatorError
667 | otherwise = let nn = d ^ (negate e)
668 dd = (negate n) ^ (negate e)
669 in if even e then (nn :% dd) else (negate nn :% dd)
670
671 -------------------------------------------------------
672 -- | @'gcd' x y@ is the non-negative factor of both @x@ and @y@ of which
673 -- every common factor of @x@ and @y@ is also a factor; for example
674 -- @'gcd' 4 2 = 2@, @'gcd' (-4) 6 = 2@, @'gcd' 0 4@ = @4@. @'gcd' 0 0@ = @0@.
675 -- (That is, the common divisor that is \"greatest\" in the divisibility
676 -- preordering.)
677 --
678 -- Note: Since for signed fixed-width integer types, @'abs' 'minBound' < 0@,
679 -- the result may be negative if one of the arguments is @'minBound'@ (and
680 -- necessarily is if the other is @0@ or @'minBound'@) for such types.
681 gcd :: (Integral a) => a -> a -> a
682 {-# NOINLINE [1] gcd #-}
683 gcd x y = gcd' (abs x) (abs y)
684 where gcd' a 0 = a
685 gcd' a b = gcd' b (a `rem` b)
686
687 -- | @'lcm' x y@ is the smallest positive integer that both @x@ and @y@ divide.
688 lcm :: (Integral a) => a -> a -> a
689 {-# SPECIALISE lcm :: Int -> Int -> Int #-}
690 {-# SPECIALISE lcm :: Word -> Word -> Word #-}
691 {-# NOINLINE [1] lcm #-}
692 lcm _ 0 = 0
693 lcm 0 _ = 0
694 lcm x y = abs ((x `quot` (gcd x y)) * y)
695
696 #if defined(OPTIMISE_INTEGER_GCD_LCM)
697 {-# RULES
698 "gcd/Int->Int->Int" gcd = gcdInt'
699 "gcd/Integer->Integer->Integer" gcd = gcdInteger
700 "lcm/Integer->Integer->Integer" lcm = lcmInteger
701 #-}
702
703 gcdInt' :: Int -> Int -> Int
704 gcdInt' (I# x) (I# y) = I# (gcdInt x y)
705
706 {-# RULES
707 "gcd/Word->Word->Word" gcd = gcdWord'
708 #-}
709
710 gcdWord' :: Word -> Word -> Word
711 gcdWord' (W# x) (W# y) = W# (gcdWord x y)
712 #endif
713
714 integralEnumFrom :: (Integral a, Bounded a) => a -> [a]
715 integralEnumFrom n = map fromInteger [toInteger n .. toInteger (maxBound `asTypeOf` n)]
716
717 integralEnumFromThen :: (Integral a, Bounded a) => a -> a -> [a]
718 integralEnumFromThen n1 n2
719 | i_n2 >= i_n1 = map fromInteger [i_n1, i_n2 .. toInteger (maxBound `asTypeOf` n1)]
720 | otherwise = map fromInteger [i_n1, i_n2 .. toInteger (minBound `asTypeOf` n1)]
721 where
722 i_n1 = toInteger n1
723 i_n2 = toInteger n2
724
725 integralEnumFromTo :: Integral a => a -> a -> [a]
726 integralEnumFromTo n m = map fromInteger [toInteger n .. toInteger m]
727
728 integralEnumFromThenTo :: Integral a => a -> a -> a -> [a]
729 integralEnumFromThenTo n1 n2 m
730 = map fromInteger [toInteger n1, toInteger n2 .. toInteger m]