Win a copy of Spring in Action (5th edition) this week in the Spring forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Bear Bibeault
• Devaka Cooray
• Liutauras Vilda
• Jeanne Boyarsky
Sheriffs:
• Knute Snortum
• Junilu Lacar
• paul wheaton
Saloon Keepers:
• Ganesh Patekar
• Frits Walraven
• Tim Moores
• Ron McLeod
• Carey Brown
Bartenders:
• Stephan van Hulst
• salvin francis
• Tim Holloway

# fractions

Ranch Hand
Posts: 4702
9
going from fraction to decimal is easy, you just divide. to go from decimal to fraction is a bit harder.
the algorithm i came up with for that is you multiply and if the result is an integer, that is the numerator and what you were dividing by is the denominator.
you loop through integers to find the denominator.
for example 1/4 = .25
you multiply .25 X 2 = .5 = no
.25 X 3 = .75 = no
.25 X 4 = 1 = yes
so .25 = 1/4
this works except for repeating numbers like .333333333333333333333
is there a way to make my algorithm work?

Bartender
Posts: 1856
81
I think that this could be a nice programming diversion or challenge.
Are you willing to post your code for others to view?

Pete Letkeman
Bartender
Posts: 1856
81
Interesting, repeat characters in strings problem seem to garner many questions on Google.
I'll try to see if I can come up with a solution, how many digits in should the I test fit before I conclude that there is not repeated sequence?
I'm thinking that recursion may be helpful here, but I'll need to dig in a little more to see.

Sheriff
Posts: 23868
50
You're looking to convert a decimal number to "a" fraction. But most decimal numbers don't correspond neatly to a simple fraction. You might consider converting a decimal number to a series of fractions which have larger and larger denominators and provide better and better approximations to it.

For example: Pi. The series of fractions which I have in mind would go something like this: 3/1, 22/7, 333/106, 355/113, ...

I'm pretty certain there's an algorithm for generating that series. Sure, if you start with a number like 0.25 you're going to get a very short series (0/1, 1/4) but otherwise you'll get a longer series.

Marshal
Posts: 61721
193

Paul Clapham wrote:. . . most decimal numbers don't correspond neatly to a simple fraction. . . .

Not even simple rational numbers like ⅓ which can neither be precisely represented in decimal nor binary. Unless the denominator's prime factors are 2ⁱ × 5ⁿ and no other factors, you will be faced with an infinite regression. I presume it is clear to readers why prime factors 2 and 5 are all right?

Ranch Hand
Posts: 151
3
my solution for this is to simply inflate the decimal to a whole number and put it over 100, then reduce it. 0.25 = 25/100 = 1/4

Campbell Ritchie
Marshal
Posts: 61721
193
Does that apply to the decimal expansion of ⅓?

S Fox
Ranch Hand
Posts: 151
3
I thought it works for all of them but nope. If you plan ahead though and store everything as a fraction to begin with, you can do your math in the style of fractions!

Campbell Ritchie
Marshal
Posts: 61721
193
Yes. It isn't that difficult to write a Fraction class. And a RationalNumber type.

Campbell Ritchie
Marshal
Posts: 61721
193
LISP programmers would wonder what all the fuss is aboiut

Master Rancher
Posts: 3001
105
A very easy algorithm, though not a fast one, makes use of the fact that A / B < (A + C) / (B + D) < C / D.

Now, start by picking two integers A and B such that this holds: 1 / A < f < 1 / B, when f is the given fraction ( 0 < f < 1). Divide the interval (1 / A, 1 / B) into two by applying the above,  determine in which of the two f lies, and repeat, until you are close enough.

Ranch Hand
Posts: 1159
9

Randall Twede wrote:going from fraction to decimal is easy, you just divide. to go from decimal to fraction is a bit harder.
the algorithm i came up with for that is you multiply and if the result is an integer, that is the numerator and what you were dividing by is the denominator.
you loop through integers to find the denominator.
for example 1/4 = .25
you multiply .25 X 2 = .5 = no
.25 X 3 = .75 = no
.25 X 4 = 1 = yes
so .25 = 1/4
this works except for repeating numbers like .333333333333333333333
is there a way to make my algorithm work?

