• Post Reply Bookmark Topic Watch Topic
  • New Topic
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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

fractions

 
Ranch Hand
Posts: 4716
9
Scala Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 1868
81
Android IntelliJ IDE MySQL Database Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 1868
81
Android IntelliJ IDE MySQL Database Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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?
 
Rancher
Posts: 285
14
Eclipse IDE C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Does that apply to the decimal expansion of ⅓?
 
S Fox
Rancher
Posts: 285
14
Eclipse IDE C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes. It isn't that difficult to write a Fraction class. And a RationalNumber type.
 
Campbell Ritchie
Marshal
Posts: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
LISP programmers would wonder what all the fuss is aboiut
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Saloon Keeper
Posts: 15489
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Google translate thinks staartdelingen means “tail divisions”. Please provide more details.
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A brief look at that link suggests it is what I was taught as “long division” at primary school.
 
Marshal
Posts: 8856
637
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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

Well, they do say that your schooldays are the happiest days of your life
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 79153
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic