任意のベースの比率展開から特定の数字を取得する（x / yのn番目の数字）

Question

最初から開始せずに、繰り返し10進数比の桁を計算できるアルゴリズムはありますか？

任意のサイズの整数を使用しないソリューションを探しています。これは、10進数の展開が任意に長い場合に機能するはずです。

たとえば、33/59は58桁の繰り返しの小数に展開されます。それを確認したい場合、58位から始まる桁をどのように計算できますか？

編集済み-比率2124679/2147483647で、2147484600番目から2147484700番目までの100桁を取得する方法。

Answer 1

OK、3回目の試行は魅力です：）

モジュラーべき乗を忘れたとは信じられません。

2番目の回答から盗み/要約するために、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

Answer 2

編集：（後世のためにここに投稿します。しかし、 はもう賛成しないでください。理論的には有用かもしれませんが、実際には実用的ではありません。実用的な観点からはるかに便利で、ファクタリングを必要とせず、bignumを使用する必要がない別の回答を投稿しました。）

---

@Daniel Brucknerには正しいアプローチがあると思います。 （いくつかの追加のねじれが必要です）

もっと簡単な方法があるかもしれませんが、以下は常に機能します：

33/59に加えて、q = x / y = 33/57820および44/65の例を使用してみましょう。理由はすぐに明らかになります。

ステップ1：分母を因数分解します（具体的には2と5を因数分解します）

Write q = x / y = x /（2 ^{a ₂} 5 ^{a ₅} z）。分母の2と5の係数は、小数の繰り返しを引き起こしません。したがって、残りの因子zは10に素であります。実際、次のステップではzの因子分解が必要なので、全体を因子分解することもできます。

a ₁₀ = max（a ₂ 、a ₅ ）を計算します。これは、係数の倍数である10の最小指数です。 yの2および5の。

この例では、57820 = 2 * 2 * 5 * 7 * 7 * 59なので、a ₂ = 2、a ₅ = 1、a ₁₀ = 2、z = 7 * 7 * 59 = 2891。

33/59の例では、59は素数であり、2または5の因子を含まないため、a ₂ = a ₅ = a ₁₀ = 0。

この例では、44 / 65、65 = 5 * 13、a ₂ = 0、a ₅ = a ₁₀ = 1 。

参考のために、こちらで優れたオンラインファクタリング計算機を見つけました。 （次のステップに重要な能力もあります）

ステップ2：オイラーの定理またはカーマイケルの定理。

欲しいのは、10 ⁿ -1がzで割り切れるような数n、つまり10 ⁿ <！>＃8801;です。 1 mod z。オイラーの関数<！>＃966;（z）およびCarmichaelの関数<！>＃955;（z）は、nに有効な値を提供し、<！>＃955;（z）は小さい数と<！ >＃966;（z）おそらく少し簡単に計算できます。これは難しくありません。zを因数分解し、少し計算するだけです。

<！>＃966;（2891）= 7 * 6 * 58 = 2436

<！>＃955;（2891）= lcm（7 * 6、58）= 1218

これは、10 ²⁴³⁶ <！>＃8801; 10 ¹²¹⁸ <！>＃8801; 1（mod 2891）。

より単純な部分33/59の場合、<！>＃966;（59）= <！>＃955;（59）= 58ので、10 ⁵⁸ <！>＃8801; 1（mod 59）。

44/65 = 44 /（5 * 13）の場合、<！>＃966;（13）= <！>＃955;（13）= 12。

だから何？さて、繰り返し小数の期間は<！>＃966;（z）と<！>＃955;（z）の両方を分割する必要があります。繰り返し小数の期間の境界。

ステップ3：より多くの数値計算処理

n = <！>＃955;（z）を使用しましょう。 Q '' = 10 ^{（a ₁₀ + n） a ₁₀} x / yを引くとsup> x / y、次のようになります：

m = 10 ^{a ₁₀} （10 ⁿ -1）x / y

整数です 10 ^{a ₁₀} はyの2と5の倍数であり、10 ⁿ -1は、yの残りの因子の倍数です。

ここで行ったのは、元の数値qをa ₁₀ 桁左にシフトしてQ 'を取得し、qをa ₁₀ + n桁左にシフトすることです。 Q ''を取得します。これは小数の繰り返しですが、それらの差は計算可能な整数です。

x / yをm / 10 ^{a ₁₀} /（10 ⁿ -1）に書き換えることができます。

