How to Know the Repeating Decimal in a Fraction

How to know the repeating decimal in a fraction?

A very simple algorithm is this: implement long division. Record every intermediate division you do. As soon as you see a division identical to the one you've done before, you have what's being repeated.

Example: 7/13.

1. 13 goes into   7 0 times with remainder  7; bring down a 0.
2. 13 goes into  70 5 times with remainder  5; bring down a 0.
3. 13 goes into  50 3 times with remainder 11; bring down a 0.
4. 13 goes into 110 8 times with remainder  6; bring down a 0.
5. 13 goes into  60 4 times with remainder  8; bring down a 0.
6. 13 goes into  80 6 times with remainder  2; bring down a 0.
7. 13 goes into  20 1 time  with remainder  7; bring down a 0.
8. We have already seen 13/70 on line 2; so lines 2-7 have the repeating part

The algorithm gives us 538461 as the repeating part. My calculator says 7/13 is 0.538461538. Looks right to me! All that remains are implementation details, or to find a better algorithm!

Algorithm for detecting repeating decimals?

To find the repeating pattern, just keep track of the values you use along the line:

1/5 = 1/101:

1 < 101 => 0
(decimal separator here)
10 < 101 => 0
100 < 101 => 0
1000 >= 101 => 1

  1000 - 101 = 11

110 >= 101 => 1

  110 - 101 = 1

10 -> match

As you reach the same value as you had at the second bit, the process will just repeat from that point producing the same bit pattern over and over. You have the pattern "0011" repeating from the second bit (first after decimal separator).

If you want the pattern to start with a "1", you can just rotate it until it matches that condition:

"0011" from the second bit
"0110" from the third bit
"1100" from the fourth bit

Edit:

Example in C#:

void FindPattern(int n1, int n2) {
   int digit = -1;
   while (n1 >= n2) {
      n2 <<= 1;
      digit++;
   }
   Dictionary<int, int> states = new Dictionary<int, int>();
   bool found = false;
   while (n1 > 0 || digit >= 0) {
      if (digit == -1) Console.Write('.');
      n1 <<= 1;
      if (states.ContainsKey(n1)) {
         Console.WriteLine(digit >= 0 ? new String('0', digit + 1) : String.Empty);
         Console.WriteLine("Repeat from digit {0} length {1}.", states[n1], states[n1] - digit);
         found = true;
         break;
      }
      states.Add(n1, digit);
      if (n1 < n2) {
         Console.Write('0');
      } else {
         Console.Write('1');
         n1 -= n2;
      }
      digit--;
   }
   if (!found) {
      Console.WriteLine();
      Console.WriteLine("No repeat.");
   }
}

Called with your examples it outputs:

.1
No repeat.
.01
Repeat from digit -1 length 2.
.10
Repeat from digit -1 length 2.
1.0
Repeat from digit 0 length 2.
.0011
Repeat from digit -1 length 4.

How to detect a repeating decimal

Here is a possible implementation how to compute the decimal expansion
of a fraction and detect repeating decimals (i.e. periods in the
decimal expansion). It is a translation of the code posted and reviewed
in Decimal expansion of a rational number on Code Review to Swift.

The algorithm is just the Long Division, and an array
(remainders) is used to check for a periodic decimal expansion.
(For the sake of simplicity, it is assumed that the numerator is
non-negative and the
denominator is positive. This can be generalised if necessary.)

struct DecimalFraction : Printable {
    let wholePart : Int         // Integer part
    let fractionDigits : [Int]  // Fractional digits
    let repeatingAt : Int?      // Position of first repeating digit, or `nil`

    // Create DecimalFraction from given fraction
    init(numerator : Int, denominator : Int) {
        precondition(numerator >= 0, "`numerator` must be non-negative")
        precondition(denominator > 0, "`denominator` must be positive")

        wholePart = numerator / denominator
        var fractionDigits : [Int] = []
        var repeatingAt : Int? = nil
        var rem = (abs(numerator) % denominator) * 10
        var remainders : [Int] = []
        while (rem > 0 && repeatingAt == nil) {
            remainders.append(rem)
            let digit = rem / denominator
            rem = (rem % denominator) * 10
            fractionDigits.append(digit)
            repeatingAt = find(remainders, rem)
        }
        self.fractionDigits = fractionDigits
        self.repeatingAt = repeatingAt
    }

    // Produce a string description, e.g. "12.3{45}"
    var description : String {
        var result = String(wholePart) + "."
        for (idx, digit) in enumerate(fractionDigits) {
            if idx == repeatingAt {
                result += "{"
            }
            result += String(digit)
        }
        if repeatingAt != nil {
            result += "}"
        }
        return result
    }
}

Examples:

println(DecimalFraction(numerator: 3, denominator: 8))
// 0.375
println(DecimalFraction(numerator: 1, denominator: 3))
// 0.{3}
println(DecimalFraction(numerator: 20, denominator: 7))
// 2.{857142}
println(DecimalFraction(numerator: 12222, denominator: 990))
// 12.3{45}

The periods are simply indicated by curly braces, but it should
be easy to modify the code to produce an NSAttributedString
which indicates the periods by – for example – horizontal lines.

Format Repeating Decimal as a Fraction

From Link

Take the number of digits in the repeating part as the numerator, take 9 repeating with the same number of digits and reduce the fraction.

E.g., .3 repeating is the same as 3/9. Reduce by dividing both sides by the gcd (3 in this case) and you get 1/3.

You'll need to do some extra math if you can extract a repeating decimal from a terminating decimal, e.g. .133333333.

