language-agnostic - 从任何基数的比率扩展中获取特定数字(x/y 的第 n 位数字)

Question

有没有一种算法可以计算重复十进制比率的位数而无需从头开始？

我正在寻找一种不使用任意大小整数的解决方案，因为这应该适用于十进制扩展可能任意长的情况。

例如，33/59 扩展为具有 58 位数字的重复小数。如果我想验证这一点，我如何计算从第 58 位开始的数字？

编辑 - 比率为 2124679/2147483647，如何获得第 2147484600 位到第 2147484700 位的百位数字。

Answer 1

好的，第三次尝试很有魅力:)

我不敢相信我忘记了模幂运算。

因此，从我的第二个答案中窃取/总结，x/y 的第 n 个数字是 (10n-1x mod y)/y = floor(10 * (10n-1x mod y)/y) mod 10 的第一个数字。

需要所有时间的部分是 10n-1 mod y，但我们可以通过快速 (O(log n)) 模幂运算来做到这一点。有了这个，就不值得尝试进行循环查找算法了。

但是，您确实需要具有执行 (a * b mod y) 的能力，其中 a 和 b 是可能与 y 一样大的数字。 (如果 y 需要 32 位，那么您需要进行 32x32 乘法，然后是 64 位 % 32 位模数，或者您需要一种绕过此限制的算法。请参阅下面的列表，因为我在使用 Javascript 时遇到了此限制。 )

所以这是一个新版本。

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;
}

(您会注意到 abmody() 的结构和模幂运算是相同的；两者都基于 Russian peasant multiplication 。)
结果:

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