Using C# .NET 4.0, I recently needed to stored a data element as a Decimal Data Type yet be able to present and edit the value as a string fraction.
An example would be a user enters a fraction of 1/2 and it is stored as 0.5. Then when queried from the database it is then displayed as 1/2.
Now that works just fine but what about repeating decimal values produced by fractions such as 1/3? Fortunately for me, I had one critical business rule where the fraction was not stored if the denominator was not a power of 2. This means the denominator will always be non-repeating. That topic is beyond the scope of this post but you can research base numbers for counting.
If you are in need in solving the issue of repeating decimals you could implement it, in a finite condition, using a simple algorithm illustrated at http://www.basic-mathematics.com/converting-repeating-decimals-to-fractions.html.
NOTE: Since we are working with Decimal Data Types we cannot use the old reliable ulong, long, uint and int Data Types. Using these types would have been great since the power of bit-shifting is very simple. But as you can see from the MSDN documentation on Built-in Data Types if we convert from a large decimal value we’ll certainly encounter overrun issues. So the best choice in using Decimal Data Type is to stick with the Decimal Data Type. And as you might recall, bit shifting on Floating Point Precision numbers doesn’t work.
Before I jump right into the conversion methods here are a few secondary methods which will be needed:
Truncate the Decimal portion of a String using a String Extension
public static string TruncateDecimal(this string source)
{
return source.Contains('.') ? source.Substring(0, source.IndexOf('.')) : source;
}
When a Decimal Data Type is converted to a string using ToString(), the string contains the decimal and any fractional values to the right of the decimal place. For example ‘1.00’ and to remove ‘.00’ we have the above string extension. You’ll see how this comes into play shortly.
Get the Greatest Common Devisor given both the Numerator and Denominator
public static decimal GreatestCommonDivisor(decimal m, decimal n)
{
var x = decimal.Truncate(m);
var y = decimal.Truncate(n);
return GreatestCommonDivisorWorker(x, y);
}
static decimal GreatestCommonDivisorWorker(decimal m, decimal n)
{
return (n == 0) ? m : GreatestCommonDivisorWorker(n, m % n);
}
Note: The order of input m and n does not effect the result.
Notice the ‘Worker’ method is left private since I wanted to force the removal of any decimal values following the decimal place. In doing this I did not want something which was only necessary once to be in the recursive method.
Reduce a Fraction given both the Numerator and Denominator
public static void ReduceFraction(ref decimal m, ref decimal n)
{
var x = decimal.Truncate(m);
var y = decimal.Truncate(n);
var gcd = GreatestCommonDivisorWorker(m, n);
m = x / gcd;
n = y / gcd;
}
Note: The order of input m and n does not effect the result.
This method is pretty straight forward by finding the largest value both the numerator and denominator can be divided by and doing so. The method has made it mandatory to remove factional data since this will skew the output.
Now the conversion methods.
Convert a Decimal Data Type to a String Fraction
public static void DecimalToFraction(decimal value, ref decimal sign, ref decimal numerator, ref decimal denominator)
{
const decimal maxValue = decimal.MaxValue / 10.0M;
// e.g. .25/1 = (.25 * 100)/(1 * 100) = 25/100 = 1/4
var tmpSign = value < decimal.Zero ? -1 : 1;
var tmpNumerator = Math.Abs(value);
var tmpDenominator = decimal.One;
// While numerator has a decimal value
while ((tmpNumerator - Math.Truncate(tmpNumerator)) > 0 && tmpNumerator < maxValue && tmpDenominator < maxValue)
{
tmpNumerator = tmpNumerator * 10;
tmpDenominator = tmpDenominator * 10;
}
tmpNumerator = Math.Truncate(tmpNumerator); // Just in case maxValue boundary was reached.
ReduceFraction(ref tmpNumerator, ref tmpDenominator);
sign = tmpSign;
numerator = tmpNumerator;
denominator = tmpDenominator;
}
public static string DecimalToFraction(decimal value)
{
var sign = decimal.One;
var numerator = decimal.One;
var denominator = decimal.One;
DecimalToFraction(value, ref sign, ref numerator, ref denominator);
return string.Format("{0}/{1}", (sign * numerator).ToString().TruncateDecimal(),
denominator.ToString().TruncateDecimal());
}
The first method is the base method performing all the work. It allows the consumer to have access to all the components of a fraction. The second method is nothing more than a friendlier approach to using the conversion.
DecimalToFraction takes a simple approach. If given a decimal value of .0625, it performs the following transformation:
.0625 = .0625/1 = .625/10 = 6.25/100 = 62.5/1000 = 625/10000 = 1/16
In order to protect from a value exceeding the upper bounds of a decimal we perform a pseudo look-ahead by dividing decimal.MaxValue by 10 since we are incremented both the numerator and denominator by 10. 10 is our magic ratio.
Couple key notes: x/0 returns null, x returns x/1.
Find the String Denominator from a Decimal Data Type
public static decimal DenominatorFromDecimal(decimal value)
{
var sign = decimal.One;
var numerator = decimal.One;
var denominator = decimal.One;
DecimalToFraction(value, ref sign, ref numerator, ref denominator);
return denominator;
}
If you recall I needed to validate if the denominator was a power of 2. In order to perform this I need access to the denominators value. This method is nothing more than yet another entry point to use DecimalToFraction.
Convert a String Fraction to a Decimal Data Type
static readonly Regex FractionalExpression = new Regex(@"^(?<sign>[-])?(?<numerator>d+)(/(?<denominator>d+))?$");
public static decimal? FractionToDecimal(string fraction)
{
var match = FractionalExpression.Match(fraction);
if (match.Success)
{
// var sign = Int32.Parse(match.Groups["sign"].Value + "1");
var numerator = Int32.Parse(match.Groups["sign"].Value + match.Groups["numerator"].Value);
int denominator;
if (Int32.TryParse(match.Groups["denominator"].Value, out denominator))
return denominator == 0 ? (decimal?)null : (decimal)numerator / denominator;
if (numerator == 0 || numerator == 1)
return numerator;
}
return null;
}
FractionToDecimal uses a regular expression to ensure it receives a string composing of four parts composed of ‘sign’, ‘numerator’, division symbol ‘/’ and ‘denominator’. If it does not receive a correct fraction it returns null.
Is a Decimal Data Type a Power Of Two
public static bool IsPowerOfTwo(decimal n)
{
const decimal maxValue = decimal.MaxValue / 2 - 1; // -1 for rounding
if (n != decimal.Truncate(n))
return false;
if (n == decimal.Zero)
return false;
var operand = Math.Abs(n);
var powerOfTwo = decimal.One;
do
{
if (powerOfTwo == operand)
return true;
powerOfTwo *= 2;
} while (powerOfTwo <= operand && powerOfTwo <= maxValue);
return false;
}
I had to be a little creative and take the more “manual” approach for this method. There are certainly a lot more clock cycles used compared to bit shifting but again since we are using floating point precision that is not an option. However consider this, using this method there are so few power’s of two that are within the range of a decimal data type you can step through all of them yourself quite quickly.
Never the less, the idea is to start at 2^0 = 1 and in the loop check if the powerOfTwo value matches the passed in value (n). If not, move to the next power by multiplying by 2 (e.g. 1 * 2 * 2 * 2…). In order to not exceed the maximum value a decimal can hold, the while loop condition makes a check to not exceed decimal.MaxValue / 2 – 1. The –1 is due to rounding when dividing by 2.
Why not create a generic Power Method?
Here is an example of a method I could have used inside the IsPowerOfTwo method above.
public static decimal Pow(decimal @base, decimal exponent)
{
if (exponent == 0M)
return 1M;
var result = @base;
for (var iteration = 1M; iteration < exponent; iteration += 1M)
{
result *= @base;
}
return result;
}
Perhaps it might seem more obvious now in using a method such as this. For each iteration of the powerOfTwo while loop it would recalculate all the previous powers of two. Therefore our Big-O would be exponential and that would be bad programming. However for any other use, a method like this would be great.
That’s it! Now you can wrap this into a public static class and you are good to go.
Bonus: Find the Closest Power of Two given an Integer Value
I used this in a mock up but perhaps some reader will find this useful to modify and create their own.
const int LargestDenominator = 1024;
public static int ClosestPowerOfTwo(int n)
{
ulong operand = (ulong)n;
if (n == 0)
return 0;
long delta = 0;
long nextDelta = 0;
for (ulong power = 1; power > 0; power = power << 1)
{
if (power == operand)
return System.Convert.ToInt32(n);
delta = nextDelta;
nextDelta = n - (long)power;
if (power > operand)
return delta > Math.Abs(nextDelta)
? n + System.Convert.ToInt32(Math.Abs(nextDelta))
: n - System.Convert.ToInt32(delta);
if (power = LargestDenominator)
return n - System.Convert.ToInt32(delta);
}
}
The strategy here is to cycle through each power of two until we find the one after and before our input value (n). Then determine which is closest and return that power of two. I would recommend two possible changes. Validate the boundaries for the values used. Next, would it make more sense for you to return the actual power of two value compared to only return the power?
Thanks for reading. Happy Coding!!
Let’s get social…