Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Your boss is old school. Really old school. He doesn't like this new fangled decimal notation and instead wants everything in fractions. 1/2. 2/3. 5647/35829. Old school.

Your challenge is to take a floating point value and convert it to a fraction. You're answer will be, necessarily, an approximation, and the preciseness of that approximation will depend on the maximum number of digits you're allowed for the denominator. Any whole parts of the value are displayed before the fraction and are not included in character limits

The function signature should be
C#
string FloatToFraction(float inputValue, int denominatorDigits)

So FloatToFraction(0.3333, 1) => "1/3", FloatToFraction(100.333333, 1) => "100 1/3"

Sample input:

(0.333, 1) => 1/3
(0.125, 2) => 10/80 or 1/8
(0.00205501, 6) => 719/349875
Posted
Updated 26-Apr-17 21:37pm
Comments
PIEBALDconsult 21-Apr-17 9:37am    
Ah, time to dust off my fraction class...
https://www.codeproject.com/Articles/12805/NET-Rational-fraction-value-type-using-Decimals-w
Chris Maunder 21-Apr-17 9:39am    
Son of a...! I should have checked :)
PIEBALDconsult 21-Apr-17 23:36pm    
(0.00205501, 6) => 411/200000
PIEBALDconsult 29-Apr-17 14:01pm    
Gaaahhh! So today I have need of finding an approximate fraction for 0.0102 !!!
It's pretty close to 1/96, which has only 2 and 3 as prime factors, so now I wonder about making a float-to-rational converter that limits the denominator to a set of prime factors...

No matter how I try and frame and sell it, my mind is resolutely refusing to get involved with this. Do I win the prize?
 
Share this answer
 
Comments
PIEBALDconsult 22-Apr-17 9:20am    
That sounds like a rational response, so yes.
I was going to write something that approximated using Farey sequence or continued fractions, but I've already submitted this solution posting.

In .NET, the float type already has a precision of only seven digits (reference) so there's already an upper limit on the precision of the conversion. But, if you really want to sell your float short, you can give it an even more stringent denominator value. It uses good ol' Euclid to generate the fraction in lowest terms. Also, as float is limited in range by 10^38, the output can be right-justified to be "pretty."

C#
using System;

namespace CodingChallenge
{
    public class Program
    {
        public static void Main(string[] args)
        {
            float[] values = { 0.12345F, 1 / 3F, 0.12345678F, 6 };
            foreach (var f in values)
            {
                FloatToFraction fc = new FloatToFraction(f);
                Console.WriteLine(fc);
            }

            // End point
            Console.WriteLine("All done!");
            Console.ReadLine();
        }
    }

    public class FloatToFraction
    {        
        // Is a private property a priverty?
        private readonly float inputValue;
        private readonly int _floatPrecisionLimit;        
        private readonly Func<float,Fraction> _convertToFraction; 

        // ctors and overrides
        public FloatToFraction(float inputValue) : this(inputValue,7){}

        public FloatToFraction(float inputValue, int denominatorDigits)
        {
            this.inputValue = inputValue;
            this._convertToFraction = PrecisionLimitMethod;
            _floatPrecisionLimit = (int) Math.Pow(10,denominatorDigits);
        }

        public override string ToString()
        {
            int leadingDigit = (int)Math.Truncate(inputValue);
            float normalizedValue = inputValue - leadingDigit;

            Fraction f = this._convertToFraction(normalizedValue);

            string A = string.Format("{0,40}", leadingDigit.ToString());
            string B = f.ToString();

            return string.Format(string.Concat(A,B));
        }


        // Lookin' at privates
        private Fraction PrecisionLimitMethod(float normalizedValue)
        {
            int numerator = (int)(normalizedValue * _floatPrecisionLimit);
            int denominator = _floatPrecisionLimit;

            int gcd = FloatToFraction.gcd(numerator, denominator);
            numerator /= gcd;
            denominator /= gcd;

            return new Fraction(numerator, denominator);
        }
        
        private static int gcd(int a, int b)
        {
            if (b == 0)
            {
                return a;
            }
            else
            {
                return gcd(b, a % b);
            }
        }

        private struct Fraction
        {
            public int numerator;
            public int denominator;

            public Fraction(int numerator,int denominator)
            {
                this.numerator = numerator;
                this.denominator = denominator;
            }

            public override string ToString()
            {
                if (numerator == 0)
                    return string.Empty;
                else
                    return string.Format("{0,8} / {1,8}", numerator, denominator);
            }
        }
    }
}
 
Share this answer
 
