Converting repeating decimals to ratios...

[BigMoosie]

Hi, I am trying to write a program that will take a number and output the numerator and the denominator of the number as a ratio.

 

I know one way of doing this mathematically:

 

[math]x = 5.142857142857142857 (given)[/math]

 

[math]1,000,000x = 5,142,857.142857142857[/math]

 

[math]1,000,000x - x = 999,999x = 5,142,852[/math]

 

[math]x = \frac{5,142,852}{999,999}[/math]

 

[math]x = \tfrac{36}{7}[/math]

 

I could write a code that does this but this piece of code will be executed very often in my code so I want it to be optimised to be very efficient.

 

Does anybody know any other ways of doing this?

 

- Oh if it is any help, the input number has a maximum of 15 decimal places.

[Dave]

Well, you've got the correct method - I can't see a more optimized version, myself. Identifying and simplifying the fraction is a fairly simple process. If you have a periodic fraction and you're given what that is (i.e. you don't have to identify it from a string), then the fraction can be worked out in one step. Moreover, Euclid's algorithm can be used to find the fraction in its lowest terms. There are more efficient versions of Euclid's algorithm, but nevertheless, I would say that this method is more than sufficient for most applications.

[BigMoosie]

Thanks dave, I'm just trying to get my head around how to effectively identify the repeating part.

 

Can you suggest any iterative methods?

[Dave]

I don't know of any mathematical methods for doing this, but it should be reasonably okay using some programming techniques. I would suggest reading your number in from the textbox as a string instead of a double (I presume that's what you're doing at the moment).

[Dave]

I should also mention that identifying periodic decimals is, to some degree, a tricky endeavour. For example, how are you meant to represent an infinite decimal? If you input something like 5.142857142857142857 as you've done above, then this is a terminating decimal. For an infinite fraction, you're much better off by allowing some sort of input such as 5.142857... or 5.142857. By doing this, it allows the user to distinguish whether they actually want to input a repeating decimal or just a plain old terminating one. Also, it makes it a lot easier for you, the programmer, to identify things such as the period or delay of the decimal.

[BigMoosie]

The input number will not be written by a person but sent from other sections of code that I have to accept as a number, for all practical purposes it is practically a string of length 15 (excluding decimal). The only way to identify repetition is to write code to manually search for it.

 

An ever so slight margin of error is acceptable for ridiculously large or ridiculously small numbers.

[DQW]

Looks like were talking terminating decimals of length 15 digits or smaller. Identifying repeating chunks should not be too hard. Something like the following should work, I'd think :

 

k=0

while ch=false

k = k+1

{

for i = k+1 to 15

{

If N = N[k]

then

{

P=1

d= i-k

for j = i to 15

{

P = P*(N[j] - N[j+d])

}

If P = 0 then ch=true

}

}

}

[Dave]

The input number will not be written by a person but sent from other sections of code that I have to accept as a number' date=' for all practical purposes it is practically a string of length 15 (excluding decimal). The only way to identify repetition is to write code to manually search for it.

 

An ever so slight margin of error is acceptable for ridiculously large or ridiculously small numbers.[/quote']

 

I didn't know that it was being sent from other parts of the program.

 

I also don't know what program you're writing, but surely it might be more prudent to write yourself a fraction class or something similar? That would save the hassle of trying to identify sections of repeating code. You also have to bear in mind that some fractions also have a delay before they repeat, which can easily be longer than 15 decimal places.