例を検討するq = 44/65 = 44 /（5 * 13）

a ₁₀ = 1、および<！>＃955;（13）= 12、したがって、Q '= 10 ¹ qおよびQ' '= 10 ^{12 + 1} qです。

m = Q ''-Q '=（10 ¹² -1）* 10 ¹ *（44/65）= 153846153846 * 44 = 6769230769224

so q = 6769230769224/10 /（10 ¹² -1）。

他の分数33/57820および33/59は、より大きな分数になります。

手順4：繰り返しのない繰り返しの小数部分を見つけます。

kが1〜9の場合、k / 9 = 0.kkkkkkkkkkkkk ...

同様に、1から99までの2桁の数字kl、k / 99 = 0.klklklklklkl ...

一般化：k桁のパターンabc ... ijの場合、この数abc ... ij /（10 ^k -1）= 0.abc ... ijabc ... ijabc ... ij ...

パターンに従うと、前のステップで取得したこの（潜在的に）巨大な整数mを取得し、m = s *（10 ^{nとして記述する必要があることがわかります。} -1）+ r、ここで1 <！>＃8804; r <！> lt; 10 ⁿ -1。

これは最終的な答えにつながります：

• sは非反復部分です
• rは繰り返し部分です（必要に応じてn桁になるように左側にゼロが埋め込まれます）
• a ₁₀ = 0、小数点は 非反復および反復部分。もし a ₁₀ <！> gt; 0、それは位置しています a ₁₀ の左側の場所 sとrのジャンクション。

44/65の場合、6769230769224 = 6 *（10 ¹² -1）+ 769230769230

を取得します

s = 6、r = 769230769230、および44/65 = 0.6769230769230ここで、下線は繰り返し部分を示しています。

ステップ2でnの最小値を見つけてCarmichael関数<！>＃955;（z）を開始し、その要因のいずれかが10 ⁿ <！>＃8801; 1（mod z）。

更新：好奇心For盛な人にとっては、Pythonインターピーターがbignumで計算する最も簡単な方法のようです。 （pow（x、y）はx ^y を計算し、//と％はそれぞれ整数除算と剰余です。）次に例を示します：

>>> N = pow(10,12)-1
>>> m = N*pow(10,1)*44//65
>>> m
6769230769224
>>> r=m%N
>>> r
769230769230
>>> s=m//N
>>> s
6
>>> 44/65
0.67692307692307696

>>> N = pow(10,58)-1
>>> m=N*33//59
>>> m
5593220338983050847457627118644067796610169491525423728813
>>> r=m%N
>>> r
5593220338983050847457627118644067796610169491525423728813
>>> s=m//N
>>> s
0
>>> 33/59
0.55932203389830504

>>> N = pow(10,1218)-1
>>> m = N*pow(10,2)*33//57820
>>> m
57073676928398478035281909373919059149083362158422691110342442061570390868211691
45624351435489450017295053614666205465236942234520927014873746108612936700103770
32168799723279142165340712556208924247665167762020062262193012798339674852992044
27533725354548599100657212037357315807679003804911795226565202352127291594603943
27222414389484607402282947077135939121411276374956762365963334486336907644413697
68246281563472846765824974057419578000691802144586648218609477689380837080594949
84434451746800415081286751988931165686613628502248356969906606710480802490487720
51193358699411968177101349014181943964026288481494292632307160152196471809062608
09408509166378415773088896575579384296091317883085437564856451054998270494638533
37945347630577654790729851262538913870632998962296783120027672085783465928744379
10757523348322379799377378069872016603251470079557246627464545140089934278796264
26841923209961950882047734347976478727084053960567277758561051539259771705292286
40608785887236250432376340366655136630923555863023175371843652715323417502594258
04219993081978554133517813905223106191629194050501556554825319958491871324801106
88343133863714977516430300933932895191975095122794880664130058803182289865098581
80560359737115185
>>> r=m%N
>>> r
57073676928398478035281909373919059149083362158422691110342442061570390868211691
45624351435489450017295053614666205465236942234520927014873746108612936700103770
32168799723279142165340712556208924247665167762020062262193012798339674852992044
27533725354548599100657212037357315807679003804911795226565202352127291594603943
27222414389484607402282947077135939121411276374956762365963334486336907644413697
68246281563472846765824974057419578000691802144586648218609477689380837080594949
84434451746800415081286751988931165686613628502248356969906606710480802490487720
51193358699411968177101349014181943964026288481494292632307160152196471809062608
09408509166378415773088896575579384296091317883085437564856451054998270494638533
37945347630577654790729851262538913870632998962296783120027672085783465928744379
10757523348322379799377378069872016603251470079557246627464545140089934278796264
26841923209961950882047734347976478727084053960567277758561051539259771705292286
40608785887236250432376340366655136630923555863023175371843652715323417502594258
04219993081978554133517813905223106191629194050501556554825319958491871324801106
88343133863714977516430300933932895191975095122794880664130058803182289865098581
80560359737115185
>>> s=m//N
>>> s
0
>>> 33/57820
0.00057073676928398479

