|
An old coworker reported an error to me when doing a comparison of 14/5 and 20/1 would yeild the wrong result. For some stupid reason, I was doing a CrossReducePair (which is only safe when doing multiplication; comparisons are subtraction). Replace that method with this corrected version.
public int CompareTo(Fraction right)
{
if (this.m_Denominator == 0)
{
return IndeterminantCompare(NormalizeIndeterminate(this.m_Numerator), right);
}
if (right.m_Denominator == 0)
{
return - IndeterminantCompare(NormalizeIndeterminate(right.m_Numerator), this);
}
right.m_Numerator = -right.m_Numerator;
Fraction difference = Add(this, right);
if (difference.m_Numerator < 0)
return -1;
else if (difference.m_Numerator > 0)
return 1;
else
return 0;
} Sorry...
-- modified at 13:28 Wednesday 9th November, 2005
|
|
|
|
|
Thanks for this class! I needed something like this just the other day. I incorporated my needs and the changes suggested by Jeffery Sax.
It avoids most overflows by finding the GCD for Add [Jeffery Sax] and Multiply [Marc C. Brooks]
Understands and handles NaN, PositiveInfinity, NegativeInfinity just like double [Marc C. Brooks]
Fixed several uses of int where long was correct [Marc C. Brooks]
Made value-type (struct) [Jeffery Sax]
Added ToInt32(), ToInt64() which throw for invalid (NaN, PositiveInfinity, NegativeInfinity) [Marc C. Brooks]
Removed redundant Value property [Jeffery Sax]
Added explicit conversion to Int32 and Int64 [Marc C. Brooks]
Better handling of exceptions [Marc C. Brooks]
Reorganize code, add XML doc and regions [Marc C. Brooks]
Proper implementations of Equals [Marc C. Brooks, Jeffery Sax]
Uses Math.Log(xx,2) and Math.Pow(xx,2) to get the best accuracy possible when converting doubles [Marc C. Brooks, Jeffery Sax]
Due to limitations of the CodeProject message system, the XML docs have been stripped. If you want a copy of the revised class, just e-mail me
Here's the revised Fraction.cs class.
using System;
using System.Globalization;
namespace Mehroz
{
public struct Fraction
{
#region Constructors
public Fraction(long wholeNumber)
{
m_Numerator = wholeNumber;
m_Denominator = 1;
}
public Fraction(double floatingPointNumber)
{
this = ToFraction(floatingPointNumber);
}
public Fraction(string inValue)
{
this = ToFraction(inValue);
}
public Fraction(long numerator, long denominator)
{
m_Numerator = numerator;
m_Denominator = denominator;
ReduceFraction(ref this);
}
private Fraction(Indeterminates type)
{
m_Denominator = 0;
m_Numerator = (long)type;
}
#endregion
#region Properties
public long Numerator
{
get
{
return m_Numerator;
}
set
{
m_Numerator = value;
}
}
public long Denominator
{
get
{
return m_Denominator;
}
set
{
m_Denominator = value;
}
}
#endregion
#region Explicit conversions
#region To primitives
public Int32 ToInt32()
{
if (this.Denominator == 0)
{
throw new FractionException(string.Format("Cannot convert {0} to Int32", IndeterminateTypeName(this.Numerator)), new System.NotFiniteNumberException());
}
long bestGuess = this.Numerator / this.Denominator;
if (bestGuess > Int32.MaxValue || bestGuess < Int32.MinValue)
{
throw new FractionException("Cannot convert to Int32", new System.OverflowException());
}
return (Int32)bestGuess;
}
public Int64 ToInt64()
{
if (this.Denominator == 0)
{
throw new FractionException(string.Format("Cannot convert {0} to Int64", IndeterminateTypeName(this.Numerator)), new System.NotFiniteNumberException());
}
return this.Numerator / this.Denominator;
}
public double ToDouble()
{
if (this.Denominator == 1)
return this.Numerator;
else if (this.Denominator == 0)
{
switch (NormalizeIndeterminate(this.Numerator))
{
case Indeterminates.NegativeInfinity:
return double.NegativeInfinity;
case Indeterminates.PositiveInfinity:
return double.PositiveInfinity;
case Indeterminates.NaN:
default:
return double.NaN;
}
}
else
{
return (double)this.Numerator / (double)this.Denominator;
}
}
public override string ToString()
{
if (this.Denominator == 1)
{
return this.Numerator.ToString();
}
else if (this.Denominator == 0)
{
return IndeterminateTypeName(this.Numerator);
}
else
{
return this.Numerator.ToString() + "/" + this.Denominator.ToString();
}
}
#endregion
#region From primitives
public static Fraction ToFraction(long inValue)
{
return new Fraction(inValue);
}
public static Fraction ToFraction(double inValue)
{
if (double.IsNegativeInfinity(inValue))
{
return new Fraction(Indeterminates.NegativeInfinity);
}
else if (double.IsPositiveInfinity(inValue))
{
return new Fraction(Indeterminates.PositiveInfinity);
}
else if (double.IsNaN(inValue))
{
return new Fraction(Indeterminates.NaN);
}
else if (inValue % 1 == 0)
{
return new Fraction((Int64) inValue);
}
else
{
try
{
checked
{
int sign = Math.Sign(inValue);
double numerator = Math.Abs(inValue);
long inScale = (long)Math.Log(numerator, 2);
double denominator = Math.Pow(2, Math.Abs(inScale));
return new Fraction((long)Math.Round(numerator * denominator * sign), (long)Math.Floor(denominator));
}
}
catch (Exception e)
{
throw new FractionException("Assigned from double", e);
}
}
}
public static Fraction ToFraction(string inValue)
{
if (inValue == null)
throw new ArgumentNullException("inValue");
NumberFormatInfo info = NumberFormatInfo.CurrentInfo;
string trimmedValue = inValue.Trim();
if (trimmedValue == info.NaNSymbol)
return new Fraction(Indeterminates.NaN);
else if (trimmedValue == info.PositiveInfinitySymbol)
return new Fraction(Indeterminates.PositiveInfinity);
else if (trimmedValue == info.NegativeInfinitySymbol)
return new Fraction(Indeterminates.NegativeInfinity);
else
{
int slashPos = inValue.IndexOf('/');
if (slashPos > -1)
{
long numerator = Convert.ToInt64(inValue.Substring(0, slashPos));
long denominator = Convert.ToInt64(inValue.Substring(slashPos + 1));
return new Fraction(numerator, denominator);
}
else
{
int decimalPos = inValue.IndexOf(info.CurrencyDecimalSeparator);
if (decimalPos > -1)
return new Fraction(Convert.ToDouble(inValue));
else
return new Fraction(Convert.ToInt64(inValue));
}
}
}
#endregion
#endregion
#region Indeterminate classifications
public bool IsNaN()
{
if (this.Denominator == 0
&& NormalizeIndeterminate(this.Numerator) == Indeterminates.NaN)
return true;
else
return false;
}
public bool IsPositiveInfinity()
{
if (this.Denominator == 0
&& NormalizeIndeterminate(this.Numerator) == Indeterminates.PositiveInfinity)
return true;
else
return false;
}
public bool IsNegativeInfinity()
{
if (this.Denominator == 0
&& NormalizeIndeterminate(this.Numerator) == Indeterminates.NegativeInfinity)
return true;
else
return false;
}
#endregion
#region Inversion
public Fraction Inverse()
{
Fraction frac = new Fraction();
frac.Numerator = this.Denominator;
frac.Denominator = this.Numerator;
return frac;
}
public static Fraction Inverted(long value)
{
Fraction frac = new Fraction(value);
return frac.Inverse();
}
public static Fraction Inverted(double value)
{
Fraction frac = new Fraction(value);
return frac.Inverse();
}
#endregion
#region Operators
#region Unary Negation operator
public static Fraction operator -(Fraction left)
{
return Negate(left);
}
#endregion
#region Addition operators
public static Fraction operator +(Fraction left, Fraction right)
{
return Add(left, right);
}
public static Fraction operator +(long left, Fraction right)
{
return Add(new Fraction(left), right);
}
public static Fraction operator +(Fraction left, long right)
{
return Add(left, new Fraction(right));
}
public static Fraction operator +(double left, Fraction right)
{
return Add(ToFraction(left), right);
}
public static Fraction operator +(Fraction left, double right)
{
return Add(left, ToFraction(right));
}
#endregion
#region Subtraction operators
public static Fraction operator -(Fraction left, Fraction right)
{
return Add(left, - right);
}
public static Fraction operator -(long left, Fraction right)
{
return Add(new Fraction(left), - right);
}
public static Fraction operator -(Fraction left, long right)
{
return Add(left, new Fraction(- right));
}
public static Fraction operator -(double left, Fraction right)
{
return Add(ToFraction(left), - right);
}
public static Fraction operator -(Fraction left, double right)
{
return Add(left, ToFraction(- right));
}
#endregion
#region Multiplication operators
public static Fraction operator *(Fraction left, Fraction right)
{
return Multiply(left, right);
}
public static Fraction operator *(long left, Fraction right)
{
return Multiply(new Fraction(left), right);
}
public static Fraction operator *(Fraction left, long right)
{
return Multiply(left, new Fraction(right));
}
public static Fraction operator *(double left, Fraction right)
{
return Multiply(ToFraction(left), right);
}
public static Fraction operator *(Fraction left, double right)
{
return Multiply(left, ToFraction(right));
}
#endregion
#region Division operators
public static Fraction operator /(Fraction left, Fraction right)
{
return Multiply(left, right.Inverse());
}
public static Fraction operator /(long left, Fraction right)
{
return Multiply(new Fraction(left), right.Inverse());
}
public static Fraction operator /(Fraction left, long right)
{
return Multiply(left, Inverted(right));
}
public static Fraction operator /(double left, Fraction right)
{
return Multiply(ToFraction(left), right.Inverse());
}
public static Fraction operator /(Fraction left, double right)
{
return Multiply(left, Inverted(right));
}
#endregion
#region Equal operators
public static bool operator ==(Fraction left, Fraction right)
{
return left.Equals(right);
}
public static bool operator ==(Fraction left, long right)
{
return left.Equals(new Fraction(right));
}
public static bool operator ==(Fraction left, double right)
{
return left.Equals(new Fraction(right));
}
#endregion
#region Not-equal operators
public static bool operator !=(Fraction left, Fraction right)
{
return ! left.Equals(right);
}
public static bool operator !=(Fraction left, long right)
{
return ! left.Equals(new Fraction(right));
}
public static bool operator !=(Fraction left, double right)
{
return ! left.Equals(new Fraction(right));
}
#endregion
#region Inequality operators
public static bool operator <(Fraction left, Fraction right)
{
if (left.Denominator == 0)
{
return IndeterminantLess(NormalizeIndeterminate(left.Numerator), right);
}
if (right.Denominator == 0)
{
return (NormalizeIndeterminate(right.Numerator) == Indeterminates.PositiveInfinity);
}
CrossReducePair(ref left, ref right);
try
{
checked
{
long leftScale = left.Numerator * right.Denominator;
long rightScale = left.Denominator * right.Numerator;
return leftScale < rightScale;
}
}
catch (Exception e)
{
throw new FractionException("Compare < error", e);
}
}
public static bool operator >(Fraction left, Fraction right)
{
if (right.Denominator == 0)
{
return IndeterminantLess(NormalizeIndeterminate(right.Numerator), left);
}
if (left.Denominator == 0)
{
return (NormalizeIndeterminate(left.Numerator) == Indeterminates.PositiveInfinity);
}
CrossReducePair(ref left, ref right);
try
{
checked
{
long leftScale = left.Numerator * right.Denominator;
long rightScale = left.Denominator * right.Numerator;
return leftScale > rightScale;
}
}
catch (Exception e)
{
throw new FractionException("Compare > error", e);
}
}
public static bool operator <=(Fraction left, Fraction right)
{
return ! (right > left);
}
public static bool operator >=(Fraction left, Fraction right)
{
return ! (right < left);
}
#endregion
#region Implict conversion from primitive operators
public static implicit operator Fraction(long value)
{
return new Fraction(value);
}
public static implicit operator Fraction(double value)
{
return new Fraction(value);
}
public static implicit operator Fraction(string value)
{
return new Fraction(value);
}
#endregion
#region Explicit converstion to primitive operators
public static explicit operator int(Fraction frac)
{
return frac.ToInt32();
}
public static explicit operator long(Fraction frac)
{
return frac.ToInt64();
}
public static explicit operator double(Fraction frac)
{
return frac.ToDouble();
}
public static implicit operator string(Fraction frac)
{
return frac.ToString();
}
#endregion
#endregion
#region Equals and GetHashCode overrides
public override bool Equals(object obj)
{
if (obj == null)
return false;
try
{
Fraction frac;
if (obj is Fraction)
frac = (Fraction)obj;
else if (obj is long)
frac = new Fraction((long)obj);
else if (obj is int)
frac = new Fraction((int)obj);
else if (obj is double)
frac = new Fraction((double)obj);
else if (obj is float)
frac = new Fraction((float)obj);
else if (obj is string)
frac = new Fraction((string)obj);
else
return false;
ReduceFraction(ref this);
ReduceFraction(ref frac);
return (this.Numerator == frac.Numerator && this.Denominator == frac.Denominator);
}
catch
{
return false;
}
}
public override int GetHashCode()
{
ReduceFraction(ref this);
return Convert.ToInt32((Numerator ^ Denominator) & 0xFFFFFFFF);
}
#endregion
#region Reduction
public static void ReduceFraction(ref Fraction frac)
{
if (frac.Denominator == 0)
{
frac.Numerator = (long)NormalizeIndeterminate(frac.Numerator);
return;
}
if (frac.Numerator == 0)
{
frac.Denominator = 1;
return;
}
long iGCD = GCD(frac.Numerator, frac.Denominator);
frac.Numerator /= iGCD;
frac.Denominator /= iGCD;
if ( frac.Denominator < 0 )
{
frac.Numerator = - frac.Numerator;
frac.Denominator = - frac.Denominator;
}
}
public static void CrossReducePair(ref Fraction frac1, ref Fraction frac2)
{
if (frac1.Denominator == 0 || frac2.Denominator == 0)
return;
long gcdTop = GCD(frac1.Numerator, frac2.Denominator);
frac1.Numerator = frac1.Numerator / gcdTop;
frac2.Denominator = frac2.Denominator / gcdTop;
long gcdBottom = GCD(frac1.Denominator, frac2.Numerator);
frac2.Numerator = frac2.Numerator / gcdBottom;
frac1.Denominator = frac1.Denominator / gcdBottom;
}
#endregion
#region Implementation
#region Inequality helper
private static bool IndeterminantLess(Indeterminates frac1Type, Fraction frac2)
{
switch (frac1Type)
{
case Indeterminates.NaN:
return ! (frac2.IsNaN() || frac2.IsNegativeInfinity());
case Indeterminates.NegativeInfinity:
return ! frac2.IsNegativeInfinity();
case Indeterminates.PositiveInfinity:
return false;
default:
return false;
}
}
#endregion
#region Math helpers
private static Fraction Negate(Fraction frac)
{
return new Fraction( - frac.Numerator, frac.Denominator);
}
private static Fraction Add(Fraction left, Fraction right)
{
long gcd = GCD(left.Denominator, right.Denominator);
long leftDenominator = left.Denominator / gcd;
long rightDenominator = right.Denominator / gcd;
try
{
checked
{
if (left.IsNaN() || right.IsNaN())
throw new ArithmeticException("Not-a-Number");
long numerator = left.Numerator * rightDenominator + right.Numerator * leftDenominator;
long denominator = leftDenominator * rightDenominator * gcd;
return new Fraction(numerator, denominator);
}
}
catch (Exception e)
{
throw new FractionException("Add error", e);
}
}
private static Fraction Multiply(Fraction left, Fraction right)
{
CrossReducePair(ref left, ref right);
try
{
checked
{
if (left.IsNaN() || right.IsNaN())
throw new ArithmeticException("Not-a-Number");
long numerator = left.Numerator * right.Numerator;
long denominator = left.Denominator * right.Denominator;
return new Fraction(numerator, denominator);
}
}
catch (Exception e)
{
throw new FractionException("Multiply error", e);
}
}
private static long GCD(long left, long right)
{
if (left < 0)
left = - left;
if (right < 0)
right = - right;
if (left < 2 || right < 2)
return 1;
do
{
if (left < right)
{
long temp = left;
left = right;
right = temp;
}
left %= right;
} while (left != 0);
return right;
}
#endregion
#region Indeterminate helpers
private static string IndeterminateTypeName(long numerator)
{
System.Globalization.NumberFormatInfo info = NumberFormatInfo.CurrentInfo;
switch (NormalizeIndeterminate(numerator))
{
case Indeterminates.PositiveInfinity:
return info.PositiveInfinitySymbol;
case Indeterminates.NegativeInfinity:
return info.NegativeInfinitySymbol;
default:
case Indeterminates.NaN:
return info.NaNSymbol;
}
}
private static Indeterminates NormalizeIndeterminate(long numerator)
{
switch (Math.Sign(numerator))
{
case 1:
return Indeterminates.PositiveInfinity;
case -1:
return Indeterminates.NegativeInfinity;
default:
case 0:
return Indeterminates.NaN;
}
}
#endregion
private long m_Numerator;
private long m_Denominator;
private enum Indeterminates
{
NaN = 0
, PositiveInfinity = 1
, NegativeInfinity = -1
}
#endregion
}
public class FractionException : Exception
{
public FractionException(string Message, Exception InnerException) : base(Message, InnerException)
{
}
}
}
|
|
|
|
|
Thank you very much for your nice work. You saved me from rewriting all the code again (taking into account all the suggestions by Jeffrey). I wrote such a simple and in-efficient(in many cases) class because all I wanted to do, was to write a matrix class using fractions so that I can verify my answers to questions of linear algebra.
Congratulations on your nice work.
Thanks,
Syed Mehroz Alam
Email: smehrozalam@yahoo.com
Homepage: Programming Home
URL: http://www.geocities.com/smehrozalam/
|
|
|
|
|
Hi Marc,
Interesting implementation of 'indeterminates.' Maybe 'special values' would have been a better name. Infinities are quite determined. There are a few things you should be aware of, however:- Operations on
NaN s do not throw exceptions. Instead, so the IEEE-754 standard for binary floating-point arithmetic[^] states, the return value should be once again NaN.
On that same note, you need to handle the special case that NaN != NaN is true. In fact, this is the only logical operation with a NaN operand that doesn't return false . - To be consistent with the rest of the Base Class Libraries, you may want to make these special values available as static readonly fields of the type. You may also want to add the related static methods defined in
Double , like IsPositiveInfinity , etc. - Your implementation of
Equals still doesn't comply with standard practices, although this is not stated as clearly as it should. Equals is used for object equality, and so should return false if the object being compared is not of type Fraction . Instead, the code in your Equals method belongs in a static, type safe Compare method that behaves like the Compare method of the IComparer interface. All logical operators should call this same method, or a st.
See the Shared Source CLI[^] for details. - The conversion from
Double can be made simpler by decoding the 64 bit floating-point number. The binary layout is fixed by the CLI standard as that of IEEE-754 double-precision numbers, so it is safe to do this. The way to do this would be to use BitConverter.DoubleToInt64Bits to obtain a usable binary representation, and then move some bits around. This method is guaranteed to work, and is much faster than using Math.Log and Math.Pow . You've added a lot of value to this class. Well done!
Jeffrey
Everything should be as simple as possible, but not simpler. -- Albert Einstein
Numerical components for C# and VB.NET
|
|
|
|
|
Jeffrey Sax wrote:
Operations on NaNs do not throw exceptions. Instead, so the IEEE-754 standard for binary floating-point arithmetic[^] states, the return value should be once again NaN.
Done. Changed Add and Multiply methods (used for all operations) to return NaN for operations involving left or right of NaN.
On that same note, you need to handle the special case that NaN != NaN is true. In fact, this is the only logical operation with a NaN operand that doesn't return false.
Done. Added a helper for comparing equality of two Fractions, made == and != call down to it. Double returns true from Equals if both values are NaN, so I do too.
Your implementation of Equals still doesn't comply with standard practices, although this is not stated as clearly as it should. Equals is used for object equality, and so should return false if the object being compared is not of type Fraction.
Done. The override now returns false for non-Fraction right-side, otherwise calls the new helper. Since Fraction is a value type, I wonder what object equality means in this case, so I just compare for same values after reduction.
Instead, the code in your Equals method belongs in a static, type safe Compare method that behaves like the Compare method of the IComparer interface. All logical operators should call this same method
Done. Added ICompare.CompareTo method. Since this is a value-type I made it handle the automatic conversions as appropriate. All the operator comparisons now use the type-safe CompareTo method (and internal helpers)
To be consistent with the rest of the Base Class Libraries, you may want to make these special values available as static readonly fields of the type
Done. Added Fraction.NaN, Fraction.PositiveInfinity and Fraction.NegativeInfinity. Also added MinValue, MaxValue and Epsilon. Also added Zero to deal with the issue of no-default constructor for structs (because it's a NaN otherwise).
You may also want to add the related static methods defined in Double, like IsPositiveInfinity, etc.
Those were already there. :grin: I did add IsInfinity
I also fixed the issues this code had with imprecise doubles (repeating decimals). I'm now using the repeating fraction logic I found here which does as good a job as possible and is relatively quick.
Here's the revised code:
using System;
using System.Runtime.InteropServices;
using System.Globalization;
namespace Mehroz
{
[Serializable, StructLayout(LayoutKind.Sequential)]
public struct Fraction : IComparable, IFormattable
{
#region Constructors
public Fraction(long wholeNumber)
{
if (wholeNumber == long.MinValue)
wholeNumber++;
m_Numerator = wholeNumber;
m_Denominator = 1;
}
public Fraction(double floatingPointNumber)
{
this = ToFraction(floatingPointNumber);
}
public Fraction(string inValue)
{
this = ToFraction(inValue);
}
public Fraction(long numerator, long denominator)
{
if (numerator == long.MinValue)
numerator++;
if (denominator == long.MinValue)
denominator++;
m_Numerator = numerator;
m_Denominator = denominator;
ReduceFraction(ref this);
}
private Fraction(Indeterminates type)
{
m_Numerator = (long)type;
m_Denominator = 0;
}
#endregion
#region Properties
public long Numerator
{
get
{
return m_Numerator;
}
set
{
m_Numerator = value;
}
}
public long Denominator
{
get
{
return m_Denominator;
}
set
{
m_Denominator = value;
}
}
#endregion
#region Expose constants
public static readonly Fraction NaN = new Fraction(Indeterminates.NaN);
public static readonly Fraction PositiveInfinity = new Fraction(Indeterminates.PositiveInfinity);
public static readonly Fraction NegativeInfinity = new Fraction(Indeterminates.NegativeInfinity);
public static readonly Fraction Zero = new Fraction(0,1);
public static readonly Fraction Epsilon = new Fraction(1, Int64.MaxValue);
private static readonly double EpsilonDouble = 1.0 / Int64.MaxValue;
public static readonly Fraction MaxValue = new Fraction(Int64.MaxValue, 1);
public static readonly Fraction MinValue = new Fraction(Int64.MinValue, 1);
#endregion
#region Explicit conversions
#region To primitives
public Int32 ToInt32()
{
if (this.m_Denominator == 0)
{
throw new FractionException(string.Format("Cannot convert {0} to Int32", IndeterminateTypeName(this.m_Numerator)), new System.NotFiniteNumberException());
}
long bestGuess = this.m_Numerator / this.m_Denominator;
if (bestGuess > Int32.MaxValue || bestGuess < Int32.MinValue)
{
throw new FractionException("Cannot convert to Int32", new System.OverflowException());
}
return (Int32)bestGuess;
}
public Int64 ToInt64()
{
if (this.m_Denominator == 0)
{
throw new FractionException(string.Format("Cannot convert {0} to Int64", IndeterminateTypeName(this.m_Numerator)), new System.NotFiniteNumberException());
}
return this.m_Numerator / this.m_Denominator;
}
public double ToDouble()
{
if (this.m_Denominator == 1)
return this.m_Numerator;
else if (this.m_Denominator == 0)
{
switch (NormalizeIndeterminate(this.m_Numerator))
{
case Indeterminates.NegativeInfinity:
return double.NegativeInfinity;
case Indeterminates.PositiveInfinity:
return double.PositiveInfinity;
case Indeterminates.NaN:
default:
return double.NaN;
}
}
else
{
return (double)this.m_Numerator / (double)this.m_Denominator;
}
}
public override string ToString()
{
if (this.m_Denominator == 1)
{
return this.m_Numerator.ToString();
}
else if (this.m_Denominator == 0)
{
return IndeterminateTypeName(this.m_Numerator);
}
else
{
return this.m_Numerator.ToString() + "/" + this.m_Denominator.ToString();
}
}
#endregion
#region From primitives
public static Fraction ToFraction(long inValue)
{
return new Fraction(inValue);
}
public static Fraction ToFraction(double inValue)
{
if (double.IsNaN(inValue))
return NaN;
else if (double.IsNegativeInfinity(inValue))
return NegativeInfinity;
else if (double.IsPositiveInfinity(inValue))
return PositiveInfinity;
else if (inValue == 0.0d)
return Zero;
if (inValue > Int64.MaxValue)
throw new OverflowException(string.Format("Double {0} too large", inValue));
if (inValue < -Int64.MaxValue)
throw new OverflowException(string.Format("Double {0} too small", inValue));
if (-EpsilonDouble < inValue && inValue < EpsilonDouble)
throw new ArithmeticException(string.Format("Double {0} cannot be represented", inValue));
int sign = Math.Sign(inValue);
inValue = Math.Abs(inValue);
return ConvertPositiveDouble(sign, inValue);
}
public static Fraction ToFraction(string inValue)
{
if (inValue == null || inValue == string.Empty)
throw new ArgumentNullException("inValue");
NumberFormatInfo info = NumberFormatInfo.CurrentInfo;
string trimmedValue = inValue.Trim();
if (trimmedValue == info.NaNSymbol)
return NaN;
else if (trimmedValue == info.PositiveInfinitySymbol)
return PositiveInfinity;
else if (trimmedValue == info.NegativeInfinitySymbol)
return NegativeInfinity;
else
{
int slashPos = inValue.IndexOf('/');
if (slashPos > -1)
{
long numerator = Convert.ToInt64(inValue.Substring(0, slashPos));
long denominator = Convert.ToInt64(inValue.Substring(slashPos + 1));
return new Fraction(numerator, denominator);
}
else
{
int decimalPos = inValue.IndexOf(info.CurrencyDecimalSeparator);
if (decimalPos > -1)
return new Fraction(Convert.ToDouble(inValue));
else
return new Fraction(Convert.ToInt64(inValue));
}
}
}
#endregion
#endregion
#region Indeterminate classifications
public bool IsNaN()
{
if (this.m_Denominator == 0
&& NormalizeIndeterminate(this.m_Numerator) == Indeterminates.NaN)
return true;
else
return false;
}
public bool IsInfinity()
{
if (this.m_Denominator == 0
&& NormalizeIndeterminate(this.m_Numerator) != Indeterminates.NaN)
return true;
else
return false;
}
public bool IsPositiveInfinity()
{
if (this.m_Denominator == 0
&& NormalizeIndeterminate(this.m_Numerator) == Indeterminates.PositiveInfinity)
return true;
else
return false;
}
public bool IsNegativeInfinity()
{
if (this.m_Denominator == 0
&& NormalizeIndeterminate(this.m_Numerator) == Indeterminates.NegativeInfinity)
return true;
else
return false;
}
#endregion
#region Inversion
public Fraction Inverse()
{
Fraction frac = new Fraction();
frac.m_Numerator = this.m_Denominator;
frac.m_Denominator = this.m_Numerator;
return frac;
}
public static Fraction Inverted(long value)
{
Fraction frac = new Fraction(value);
return frac.Inverse();
}
public static Fraction Inverted(double value)
{
Fraction frac = new Fraction(value);
return frac.Inverse();
}
#endregion
#region Operators
#region Unary Negation operator
public static Fraction operator -(Fraction left)
{
return Negate(left);
}
#endregion
#region Addition operators
public static Fraction operator +(Fraction left, Fraction right)
{
return Add(left, right);
}
public static Fraction operator +(long left, Fraction right)
{
return Add(new Fraction(left), right);
}
public static Fraction operator +(Fraction left, long right)
{
return Add(left, new Fraction(right));
}
public static Fraction operator +(double left, Fraction right)
{
return Add(ToFraction(left), right);
}
public static Fraction operator +(Fraction left, double right)
{
return Add(left, ToFraction(right));
}
#endregion
#region Subtraction operators
public static Fraction operator -(Fraction left, Fraction right)
{
return Add(left, - right);
}
public static Fraction operator -(long left, Fraction right)
{
return Add(new Fraction(left), - right);
}
public static Fraction operator -(Fraction left, long right)
{
return Add(left, new Fraction(- right));
}
public static Fraction operator -(double left, Fraction right)
{
return Add(ToFraction(left), - right);
}
public static Fraction operator -(Fraction left, double right)
{
return Add(left, ToFraction(- right));
}
#endregion
#region Multiplication operators
public static Fraction operator *(Fraction left, Fraction right)
{
return Multiply(left, right);
}
public static Fraction operator *(long left, Fraction right)
{
return Multiply(new Fraction(left), right);
}
public static Fraction operator *(Fraction left, long right)
{
return Multiply(left, new Fraction(right));
}
public static Fraction operator *(double left, Fraction right)
{
return Multiply(ToFraction(left), right);
}
public static Fraction operator *(Fraction left, double right)
{
return Multiply(left, ToFraction(right));
}
#endregion
#region Division operators
public static Fraction operator /(Fraction left, Fraction right)
{
return Multiply(left, right.Inverse());
}
public static Fraction operator /(long left, Fraction right)
{
return Multiply(new Fraction(left), right.Inverse());
}
public static Fraction operator /(Fraction left, long right)
{
return Multiply(left, Inverted(right));
}
public static Fraction operator /(double left, Fraction right)
{
return Multiply(ToFraction(left), right.Inverse());
}
public static Fraction operator /(Fraction left, double right)
{
return Multiply(left, Inverted(right));
}
#endregion
#region Modulus operators
public static Fraction operator %(Fraction left, Fraction right)
{
return Modulus(left, right);
}
public static Fraction operator %(long left, Fraction right)
{
return Modulus(new Fraction(left), right);
}
public static Fraction operator %(Fraction left, long right)
{
return Modulus(left, right);
}
public static Fraction operator %(double left, Fraction right)
{
return Modulus(ToFraction(left), right);
}
public static Fraction operator %(Fraction left, double right)
{
return Modulus(left, right);
}
#endregion
#region Equal operators
public static bool operator ==(Fraction left, Fraction right)
{
return left.CompareEquality(right, false);
}
public static bool operator ==(Fraction left, long right)
{
return left.CompareEquality(new Fraction(right), false);
}
public static bool operator ==(Fraction left, double right)
{
return left.CompareEquality(new Fraction(right), false);
}
#endregion
#region Not-equal operators
public static bool operator !=(Fraction left, Fraction right)
{
return left.CompareEquality(right, true);
}
public static bool operator !=(Fraction left, long right)
{
return left.CompareEquality(new Fraction(right), true);
}
public static bool operator !=(Fraction left, double right)
{
return left.CompareEquality(new Fraction(right), true);
}
#endregion
#region Inequality operators
public static bool operator <(Fraction left, Fraction right)
{
return left.CompareTo(right) < 0;
}
public static bool operator >(Fraction left, Fraction right)
{
return left.CompareTo(right) > 0;
}
public static bool operator <=(Fraction left, Fraction right)
{
return left.CompareTo(right) <= 0;
}
public static bool operator >=(Fraction left, Fraction right)
{
return left.CompareTo(right) >= 0;
}
#endregion
#region Implict conversion from primitive operators
public static implicit operator Fraction(long value)
{
return new Fraction(value);
}
public static implicit operator Fraction(double value)
{
return new Fraction(value);
}
public static implicit operator Fraction(string value)
{
return new Fraction(value);
}
#endregion
#region Explicit converstion to primitive operators
public static explicit operator int(Fraction frac)
{
return frac.ToInt32();
}
public static explicit operator long(Fraction frac)
{
return frac.ToInt64();
}
public static explicit operator double(Fraction frac)
{
return frac.ToDouble();
}
public static implicit operator string(Fraction frac)
{
return frac.ToString();
}
#endregion
#endregion
#region Equals and GetHashCode overrides
public override bool Equals(object obj)
{
if (obj == null || ! (obj is Fraction))
return false;
try
{
Fraction right = (Fraction)obj;
return this.CompareEquality(right, false);
}
catch
{
return false;
}
}
public override int GetHashCode()
{
ReduceFraction(ref this);
int numeratorHash = this.m_Numerator.GetHashCode();
int denominatorHash = this.m_Denominator.GetHashCode();
return (numeratorHash ^ denominatorHash);
}
#endregion
#region IComparable member and type-specific version
public int CompareTo(object obj)
{
if (obj == null)
return 1;
Fraction right;
if (obj is Fraction)
right = (Fraction)obj;
else if (obj is long)
right = (long)obj;
else if (obj is double)
right = (double)obj;
else if (obj is string)
right = (string)obj;
else
throw new ArgumentException("Must be convertible to Fraction", "obj");
return this.CompareTo(right);
}
public int CompareTo(Fraction right)
{
if (this.m_Denominator == 0)
{
return IndeterminantCompare(NormalizeIndeterminate(this.m_Numerator), right);
}
if (right.m_Denominator == 0)
{
return - IndeterminantCompare(NormalizeIndeterminate(right.m_Numerator), this);
}
CrossReducePair(ref this, ref right);
try
{
checked
{
long leftScale = this.m_Numerator * right.m_Denominator;
long rightScale = this.m_Denominator * right.m_Numerator;
if (leftScale < rightScale)
return -1;
else if (leftScale > rightScale)
return 1;
else
return 0;
}
}
catch (Exception e)
{
throw new FractionException(string.Format("CompareTo({0}, {1}) error", this, right), e);
}
}
#endregion
#region IFormattable Members
string System.IFormattable.ToString(string format, IFormatProvider formatProvider)
{
return this.m_Numerator.ToString(format, formatProvider) + "/" + this.m_Denominator.ToString(format, formatProvider);
}
#endregion
#region Reduction
public static void ReduceFraction(ref Fraction frac)
{
if (frac.m_Denominator == 0)
{
frac.m_Numerator = (long)NormalizeIndeterminate(frac.m_Numerator);
return;
}
if (frac.m_Numerator == 0)
{
frac.m_Denominator = 1;
return;
}
long iGCD = GCD(frac.m_Numerator, frac.m_Denominator);
frac.m_Numerator /= iGCD;
frac.m_Denominator /= iGCD;
if ( frac.m_Denominator < 0 )
{
frac.m_Numerator = - frac.m_Numerator;
frac.m_Denominator = - frac.m_Denominator;
}
}
public static void CrossReducePair(ref Fraction frac1, ref Fraction frac2)
{
if (frac1.m_Denominator == 0 || frac2.m_Denominator == 0)
return;
long gcdTop = GCD(frac1.m_Numerator, frac2.m_Denominator);
frac1.m_Numerator = frac1.m_Numerator / gcdTop;
frac2.m_Denominator = frac2.m_Denominator / gcdTop;
long gcdBottom = GCD(frac1.m_Denominator, frac2.m_Numerator);
frac2.m_Numerator = frac2.m_Numerator / gcdBottom;
frac1.m_Denominator = frac1.m_Denominator / gcdBottom;
}
#endregion
#region Implementation
#region Convert a double to a fraction
private static Fraction ConvertPositiveDouble(int sign, double inValue)
{
long fractionNumerator = (long)inValue;
double fractionDenominator = 1;
double previousDenominator = 0;
double remainingDigits = inValue;
int maxIterations = 594;
while (remainingDigits != Math.Floor(remainingDigits)
&& Math.Abs(inValue - (fractionNumerator / fractionDenominator)) > double.Epsilon)
{
remainingDigits = 1.0 / (remainingDigits - Math.Floor(remainingDigits));
double scratch = fractionDenominator;
fractionDenominator =(Math.Floor(remainingDigits) * fractionDenominator) + previousDenominator;
fractionNumerator = (long)(inValue * fractionDenominator + 0.5);
previousDenominator = scratch;
if (maxIterations-- < 0)
break;
}
return new Fraction(fractionNumerator * sign, (long)fractionDenominator);
}
#endregion
#region Equality helper
private bool CompareEquality(Fraction right, bool notEqualCheck)
{
ReduceFraction(ref this);
ReduceFraction(ref right);
if (this.m_Numerator == right.m_Numerator && this.m_Denominator == right.m_Denominator)
{
if (notEqualCheck && this.IsNaN())
return true;
else
return ! notEqualCheck;
}
else
{
return notEqualCheck;
}
}
#endregion
#region Comparison helper
private static int IndeterminantCompare(Indeterminates leftType, Fraction right)
{
switch (leftType)
{
case Indeterminates.NaN:
if (right.IsNaN())
return 0;
else if (right.IsNegativeInfinity())
return 1;
else
return -1;
case Indeterminates.NegativeInfinity:
if (right.IsNegativeInfinity())
return 0;
else
return -1;
case Indeterminates.PositiveInfinity:
if (right.IsPositiveInfinity())
return 0;
else
return 1;
default:
return 0;
}
}
#endregion
#region Math helpers
private static Fraction Negate(Fraction frac)
{
return new Fraction( - frac.m_Numerator, frac.m_Denominator);
}
private static Fraction Add(Fraction left, Fraction right)
{
if (left.IsNaN() || right.IsNaN())
return NaN;
long gcd = GCD(left.m_Denominator, right.m_Denominator);
long leftDenominator = left.m_Denominator / gcd;
long rightDenominator = right.m_Denominator / gcd;
try
{
checked
{
long numerator = left.m_Numerator * rightDenominator + right.m_Numerator * leftDenominator;
long denominator = leftDenominator * rightDenominator * gcd;
return new Fraction(numerator, denominator);
}
}
catch (Exception e)
{
throw new FractionException("Add error", e);
}
}
private static Fraction Multiply(Fraction left, Fraction right)
{
if (left.IsNaN() || right.IsNaN())
return NaN;
CrossReducePair(ref left, ref right);
try
{
checked
{
long numerator = left.m_Numerator * right.m_Numerator;
long denominator = left.m_Denominator * right.m_Denominator;
return new Fraction(numerator, denominator);
}
}
catch (Exception e)
{
throw new FractionException("Multiply error", e);
}
}
private static Fraction Modulus(Fraction left, Fraction right)
{
if (left.IsNaN() || right.IsNaN())
return NaN;
try
{
checked
{
Int64 quotient = (Int64)(left / right);
Fraction whole = new Fraction(quotient * right.m_Numerator, right.m_Denominator);
return left - whole;
}
}
catch (Exception e)
{
throw new FractionException("Modulus error", e);
}
}
private static long GCD(long left, long right)
{
if (left < 0)
left = - left;
if (right < 0)
right = - right;
if (left < 2 || right < 2)
return 1;
do
{
if (left < right)
{
long temp = left;
left = right;
right = temp;
}
left %= right;
} while (left != 0);
return right;
}
#endregion
#region Indeterminate helpers
private static string IndeterminateTypeName(long numerator)
{
System.Globalization.NumberFormatInfo info = NumberFormatInfo.CurrentInfo;
switch (NormalizeIndeterminate(numerator))
{
case Indeterminates.PositiveInfinity:
return info.PositiveInfinitySymbol;
case Indeterminates.NegativeInfinity:
return info.NegativeInfinitySymbol;
default:
case Indeterminates.NaN:
return info.NaNSymbol;
}
}
private static Indeterminates NormalizeIndeterminate(long numerator)
{
switch (Math.Sign(numerator))
{
case 1:
return Indeterminates.PositiveInfinity;
case -1:
return Indeterminates.NegativeInfinity;
default:
case 0:
return Indeterminates.NaN;
}
}
private enum Indeterminates
{
NaN = 0
, PositiveInfinity = 1
, NegativeInfinity = -1
}
#endregion
#region Member variables
private long m_Numerator;
private long m_Denominator;
#endregion
#endregion
}
public class FractionException : Exception
{
public FractionException(string Message, Exception InnerException) : base(Message, InnerException)
{
}
}
}
|
|
|
|
|
Very cool code.
Just one comment, is it possible to add some fuzzy logic to convert something like 0.166666666667 into 1/6?
Thanks!
Hardy
|
|
|
|
|
I added my own DenominateTo() method. That does what you're talking about. I prefer methods that provide a new result, so note that in the following code, Reduce() returns a new Fraction, as does my method. Also, I used "this" for clarification but it's unnecessary...
public Fraction DenominateTo(long denominator) {
var ʀ = new Fraction (
(long)Math.Round(this.ToDouble() * denominator),
denominator
);
return ʀ.Reduce();
}
So if you want to get the nearest sixth....
var oneSixthFraction = FromDouble(0.1666667).DenominateTo(6);
I also overloaded the static FromDouble() method (I renamed it) to accept a double value as well as a denominator to simplify things...
public static Fraction FromDouble(double value, long denominator) {
return FromDouble(value).DenominateTo(denominator);
}
... which can be used like...
var oneSixthFraction = Fraction.FromDouble(0.1666667, 6);
And you can make the Reduce() optional or remove it.
=)
|
|
|
|
|
Overall, this is a nice implementation of basic fraction functionality. There is still room for improvement, however:- Conversion from Double should use base 2 rather than base 10. The 'ToString()' causes loss of precision in several ways, most notably due to the fact that it uses only 15 digits of precision.
Every double value within the range of Fraction is exactly representable by a Fraction , and so you should make this conversion exact. A round-trip cast expression like (double)(Fraction)x should return the original value x , or throw an OverflowException if x is out of range.
Ideally, you would also offer to find the fraction closest to the number, using Euclid's GCD algorithm backwards. You could put an upper limit on the size of the denominator, so that, for example, 0.333333334 gets converted to 1/3 rather than 166666667/500000000. - Your addition method can cause overflow when that is not necessary. You should divide out any common factors of the denominators. This common factor will only be divided out in the normalization. You could do something like:
long gcd = GCD(frac1.Denominator, frac2.Denominator);
long denominator1 = frac1.Denominator / gcd;
long denominator2 = frac2.Denominator / gcd;
long iNumerator=frac1.Numerator*denominator2 + frac2.Numerator*denominator1;
long iDenominator=denominator1*denominator2*gcd;
return ( new Fraction(iNumerator, iDenominator) ); Similar improvements are possible for the other operators. - You may want to consider making this a value type (
struct ). The reasoning? We definitely have an object with value semantics here - it is just an alternate representation of a number. Moreover, it is small enough (16 bytes) so the by-value passing of value types shouldn't hinder performance.
It would also eliminate the need for methods like Duplicate and properties like Value , since you can use direct assignments. - Your implementation of
Equals does not comply with the guidelines[^]. For example, your code throws an exception if the argument isn't of type Fraction . Equals should never throw an exception. There may well be more. Improving code is like ironing out all the wrinkles: you get some of the bigger ones first, and then take care of the progressively smaller ones.
Nice work!
Jeffrey
Everything should be as simple as possible, but not simpler. -- Albert Einstein
Numerical components for C# and VB.NET
|
|
|
|
|
Thank you for your valuable comments. I always need such comments to improve my programming skills. I admire your ideas and had it not been Marc there, I would have to re-write the code again. I thank you and Marc for your contribution to my class.
I agree with all of your suggestions except for one:
You have said to implement the class as a structure. The problem is that instance field members in a struct can not be initialized to any particular value and a fraction object having a denominator with 0 value is always a bad idea.
To illustrate my point, consider the following code
Struct Fraction
{
}
public static void Main()
{
Fraction frac=new Fraction();
Console.WriteLine( frac.ToString() )
Console.WriteLine( frac.ToDouble().ToString() )
Frac+=1
}
Please do inform me if you have a solution to this problem.
Thanks,
Syed Mehroz Alam
Email: smehrozalam@yahoo.com
Homepage: Programming Home
URL: http://www.geocities.com/smehrozalam/
|
|
|
|
|
Hi Syed,
Syed Mehroz Alam wrote:
You have said to implement the class as a structure. The problem is that instance field members in a struct can not be initialized to any particular value and a fraction object having a denominator with 0 value is always a bad idea.
You make a very good point. It is a strong recommendation that value types should have their natural, default value when uninitialized (or created using the default constructor). For fractions, this value would be 0.
However, I don't see too much wrong with implementing 0 as a special value, and giving it special treatment where required. Most operations would benefit from such special treatment anyway. I feel it would be perfectly acceptable to have the value of zero represented internally as "0/0", especially if you also implement the other special values (NaNs and infinities), as Marc did. The internal representation is not important for the users of your type.
As a 'justification,' you may be interested to know that the value of zero is a special value for the standard floating-point types as well. Floating-point numbers can be written as a sign times a value between 1 and 2 (the significand) times a power of two. Because the leading bit of the significand is always 1, it is implied and not explicitly set in the floating-point formats. This means, however, that the value of zero cannot be treated as most other numbers, because the 'leading' bit of the significand is zero.
Jeffrey
Everything should be as simple as possible, but not simpler. -- Albert Einstein
Numerical components for C# and VB.NET
|
|
|
|
|