5 // Alexander Chebaturkin (chebaturkin@gmail.com)
7 // Copyright (C) 2012 Alexander Chebaturkin
9 // Permission is hereby granted, free of charge, to any person obtaining
10 // a copy of this software and associated documentation files (the
11 // "Software"), to deal in the Software without restriction, including
12 // without limitation the rights to use, copy, modify, merge, publish,
13 // distribute, sublicense, and/or sell copies of the Software, and to
14 // permit persons to whom the Software is furnished to do so, subject to
15 // the following conditions:
17 // The above copyright notice and this permission notice shall be
18 // included in all copies or substantial portions of the Software.
20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 using Mono.CodeContracts.Static.DataStructures;
33 namespace Mono.CodeContracts.Static.Analysis.Numerical {
35 /// Represents a rational number.
37 public struct Rational : IEquatable<Rational> {
38 public static readonly Rational Zero = new Rational (0L);
39 public static readonly Rational One = new Rational (1L);
40 public static readonly Rational MinusOne = new Rational (-1L);
42 public static Rational PlusInfinity = new Rational (Kind.PlusInfinity);
43 public static Rational MinusInfinity = new Rational (Kind.MinusInfinity);
45 public static Rational MaxValue = new Rational (long.MaxValue);
46 public static Rational MinValue = new Rational (long.MinValue);
54 if (kind == Kind.Normal)
55 throw new ArgumentException (
56 "Kind should be equal to Kind.PlusInfinity or Kind.MinusInfinity", "kind");
63 Rational (long number)
68 Rational (long nominator, long denominator)
70 if (denominator == 0L)
71 throw new ArgumentException ("Denominator should not be equal to 0");
73 if (nominator == 0L) {
74 this.kind = Kind.Normal;
81 this.kind = Kind.Normal;
83 int sign = System.Math.Sign (nominator) * System.Math.Sign (denominator);
85 if (nominator == long.MinValue)
86 nominator = sign >= 0 ? long.MaxValue : long.MinValue;
88 nominator = sign * System.Math.Abs (nominator);
90 if (denominator == long.MinValue)
91 denominator = long.MaxValue;
93 denominator = System.Math.Abs (denominator);
95 if (nominator % denominator == 0) {
96 this.up = nominator / denominator;
102 long gcd = (nominator == 0L || nominator == long.MaxValue ||
103 denominator == 0L || denominator == long.MaxValue)
105 : GCD (System.Math.Abs (nominator), System.Math.Abs (denominator));
107 this.up = nominator / gcd;
108 this.down = denominator / gcd;
111 public bool IsInteger { get { return !this.IsInfinity && (this.up % this.down == 0L); } }
113 public bool IsInt32 { get { return this.IsInteger && this.up >= int.MinValue && this.up <= int.MaxValue; } }
115 public bool IsInfinity { get { return this.kind == Kind.PlusInfinity || this.kind == Kind.MinusInfinity; } }
116 public bool IsPlusInfinity { get { return this.kind == Kind.PlusInfinity; } }
117 public bool IsMinusInfinity { get { return this.kind == Kind.MinusInfinity; } }
119 public bool IsZero { get { return this.kind == Kind.Normal && this.up == 0L; } }
121 public bool IsMaxValue { get { return this.kind == Kind.Normal && this.up == long.MaxValue && this.down == 1L; } }
122 public bool IsMinValue { get { return this.kind == Kind.Normal && this.up == -long.MaxValue && this.down == 1L; } }
124 public int Sign { get { return GetSign (this); } }
126 public Rational NextInt32
132 var next = (long) System.Math.Ceiling ((double) this);
134 return For (next >= int.MaxValue ? int.MaxValue : next);
138 public Rational PreviousInt32
145 var prev = (long) System.Math.Floor ((double) this);
147 return For (prev <= int.MinValue ? int.MinValue : prev);
151 public Rational NextInt64
157 double next = System.Math.Ceiling ((double) this);
159 return For (next >= (double) long.MaxValue ? long.MaxValue : (long) System.Math.Truncate (next));
163 public long Up { get { return up; } }
164 public long Down { get { return down; } }
166 public bool IsInRange (long min, long max)
168 return min <= this && this <= max;
171 public static Rational For (long number)
173 return new Rational (number);
176 public static Rational For (long nominator, long denominator)
178 switch (denominator) {
180 return new Rational (nominator >= 0 ? Kind.PlusInfinity : Kind.MinusInfinity);
182 return new Rational (nominator, denominator);
186 public static bool operator == (Rational l, Rational r)
188 if (l.kind != r.kind)
191 if (l.kind != Kind.Normal)
194 return l.up == r.up && l.down == r.down;
197 public static bool operator != (Rational l, Rational r)
202 public static bool operator < (Rational l, Rational r)
204 if (l.IsMinusInfinity && !r.IsMinusInfinity
205 || r.IsPlusInfinity && !l.IsPlusInfinity)
207 if (l.IsPlusInfinity || r.IsMinusInfinity)
209 if (l.down == r.down)
211 if (l.up <= 0L && r.up > 0L)
213 if (l.up < 0L && r.up == 0L)
217 return checked(l.up * r.down) < checked(r.up * l.down);
219 catch (ArithmeticException) {
220 return (decimal) l.up / l.down < (decimal) r.up / r.down;
224 public static bool operator <= (Rational l, Rational r)
226 if (l.IsMinusInfinity || r.IsPlusInfinity)
228 if (l.IsPlusInfinity || r.IsMinusInfinity)
231 if (l.down == r.down)
235 return checked(l.up * r.down) <= checked(r.up * l.down);
237 catch (ArithmeticException) {
238 return (decimal) l.up / l.down <= (decimal) r.up / r.down;
242 public static bool operator >= (Rational l, Rational r)
247 public static bool operator <= (Rational l, long r)
250 case Kind.PlusInfinity:
252 case Kind.MinusInfinity:
256 return l.up <= checked(l.down * r);
258 catch (ArithmeticException) {
259 return (decimal) l.up / l.down <= r;
264 public static bool operator <= (long l, Rational r)
267 case Kind.PlusInfinity:
269 case Kind.MinusInfinity:
273 return r.up >= checked(r.down * l);
275 catch (ArithmeticException) {
276 return (decimal) r.up / r.down >= l;
281 public static bool operator >= (long l, Rational r)
286 public static bool operator >= (Rational l, long r)
291 public static bool operator > (Rational l, Rational r)
296 public static bool operator < (Rational l, long r)
299 case Kind.PlusInfinity:
301 case Kind.MinusInfinity:
305 return l.up < checked(r * l.down);
308 return (decimal) l.up / l.down < r;
313 public static bool operator > (Rational l, long r)
318 public static bool operator < (long l, Rational r)
321 case Kind.PlusInfinity:
323 case Kind.MinusInfinity:
327 return checked(l * r.down) < r.up;
330 return l < (decimal) r.up / r.down;
335 public static bool operator > (long l, Rational r)
340 public static Rational operator + (Rational l, Rational r)
343 if (TryAdd (l, r, out result))
346 throw new ArithmeticException ();
349 public static Rational operator - (Rational l, Rational r)
352 if (TrySubtract (l, r, out result))
355 throw new ArithmeticException ();
358 public static Rational operator * (Rational l, Rational r)
361 if (TryMultiply (l, r, out result))
364 throw new ArithmeticException ();
367 public static Rational operator / (Rational l, Rational r)
370 if (TryDivide (l, r, out result))
373 throw new ArithmeticException ();
376 public static Rational operator - (Rational l, long i)
378 if (l.kind == Kind.Normal && l.down == 1L)
380 return For (checked(l.up - i));
382 catch (ArithmeticException) {
388 public static Rational operator + (Rational l, long i)
390 if (l.kind == Kind.Normal && l.down == 1L)
392 return For (checked(l.up + i));
394 catch (ArithmeticException) {
400 public static Rational operator - (Rational value)
403 if (TryUnaryMinus (value, out result))
406 throw new ArithmeticException ();
409 public static explicit operator double (Rational r)
412 case Kind.PlusInfinity:
413 return double.PositiveInfinity;
414 case Kind.MinusInfinity:
415 return double.NegativeInfinity;
417 return (double) r.up / r.down;
421 public static explicit operator long (Rational r)
424 return r.up >= 0L ? long.MaxValue : long.MinValue;
427 return (long) System.Math.Round ((double) r.up / r.down);
432 public static explicit operator int (Rational r)
435 return (int) System.Math.Round ((double) r.up / r.down);
437 return r.up >= 0L ? int.MaxValue : int.MinValue;
440 public static implicit operator Rational (long l)
445 public static Rational Abs (Rational a)
448 case Kind.PlusInfinity:
449 case Kind.MinusInfinity:
452 return a.IsZero || a > 0L ? a : -a;
456 public static Rational Max (Rational a, Rational b)
458 return a < b ? b : a;
461 public static Rational Min (Rational a, Rational b)
463 return a < b ? a : b;
466 public static bool TryAdd (Rational l, Rational r, out Rational result)
469 return true.With (r, out result);
471 if (r.IsZero || l.IsInfinity)
472 return true.With (l, out result);
475 return true.With (r, out result);
477 if (l.IsMaxValue && r > 0L || r.IsMaxValue && l > 0L)
478 return true.With (PlusInfinity, out result);
483 if (l.down == r.down) {
484 if (l.up == r.up && (r.down & 1L) == 0L) {
489 nom = checked (l.up + r.up);
494 nom = checked (l.up * r.down + r.up * l.down);
495 denom = checked (l.down * r.down);
498 catch (ArithmeticException) {
500 long gcd = GCD (l.down, r.down);
503 l.up * unchecked (r.down / gcd) +
504 r.up * unchecked (l.down / gcd));
505 denom = checked ((l.down / gcd) * r.down);
507 catch (ArithmeticException) {
508 return false.Without (out result);
512 return true.With (denom == 1L ? For (nom) : For (nom, denom), out result);
515 public static bool TrySubtract (Rational l, Rational r, out Rational result)
518 return true.With (l, out result);
521 return true.With (-r, out result);
524 return true.With (Zero, out result);
526 if (r < 0L && !r.IsMinValue)
527 return TryAdd (l, Abs (r), out result);
530 return true.With (l, out result);
533 return true.With (-r, out result);
535 if (l.IsMinValue && r > 0L)
536 return true.With (MinusInfinity, out result);
541 if (l.down == r.down) {
542 nom = checked (l.up - r.up);
546 nom = checked (l.up * r.down - r.up * l.down);
547 denom = checked (l.down * r.down);
550 catch (ArithmeticException) {
551 return false.Without (out result);
554 return true.With (For (nom, denom), out result);
557 public static bool TryDivide (Rational l, Rational r, out Rational result)
560 return true.With (l, out result);
563 return false.Without (out result);
565 if (l.IsZero || r.IsInfinity)
566 return true.With (Zero, out result);
568 if (l.IsPlusInfinity)
569 return true.With (r.Sign > 0 ? PlusInfinity : MinusInfinity, out result);
571 if (l.IsMinusInfinity)
572 return true.With (r.Sign > 0 ? MinusInfinity : PlusInfinity, out result);
578 // (a/b)/(a/c) = (c/b)
583 else if (l.down == r.down) {
584 // (a/c)/(b/c) = (a/b)
590 // (x/y) / (e/f) == (x/e) * (f/y)
592 Rational a = For (l.up, r.up);
593 Rational b = For (r.down, l.down);
596 return TryMultiply (a, b, out result);
598 catch (ArithmeticException) {
599 return false.Without (out result);
603 return true.With (For (nom, denom), out result);
606 public static bool TryMultiply (Rational l, Rational r, out Rational result)
608 if (l.IsZero || r.IsZero)
609 return true.With (Zero, out result);
612 return true.With (r, out result);
614 return true.With (l, out result);
616 if (l.IsPlusInfinity) {
617 if (r.IsPlusInfinity)
618 result = PlusInfinity;
619 else if (r.IsMinusInfinity)
620 result = MinusInfinity;
624 result = r.Sign > 0 ? PlusInfinity : MinusInfinity;
629 if (l.IsMinusInfinity) {
630 if (r.IsPlusInfinity)
631 result = MinusInfinity;
632 else if (r.IsMinusInfinity)
633 result = PlusInfinity;
637 result = r.Sign > 0 ? MinusInfinity : PlusInfinity;
642 if (r.IsPlusInfinity) {
646 result = l.Sign > 0 ? PlusInfinity : MinusInfinity;
651 if (r.IsMinusInfinity) {
655 result = l.Sign > 0 ? MinusInfinity : PlusInfinity;
664 Rational a = For (l.up, r.down);
665 Rational b = For (r.up, l.down);
667 nom = checked(a.up * b.up);
668 denom = checked(a.down * b.down);
670 catch (ArithmeticException) {
671 return false.Without (out result);
674 return true.With (For (nom, denom), out result);
677 public static bool TryUnaryMinus (Rational value, out Rational result)
680 return true.With (value, out result);
682 switch (value.kind) {
683 case Kind.PlusInfinity:
684 return true.With (MinusInfinity, out result);
685 case Kind.MinusInfinity:
686 return true.With (PlusInfinity, out result);
689 if (value.IsMinValue)
690 return true.With (MaxValue, out result);
691 if (value.IsMaxValue)
692 return true.With (MinValue, out result);
694 return true.With (For (-value.up, value.down), out result);
697 static int GetSign (Rational r)
700 case Kind.PlusInfinity:
702 case Kind.MinusInfinity:
705 return System.Math.Sign (r.up) * System.Math.Sign (r.down);
709 static long GCD (long a, long b)
716 while (((aa | bb) & 1L) == 0L) //while both divide by 2
723 while ((aa & 1L) == 0L) //get rid of other 2's factors
727 while ((bb & 1L) == 0L)
742 return (long) aa << pow;
745 public override bool Equals (object obj)
747 if (ReferenceEquals (null, obj))
749 if (ReferenceEquals (this, obj))
751 return obj is Rational && this.Equals ((Rational) obj);
754 public bool Equals (Rational other)
756 return this == other;
759 public override int GetHashCode ()
762 int hashCode = this.kind.GetHashCode ();
763 hashCode = (hashCode * 397) ^ this.up.GetHashCode ();
764 hashCode = (hashCode * 1001) ^ this.down.GetHashCode ();
769 public override string ToString ()
772 case Kind.MinusInfinity:
774 (this.up == -1L || this.down == 0L
776 : string.Format ("({0} / {1})", this.up, this.down));
777 case Kind.PlusInfinity:
779 (this.up == 1L || this.down == 0L
781 : string.Format ("({0} / {1})", this.up, this.down));
783 return this.IsInteger
784 ? this.up.ToString ()
785 : string.Format ("({0} / {1})", this.up, this.down);
796 static class RationalExtensions {
797 public static TExpr ToExpression<TVar, TExpr>(this Rational value, IExpressionEncoder<TVar, TExpr> encoder )
800 return encoder.ConstantFor ((long) value);
801 if (value.IsPlusInfinity)
802 return encoder.CompoundFor (ExpressionType.Int32, ExpressionOperator.Div,
803 encoder.ConstantFor (1L), encoder.ConstantFor (0L));
804 if (value.IsMinusInfinity)
805 return encoder.CompoundFor (ExpressionType.Int32, ExpressionOperator.Div,
806 encoder.ConstantFor (-1L), encoder.ConstantFor (0L));
808 TExpr l = encoder.ConstantFor (value.Up);
809 TExpr r = encoder.ConstantFor (value.Down);
811 return encoder.CompoundFor (ExpressionType.Int32, ExpressionOperator.Div, l, r);