13,446,079 members (38,511 online)

Email

Password

Sign in with

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

So

Sample input:

(0.333, 1) => 1/3

(0.125, 2) => 10/80 or 1/8

(0.00205501, 6) => 719/349875

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

Comments

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?

Comments

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

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);
}
}
}
}
```

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.

I like this fraction of PI, very easy to remember:

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`

v7

Comments

Just for that I added BASIC syntax colourising

Thank you Chris

For Pi, my code produces...

3 14/99

3 14159/100000

3 14/99

3 14159/100000

With what ? a HP Prime ?

Which parameters ?

Which parameters ?

Oh, oh, sorry... I meant with _my_ code, not yours.

:)

My code gives different results

FareyMax(PI, 99) => 311/99

FareyMax(PI, 100000) => 312689/99532

FareyMax(PI, 99) => 311/99

FareyMax(PI, 100000) => 312689/99532

I knew that as a Stern-Brocot binary search tree.

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.

I used to name this as Farey series because it is the way I have learned to calculate the Farey sequences.

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.

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.

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; }

Comments

Are you sure this code is related to the challenge ?

:)

Maybe you like #8 better? :)

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

My Rational class has two methods for converting floating-point to fraction:

Decimal basically chooses an appropriate power of ten as the denominator -- for

BestGuess "tries (with some success) to determine what numbers can be divided to produce the value".

Both methods work well for

BestGuess works well for

For

What does BestGuess produce for that value?

Well, it produces

When I divide by

If I round, I get

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.

-- 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() ) ;
}
```

v2

Comments

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[^]

Try every possible denominator of

Compute the numerator as NUMER = NINT(X DENOM)

Keep the closest approximation.

Old-school boss should approve of a no-brain solution in FORTRAN.

sample output:

`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 !

v2

Comments

Rather brut force !

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

I think you should start with a better pi as

`3.141592653589`

instead of `3.141592741013`

, then we can see which method is better.3.1415927 is as close as possible in 32-bit math.

Fortran can't fo better than 32 bits floating point ?

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?

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?

Indeed, better results. I disagree with 6 and 7 digits, but there, we are dealing accuracy.

Use**Improve question** to update your question.

Use

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; }

Comments

Try again without obfuscating your code.

Nota: showing your results would be interesting too.

Nota: showing your results would be interesting too.

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.

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.

Results a weird, there probably a problem in your code.

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.

and 1829/890020 is closer than yours. :)

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

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

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

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)

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

https://www.codeproject.com/Articles/12805/NET-Rational-fraction-value-type-using-Decimals-w

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