finding cycles in decimal expansion of rational numbers

Question

I need to write a program that prints 0.(03) for input 1 and 33. (1/33 = 0.03030303.... We use the notation 0.(03) to denote that 03 repeats indefinitely.)

As another example, 8639/70000 = 0.1234(142857)

I understand, I need to use an algorithm like floyds. But how do I get 0.0.030303030303 instead of 0.03030303030304 in java.

For arbitary precision you need to use BigDecimal. For greater precision you should use fractions. You need to evaluate until you get a multiple of 9, 99, 999, 9999 ... — Peter Lawrey, Jun 14 '12 at 08:07

Peter Lawrey · Answer 1 · 2012-06-14T11:43:25.263

You can try the following which more robust.

The theory is that all repeating sequences have to be a multiple of

1/9 or 0.(1), 
1/99 or 0.(01)
1/999 or 0.(001)
1/9999 or 0.(0001)
etc.

So to find how a fraction is a factor of 9, 99, 999, 9999 etc. Once you know which "nines" your denominator is a factor of, you know how it repeats.

/*
8639/70000 : 0.1234(142857)
1/1: 1.
1/2: 0.5
1/3: 0.(3)
1/4: 0.25
1/5: 0.2
1/6: 0.1(6)
1/7: 0.(142857)
1/8: 0.125
1/9: 0.(1)
1/10: 0.1
1/11: 0.(09)
1/12: 0.08(3)
1/13: 0.(076923)
1/14: 0.0(714285)
 etc
 */
public static final BigInteger NINE = BigInteger.valueOf(9);

public static void main(String... args) {
    System.out.println("8639/70000 : " + repeatingFraction(8639, 70000));
    for (int i = 1; ; i++)
        System.out.println("1/" + i + ": " + repeatingFraction(1, i));
}

private static String repeatingFraction(long num, long den) {
    StringBuilder sb = new StringBuilder();
    sb.append(num / den);
    sb.append('.');
    num %= den;
    for (int i = 3, lim = (int) Math.sqrt(num); i <= lim; i++) {
        while (num % i == 0 && den % i == 0) {
            num /= i;
            den /= i;
        }
    }

    while (num > 0) {
        while (den % 2 == 0 && num % 2 == 0) {
            num /= 2;
            den /= 2;
        }
        while (den % 5 == 0 && num % 5 == 0) {
            num /= 5;
            den /= 5;
        }
        // simplify.
        BigInteger nine = NINE;
        BigInteger denBI = BigInteger.valueOf(den);
        long lim = den;
        while (lim % 2 == 0) lim /= 2;
        while (lim % 5 == 0) lim /= 5;
        for (int j = 1; j <= lim; j++, nine = nine.multiply(BigInteger.TEN).add(NINE)) {
            if (nine.mod(denBI).equals(BigInteger.ZERO)) {
                BigInteger repeat = BigInteger.valueOf(num).multiply(nine).divide(denBI);
                sb.append('(').append(String.format("%0" + j + "d", repeat)).append(')');
                return sb.toString();
            }
        }
        num *= 10;
        sb.append(num / den);
        num %= den;
    }
    return sb.toString();
}

I made it up. ;) I sure it has a name but I don't know what it is. — Peter Lawrey, Jun 14 '12 at 11:17

score 4 · Answer 2 · edited May 23 '17 at 12:06

4

To properly detect cycles in the decimal expansion, you ought to avoid floating-point math altogether.

Here is a way to do it using integer arithmetic alone: Algorithm for detecting repeating decimals?

edited May 23 '17 at 12:06

Community

1
1

answered Jun 14 '12 at 08:17

NPE

486,780
108
951
1,012

score 2 · Accepted Answer · edited May 06 '13 at 21:47

2

With this code, I think you'll find what you're looking for:

BigDecimal one = new BigDecimal(1);

BigDecimal thirtyThree = new BigDecimal(33);

//Fix the decimals you want, i.e. 21
MathContext context = new MathContext(21, RoundingMode.DOWN);

BigDecimal result = one.divide(thirtyThree, context);       

System.out.println(result);

This yields the next result: 0.0303030303030303030303

edited May 06 '13 at 21:47

nhahtdh

55,989
15
126
162

answered Jun 14 '12 at 08:18

raven1981

1,415
1
16
20

This is implicitly `0.0303030303030303030303000000000000000000000000` ;) – Peter Lawrey Jun 14 '12 at 08:34
1

Of course, you can't store an infinite number, you must choose the right decimals depending on the context you're using – raven1981 Jun 14 '12 at 08:54
1

An alternative is leave everything as a fraction so there is never a loss of precision. The number of digits you need escalates very quickly. 1/97 = 0.(010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567) – Peter Lawrey Jun 14 '12 at 09:50

score 1 · Answer 4 · answered Jun 14 '12 at 08:10

1

By using a BigDecimal with the ROUND_DOWN rounding mode.

answered Jun 14 '12 at 08:10

Dawood ibn Kareem

77,785
15
98
110

finding cycles in decimal expansion of rational numbers

4 Answers4