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

Question

是否有算法可以计算重复小数比的数字而不从头开始？

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

例如,33/59扩展为58位的重复小数.如果我想验证,我怎么能计算从第58位开始的数字？

编辑 - 比率2124679/2147483647,如何获得2147484600th到2147484700位的百位数.

Answer 1

好的,第三次尝试是一个魅力:)

我无法相信我忘记了模幂运算.

所以从我的第二个答案中窃取/总结,x/y的第n个数字是(10 ^n-1 x mod y)/ y = floor(10*(10 ^n-1 x mod y)/ y)的第一个数字mod 10.

一直占用的部分是10 ^n-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()模幂运算的结构和模幂运算都是一样的;两者都是基于俄罗斯农民的乘法.)结果如下:

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