任意の基数の比率展開から特定の桁を取得する(x / yのn桁目)

language-agnostic math puzzle

先頭から始めずに繰り返し小数の桁数を計算できるアルゴリズムはありますか。

私は、任意の大きさの整数を使わない解決策を探しています。なぜなら、これは小数展開が任意に長い場合にはうまくいくはずですから。

たとえば、33/59は58桁の反復10進数に展開されます。 それを検証したい場合は、58桁目からどのように数字を計算すればよいでしょうか。

編集済み – 比率2124679/2147483647で、2147484600から2147484700の場所で100桁の数字を取得する方法。

  7  6


ベストアンサー

さて、3回目の試みは魅力です:)

モジュラー指数について忘れたとは思えない。

私の2番目の答えから盗む/要約すると、x / yのn桁目は(10 ^ n-1 ^ x mod y)/ y = floor(10 *(10 ^ n-1 ^ x mod y)の1桁目)/ y)mod 10

常にかかる部分は10 ^ n-1 ^ mod yですが、それを高速な(O(log n))モジュラー指数で行うことができます。 これが整っていれば、サイクル発見アルゴリズムを実行しようとする価値はありません。

ただし、(a * b mod y)を実行する機能は必要です。ここで、aとbは、yと同じ大きさの数値です。 (yが32ビットを必要とするならば、あなたは32×32乗算をしてから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()`の構造とべき乗剰余は同じであることに注意してください。どちらもhttp://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication#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

6


  • edit:*(私は後世のためにここにポストを残しています。 しかし、それを支持する必要はもうありません。理論的には有用かもしれませんが、実際的ではありません。 私は実用的な観点からはるかに有用で、因数分解を必要とせず、そしてbignumの使用を必要としない別の答えを投稿しました。

” ” ‘

@ Daniel Brucknerが正しいアプローチをしていると思います。 (いくつか追加の工夫が必要です)

もっと簡単な方法があるかもしれませんが、以下はいつもうまくいくでしょう:

33/59に加えて、例q = x / y = 33/57820と44/65を使用しましょう。

ステップ1:分母の因数分解(具体的には2と5の因数分解)

q = x / y = x /(2 ^ a〜2〜^ 5 ^ a〜5〜^ z)と書く。 分母の2と5の係数は、小数点以下の桁数を繰り返さないでください。 それで、残りの因子zは10と互いに素です。 実際、次のステップではzを因数分解する必要があるため、全体を因数分解することもできます。

yの2と5の因数の倍数である10の最小指数であるa〜10〜= max(a〜2〜、a〜5〜)を計算します。

この例では、57820 = 2 * 2 * 5 * 7 * 7 * 59なので、a 2 = 2、a 5 = 1、a 10 = 2、z = 7 * 7 * 59 = 2891です。

我々の例33/59では、59は素数で2や5の因数を含んでいないので、a〜2〜= a〜5〜= a〜10〜= 0です。

この例の44/65では、65 = 5 * 13、およびa〜2〜= 0、a〜5〜= a〜10〜= 1です。

参考のために、私は良いオンラインファクタリング計算機http://www.alpertron.com.ar/ECM.HTM [ここ]を見つけました。 (次のステップに重要な合計でも)

*ステップ2:http://en.wikipedia.org/wiki/Euler%27s_theorem [Eulerの定理]または​​http://en.wikipedia.org/wiki/Carmichael_function[Carmichaelの定理]を使用してください。

欲しいのは、10 ^ n ^ – 1がzで割り切れる数n、つまり10 ^ n ^≡1 mod zです。 オイラー関数φ(z)とカーマイケル関数λ(z)はどちらもnに有効な値を与えます。λ(z)は小さい数を与え、φ(z)はおそらく計算がもう少し簡単になります。 これはそれほど難しくありません、それはただzを因数分解して少し数学をすることを意味します。

φ(2891)= 7×6×58 = 2436

λ(2891)= 1cm(7×6,58)= 1218

これは10 ^ 2436 ^≡10 ^ 1218 ^≡1(mod 2891)を意味します。

より単純な分数33/59の場合、φ(59)=λ(59)= 58なので、10 ^ 58 ^≡1(mod 59)となります。

44 / 65 = 44 /(5×13)の場合、φ(13)=λ(13)= 1​​2である。

*そうですね。*繰り返し小数の周期は、φ(z)とλ(z)の両方を除算しなければならないため、実際には繰り返し小数の周期の上限になります。

ステップ3:より多くの数字のクランチ

n =λ(z)を使いましょう。 Q ‘= 10 (a〜10〜n) x / yからQ’ = 10 ^ a〜10〜^ x / yを引くと、

m = 10 ^ a〜10〜^(10 ^ n ^ – 1)x / y

10 ^ a〜10〜^はyの2と5の因数の倍数であり、10 ^ n ^ -1はyの残りの因数の倍数であるため、*は整数*です。

ここで行ったことはQ ‘を得るために元の数qを左に10〜10桁シフトし、Q’ ‘を得るために左にqを10〜n桁シフトすることです。それらの間は計算できる整数です。

それからx / yをm / 10 ^ a〜10〜^ /(10 ^ n ^ – 1)のように書き換えることができます。

例q = 44/65 = 44 /(5 * 13)を考えてください。

a〜10〜= 1、λ(13)= 12なので、Q ‘= 10 ^ 1 ^ qとQ’ ‘= 10 ^ 12 1 ^ qです。

m = Q ” – Q ‘=(10 ^ 12 ^ – 1)* 10 ^ 1 ^ *(44/65)= 153846153846 * 44 = 6769230769224

だからq = 6769230769224/10 /(10 ^ 12 ^ – 1)。

他のフラクション33/57820および33/59はより大きいフラクションをもたらす。

ステップ4:繰り返しのない繰り返しの小数部分を見つけます。

1から9までのkの場合、k / 9 = 0.kkkkkkkkkkkk …​

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

これは次のように一般化されます。

このパターンに従うと、前のステップで得たこの(潜在的に)巨大な整数mを取り、m = s *(10 ^ n ^ -1)rと書く必要があります。ここで、1≤r <10 ^ n ^ -1です。

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

  • sは非繰り返し部分です

  • rは繰り返し部分です(必要に応じて左側にゼロが埋め込まれます)
    n桁であることを確認してください)

  • a〜10〜= 0の場合、小数点は非繰り返しと
    繰り返し部分; a〜10〜> 0の場合、sとrの間のジャンクションの左側のa〜10〜の位置にあります。

44/65の場合、6769230769224 = 6 *(10 ^ 12 ^ -1)769230769230となります。

s = 6、r = 769230769230、および44/65 = 0.6769230769230であり、ここで下線は反復部分を示す。

ステップ2でnの最小値を見つけることで、カーマイケル関数λ(z)から始めて、その要素のいずれかが10 ^ n ^≡1(mod z)のようなnの値につながるかどうかを調べることで数値を小さくできます)

*更新:*興味がある人には、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'

4


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

nnn.xxxxxxxxrrrrrr

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

  1. 繰り返しのない部分の長さを決めます。

  2. 問題の数字が非繰り返し部分にある場合は、計算します
    除算を直接使用します。

  3. 問題の数字が繰り返し部分にある場合、その計算
    繰り返しシーケンス内の位置(すべての長さがわかった)、正しい数字を選択します。

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

2


ああ! caffiend:私のもう1つの(より長い)答え(具体的には「重複剰余」)に対するあなたのコメントは、O(n)という非常に単純な解決策を導きます。ここで、yは分母です。

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

関数digit(x、y、n){if(n == 0)はMath.floor(x / y)%10を返します。戻り数字(10 *(x%y)、y、n-1)。 }

反復ではなく再帰的で、サイクルを検出するのに十分スマートではありません(1/3の10000桁は明らかに3ですが、これは10000回反復に達するまで続きます)。メモリ。

基本的にこれは2つの事実のために働く:

  • x / yのn桁目は10 x / 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のサイクル発見アルゴリズムと組み合わせることができます。 Martin Gardnerのコラムを参照して)このアプローチを近道するものを入手してください。

これが、このアプローチで解を計算するJavaScript関数です。

関数digit(x、y、n、returnstruct){関数kernel(x、y){return 10 *(x%y); }

var period = 0; var x1 = x; var x 2 = x; var i = 0; while(n> 0){n--;私  ; x 1 =カーネル(x 1、y)。 // x2 = kernel(x2、y);を一度繰り返します。 x 2 =カーネル(x 2、y)。 // 2回繰り返す

// 1倍と2倍の繰り返しが同じ状態になったか if(x 1 == x 2){期間= 1; n = n%期間。 i = 0。 //繰り返しのない部分でピリオドそのものではなく// //ピリオドの倍数が与えられた場合には、もう一度開始してください。 if(returnstruct)return {ピリオド:ピリオド、数字:回答、toString:function(){return 'ピリオド=' this.period '、数字=' this.digit; ;}};そうでなければ答えを返す。 }

そして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) = 0、桁= 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
関数ディジット(x、y、n1、n2、returnstruct){関数kernel(x、y){return 10 *(x%y); }

var period = 0; var x1 = x; var x 2 = x; var i = 0; var answer = ''; while(n2> = 0){//数字を表示する時間? if(n1 <= 0)answer = answer Math.floor(x1 / y);

n1  - 、n2--。私  ; x 1 =カーネル(x 1、y)。 // x2 = kernel(x2、y);を一度繰り返します。 x 2 =カーネル(x 2、y)。 // 2回繰り返す

// 1倍と2倍の繰り返しが同じ状態になったか if(x 1 == x 2){期間= 1; (n1>ピリオド){var jumpade = n1−(n1%ピリオド)である場合。 n1  -  =ジャンプヘッド、n2  -  =ジャンプヘッド。 i = 0。 //繰り返しのない部分がピリオドそのものではなく//ピリオドの倍数を//返す場合には、もう一度開始してください。 this.period '、digits =' this.digits; ;}};そうでなければ答えを返す。 }

私はあなたの答えの結果を含めました(Javascript#があふれていないと仮定して):

js> digit(1,7,1,7、true)期間= 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 = 20513882650385881630475914166090026658968726872786883636838377559799232373208220950057329190307649696 js> digit(122222,9965,100,116565)。

1


アドホックよくわかりません。 たぶんhttp://en.wikipedia.org/wiki/Continued_fraction[continued fraction]が役に立ちます。 私はそれについて少し考えるつもりです…​

更新

http://en.wikipedia.org/wiki/Fermat’s_little_theorem [Fermatの小さな定理]から、39が素数であるため、以下が成り立ちます。 ( `=`は一致を示す)

10^39 = 10 (39)

10は39と互いに素だからです。

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

10^38 - 1 = 0 (39)

[to be continued tomorow]

私は39が素数ではないことを認識するように段階的になっていました…​ ^^次の日に更新と答えを出して全体のアイデアを提示します。 39が素数ではないことに注目してくれてありがとう。

「a <b」と仮定期間の長さ「p」を持つ「a / b」に対する短い答え
…​

  • `k =(10 ^ p-1)/ b`を計算し、それが整数であることを確認します。
    「a / b」には「p」のピリオドがありません

  • `c = k * a`を計算する

  • `c`を10進数表現に変換し、ゼロで左詰めします
    全長が「p」

  • 小数点の後のi番目の桁は、(i mod p)番目の桁
    パディングされた10進表現(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

0


タイトルとURLをコピーしました