最初から開始せずに繰り返し小数比率の桁数を計算できるアルゴリズムはありますか?
これは、小数展開が任意に長くなる可能性がある場合に機能するはずなので、任意のサイズの整数を使用しないソリューションを探しています。
たとえば、33/59 は 58 桁の繰り返し小数に展開されます。それを確認したい場合、58 位から始まる数字を計算するにはどうすればよいでしょうか。
編集済み - 2124679 / 2147483647 の比率で、2147484600 番目から 2147484700 番目までの 100 桁を取得する方法。
OK、3回目の試行は魅力です:)
べき乗剰余を忘れたなんて信じられません。
したがって、私の2番目の回答から盗む/要約すると、x / yのn番目の桁は（10 n-1 x mod y）/ y = floor（10 *（10 n-1 x mod y）/ y）の1番目の桁です。 mod10。
常にかかる部分は10n - 1mod 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
編集:(後世のためにここに投稿を残します。しかし、もう賛成しないでください。理論的には役立つかもしれませんが、実際には実用的ではありません。実用的な観点からはるかに役立つ別の回答を投稿しました。因数分解を必要とせず、bignumを使用する必要もありません。）
@DanielBrucknerは正しいアプローチをしていると思います。（いくつかの追加のひねりが必要です）
もっと簡単な方法があるかもしれませんが、以下は常に機能します。
すぐに明らかになるかもしれない理由のために、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を因数分解する必要があるため、全体を因数分解することもできます。
10 = max（a 2、a 5 ）を計算します。これは、yの2と5の因数の倍数である10の最小の指数です。
この例では、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です。
参考までに、ここで優れたオンライン因数分解計算機を見つけました。（次のステップで重要なtotientsも行います）
ステップ2：オイラーの定理またはカーマイケルの定理を使用します。
必要なのは、10 n -1がzで割り切れるような数n 、つまり10n≡1modzです。オイラーの関数φ（z）とカーマイケルの関数λ（z）はどちらもnの有効な値を示し、λ（z）は小さい数を示し、φ（z）はおそらく計算が少し簡単です。これはそれほど難しいことではありません。zを因数分解して少し計算することを意味します。
φ（2891）= 7 * 6 * 58 = 2436
λ（2891）= lcm（7 * 6、58）= 1218
これは、102436≡101218≡1（mod 2891）を意味します。
より単純な分数33/59の場合、φ（59）=λ（59）= 58であるため、1058≡1 （ mod 59）です。
44/65 = 44 /（5 * 13）の場合、φ（13）=λ（13）=12。
だから何？さて、循環小数の周期はφ（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を10桁左にシフトしてQ'を取得し、qを10 +n桁左にシフトしてQ''を取得することです。これは、循環小数ですが、両者の違いは次のとおりです。計算できる整数。
次に、x/yをm/10 a 10 /（10 n -1）と書き直すことができます。
例を考えてみましょうq=44/65 = 44 /（5 * 13）
a 10 = 1、およびλ（13）= 12であるため、Q'= 101qおよびQ''=10 12 + 1q。
m = Q''-Q'=（10 12-1 ） * 10 1 *（44/65）= 153846153846 * 44 = 6769230769224
したがって、q = 6769230769224/10 /（10 12-1 ）。
他の分数33/57820および33/59は、より大きな分数につながります。
ステップ4：非循環小数部と循環小数部を見つけます。
kが1から9の間の場合、k / 9 = 0.kkkkkkkkkkkkk .. ..
同様に、1から99までの2桁の数字kl、k / 99 = 0.klklklklklklkl .. ..
これは一般化されます：k桁のパターンabc ... ijの場合、この数abc ... ij /（10 k -1）= 0.abc ... ijabc ... ijabc ... ij .. ..
このパターンに従うと、前の手順で取得したこの（潜在的に）巨大な整数mを取得し、m = s *（10 n -1）+rと書く必要があることがわかります。ここで、1≤r<10n - 1です。
これが最終的な答えにつながります。
44/65の場合、6769230769224 = 6 *（10 12 -1）+769230769230になります。
s = 6、r = 769230769230、および44/65 = 0.6769230769230ここで、下線は繰り返し部分を示します。
ステップ2でnの最小値を見つけ、カーマイケル関数λ（z）から始めて、その因子のいずれかが10n≡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'
AHA！caffiend：他の（より長い）答え（具体的には「重複する剰余」）に対するあなたのコメントは、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つの事実のために機能します。
これを反復ルーチンになるように調整し、フロイドの循環検出アルゴリズム（Martin Gardnerのコラムから「rho」メソッドとして学習した）と組み合わせて、このアプローチを短縮するものを取得できます。
このアプローチでソリューションを計算する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
一般的な手法として、有理分数には次のように非反復部分と反復部分があります。
nnn.xxxxxxxxrrrrrr
xxxxxxxxは非反復部分で、rrrrrrは反復部分です。
上記は大まかな概要であり、実際のアルゴリズムに実装するにはさらに精度が必要ですが、開始する必要があります。
アドホック私には良い考えがありません。連分数が役に立つかもしれません。ちょっと考えてみます…。
アップデート
フェルマーの小定理と 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とa < b想定される期間の長さp...
k = (10^p - 1) / bそれが整数であることを計算して検証しa/bます。pc = k * acし、全長がp例
a = 3
b = 7
p = 6
k = (10^6 - 1) / 7
= 142,857
c = 142,857 * 3
= 428,571
パディングは必要ありません。
3 ______
- = 0.428571
7