15,965,165 members

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

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

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?

Permalink

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

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

Permalink

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.

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.

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

Permalink

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

3 14/99

3 14159/100000

Patrice T
22-Apr-17 13:08pm

With what ? a HP Prime ?

Which parameters ?

Which parameters ?

PIEBALDconsult
22-Apr-17 13:20pm

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

Patrice T
22-Apr-17 13:46pm

:)

Patrice T
22-Apr-17 20:44pm

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

Jörgen Andersson
22-Apr-17 13:15pm

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

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

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.

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.

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.

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

Permalink

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

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

Permalink

Share this answer

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.

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

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 ?

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?

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?

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

Use

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

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

Permalink

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.

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.

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.

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.

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,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900

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