Repeating decimals and rational numbers

Now for another rabbit hole… How can we use a program to convert repeating decimals to a rational number (aka, fraction)? On paper this is not a complicated process, but in a floating point environment it may present with challenges.

My first attempt will be naive, and avoidable if anybody can toss out some pointers for us to keep in mind when designing a solution. Any takers?

2 Likes

Are we talking: 0.3333, 0.6666 or 0.123123123, 0.153846153846, etc.?

Si.

If it’s a float then it isn’t repeating, is it? If you know a number has repeating digits then that’s because you have additional information, use that information instead

Interesting question @mtf

Perhaps you could write a function that checks how many times your repeating decimal fits inside 1, 2, 3, 4, etc.

How about a while loop that checks the modulo of i versus your repeating decimal, if it is 0 you know your fraction.

i will increase at each check starting with 1, the moment the modulo is 0 you can print your i and the number of times the repeating decimal fits inside i. Does this make any sense?

1 Like

Here’s what I have so far.

1 Like

0.01234567890123456789

['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '1', '2', '3', '4', '5', '6', '8']
Not a repeating decimal!

This is the problem I am referring to, or at least one of them. There are limits in Python’s representation of decimal numbers and those same limits lead to mathematical errors (of a sort) that do not agree with our pencil and paper results.

Great first draft! Will need a spell to wriggle through the logic, but I can see where it’s going.

1 Like

To my mind it suggests we need first to determine if a given value indeed has a repeating sequence. That would also be my first concern.

We need to recognize that the sequence may not include the first n digits in the decimal fraction; and, need to identify and extract those digits before we can apply an algorithm to the remaining sequence.

0.5909090909090

The repitend is 90, once we remove the leading 5. Some precise way to identify any repitend, if it exists, is what we require.

1 Like

Rather than paramatize a numeric in this problem, we of necessity must turn to character sequences.

Now the first problem is the input.

0.5909090909090

versus,

'0.5909090909090'; or,
'.5909090909090'
>>> 13/22
0.5909090909090909
>>> 25/44
0.5681818181818182
>>> 
>>> '%f' % (25/44)
'0.568182'
>>> 

The problem isn’t that digits stop, it’s that you don’t know whether there would be digits, or if they really do stop, or if it actually keeps repeating after that, maybe other digits follow.

If you know that they repeat, then your input isn’t a float, it’s something else.

You can’t even know that those are the digits.

>>> 1.999999999999999999999999999999999999999999999999999999999999999
2.0

If the actual input to the program is a string together with the promise that they do continue in a pattern represented in the string, then that is the data type that should be used.

1 Like

Baby steps… The first step I’ve chosen is to extract the sequence from the input string. There are some assumptions, namely that the string will contain a dot. Will need an alternate action if no dot is present.

https://repl.it/@mtf/rational-from-repeating-decimal

False
No repeat
9090909090
818181818181

Also, will need to confirm that the characters are actually numbers.

1 Like

What if we have 56185185185185? There are so many possible kinks. What if the repitend is 100’s of digits long? We may want to decide on some limits at some point, but for now we’ve still got basic logic to work on. :slightly_smiling_face:

Longest repeating pattern starting from the back that can be found at least twice, then split it up into smallest repeating cycle

However. I still suspect that the user knows what repeats, and could therefore tell the program this directly.
If the user knows it repeats (this whole thing makes that assumption) then it must also know what repeats, right?

If the user doesn’t know that there’s a cycle, then the program can’t tell either because the program is receiving finite digits.
One could look for what-would-it-be-if-it-is-known-to-repeat, but then we’re back to that the user already knows.

2 Likes

Tell me about it. I mentioned assumptions, and your example did come to mind but I steamed ahead, anyway.

Something we do know is that there may be a prefix which is not part of the repitend, and the repitend is not interrupted once we get into the sequence past the possible prefix. In your example we might be able to check if the number following the first 5 is the same as the number following the second 5. That would help rule out the first five if they are different.

Seems at some point we will need to recurse through the sequence in progressively larger chunks. I’ve not come up with the logic for that.

Perhaps we should be looking for the repeating chunk first, and then elliminate the prefix as a result of that?

1 Like

I tend to agree that this is the avenue of approach we should take, and not burden the program with sussing the repitend. It would certainly simplify things.

1 Like

@ionatan has a good point.

Code to convert a known repitend to a fraction is not so difficult. Maybe a few parameters are in order here. Do all inputs definitely have a repitend? If not, we could include logic to convert those inputs to fractions as well. I don’t know. It’s your rabbit hole, Roy. I’m game for whatever. I enjoy a challenge.

1 Like

Took me a minute for this to sink in. Makes perfect sense, AND it lets us isolate the possible prefix.

Unless we throw in values where the last instance of the repitend is incomplete.
0.1538461538461538
You know. Just for fun. :laughing:

that still works (I’m assuming you mean that’s supposed to break that strategy, it doesn’t)