Now posted: Rationalise recurring binary

Given a potentially recurring binary string, output the number it represents, as a fraction in lowest terms.

The notation used in this challenge for recurring digits is non-standard. An r is used to indicate that the remaining digits recur. For example, 0.000r10 means the last 2 digits recur, like this: 0.000101010.... This is the binary representation of $\frac{1}{12}$, which cannot be expressed in binary without recurring digits.

Input

• A binary string made up of
  • Zero or more of 0
  • Zero or more of 1
  • Zero or one of .
  • Zero or one of r
• If r is present then there will always be a . somewhere to the left of the r
• There may be zero or more leading zeroes
• There may be zero or more trailing zeroes (in both recurring and non-recurring inputs)
• The last character will never be an r
• There will always be at least 1 character (the string will not be empty)
• The maximum length of input required to be handled is 15 characters

Interpretation

• All digits to the right of an r are recurring (repeating forever)
• Anything to the left of a . represents the integer part of the number (in binary)
• Anything to the right of a . represents the fractional part of the number (in binary)
• If the first character is a . then the integer part is zero
• If the last character is a . then the fractional part is zero
• If there is no . then the fractional part is zero

Output

• A numerator and denominator, in that order, or a rational type if your language supports one
• These can be in a multi-value data type such as a list/array/vector, or as a single string containing a non-numeric separating character (such as a space or a /)
• The numerator and denominator must be in lowest terms (that is, their greatest common factor is 1)
• An integer output N is represented as the fraction N/1, a numerator of N and a denominator of 1
• Zero is represented as the fraction 0/1, a numerator of zero and a denominator of 1
• The numerator and denominator are output as base 10 (decimal) - only the input is in binary

Examples

Throughout these examples binary strings are represented as fixed width and all other numbers are base 10 (decimal).

Non-recurring examples

• 10.00 is the integer 2, represented as 2/1
• 01.00 is the integer 1, represented as 1/1
• 00.10 is the fraction 1/2
• 00.01 is the fraction 1/4

Recurring examples

• 10.r0 is the same as 10.000..., the same as 10, the integer 2, represented as 2/1
• 0.r1 is the same as 0.111..., the same as 1, the integer 1, represented as 1/1
• 0.r01 is the same as 0.010101..., the fraction 1/3
• 0.r10 is the same as 0.101010..., the fraction 2/3
• 1.r01 is the same as 1.010101..., the fraction 4/3
• 0.r001 is the same as 0.001001001..., the fraction 1/7
• 0.r010 is the same as 0.010010010..., the fraction 2/7
• 0.r100 is the same as 0.100100100..., the fraction 4/7
• 1.r001 is the same as 1.001001001..., the fraction 8/7

Test cases

Test cases are in the format input : output

Outputs are in the format numerator/denominator

. : 0/1
.0 : 0/1
0. : 0/1
.1 : 1/2
1. : 1/1
0.0 : 0/1
00.00 : 0/1
.r0 : 0/1
.r1 : 1/1
00.r00 : 0/1
11.r11 : 4/1
00.0r0 : 0/1
11.1r1 : 4/1
.0101r01 : 1/3
.1010r10 : 2/3
.r01 : 1/3
.r0101 : 1/3
.r010101 : 1/3
.r0101010 : 42/127
.r0011 : 1/5
.r0110 : 2/5
.r1001 : 3/5
.r1100 : 4/5
.0r01 : 1/6
.00r10 : 1/6
.1r10 : 5/6
.r001 : 1/7
.r010 : 2/7
.r011 : 3/7
.r100 : 4/7
.r101 : 5/7
.r110 : 6/7
.r111 : 1/1
0001000.r01001 : 257/31
.r000111 : 1/9
.0r001110 : 1/9
.00r011100 : 1/9
.000r111000 : 1/9
.0001r110001 : 1/9
.00011r100011 : 1/9
.000111r000111 : 1/9
.r001110 : 2/9
.r011100 : 4/9
.r100011 : 5/9
.r110001 : 7/9
.r111000 : 8/9
1 : 1/1
10 : 2/1
11 : 3/1
100 : 4/1
101 : 5/1
110 : 6/1
111 : 7/1
111. : 7/1
111.0 : 7/1
111.r0 : 7/1
111.0r0 : 7/1

Explanations in answers are optional, but I'm more likely to upvote answers that have one.

Sandbox questions

• Is the max input length of 15 characters reasonable? Are there any reasons to make it longer or shorter?
• Are there any edge cases that should be added to the test cases?
• Is there a preferred format for the test cases?
• Are there any extra examples that would give insight?
• Is anything ambiguous?
• Is anything underspecified?
• Does anything take multiple readings to make sense, which could be explained more clearly?

To anyone already familiar with converting recurring decimal numbers to fractions, converting recurring binary numbers can be done with exactly the same method.

To anyone not already familiar with converting recurring decimal numbers to fractions, things such as 0.111... = 1 may be counterintuitive. I have deliberately focused only on explaining the meaning of the numbers, not the method of converting them, as that is the challenge.

Would it help to put a disclaimer at the top of the post, suggesting people look up how to convert recurring decimal numbers to fractions if not already familiar? I'm leaning towards not doing this, but I have carefully aligned the recurring examples to give a hint for those who haven't seen this kind of conversion before.

posted about 2 years ago

CC BY-SA 4.0

2y ago

trichoplax‭

1020 reputation 83 17 129 471