If you need to report out a fraction at the end of a calculation, could you just do the whole calculation in fractions instead of using doubles at all?  There are a few "Fraction" classes available that you could download.  Or it could be a fun way to spend a few hours some evening writing your own class, as an exercise.

Bartender
Posts: 9493
184

Randall Twede wrote:going from fraction to decimal is easy, you just divide

It's funny, these operations are actually equally hard, probably. You're just more used to one than the other, because we learn about division in primary school.

Think about how difficult converting a fractional notation to a decimal notation would be if you were only allowed to use integer division and not real division.

Piet Souris
Master Rancher
Posts: 3001
105

Stephan van Hulst wrote:Think about how difficult converting a fractional notation to a decimal notation would be if you were only allowed to use integer division and not real division.

But they learned us 'staartdelingen' in primary school (don't know the English terms)? That is all about integer division.

Campbell Ritchie
Marshal
Posts: 61721
193

Piet Souris
Master Rancher
Posts: 3001
105
Yes I saw that Google translate gave this. However, it is a litteral translation and it seemed wrong to use that.

But here is a link to a Dutch page, but I'm sure you recognize the 'staartdelingen'. The method has changed since I went to primary, though....

staartdelingen - see examples 4 and further

Campbell Ritchie
Marshal
Posts: 61721
193
A brief look at that link suggests it is what I was taught as “long division” at primary school.

Marshal
Posts: 6257
420

Piet Souris wrote:But here is a link to a Dutch page, but I'm sure you recognize the 'staartdelingen'. The method has changed since I went to primary, though....

staartdelingen - see examples 4 and further

I was taught similarly, it seems just layout was different.

Piet Souris
Master Rancher
Posts: 3001
105
Indeed, that's it! Long division... okay!

And if you ran out of the numerator, you just added a comma and as many zeroes as necessary, and you had your decimal number, long before computers arrived. Hmm, nealy getting emotional about it... sniff

Campbell Ritchie
Marshal
Posts: 61721
193

Piet Souris wrote:. . .  getting emotional about it... sniff . . .

Well, they do say that your schooldays are the happiest days of your life

Ryan McGuire
Ranch Hand
Posts: 1159
9
Randall, are you saying that you don't need to be exact and a good approximation is reasaonble.

e.g. (1/14 + 2/3) * 5/32 = 0.738095238095 to some level of precision.  You'd accept any fraction that divides out to 0.738095238095 even if it's not 155/1344.  Is that right?

Getting the exact fraction for any terminating decimal (which is what you have to assume your result is) is easy.  Just put the digits as the numerator and 10^N (where N is the number of decimal places) in the denominator.

0.738095238095 = 738095238095/1000000000000

There... done.  Of course you could factor out any powers of 2 and/or 5 (up to N).

0.738095238095 = 738095238095/1000000000000 = 147619047619/200000000000  Final answer.

That unwieldy fraction is closer to the decimal version of your calculation result than the real answer of 155/1344.

Ryan McGuire wrote:
If you need to report out a fraction at the end of a calculation, could you just do the whole calculation in fractions instead of using doubles at all?

I just noticed that S Fox made the same suggestion before I did.  Well played.

Campbell Ritchie
Marshal
Posts: 61721
193

Ryan McGuire wrote:. . .factor out any powers of 2 and/or 5 (up to N).  . . .

We called that cancelling out when I was at school.

147619047619/200000000000  Final answer. . . .

You can easily tell the numerator and denominator are co‑prime because the denominator has 2 and 5 as its prime factors, well actually 2¹² and 5¹¹. Since the numerator doesn't end in an even digit nor 5, you can tell it has been reduced so it doesn't have 2 or 5 as a factor.

Ryan McGuire
Ranch Hand
Posts: 1159
9
Before anyone else points it out, I had a bit of a transcription error in the initial math above.

(1/14 + 2/3) * 5/32 = 0.738095238095

I reported the sum of the first two fractions as the final result.

(1/14 + 2/3) = 0.738095238095

(1/14 + 2/3) * 5/32 = 0.11532738095

All of my original comments still hold, even though the math needs to be updated:

0.11532738095 = 11532738095 / 100000000000

Cancelling out a factor of 5 gives us 2306547619/20000000000  final answer.

Ok, I feel better now.

 It is sorta covered in the JavaRanch Style Guide.