得到一个特定的数字从一个比膨胀在任何基(n位的x/y)
https://stackoverflow.com/questions/804934
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
有一种算法，可以计算的数字的重复-小数比例没有开始在开始?
我在寻找一个解决方案，不使用任意的中小型整数，因为本应该工作的情况的十进制的扩展可以任意长。
例如，33/59扩大的重复的小数与58个数字。如果我想确认，我怎么可以计算的数字开始在第58地方吗？
编辑-比2124679/2147483647，如何得到百位数2147484600th通过2147484700th的地方。
解决方案
好的，第3次尝试是一个魅力：）
我无法相信我忘记了模幂运算。
所以从我的第二个答案中窃取/总结，x / y的第n位是（10 n-1 x mod y）/ y = floor（10 *（10）的第1位数 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
其他提示
编辑： (我离开后这里为子孙后代。但 请 不要投票，它了：它可能是理论上是有益的，但它不是真实际的。我已经发布另一个答案是有用得多从实际的角度来看，并不需要任何的保理业务，并不需要使用bignums.)
@丹尼尔布鲁克纳有权的方法，我认为。(与一些额外的曲折需要的)
也许有一个简单的方法，但下面将始终是工作：
让我们使用的示例q=x/y=33/57820和44/65外33/59，原因可能成为明确的联系。
步骤1：因的分母 (具体的因素出2和5)
写q=x/y=x/(2一个25一个5z)。因2和5中的分母不会导致重复小数。因此剩下的因素z是互质至10。事实上，下一步需要保z，你可以的因素的整个事情。
计算一个10 =max(a2, ，5)是最小的指数的10倍的因素2和5中。
在我们的例子57820 = 2 * 2 * 5 * 7 * 7 * 59, 所以2 =25 =1,10 =2,z=7 * 7 * 59 =2891.
在我们的例子33/59，59是总理，不包含任何因素的2个或5，所以2 =一个5 =一个10 = 0.
在我们的例子44/65,65=5*13和一个2 =0，5 =一个10 = 1.
仅供参考，我发现了一个良好的保理业务在线计算器 在这里，.(甚至并totients这是重要的下一步骤)
我们想要的是一个数字n使10n -1是可分割的，z，或者换句话说，10n ≡1mod z。欧拉的功能φ(z)和卡迈克尔的功能λ(z)将两个给你的有效值n，与λ(z)给你的小号和φ(z)正在或许更容易一些计算。这是不是太难了，它仅仅意味着保z和做一个小小的数学。
φ(2891) = 7 * 6 * 58 = 2436
λ(2891)=液晶模(7*6,58)=1218
这意味着102436 ≡ 101218 ≡1(mod2891).
简单的分33/59，φ(59)=λ(59)=58，使1058 ≡1(mod59).
对于44/65 = 44/(5*13), φ(13)=λ(13)=12.
所以什么？ 好了，该时期的重复的小数必须把两φ(z)和λ(z)，因此它们有效地给你的上限在期间的重复的小数。
步骤3：更多的数字运算的
让我们使用n=λ(z)。如果我们减去Q'=10一个10x/y Q"=10(a10 +n)x/y,我们会得到：
m=10一个10(10n -1)x/y
它是一个整数 因为10一个10 是一种多因素的2和5y和10n-1是多余的因素。
我们在这里所做的是转移离开的原始数q通过一个10 地方得到Q'，左移q通过一个10 +n地方得到Q"，这是重复的小数，但它们之间的区别是一个整数我们就可以计算。
然后我们可以重写x/y m/10一个10 / (10n - 1).
考虑例q= 44/65 = 44/(5*13)
一个10 =1和λ(13)=12，所以Q'=101q，Q"=1012+1q.
m=Q"-Q'=(1012 - 1) * 101 * (44/65) = 153846153846*44 = 6769230769224
因此q=6769230769224/10/(1012 - 1).
其他分33/57820和33/59导致大部分。
步骤4：找到非重复和重复的小数部分。
注意到对于k1和9之间、k/9=0.kkkkkkkkkkkkk...
同样注意到，一个2位数字吉隆坡之间1和99k/99=0.klklklklklkl...
这概括:k-数字模式的abc...ij，这些abc...ij/(10k-1)=0.abc...ijabc...ijabc...j...
如果你按照模式，你会看到什么我们要做的就是采取这种(潜在的)巨大的整数米，我们得到了在先前的步骤，并把它写作m=s*(10n-1)+r,其中1≤r < 10n-1.
这就导致最终的答案:
- s为非重复一部分
- r是重复的一部分(zero-padded左如果必要的，以确保它是正数字)
- 与10 = 0时，小数点之间 非重复和重复的部分；如果 一个10 >0然后它位于 一个10 地方的左边 之间的结s和r.
为44/65，我们得到6769230769224=6*(1012-1) + 769230769230
s=6、r=769230769230，并44/65=0.6769230769230这里强调，这里指明的重复的一部分。
你可以让数量小的通过找到最小值n中的步骤2，通过开始与卡迈克尔的功能λ(z)和看到，如果其任何因素导致价值观的n使10n ≡1(mod z)。
更新： 出于好奇，Python interpeter似乎是最简单的方法来计算与bignums.(pow(x,y)计算xy, 和//和％是整数分与其余部分，分别。) 这里有一个例子：
>>> 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
与所载的蟒蛇 % 串操作人员可使用零填充，看到一套完整的反复的数字：
>>> "%01218d" % r
'0570736769283984780352819093739190591490833621584226911103424420615703908682116
91456243514354894500172950536146662054652369422345209270148737461086129367001037
70321687997232791421653407125562089242476651677620200622621930127983396748529920
44275337253545485991006572120373573158076790038049117952265652023521272915946039
43272224143894846074022829470771359391214112763749567623659633344863369076444136
97682462815634728467658249740574195780006918021445866482186094776893808370805949
49844344517468004150812867519889311656866136285022483569699066067104808024904877
20511933586994119681771013490141819439640262884814942926323071601521964718090626
08094085091663784157730888965755793842960913178830854375648564510549982704946385
33379453476305776547907298512625389138706329989622967831200276720857834659287443
79107575233483223797993773780698720166032514700795572466274645451400899342787962
64268419232099619508820477343479764787270840539605672777585610515392597717052922
86406087858872362504323763403666551366309235558630231753718436527153234175025942
58042199930819785541335178139052231061916291940505015565548253199584918713248011
06883431338637149775164303009339328951919750951227948806641300588031822898650985
8180560359737115185'
作为一般技术，有理分数具有非重复部分，后跟重复部分，如下所示：
nnn.xxxxxxxxrrrrrr
xxxxxxxx是非重复部分，rrrrrr是重复部分。
- 确定非重复部分的长度。
- 如果有问题的数字位于非重复部分，则使用除法直接计算。
- 如果有问题的数字位于重复部分，请计算其在重复序列中的位置（您现在知道所有部分的长度），并选出正确的数字。
以上是一个粗略的概述，在实际算法中需要更高的精度才能实现，但它应该让你开始。
啊哈！caffiend:你的评论给我其他的(长期)的答案(特别是"重复剩下的人")导致我到一个非常简单的解决方案，这是O(n)，其中n=的总长度的非重复的+重复部分，并且只需要整数学之间的数字，0到10*y其中y为分母。
这里有一个Javascript功能，以获得nth位的权利的小数点的合理数量的x/y：
function digit(x,y,n)
{
if (n == 0)
return Math.floor(x/y)%10;
return digit(10*(x%y),y,n-1);
}
这是递归的，而不是迭代，而是没有足够的智慧来检测周期(第10000条数字为1/3是很明显3，但这种保持下去，直到达到第10000条迭代)，但它的工作原理至少直到堆运行的存储器。
基本上这是因为，两个事实：
- 第n位的x/y(n-1)个数字的10倍/y(例如：6位数的1/7的第5位数的10月7日的第4位数的100/7等)。
- 第n位的x/y n位(x%y)/y(例如：第5位数的10月7日也是在第5位数为3/7)
我们可以调整这是一个迭代的例行程序，并结合 弗洛伊德的周期调查的算法 (这是我学到的作为"卢"的方法从一个马丁*加德纳列)获得的东西，快捷方式，这种方法。
这里有一个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;
}
和一个实例的运行nth位的1/700:
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#'s没有溢出):
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
特设我没有好主意。也许 继续分 可以提供帮助。我要想一下它...
更新
从 费马大小小的理论 因为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没有一段时间的p - 计算
c = k * a - 转换
c其小数represenation和左垫用零总长度p - 第i位小数点后是(i模p)第位的paded表示小数(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
