Getting a specific digit from a ratio expansion in any base (nth digit of x/y)

Question

Is there an algorithm that can calculate the digits of a repeating-decimal ratio without starting at the beginning?

I'm looking for a solution that doesn't use arbitrarily sized integers, since this should work for cases where the decimal expansion may be arbitrarily long.

For example, 33/59 expands to a repeating decimal with 58 digits. If I wanted to verify that, how could I calculate the digits starting at the 58th place?

Edited - with the ratio 2124679 / 2147483647, how to get the hundred digits in the 2147484600th through 2147484700th places.

Answer 1

OK, 3rd try's a charm :)

I can't believe I forgot about modular exponentiation.

So to steal/summarize from my 2nd answer, the nth digit of x/y is the 1st digit of (10^n-1x mod y)/y = floor(10 * (10^n-1x mod y) / y) mod 10.

The part that takes all the time is the 10^n-1 mod y, but we can do that with fast (O(log n)) modular exponentiation. With this in place, it's not worth trying to do the cycle-finding algorithm.

However, you do need the ability to do (a * b mod y) where a and b are numbers that may be as large as y. (if y requires 32 bits, then you need to do 32x32 multiply and then 64-bit % 32-bit modulus, or you need an algorithm that circumvents this limitation. See my listing that follows, since I ran into this limitation with Javascript.)

So here's a new version.

function abmody(a,b,y)
{
  var x = 0;
  // binary fun here
  while (a > 0)
  {
    if (a & 1)
      x = (x + b) % y;
    b = (2 * b) % y;
    a >>>= 1;
  }
  return x;
}

function digits2(x,y,n1,n2)
{
  // the nth digit of x/y = floor(10 * (10^(n-1)*x mod y) / y) mod 10.
  var m = n1-1;
  var A = 1, B = 10;
  while (m > 0)
  {
    // loop invariant: 10^(n1-1) = A*(B^m) mod y

    if (m & 1)
    {
      // A = (A * B) % y    but javascript doesn't have enough sig. digits
      A = abmody(A,B,y);
    }
    // B = (B * B) % y    but javascript doesn't have enough sig. digits
    B = abmody(B,B,y);
    m >>>= 1;
  }

  x = x %  y;
  // A = (A * x) % y;
  A = abmody(A,x,y);

  var answer = "";
  for (var i = n1; i <= n2; ++i)
  {
    var digit = Math.floor(10*A/y)%10;
    answer += digit;
    A = (A * 10) % y;
  }
  return answer;
}

(You'll note that the structures of abmody() and the modular exponentiation are the same; both are based on Russian peasant multiplication.) And results:

js>digits2(2124679,214748367,214748300,214748400)
20513882650385881630475914166090026658968726872786883636698387559799232373208220950057329190307649696
js>digits2(122222,990000,100,110)
65656565656
js>digits2(1,7,1,7)
1428571
js>digits2(1,7,601,607)
1428571
js>digits2(2124679,2147483647,2147484600,2147484700)
04837181235122113132440537741612893408915444001981729642479554583541841517920532039329657349423345806

Answer 2

As a general technique, rational fractions have a non-repeating part followed by a repeating part, like this:

nnn.xxxxxxxxrrrrrr

xxxxxxxx is the nonrepeating part and rrrrrr is the repeating part.

1. Determine the length of the nonrepeating part.
2. If the digit in question is in the nonrepeating part, then calculate it directly using division.
3. If the digit in question is in the repeating part, calculate its position within the repeating sequence (you now know the lengths of everything), and pick out the correct digit.

The above is a rough outline and would need more precision to implement in an actual algorithm, but it should get you started.