ゼロパディングに使用可能なオーバーロードされたPython %文字列演算子を使用して、繰り返される数字の完全なセットを表示します。

>>> "%01218d" % r
'0570736769283984780352819093739190591490833621584226911103424420615703908682116
91456243514354894500172950536146662054652369422345209270148737461086129367001037
70321687997232791421653407125562089242476651677620200622621930127983396748529920
44275337253545485991006572120373573158076790038049117952265652023521272915946039
43272224143894846074022829470771359391214112763749567623659633344863369076444136
97682462815634728467658249740574195780006918021445866482186094776893808370805949
49844344517468004150812867519889311656866136285022483569699066067104808024904877
20511933586994119681771013490141819439640262884814942926323071601521964718090626
08094085091663784157730888965755793842960913178830854375648564510549982704946385
33379453476305776547907298512625389138706329989622967831200276720857834659287443
79107575233483223797993773780698720166032514700795572466274645451400899342787962
64268419232099619508820477343479764787270840539605672777585610515392597717052922
86406087858872362504323763403666551366309235558630231753718436527153234175025942
58042199930819785541335178139052231061916291940505015565548253199584918713248011
06883431338637149775164303009339328951919750951227948806641300588031822898650985
8180560359737115185'

Answer 3

一般的な手法として、有理数には次のように非反復部分とそれに続く反復部分があります：

nnn.xxxxxxxxrrrrrr

xxxxxxxxは非繰り返し部分で、rrrrrrは繰り返し部分です。

1. 非反復部分の長さを決定します。
2. 問題の数字が非繰り返し部分にある場合は、除算を使用して直接計算します。
3. 問題の数字が繰り返し部分にある場合は、繰り返しシーケンス内での位置を計算し（すべての長さがわかっている）、正しい数字を選びます。

上記は大まかな概要であり、実際のアルゴリズムで実装するにはより高い精度が必要ですが、開始する必要があります。

Answer 4

AHA！ caffiend：他の（より長い）回答（具体的には<！> quot;重複する残り<！> quot;）へのコメントは、O（n）（n =非反復の長さの合計）である非常に単純なソリューションにつながります+繰り返し部分。0〜10 * yの整数演算のみが必要です。yは分母です。

これは、有理数x / yの小数点の右側のn番目の桁を取得するJavascript関数です。

function digit(x,y,n) 
{ 
   if (n == 0) 
      return Math.floor(x/y)%10; 
   return digit(10*(x%y),y,n-1);
}

反復ではなく再帰的であり、サイクルを検出するのに十分ではありません（1/3の10000桁目は明らかに3ですが、10000番目の反復に達するまで継続します）が、少なくともスタックまでは動作しますメモリ不足です。

基本的に、これは2つの事実により機能します：

• x / yのn桁目は10x / yの（n-1）桁目（例：1/7の6桁目は10/7の5桁目は100/7の4桁目など。）
• x / yのn桁目は（x％y）/ yのn桁目です（例：10/7の5桁目は3/7の5桁目です）

これを反復ルーチンに調整し、 Floydのサイクルと組み合わせることができます。 -findingアルゴリズム（Martin Gardnerコラムから<！> quot; rho <！> quot;メソッドとして学びました）このアプローチを短縮するものを取得します。

このアプローチでソリューションを計算するjavascript関数は次のとおりです。