This program is for a HP Prime calculator
The second parameter is the maximum value of both numerator and denominator.
It is useful when both parts of the fraction must fit 8 or 16 bits values.
As the name indicate, it use Farey series.
BASIC
#pragma mode( separator(.,;) integer(h64) )
// rev 6030 update

EXPORT FareyMax(Vl, DMax)
// Round a Vl to the best fraction with denominator < DMax
BEGIN
    LOCAL VlE, Tmp;
    LOCAL DbN,DbD, FnN,FnD, RsN,RsD,RsE;
    VlE:= ABS(Vl);
    DbN:= IP(VlE); DbD:=1; FnN:=DbN+1; FnD:=1;
    RsN:= ROUND(VlE,0); RsD:= 1; RsE:= ABS(VlE-(RsN/RsD));
    WHILE DbD+FnD <= DMax AND DbN+FnN <= DMax DO
      Tmp:= (DbN+FnN)/(DbD+FnD);
      IF RsE > ABS(VlE-Tmp) THEN
        RsN:= (DbN+FnN); RsD:= (DbD+FnD); RsE:= ABS(VlE-(RsN/RsD));
      END;
      IF Tmp < VlE THEN
        DbN:= (DbN+FnN); DbD:= (DbD+FnD);
      ELSE
        FnN:= (DbN+FnN); FnD:= (DbD+FnD);
      END;
    END;
    // RETURN "'"+STRING(SIGN(Vl)*RsN,2,0)+"/"+STRING(RsD,2,0)+"'";
    RETURN EXPR("QUOTE("+STRING(SIGN(Vl)*RsN,2,0)+"/"+STRING(RsD,2,0)+")");
END;

FareyMax(0.3333, 9) => 1/3
FareyMax(100.333333, 9) => 301/3
FareyMax(0.125, 99) => 1/8
FareyMax(0.00205501, 999999) => 1829/890020 // Chris I fear your example is wrong.
FareyMax(PI, 500) => 355/113

I like this fraction of PI, very easy to remember:
113355, cut in middle 113/355, and swap 355/113
 
Share this answer
 
v7
Comments
Chris Maunder 21-Apr-17 17:17pm    
Just for that I added BASIC syntax colourising
Patrice T 21-Apr-17 18:08pm    
Thank you Chris
PIEBALDconsult 22-Apr-17 11:59am    
For Pi, my code produces...
3 14/99
3 14159/100000
Patrice T 22-Apr-17 13:08pm    
With what ? a HP Prime ?
Which parameters ?
PIEBALDconsult 22-Apr-17 13:20pm    
Oh, oh, sorry... I meant with _my_ code, not yours.
This uses my Rational class -- .NET Rational (fraction) value type using Decimals, written in C#[^]
-- then tries to adjust the magnitude of the denominator.
Basically, if the denominator requires ten digits, but you want only four, it divides the fraction by 10^6 / 10^6 .

My Rational class has two methods for converting floating-point to fraction:
Decimal basically chooses an appropriate power of ten as the denominator -- for 0.333 it will make 333/1000.
BestGuess "tries (with some success) to determine what numbers can be divided to produce the value".

Both methods work well for 0.125 , 2.
BestGuess works well for 0.333 , 1 , but Decimal wants to produce 3/10.

For 0.00205501f , 6, Decimal produces 411/200000 -- which will make the boss happy.
What does BestGuess produce for that value?
Well, it produces 277584040019137491/135076734429096447706, which equals 0.00205501 -- which is good, but too many digits.
When I divide by 10^15 / 10^15, the result is 277/135076, which equals 0.002050697 -- which is not good.
If I round, I get 278/135077, which equals 0.002058085 -- which is also not good.

Edit: I decide to try selecting the method based on the number denominator digits desired.

I might need to implement a DecimalConversionMethod specifically to take the number of denominator digits into account from the start.

C#
private static string
FloatToFraction
(
  float inputValue
,
  int   denominatorDigits
)
{
  System.Text.StringBuilder result = new System.Text.StringBuilder() ;

  PIEBALD.Types.Rational.ConversionMethod =
    denominatorDigits > 4
    ? PIEBALD.Types.Rational.DecimalConversionMethod.Decimal
    : PIEBALD.Types.Rational.DecimalConversionMethod.BestGuess ;

  PIEBALD.Types.Rational r = (decimal) inputValue ;

  if ( r.IsNegative )
  {
    result.Append ( '-' ) ;

    r = -r ;
  }

  if ( !r.IsProper )
  {
    decimal i = System.Decimal.Floor ( r ) ;

    result.Append ( i ) ;

    r -= i ;
  }

  decimal f = System.Decimal.Ceiling ( (decimal) System.Math.Log10 ( (double) r.Denominator ) ) ;

  if ( f > denominatorDigits )
  {
    f = (decimal) System.Math.Pow ( 10 , (double) f - (double) denominatorDigits ) ;

    decimal n = System.Decimal.Round ( r.Numerator   / f , 0 ) ;
    decimal d = System.Decimal.Round ( r.Denominator / f , 0 ) ;

    r = n ;
    r /= d ;
  }

  result.Append ( r.ToString() ) ;

  return ( result.ToString() ) ;
}
 