Determine x/y fraction has repeating decimal expansion

Given integers x and y, the fraction x/y has a repeating decimal expansion if and only if:

1. y / gcd(x, y) has factors other than 2 and 5, and
2. the remainder after dividing x by y is not zero

NOTE: as pointed out in the comments, my original answer had a flaw in that it only worked if x/y was an irreducible fraction (in lowest terms). This is remedied by first dividing y by gcd(x, y) so that you're checking whether the denominator of the equivalent irreducible fraction has factors other than powers of 2 and 5.

The second condition is pretty easy to check:

HasRepeatingDecimal(x, y)
1. if x % y == 0 then return false

Now we need to see if y / gcd(x, y) has factors other than 2 and 5. We can do this by repeatedly dividing y / gcd(x, y) by 5 and then by 2 and see if we end up with the number 1:

HasRepeatingDecimal(x, y)
1. if x % y == 0 then return false
2. y = y / gcd(x, y)
3. while (y % 5 == 0) y = y / 5
4. while (y % 2 == 0) y = y / 2
5. if y == 1 then return true else return false

The reason you can check the denominator's divisibility by 2 and 5 is that the decimal system has base 10 and 2 and 5 are the only prime factors of 10. If you were using base-21, you'd check for y / gcd(x, y) being of the form 3^a x 7^b instead.

Find repeating part of repeating decimal -- PHP

Gotta say this isn't as easy as i thought it'd be. but i got it working. I'm sure there is a more efficient way of doing this, hopefully someone else will improve upon this. Especially the part where it gets printed.

$number1 =  $number / $divisor;
if(findRepeat( $number1 ) !== false)
{
    $result = findRepeat($number1);
    $leadingNum = strstr($number1, '.', true);
    $nonRepeat = substr($number1, strpos($number1, '.') + 1 , $result['position']);
    if($nonRepeat == '')
        $nonRepeat = '.';

    $repeat = substr($number1,strpos($number1,$nonRepeat) + strlen($nonRepeat), $result['patternSize']);
    $nonRepeat = $nonRepeat == '.' ? '.' : '.'.$nonRepeat;
    echo $leadingNum.$nonRepeat."<span style='text-decoration:overline'>".$repeat."</span>";

}
else
  echo number_format( $number1 , 6);

now for the function

function findRepeat($number)
{
    $maxLength = 6;
    $decimal = substr($number, strpos($number,'.') + 1 );
    if(strlen($decimal) >= $maxLength )
        $decimal = substr($decimal,0, $maxLength);
    else
        $maxLength = strlen($decimal);

    for($i =0; $i < $maxLength - 3; ++$i)
    {
        //check for single repeition
        if( $decimal[$i] == $decimal[$i + 1] &&  $decimal[$i + 1] == $decimal[$i+2])
            return array('position'=>$i,'patternSize'=>1);
        //triple repetition
        if(substr($decimal,$i,3) == substr($decimal, $i + 3, 3) )
            return array('position'=>$i,'patternSize'=>3);
        //double repetition
        if(substr($decimal,$i,2) == substr($decimal, $i + 2, 2) )
            return array('position'=>$i,'patternSize'=>2);
    }

    return false;
}

Repeating Decimal Algorithm

You've got most of it figured out, only 2 parts are missing:

1. Check that the numerator of long division is repeating and halt the loop. When numerator repeats, it means that we have found the repeating decimal.

2. Convert array to string without commas, which is easily achievable by using join('').

Here's the relevant part of your code with the above 2 points implemented:

function fractionToDecimal(n, d) {
    var pFS = primeFactors(d);
    for (var i = 0; i < pFS.length; i++) { // Go through each of the denominators prime factors

        if (pFS[i] !== 2 && pFS[i] !== 5) { // We have a repeating decimal

            var output = new Array();
            var ns = new Array();

            // Let's find the repeating decimal
            // Repeating decimal algorithm - uses long division
            for (var i = 0; i < 20; i++) { // For now find 20 spots, ideally this should stop after it finds the repeating decimal
                // How many times does the denominator go into the numerator evenly
                var temp2 = parseInt(n / d);

                if (ns[n] === undefined) {
                    ns[n] = i;
                } else {
                    return "Repeating decimal: " + 
                        output.slice(0, 1).join('') +
                        '.' +
                        output.slice(1, ns[n]).join('') +
                        '[' + output.slice(ns[n]).join('') + ']'
                    ;
                }

                output.push(temp2);
                var n = n % d;
                n += "0";
            }           
            return "Repeating decimal: " + output;
        }
    }

    // Terminating decimal
    return "Terminating decimal: " + n / d;
}

jsFiddle with the complete code: http://jsfiddle.net/49Xks/

Convert fraction to string with repeating decimal places in brackets

Your code just needed some minor changes (see the comments below):

def convert(numerator, denominator):
    #print("---->", numerator, "/", denominator)
    result = [str(numerator//denominator) + "."]
    subresults = [numerator % denominator]          ### changed ###
    numerator %= denominator
    while numerator != 0:
        #print(numerator)
        numerator *= 10
        result_digit, numerator = divmod(numerator, denominator)
        result.append(str(result_digit))             ### moved before if-statement

        if numerator not in subresults:
            subresults.append(numerator)
            #print("appended", result_digit)

        else:
            result.insert(subresults.index(numerator) + 1, "(")   ### added '+ 1'
            #print("index", subresults.index(numerator), subresults, "result", result)
            result.append(")")
            #print("repeating", numerator)
            break
    #print(result)
    return "".join(result)

---

Related Topics