function digit(x,y,n,returnstruct)
{
  function kernel(x,y) { return 10*(x%y); }

  var period = 0;
  var x1 = x;
  var x2 = x;
  var i = 0;
  while (n > 0)
  {
    n--;
    i++;
    x1 = kernel(x1,y); // iterate once
    x2 = kernel(x2,y);
    x2 = kernel(x2,y); // iterate twice  

    // have both 1x and 2x iterations reached the same state?
    if (x1 == x2)
    {
      period = i;
      n = n % period;
      i = 0; 
      // start again in case the nonrepeating part gave us a
      // multiple of the period rather than the period itself
    }
  }
  var answer=Math.floor(x1/y);
  if (returnstruct)
    return {period: period, digit: answer, 
      toString: function() 
      { 
        return 'period='+this.period+',digit='+this.digit;
      }};
  else
    return answer;
}

そして、1/700のn桁目を実行する例：

js>1/700
0.0014285714285714286
js>n=10000000
10000000
js>rs=digit(1,700,n,true)
period=6,digit=4
js>n%6
4
js>rs=digit(1,700,4,true)
period=0,digit=4

33/59で同じこと：

js>33/59
0.559322033898305
js>rs=digit(33,59,3,true)
period=0,digit=9
js>rs=digit(33,59,61,true)
period=58,digit=9
js>rs=digit(33,59,61+58,true)
period=58,digit=9

および122222/990000（繰り返しのない長い部分）：

js>122222/990000
0.12345656565656565
js>digit(122222,990000,5,true)
period=0,digit=5
js>digit(122222,990000,7,true)
period=6,digit=5
js>digit(122222,990000,9,true)
period=2,digit=5
js>digit(122222,990000,9999,true)
period=2,digit=5
js>digit(122222,990000,10000,true)
period=2,digit=6

次の関数は、一連の数字を見つける別の関数です。

// find digits n1 through n2 of x/y
function digits(x,y,n1,n2,returnstruct)
{
  function kernel(x,y) { return 10*(x%y); }

  var period = 0;
  var x1 = x;
  var x2 = x;
  var i = 0;
  var answer='';
  while (n2 >= 0)
  {
    // time to print out digits?
    if (n1 <= 0) 
      answer = answer + Math.floor(x1/y);

    n1--,n2--;
    i++;
    x1 = kernel(x1,y); // iterate once
    x2 = kernel(x2,y);
    x2 = kernel(x2,y); // iterate twice  

    // have both 1x and 2x iterations reached the same state?
    if (x1 == x2)
    {
      period = i;
      if (n1 > period)
      {
        var jumpahead = n1 - (n1 % period);
        n1 -= jumpahead, n2 -= jumpahead;
      }
      i = 0; 
      // start again in case the nonrepeating part gave us a
      // multiple of the period rather than the period itself
    }    
  }
  if (returnstruct)
    return {period: period, digits: answer, 
      toString: function() 
      { 
        return 'period='+this.period+',digits='+this.digits;
      }};
  else
    return answer;
}

回答の結果を含めました（Javascript＃がオーバーフローしなかったと仮定）：

js>digit(1,7,1,7,true)
period=6,digits=1428571
js>digit(1,7,601,607,true)
period=6,digits=1428571
js>1/7
0.14285714285714285
js>digit(2124679,214748367,214748300,214748400,true)
period=1759780,digits=20513882650385881630475914166090026658968726872786883636698387559799232373208220950057329190307649696
js>digit(122222,990000,100,110,true)
period=2,digits=65656565656

Answer 5

アドホック良いアイデアはありません。 継続分数が役立つ場合があります。私はそれについて少し考えるつもりです...

更新

<ストライク> Fermatの小さな定理から。 （=は一致を示します）

10^39 = 10 (39)

10は39と互いに素であるため。

10^(39 - 1) = 1 (39)

10^38 - 1 = 0 (39)

[to be continued tomorow]

私は39が素数ではないことを認識するために階層化するつもりでした... ^^数日中に更新と回答を行い、全体のアイデアを提示します。 39は素数ではないことに注意していただきありがとうございます。

a/bとa < bおよび想定期間の長さp ...の短い答え...

• k = (10^p - 1) / bを計算し、整数であることを確認します。そうでない場合、c = k * aにはピリオドc
がありません
• 計算<=>
• <=>を10進数表現に変換し、ゼロで左詰めして<=>
の全長にします
• 小数点の後のi番目の数字は、パディングされた10進表現の（i mod p）番目の数字です（i = 0は小数点の後の最初の数字です-開発者です）

例

a = 3
b = 7
p = 6

k = (10^6 - 1) / 7
  = 142,857

c = 142,857 * 3
  = 428,571

パディングは不要であり、結論付けました。

3     ______
- = 0.428571
7