Share this answer
 
v2
Comments
Patrice T 22-Apr-17 21:01pm    
I fear you will have to improve your method, I get completely different results.
FareyMax(0.00205501, 136000) => 268/130413
FareyMax(0.00205501, 140000) => 281/136739
FareyMax(0.00205501, 999999) => 1829/890020
Don't have time to do this one this week, so I'll solve it using Google Search instead: c# - Algorithm for simplifying decimal to fractions - Stack Overflow[^]
 
Share this answer
 
Try every possible denominator of DENDIG digits or fewer.
Compute the numerator as NUMER = NINT(X DENOM)
Keep the closest approximation.
Old-school boss should approve of a no-brain solution in FORTRAN.

FORTRAN
!-----------------------------------------------------------------------
! Convert a float to a fraction, by exhaustive search!
!-----------------------------------------------------------------------
      FUNCTION F2F (INPVAL, DENDIG)
       IMPLICIT NONE
       REAL INPVAL         ! float number
       INTEGER DENDIG      ! max digits in denominator
       CHARACTER*32 F2F
       INTEGER KTRIM, LTRIM       ! external functions
       
       INTEGER NUMER, DENOM, BESTN, BESTD, MAXDEN, K, L, WHOLE
       REAL AERR, BESTER, FRACT
       CHARACTER*32 NUMSTR
       
!          begin
       MAXDEN = 10 **DENDIG - 1
       WHOLE = INT(INPVAL)
       FRACT = INPVAL - FLOAT(WHOLE)
       BESTER = 1.0
       BESTD = 1                               ! needless initializations
       BESTN = 0                               !       "    "
       DO 10 DENOM = MAXDEN, 2, -1             ! backwards step for extra confusion
         NUMER = NINT(FRACT * FLOAT(DENOM))
         AERR = ABS(FRACT - FLOAT(NUMER) / FLOAT(DENOM))
         IF (AERR .LE. BESTER) THEN
           BESTER = AERR
           BESTN = NUMER
           BESTD = DENOM
         END IF
  10   CONTINUE
       
!         format output
       F2F = ''
  20   FORMAT (I16)
       IF (WHOLE > 0) THEN
         WRITE (UNIT=NUMSTR, FMT=20) WHOLE
         K = KTRIM(NUMSTR)
         L = LTRIM(NUMSTR)
         F2F = NUMSTR(K:L)
       END IF
       
       WRITE (UNIT=NUMSTR, FMT=20) BESTN
       K = KTRIM(NUMSTR)
       L = LTRIM(NUMSTR)
       F2F = F2F(1:LTRIM(F2F)) // ' ' // NUMSTR(K:L)
       
       WRITE (UNIT=NUMSTR, FMT=20) BESTD
       K = KTRIM(NUMSTR)
       L = LTRIM(NUMSTR)
       F2F = F2F(1:LTRIM(F2F)) // '/' // NUMSTR(K:L)
       RETURN
      END  ! of F2F
      
      
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!       substitute for LEN_TRIM for old compilers
      FUNCTION LTRIM (STRING)
       IMPLICIT NONE
       CHARACTER*(*) STRING
       INTEGER LTRIM
       INTEGER J, L
       
       L = LEN(STRING)
       DO 50 J = L, 1, -1
         IF (STRING(J:J) .EQ. ' ') GO TO 50
         LTRIM = J
         RETURN
  50   CONTINUE
       LTRIM = 0
       RETURN
      END ! of LTRIM


