Conseguir um dígito específico a partir de uma proporção de expansão em qualquer base (dígitos de ordem n de x / y)
https://stackoverflow.com/questions/804934
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Existe um algoritmo que pode calcular os dígitos de uma relação repetindo-decimal sem começar no início?
Eu estou procurando uma solução que não usa números inteiros arbitrariamente porte, uma vez que este deve funcionar para casos em que a expansão decimal pode ser arbitrariamente longo.
Por exemplo, 33/59 expande para uma dízima periódica com 58 dígitos. Se eu quisesse verificar se, como eu poderia calcular os dígitos começando no local 58?
Editado - com a relação de 2124679/2147483647, como obter os cem dígitos no 2147484600 através 2147484700th lugares.
Solução
OK, 3ª prova é um encanto:)
Eu não posso acreditar que eu esqueci exponenciação modular.
Assim, para roubar / resumir minhas 2nd resposta, o dígito enésimo de x / y é o 1º dígito (10 n-1 x mod y) / y = andar (10 * (10 n-1 x mod y) / y) mod 10.
A parte que leva o tempo todo é a n-1 mod y 10 mas podemos fazer isso com rápido (O (log n)) exponenciação modular. Com isso no lugar, não vale a pena tentar fazer o algoritmo de encontrar ciclo.
No entanto, você precisa ter a capacidade de fazer (a * b y mod) onde a e b são números que podem ser tão grandes como y. (Se y requer 32 bits, então você precisa fazer 32x32 multiplicar e, em seguida,% 32-bit módulo de 64 bits, ou você precisa de um algoritmo que contorna essa limitação. Ver a minha lista que se segue, desde que eu corri para esta limitação com Javascript. )
Então aqui está uma nova versão.
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;
}
(Você vai notar que as estruturas de abmody() ea exponenciação modular são os mesmos; ambos são baseados em Russian camponês multiplicação.)
E os resultados:
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
Outras dicas
Editar: (estou deixando post aqui para a posteridade Mas por favor não upvote-lo mais:.. Pode ser teoricamente útil, mas não é realmente prático I colocaram outra resposta que é muito mais útil do ponto de vista prático, não requer qualquer factoring, e não requer o uso de bignums.)
@ Daniel Bruckner tem a abordagem certa, eu acho. (Com algumas torções adicionais necessários)
Talvez haja um método mais simples, mas a seguir será sempre funciona:
Vamos utilizar os exemplos q = x / y = 33/57820 e 44/65, além de 33/59, por razões que podem tornar-se claro em breve.
Escrever q = x / y = x / (2 2 5 5 z). Fatores de 2 e 5 no denominador não causam decimais repetidas. Assim, o fator restante z é coprime a 10. Na verdade, o próximo passo requer factoring z, então você pode muito bem levar a coisa toda.
Calcular uma 10 = max ( 2 , 5 ) que é o menor expoente de 10 que é um múltiplo dos factores de 2 e 5 em y.
No nosso exemplo 57820 = 2 * 2 * 5 * 7 * 7 * 59, de modo que uma 2 = 2, um 5 = 1, um 10 = 2, z = 7 * 7 * 59 = 2891.
No nosso exemplo, 33/59, 59 é um número primo e não contém factores de 2 ou 5, de modo que uma 2 = 5 = 10 = 0.
No nosso exemplo, 44/65, 65 = 5 * 13, e uma 2 = 0, um 5 = 10 = 1 .
Apenas para referência eu achei uma boa factoring on-line calculadora aqui . (Mesmo faz totients que é importante para o próximo passo)
Passo 2: Use de Euler Teorema ou o Carmichael Teorema .
O que nós queremos é um número n tal que 10 n - 1 é divisível por z, ou em outras palavras, 10 n = 1 mod z. f de Euler função (z) e ? função de Carmichael (z) será tanto dar-lhe valores válidos para n, com ? (z), dando-lhe o menor número e f (z) sendo talvez um pouco mais fácil de calcular. Isso não é muito difícil, isso significa apenas factoring z e fazer um pouco de matemática.
f (2891) = 7 * 6 * 58 = 2436
? (2891) = lcm (7 * 6, 58) = 1.218
Isto significa que 10 2436 = 10 1218 = 1 (mod 2891).
Para a fracção mais simples 33/59, f (59) = ? (59) = 58, de modo 10 58 = 1 (mod 59).
Para 44/65 = 44 / (5 * 13), f (13) = ? (13) = 12.
Então, o que? Bem, o período do decimal repetindo deve dividir tanto f (z) e ? (z), para que eles efetivamente dar-lhe limites superiores no período da dízima periódica.
Passo 3: Mais trituração de número
Vamos uso n = ? (z). Se subtrair Q'= 10 10 x / y de Q ''= 10 ( 10 + n) x / y, obtemos:
m = 10 10 (10 n - 1) x / y
O que fizemos aqui é deslocamento à esquerda do número original q por um 10 lugares para obter Q', e mudar q esquerda por um 10 + n lugares para obter Q '', que são dízima periódica, mas a diferença entre eles é um inteiro podemos calcular.
Em seguida, pode reescrever x / y, como m / 10 10 / (10 n - 1).
Considere o exemplo q = 44/65 = 44 / (5 * 13)
a 10 = 1, e ? (13) = 12, então Q'= 10 1 Q e Q ''= 10 12 + 1 q.
m = Q '' - Q'= (10 12 - 1) * 10 1 * (44/65) =153846153846 * 44 = 6769230769224
= 6769230769224 por isso q / 10 / (10 12 - 1).
As outras fracções 33/57820 e 33/59 chumbo para fracções maiores.
Passo 4:. Encontre os não repetidos e repetidos partes decimais
Observe que para k entre 1 e 9, k / 9 = 0.kkkkkkkkkkkkk ...
De modo semelhante nota que um número kl dois dígitos entre 1 e 99, k / 99 = 0.klklklklklkl ...
A: generaliza para padrões k dígitos ABC ... ij, este número ABC ... ij / (10 k -1) = 0.abc ... ... ijabc ijabc ... ij ...
Se você seguir o padrão, você verá que o que temos a fazer é tomar este (potencialmente) enorme número inteiro m chegamos na etapa anterior, e escrevê-lo como m = s * (10 n -1) + r, onde 1 = r <10 n -1.
Isso leva à resposta final:
- S é a parte não-repetição
- r é a parte repetindo (zero-preenchido à esquerda, se necessário, para garantir que ele é n dígitos)
- com 10 = 0, o ponto decimal é entre o não repetidos e repetindo parte; E se um 10 > 0, então ele está localizado um 10 lugares à esquerda do a junção entre s e r.
Para 44/65, obtemos 6769230769224 = 6 * (10 12 -1) + 769230769230
s = 6, r = 769230769230, e 44/65 = ,6769230769230 onde o sublinhado aqui designa a parte repetida.
É possível tornar os números menor, encontrando o menor valor de n no passo 2, iniciando-se com a função ? Carmichael (z) e ver se qualquer um dos seus factores conduzem a valores de n tal que 10 n = 1 (mod z).
atualização: Para os curiosos, o interpeter Python parece ser a maneira mais fácil de calcular com bignums. (POW (x, y) calcula x y , e //% e são inteiro divisão e restante, respectivamente.) Segue-se um exemplo:
>>> 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
com o Python % corda utilizável operador sobrecarregado para zero preenchimento, para ver o conjunto completo de dígitos repetidos:
>>> "%01218d" % r
'0570736769283984780352819093739190591490833621584226911103424420615703908682116
91456243514354894500172950536146662054652369422345209270148737461086129367001037
70321687997232791421653407125562089242476651677620200622621930127983396748529920
44275337253545485991006572120373573158076790038049117952265652023521272915946039
43272224143894846074022829470771359391214112763749567623659633344863369076444136
97682462815634728467658249740574195780006918021445866482186094776893808370805949
49844344517468004150812867519889311656866136285022483569699066067104808024904877
20511933586994119681771013490141819439640262884814942926323071601521964718090626
08094085091663784157730888965755793842960913178830854375648564510549982704946385
33379453476305776547907298512625389138706329989622967831200276720857834659287443
79107575233483223797993773780698720166032514700795572466274645451400899342787962
64268419232099619508820477343479764787270840539605672777585610515392597717052922
86406087858872362504323763403666551366309235558630231753718436527153234175025942
58042199930819785541335178139052231061916291940505015565548253199584918713248011
06883431338637149775164303009339328951919750951227948806641300588031822898650985
8180560359737115185'
Como uma técnica geral, as fracções racionais tem uma parte não-repetição seguida por uma parte de repetição, como este:
nnn.xxxxxxxxrrrrrr
xxxxxxxx é a parte não repetidos e rrrrrr é a parte repetindo.
- Determine o comprimento da parte não repetidos.
- Se o dígito em questão é na parte não repetidos, em seguida, calcular-lo diretamente usando divisão.
- Se o dígito em questão é na parte repetindo, calcular a sua posição dentro da seqüência repetindo (você já sabe os comprimentos de tudo), e escolher o dígito correto.
A descrição acima é um esboço e precisaria de mais precisão para implementar em um algoritmo real, mas deve começar.
AHA! Caffiend: o seu comentário para o meu outro (mais) resposta (especificamente "restos duplicados") leva-me a uma solução muito simples que é O (n), onde n = a soma dos comprimentos dos não repetidos + partes que se repetem, e requer apenas inteiro matemática com números entre 0 e 10 * y, onde y é o denominador.
Aqui está uma função JavaScript para obter o dígito enésimo à direita do ponto decimal para o número racional x / y:
function digit(x,y,n)
{
if (n == 0)
return Math.floor(x/y)%10;
return digit(10*(x%y),y,n-1);
}
É recursiva em vez de iterativo, e não é inteligente o suficiente para detectar ciclos (o dígito 10000 de 1/3 é, obviamente, 3, mas este mantém em curso até que ele atinja a iteração 10000), mas funciona, pelo menos até que a pilha ficar sem memória.
Basicamente, este obras por causa de dois fatos:
- o dígito enésimo de x / y é o (n-1) ésimo dígito de 10x / y (exemplo: o 6 dígitos de 1/7 é o quinto dígito de 07/10 é o quarto dígitos de 100/7 etc. .)
- o dígito enésimo de x / y é o dígito enésimo de (x% y) / y (exemplo: o quinto dígito de 07/10 também é o quinto dígito de 3/7)
Podemos ajustar isso para ser uma rotina iterativo e combiná-lo com ciclo de Floyd -finding algoritmo (que eu aprendi como o método "rho" a partir de uma coluna de Martin Gardner) para obter algo que atalhos esta abordagem.
Aqui está uma função JavaScript que calcula uma solução com esta abordagem:
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;
}
E um exemplo de execução do dígito enésimo de 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
A mesma coisa para a 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
E 122222/990000 (long não repetidos parte):
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
Aqui está outra função que encontra um trecho de dígitos:
// 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;
}
Eu incluí os resultados para a sua resposta (assumindo que o JavaScript # 's não overflow):
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
Ad hoc Eu não tenho nenhuma idéia boa. Talvez continuou frações pode ajudar. Vou pensar um pouco sobre isso ...
Atualizar
De pouco de Fermat teorema e porque 39 é primo a seguinte detém. ( = indica congruência)
10^39 = 10 (39)
Porque 10 é coprime a 39.
10^(39 - 1) = 1 (39)
10^38 - 1 = 0 (39)
[to be continued tomorow]
Eu era hierárquico reconhecer que 39 não é primo ... ^^ vou atualizar e a resposta nos próximos dias e apresentar toda a idéia. Obrigado por notar que 39 não é primo.
A resposta curta para a/b com a < b e um comprimento período considerado p ...
-
k = (10^p - 1) / bcalcular e verificar que ele é um inteiro, senãoa/bnão tem um período dep - calcular
c = k * a - converso
cà sua represenation decimal e pad esquerda com zeros para um comprimento total dep - o i-th dígitos depois do ponto decimal é a (i mod p) dígitos -ésimo da representação decimal paded (i = 0 é o primeiro dígito depois do ponto decimal - somos desenvolvedores)
Exemplo
a = 3
b = 7
p = 6
k = (10^6 - 1) / 7
= 142,857
c = 142,857 * 3
= 428,571
estofamento não é necessário e nós concluímos.
3 ______
- = 0.428571
7
