Ottenere una cifra specifica da un'espansione del rapporto in qualsiasi base (ennesima cifra di x / y)
https://stackoverflow.com/questions/804934
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Esiste un algoritmo in grado di calcolare le cifre di un rapporto decimale ripetuto senza iniziare dall'inizio?
Sto cercando una soluzione che non usi numeri interi di dimensioni arbitrarie, dal momento che dovrebbe funzionare in casi in cui l'espansione decimale potrebbe essere arbitrariamente lunga.
Ad esempio, 33/59 si espande in un decimale ripetuto con 58 cifre. Se volessi verificarlo, come potrei calcolare le cifre a partire dal 58 ° posto?
Modificato - con il rapporto 2124679/2147483647, come ottenere le cento cifre tra il 2147484600 e il 2147484700esimo posto.
Soluzione
OK, il 3 ° tentativo è un incanto :)
Non posso credere di essermi dimenticato dell'espiazione modulare.
Quindi per rubare / riassumere dalla mia seconda risposta, l'ennesima cifra di x / y è la prima cifra di (10 n-1 x mod y) / y = floor (10 * (10 n-1 x mod y) / y) mod 10.
La parte che richiede sempre è la mod <10 n-1 , ma possiamo farlo con esponenziazione modulare veloce (O (log n)). Con questo in atto, non vale la pena provare a fare l'algoritmo di ricerca del ciclo.
Tuttavia, hai bisogno dell'abilità di fare (a * b mod y) dove aeb sono numeri che possono essere grandi quanto y. (se y richiede 32 bit, allora devi fare moltiplicare 32x32 e quindi modulo 32-bit% 64-bit, oppure hai bisogno di un algoritmo che aggiri questa limitazione. Vedi il mio elenco che segue, dal momento che ho incontrato questa limitazione con Javascript. )
Quindi ecco una nuova versione.
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;
}
(Noterai che le strutture di abmody() e l'esponenziazione modulare sono le stesse; entrambe sono basate su moltiplicazione contadina russa .)
E risultati:
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
Altri suggerimenti
modifica: (Lascio qui i post per i posteri. Ma per favore non lo votano più: potrebbe essere teoricamente utile ma non è davvero pratico. I ha pubblicato un'altra risposta che è molto più utile dal punto di vista pratico, non richiede alcun factoring e non richiede l'uso di bignum.)
@Daniel Bruckner ha l'approccio giusto, credo. (con alcuni colpi di scena aggiuntivi richiesti)
Forse esiste un metodo più semplice, ma funzionerà sempre quanto segue:
Usiamo gli esempi q = x / y = 33/57820 e 44/65 oltre a 33/59, per ragioni che potrebbero diventare chiare a breve.
Passaggio 1: fattore il denominatore (in particolare fattore 2 e 5)
Scrivi q = x / y = x / (2 a 2 5 a 5 z). I fattori di 2 e 5 nel denominatore non causano ripetuti decimali. Quindi il fattore z rimanente è coprime a 10. In effetti, il passaggio successivo richiede il factoring z, quindi potresti anche considerare il tutto.
Calcola un 10 = max (un 2 , un 5 ) che è l'esponente più piccolo di 10 che è un multiplo dei fattori di 2 e 5 in y.
Nel nostro esempio 57820 = 2 * 2 * 5 * 7 * 7 * 59, quindi a 2 = 2, a 5 = 1, a 10 = 2, z = 7 * 7 * 59 = 2891.
Nel nostro esempio 33/59, 59 è un numero primo e non contiene fattori di 2 o 5, quindi un 2 = a 5 = a 10 = 0.
Nel nostro esempio 44/65, 65 = 5 * 13 e un 2 = 0, un 5 = a 10 = 1 .
Solo per riferimento ho trovato un buon calcolatore di factoring online qui . (fa anche il totients che è importante per il passaggio successivo)
Passaggio 2: utilizzare Teorema di Eulero o Teorema di Carmichael .
Ciò che vogliamo è un numero n tale che 10 n - 1 è divisibile per z, o in altre parole, 10 n & # 8801; 1 mod z. La funzione di Eulero & # 966; (z) e la funzione di Carmichael & # 955; (z) ti daranno entrambi valori validi per n, con & # 955; (z) ti darà il numero più piccolo e # 966; (z) essendo forse un po 'più facile da calcolare. Questo non è troppo difficile, significa solo factoring z e fare un po 'di matematica.
& # 966; (2891) = 7 * 6 * 58 = 2436
& # 955; (2891) = mcm (7 * 6, 58) = 1218
Ciò significa che 10 2436 & # 8801; 10 1218 & # 8801; 1 (mod 2891).
Per la frazione più semplice 33/59, & # 966; (59) = & # 955; (59) = 58, quindi 10 58 & # 8801; 1 (mod 59).
Per 44/65 = 44 / (5 * 13), & # 966; (13) = & # 955; (13) = 12.
E allora? Bene, il periodo del decimale ripetuto deve dividere sia & # 966; (z) che & # 955; (z), in modo che ti diano effettivamente limiti al periodo del decimale ripetuto.
Passaggio 3: maggiore riduzione del numero
Usiamo n = & # 955; (z). Se sottraiamo Q '= 10 a 10 x / y da Q' '= 10 (a 10 + n) x / y, otteniamo:
m = 10 a 10 (10 n - 1) x / y
che è un numero intero perché 10 a 10 è un multiplo dei fattori di 2 e 5 di ye 10 n -1 è un multiplo dei restanti fattori di y.
Quello che abbiamo fatto qui è spostare a sinistra il numero originale q di un 10 posti per ottenere Q ', e spostare a sinistra q di un 10 + n posti per ottenere Q '', che sta ripetendo i decimali, ma la differenza tra loro è un numero intero che possiamo calcolare.
Quindi possiamo riscrivere x / y come m / 10 a 10 / (10 n - 1).
Considera l'esempio q = 44/65 = 44 / (5 * 13)
a 10 = 1 e & # 955; (13) = 12, quindi Q '= 10 1 q e Q' '= 10 12 + 1 q.
m = Q '' - Q '= (10 12 - 1) * 10 1 * (44/65) = 153846153846 * 44 = 6769230769224
so q = 6769230769224/10 / (10 12 - 1).
Le altre frazioni 33/57820 e 33/59 portano a frazioni maggiori.
Passaggio 4: trova le parti decimali non ripetute e ripetute.
Nota che per k tra 1 e 9, k / 9 = 0.kkkkkkkkkkkkk ...
Allo stesso modo si noti che un numero di 2 cifre kl tra 1 e 99, k / 99 = 0.klklklklklkl ...
Questo generalizza: per i modelli di cifre k abc ... ij, questo numero abc ... ij / (10 k -1) = 0.abc ... ijabc ... ijabc ... ij ...
Se segui il modello, vedrai che quello che dobbiamo fare è prendere questo intero (potenzialmente) enorme m che abbiamo ottenuto nel passaggio precedente e scriverlo come m = s * (10 n -1) + r, dove 1 & # 8804; r < 10 n -1.
Questo porta alla risposta finale:
- s è la parte non ripetitiva
- r è la parte ripetuta (zero-padding a sinistra, se necessario, per assicurarsi che sia n cifre)
- con un 10 = 0, il punto decimale è compreso tra parte non ripetitiva e ripetitiva; Se a 10 > 0 quindi si trova un 10 posiziona a sinistra di la giunzione tra s e r.
Per 44/65, otteniamo 6769230769224 = 6 * (10 12 -1) + 769230769230
s = 6, r = 769230769230 e 44/65 = 0.6769230769230 dove la sottolineatura indica la parte ripetuta.
Puoi ridurre i numeri trovando il valore più piccolo di n nel passaggio 2, iniziando con la funzione Carmichael & # 955; (z) e vedendo se uno dei suoi fattori porta a valori di n tali che 10 n & # 8801; 1 (mod z).
aggiornamento: per i curiosi, l'interpeter Python sembra essere il modo più semplice per calcolare con i bignum. (pow (x, y) calcola x y e // e% sono rispettivamente divisione intera e resto.) Ecco un esempio:
>>> 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
con l'operatore di stringa Python % sovraccarico utilizzabile per lo zero padding, per vedere l'intero set di cifre ripetute:
>>> "%01218d" % r
'0570736769283984780352819093739190591490833621584226911103424420615703908682116
91456243514354894500172950536146662054652369422345209270148737461086129367001037
70321687997232791421653407125562089242476651677620200622621930127983396748529920
44275337253545485991006572120373573158076790038049117952265652023521272915946039
43272224143894846074022829470771359391214112763749567623659633344863369076444136
97682462815634728467658249740574195780006918021445866482186094776893808370805949
49844344517468004150812867519889311656866136285022483569699066067104808024904877
20511933586994119681771013490141819439640262884814942926323071601521964718090626
08094085091663784157730888965755793842960913178830854375648564510549982704946385
33379453476305776547907298512625389138706329989622967831200276720857834659287443
79107575233483223797993773780698720166032514700795572466274645451400899342787962
64268419232099619508820477343479764787270840539605672777585610515392597717052922
86406087858872362504323763403666551366309235558630231753718436527153234175025942
58042199930819785541335178139052231061916291940505015565548253199584918713248011
06883431338637149775164303009339328951919750951227948806641300588031822898650985
8180560359737115185'
Come tecnica generale, le frazioni razionali hanno una parte non ripetitiva seguita da una parte ripetitiva, come questa:
nnn.xxxxxxxxrrrrrr
xxxxxxxx è la parte non ripetitiva e rrrrrr è la parte ripetuta.
- Determina la lunghezza della parte non ripetitiva.
- Se la cifra in questione si trova nella parte non ripetitiva, calcola direttamente utilizzando la divisione.
- Se la cifra in questione si trova nella parte ripetuta, calcola la sua posizione all'interno della sequenza ripetitiva (ora conosci le lunghezze di tutto) e scegli la cifra corretta.
Quanto sopra è uno schema approssimativo e avrebbe bisogno di più precisione per essere implementato in un algoritmo reale, ma dovrebbe iniziare.
AHA! caffiend: il tuo commento all'altra mia (più lunga) risposta (in particolare " resti duplicati ") mi porta a una soluzione molto semplice che è O (n) dove n = la somma delle lunghezze del non ripetitivo + parti ripetute e richiede solo matematica intera con numeri compresi tra 0 e 10 * y dove y è il denominatore.
Ecco una funzione Javascript per ottenere l'ennesima cifra a destra del punto decimale per il numero razionale x / y:
function digit(x,y,n)
{
if (n == 0)
return Math.floor(x/y)%10;
return digit(10*(x%y),y,n-1);
}
È ricorsivo piuttosto che iterativo e non è abbastanza intelligente da rilevare i cicli (la 10000 ° cifra di 1/3 è ovviamente 3, ma questo continua fino a raggiungere la 10000esima iterazione), ma funziona almeno fino allo stack esaurisce la memoria.
Fondamentalmente funziona a causa di due fatti:
- l'ennesima cifra di x / y è la (n-1) cifra di 10x / y (esempio: la sesta cifra di 1/7 è la quinta cifra di 10/7 è la quarta cifra di 100/7 ecc. .)
- l'ennesima cifra di x / y è l'ennesima cifra di (x% y) / y (esempio: la 5a cifra di 10/7 è anche la 5a cifra di 3/7)
Possiamo modificarlo per essere una routine iterativa e combinarlo con Ciclo di Floyd -finding algoritmo (che ho imparato come metodo " rho " da una colonna di Martin Gardner) per ottenere qualcosa che scorcia questo approccio.
Ecco una funzione javascript che calcola una soluzione con questo approccio:
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 un esempio di esecuzione dell'ennesima cifra di 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
Stessa cosa per 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 (parte lunga non ripetitiva):
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
Ecco un'altra funzione che trova un tratto di cifre:
// 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;
}
Ho incluso i risultati per la tua risposta (supponendo che Javascript # non sia traboccato):
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 Non ho una buona idea. Forse le frazioni continue possono essere d'aiuto. Ci penserò un po '...
Aggiorna
Da il piccolo teorema di Fermat e poiché 39 è primo vale quanto segue. ( = indica congruenza)
10^39 = 10 (39)
Perché 10 è coprime a 39.
10^(39 - 1) = 1 (39)
10^38 - 1 = 0 (39)
[to be continued tomorow]
Sono stato a più livelli per riconoscere che 39 non è il primo ... ^^ Ho intenzione di aggiornare e la risposta nei prossimi giorni e presentare l'intera idea. Grazie per aver notato che 39 non è un numero primo.
La risposta breve per a/b con a < b e una durata presunta del periodo p ...
- calcola
k = (10^p - 1) / be verifica che sia un numero intero, altrimentic = k * anon ha un periodo dic - calcola <=>
- converti <=> nella sua rappresentazione decimale e lascialo con zeri per una lunghezza totale di <=>
- l'i-esima cifra dopo il punto decimale è la (i mod p) -esima cifra della rappresentazione decimale con pad (i = 0 è la prima cifra dopo il punto decimale - siamo sviluppatori)
Esempio
a = 3
b = 7
p = 6
k = (10^6 - 1) / 7
= 142,857
c = 142,857 * 3
= 428,571
L'imbottitura non è richiesta e concludiamo.
3 ______
- = 0.428571
7