!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!        first non-blank position in character variable
      FUNCTION KTRIM (STRING)
       IMPLICIT NONE
       CHARACTER*(*) STRING
       INTEGER KTRIM
       INTEGER J, L
       L = LEN(STRING)
       DO 50 J = 1, L, +1
         IF (STRING(J:J) .EQ. ' ') GO TO 50
         KTRIM = J
         RETURN
  50   CONTINUE
       KTRIM = 0
       RETURN
      END ! of KTRIM


      PROGRAM FPI  ! test pi fractions
       IMPLICIT NONE
       INTEGER J
       REAL PI
       CHARACTER*32 F2F, STRING
       
       PI = ACOS(-1.)
       DO J = 1, 7
         STRING = F2F(PI, J)
         PRINT *, 'with ', J, ' digits, the best representation ',
     $         'of pi is ', STRING
       END DO
       
       STRING = F2F(.00205501, 6)
       PRINT *, 'F2F(.00205501, 6): ', STRING
      END  ! of test program


sample output:
 with  1  digits, the best representation of pi is 3 1/7
with  2  digits, the best representation of pi is 3 14/99
with  3  digits, the best representation of pi is 3 16/113
with  4  digits, the best representation of pi is 3 16/113
with  5  digits, the best representation of pi is 3 13966/98635
with  6  digits, the best representation of pi is 3 132749/937541
with  7  digits, the best representation of pi is 3 593883/4194304
F2F(.00205501, 6):  1293/629194                    ! closer approximation !
 
Share this answer
 
v2
Comments
Patrice T 23-Apr-17 15:02pm    
Rather brut force !
Andy Allinger 23-Apr-17 20:56pm    
The Farey tree gives the answer to a subtly different question: find the smallest fraction to approximate within a given tolerance. Brute force will find the best approximation, up to machine precision
Patrice T 23-Apr-17 22:10pm    
I think you should start with a better pi as 3.141592653589 instead of 3.141592741013, then we can see which method is better.
Andy Allinger 23-Apr-17 22:35pm    
3.1415927 is as close as possible in 32-bit math.
Patrice T 23-Apr-17 23:00pm    
Fortran can't fo better than 32 bits floating point ?
In imitation of the best old school traditions:
#include <iostream>
#include <sstream>
using namespace std; string aaa(float a, int aa) { int aaa = (int)a; float aaaa = a - aaa; int aaaaa = abs((int)(aaaa * 60)); stringstream str; str << aaa << " " << aaaaa << "/60"; return str.str(); } int main() { float a; int aa; cout << "Enter number: "; cin >> a; cout << "Enter digits: "; cin >> aa; string str(aaa(a, aa)); cout << "True Old School Curmudgeons only work in sexagesimal system: "; cout << str << endl; system ("PAUSE"); return 0; }
 
Share this answer
 
Comments
Patrice T 22-Apr-17 0:54am    
Are you sure this code is related to the challenge ?
David O'Neil 22-Apr-17 1:42am    
:)
David O'Neil 27-Apr-17 3:39am    
Maybe you like #8 better? :)
Perhaps the picky boss will like this one better?
#include <iostream>
#include <sstream>
using namespace std; size_t a(int a) { int aa = 1; int aaa = 10;  while (a/aaa > 0) { ++aa; aaa *= 10; } return aa; } string aa(double aa, size_t aaa) { double aaaa = (double)(1/(aa - (int)aa)); int aaaaa = aaa - a((int)(aaaa)); int aaaaaa = 1; while (aaaaa > 0) { aaaaaa *= 10; --aaaaa; } int aaaaaaa = aaaaaa; int aaaaaaaa = (int)(aaaa * aaaaaa + 0.5); stringstream aaaaaaaaa; aaaaaaaaa << (int)aa << " " << aaaaaaa << "/" << aaaaaaaa; return aaaaaaaaa.str(); } int main() { string a = aa(0.333, 1); cout << a << endl; a = aa(0.125, 2); cout << a << endl; a = aa(0.00205501, 6); cout << a << endl; system ("PAUSE"); return 0; }
 
Share this answer
 
Comments
Patrice T 27-Apr-17 4:35am    
Try again without obfuscating your code.
Nota: showing your results would be interesting too.
David O'Neil 27-Apr-17 4:48am    
For now, point B:
Results:
.333, 1: 0 1/3
.125, 2: 0 10/80
.00205501, 6: 0 1000/486616
pi, 2: 3 10/71
pi, 3: 3 100/706
pi, 4: 3 1000/7063

That gives a clue as to the method.
Patrice T 27-Apr-17 4:56am    
Results a weird, there probably a problem in your code.
David O'Neil 27-Apr-17 5:04am    
Define 'weird' more precisely. All of the fractions are close approximations to the desired numbers. In fact, the one for 0.00205501 is closer than Chris's approximation.
Patrice T 27-Apr-17 6:57am    
and 1829/890020 is closer than yours. :)
weird: it is odd to have all numerator a power of 10 apart of the first one.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900