Click here to Skip to main content
13,143,637 members (30,110 online)
Rate this:
 
Please Sign up or sign in to vote.
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
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 21-Apr-17 3:32am
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...
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

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?
  Permalink  
Comments
PIEBALDconsult 22-Apr-17 9:20am
   
That sounds like a rational response, so yes.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 2

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."

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);
            }
        }
    }
}
  Permalink  
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 3

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.
#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
  Permalink  
v7
Comments
Chris Maunder 21-Apr-17 17:17pm
   
Just for that I added BASIC syntax colourising
ppolymorphe 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
ppolymorphe 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.
ppolymorphe 22-Apr-17 13:46pm
   
:)
ppolymorphe 22-Apr-17 20:44pm
   
My code gives different results
FareyMax(PI, 99) => 311/99
FareyMax(PI, 100000) => 312689/99532
Jörgen Andersson 22-Apr-17 13:15pm
   
I knew that as a Stern-Brocot binary search tree.
ppolymorphe 22-Apr-17 13:53pm
   
Thank you for the reference Stern–Brocot tree - Wikipedia[^]
I used to name this as Farey series because it is the way I have learned to calculate the Farey sequences.
Jörgen Andersson 22-Apr-17 14:52pm
   
Stern-Brocot and Farey are obviously related, now that I know about Farey.
I would have linked to wikipedia if I had been close to a computer, I am alas to lazy to do that on the phone.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 4

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; }
  Permalink  
Comments
ppolymorphe 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? :)
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 5

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.

        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() ) ;
        }
  Permalink  
v2
Comments
ppolymorphe 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
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 6

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[^]
  Permalink  
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 7

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.

!-----------------------------------------------------------------------
! 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 !
  Permalink  
v2
Comments
ppolymorphe 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
ppolymorphe 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.
ppolymorphe 23-Apr-17 23:00pm
   
Fortran can't fo better than 32 bits floating point ?
Andy Allinger 25-Apr-17 1:17am
   
My apologies. Changed program to DOUBLE PRECISION for 64-bit math. It turns out that your answer for .00205501 was better, and that the Pi approximations were wrong too.

with 1 digits, approx of pi is 3 1/7
with 2 digits, approx of pi is 3 14/99
with 3 digits, approx of pi is 3 16/113
with 4 digits, approx of pi is 3 16/113
with 5 digits, approx of pi is 3 14093/99532
with 6 digits, approx of pi is 3 140914/995207
with 7 digits, approx of pi is 3 244252/1725033
DF2F(.00205501D0, 6): 1829/890020

Why did I ever doubt the mathematicians?

ppolymorphe 25-Apr-17 2:38am
   
Indeed, better results. I disagree with 6 and 7 digits, but there, we are dealing accuracy.
Use Improve question to update your question.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 8

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; }
  Permalink  
Comments
ppolymorphe 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.
ppolymorphe 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.
ppolymorphe 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.
David O'Neil 27-Apr-17 13:06pm
   
>> and 1829/890020 is closer than yours. :)

Fortunately, not part of the requirements! :)

>> weird: it is odd to have all numerator a power of 10 apart of the first one.

That is the clue I was talking about. The technique may be the fastest available method to come up with a decent fractional approximation. I could make the denominator 9, 99, 999, 9999, etc, without too much more work, for a little more accuracy. The code only relies upon std functions for printing. No other external libraries used.

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

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy |
Web04 | 2.8.170915.1 | Last Updated 27 Apr 2017
Copyright © CodeProject, 1999-2017
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100