[Medium] C++ factorial

[em]

S? spunem c? un prieten v? spune c? a g?sit un algoritm minune care calculeaza factorial foarte repede ?i pentru numere foarte mari. (S? zicem pân? la 10.000.000).

V? d? doar un executabil (care preia inputurile dintr-un fi?ier ?i v? d? outputi în altu).

Voi cum a?i verifica dac? algoritmu lui este bun?

Posta?i ideile voastre aici.

P.S. Nu da?i paste la r?spunsuri de pe Google. Don't spoil the fun.

[nedo]

pai ... o metoda ar fi sa cauti un algoritm standard pentru acest lucru, si sa compari timpi de executie si calitatea raspunsurilor. Ps ar fi nevoie sa facem si o demonstratie ceva in c++ ? .... inca nu mi-am facut nici o clasa pentru numere mari...

[Patrunjel]

Faci pe hartie. Ori suntem hardcor ori nu suntem.

E posibil sa gasesti pe net tabele cu toate valorile factorialelor pana la x, iti faci un script care-ti trece prin executabilul de la tovarasul l33t toate valorile pana la X-u maxim din tabel, salvezi intr-un fisier, dupa aia e vorba de 10 minute de programare, sa-ti scrii ceva care iti compara datele din 2 fisiere diferite, dublu-click & wait.

Nustiu de ce am un filing ca n-o sa-ti incapa toate factorialele de la 1 la 10KK pe un hard casnic (nu animale de-alea de jdemii de tera). ACareva care le are cu matematica, ar fi fain de aproximat cam cate cifre ar avea 10KK!

Edited July 14, 2011 by Patrunjel

[em]

Nu ai internet.

[nedo]

pai si atunci noi cam ce anume ar trebui sa facem? Sa incercam sa facem un cod pentru a verifica ??

[Patrunjel]

Decompilam, ce pula mea?

Sau ii rapim mama si il amenintam ca daca nu ne zice cum a facut, ma-sa moare.

[Zamolxis666]

Reprezinti numerele sub forma de stringuri si definesti functii pentru adunarea, respectiv inmultirea lor, determinand apoi timpul de executie.

[l3asketballplayer]

Exista o varianta ceva mai rapida de inmultire a 2 numere mari care se bazeaza pe algoritmul lui Strassen de inmultire a doua matrici. Complexitatea e N^(Log2 (3))

[Patrunjel]

^^ Si cam cand se termina executia? Dupa cum ai spus tu, pentru 10! ai nevoie de 10 iterari, pentru 11 ai nevoie de 11, etc. Deci pentru 10KK treci prin acelasi ciclu de 10 milioane de ori. Si timpul prin care ti se parcurge o data ciclul e direct proportional cu n, cu cat n e mai mare, cu atat n! e mai mare, si ai mai multe cacaturi de verificat/inserat/sloboz. Deci dureaza oleaca cam mult.

Si oricum, n! > n^n, deci daca s-ar folosi char (1byte) ai avea nevoie de 10KK^10KK octeti. Cine pula mea are atata ram?Si asta e aproximata mult in lipsa. (ca idee, asa arata 20! 2432902008176640000).

*Am calculat cu pula, ai avea nevoie de 10KK+8 caractere, adica 10.000.008 octeti *

Totusi, ar fi interesant de vazut cum se calculeaza factoriale pentru numere de-astea super-mega-dublu mari.

Am gasit pe net asta .

am incercat sa calculez (mult aproximat, vroiam doar sa-mi fac o idee), si 10KK! arata cam asa : 7926,654*3678794,4096^10KK. Gojira.

Edited July 14, 2011 by Patrunjel

[tiodr]

Nustiu de ce am un filing ca n-o sa-ti incapa toate factorialele de la 1 la 10KK pe un hard casnic (nu animale de-alea de jdemii de tera)

daca nu ma insel nu incape nici 17 factorial, nici macar ca unsigned long int

[Patrunjel]

ei, da eu nu ziceam de tipuri de date standard, ma refeream la numere salvate ca sir de caractere.

[tiodr]

pei si cand ai calculat 10kk factorial nu crezi ca tine mult acel while ca sa pastreze restul impartiri la 10? pana si afisarea tine mult banuiesc

[l3asketballplayer]

10.000.000 are 66.000.000 cifre ceea ce incape destul de lejer intr-un vector de int(asta daca ai avea cifre pana la limita maxima de int dar tu ai doar 10 cifre).

@ patrunjelu, tiodr nu va mai bagati daca nu stiti despre ce vorbiti.

Tipul a intrebat cum se calc rapid factorial de 10.000.000 si eu i-am zis ca e un alg care inm 2 numere mari mai eficient decat O(N^2). Nu vad ce pb ai aici cu memoria. Tu fol doar 3 vectori

@ patrunjelu De ce nu fol si tu un limbaj mai civilizat? Nu cred ca ai crescut in gunoaie.

Edited July 14, 2011 by l3asketballplayer

[dranaxum]

O prima verificare este sa obtii outputuri pentru numere "mici": 10!,11!,12!,13!,etc. Faci interpolare. Daca algoritmul este corect, atunci cand vei creste putin n-ul functia ta nu ar putea face fata fiindca factorialul nu este o functie care se poate aproxima ca un polinom (fata de altele). Asta e un semn bun.

Acum ca ai trecut acest test, in input bagi cel mai mare numar acceptat de program (fie el n). Faci ciurul lui erastotene (exista implementari rapide) si obtii toate nr prime mai mici decat n. Pentru fiecare numar prim stii la ce putere ar trebui sa apara in rezultat (se poate calcula matematic). Deci, avand outputul (fie el y) calculezi (log in baza nr_prim din y) + 1, obtii puterea numarului prim si il compari cu rezultatul matematic.

[Patrunjel]

10.000.000 are 66.000.000

Fii bun si explica-mi si mie cum ai ajuns la 66milioane, macar asa, sa nu mor in intuneric. (e destul de ne-obscen?)

7926,654*3678794,4096^10KK e are mai mult decat 66KK caractere oricand, la orice ora. (factorialele mare se pot aproxima, am postat un link mai sus pe undeva)

Edited July 14, 2011 by Patrunjel

[l3asketballplayer]

wolframalpha

Eu vorbeam de 10.000.000 !

Edited July 14, 2011 by l3asketballplayer

[cmiN]

1. Inmultire de numar mare cu un uint32 (iti ajung 66 mb pentru vector) vezi aici.

2. Pastrarea rezultatului intr-un uint64 (unsigned long long) si la fiecare inmultire sa se faca mod 2^39 (valoarea asta ca in caz de se face * 10kk sa nu sara din 64 biti) si apoi sa se faca modulo si din rezultatul din output (tot numere mari dar ai o complexitate realizabila in timp uman ).

3. Ar mai fi o idee sa numeri ultimile zerouri din numar pentru fiecare inmultire is vreo maxim 2.500.000 si apoi sa le numeri si pe cele din output.

Or ... use python

>>> def fac(x):
...     if x > 1:
...         return x * fac(x - 1)
...     else:
...         return 1
...
>>> from decimal import Decimal
>>> x = Decimal(100)
>>> fac(x)
Decimal('9.332621544394415268169923877E+157')
>>> fac(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915
608941463976156518286253697920827223758251185210916864000000000000000000000000L
>>>

[Xander]

o cifra poate fi foarte usor stocata pe jumate de byte

un byte : [ 0000 0000 ] ( 8 biti ) - val max : 255

jumatate de byte[ 0000 ] ( 4 biti ) - val max : 15 (deci 0-9 intra usor)

pentru un numar cu 1 miliard de cifre ai nevoie de 500 mega ram ( destul de putin ).

problema e ca oricat de optimizat ar fi algoritmul de inmultire al numerelor mari ( am facut si eu pe la facultate )

trebuie sa il aplici de 10 milioane de ori pentru 10m!

niste optimizari cand faci inmultiri cu 2 numere mari( asta am folosit eu cel putin):

1. iei numarul cel mai mic(de la coada la cap - e mult mai usor sa faci carry asa) si il inmultesti cu toate numerele 2-9 si stochezi intr-o matrice

2. stochezi intr-un vector numarul initial ( tot reverse)

si pentru fiecare cifra din numarul al doilea aduni in vector randul din matrice corespunzator cifrei(decaland o pozitie la dreapta pentru fiecare cifra prin care treci)

am inmultit asa intr-un timp extrem de mic 2 numere mari extrem de rapid. (9 inmultiri) + n2 adunari unde n2 = lungimea numarului mai lung

[devianc3]

Si oricum, n! > n^n

Deeeci, daca n=3 => 6 > 27 ...

n=4 => 12 > 256 ...

Esti siiiigur ca asta e inegalitatea care o cautai?

[cmiN]

N-ai specificat, un algoritm euristic sau exhaustiv ? Vrei si rata de succes ?

[em]

N-ai specificat un algoritm euristic sau exhaustiv ? Vrei si rata de succes ?

Întrebarea asta am primit-o la un interviu. De?i eu nu am r?spuns prea bine la el am vorbit cu al?i candida?i care au dat r?spunsuri foarte bune (unele se legau mai mult sau mai pu?in de matematic?).

R?spunsul nu trebuie s? fie exact, po?i spune c? "dac? aplic algoritmul acesta ?i ob?in rezultate favorabile atunci exist? o ?ans? mare ca ce a g?sit prietenul meu s? fie bun".

Nu exist? restric?ii legate de algoritm. Nu v? mai lega?i de limita mare inferioar?, a fost pus? a?a de sus ca s? nu pute?i s? spune?i "Imi fac eu factorialul meu s? verific" (Chiar daca il face?i nu se va incadra in timp).

[cmiN]

Atunci ori se numara zerourile (incrementare cu x la intalnirea unui numar cu x zerouri) ori se aplica modulo la fiecare inmultire. La prima varianta mai pot aparea optimizari cu precalculari pe intervale dar nu cred ca e nevoie, iar la a doua varianta se mai face un modulo din numarul din fisier si asta-i tot cacatu.

P.S.: @em am uitat sa pun virgula dupa "specificat" .

[crs12decoder]

Pentru a determina cu siguranta daca algoritmul prietenului este bun, punem programul sa calculeze mai intai 10.000.000! dupa aceea 9.999.999!. Si impartim numarul rezultat de la primul calcul la numarul din cel de-al doilea calcul. Rezultatul trebuie sa fie exact 10.000.000 . In caz contrar, algoritmul nu e bun.

De ce merge?

Pentru a generaliza putem folosi algoritmul

n!/(n-1)! = n

Matematic il putem scrie pe n! de la numarator ca (n-1)!*n . Algoritmul devine (n-1)!*n/(n-1)! Iar acest (n-1)! de la numarator se simplifica cu cel de la numitor si ramane n.

Sigura situatie prin care numarul de la numarator se simplifica cu cel de la numitor este atunci cand algoritmul calculeaza corect n! si (n-1)!.

Ca sa dau un exemplu mai concret folosesc numere mici ca sa fie usor de inteles.

Presupunem n=5.

Dupa algoritmul folosit de mine avem

(5!)/(5-1)! = 5!/4! = 120/24

120/24 = 5 (adevarat)

Inseamna ca programul a calculat corect n! si (n-1)!.

Daca era sa fi calculat gresit. Sa presupunem ca la 5! programul nu a facut calculul corect si a cosiderat ca 5! este altceva decat 120. De exemplu 121. Ar insemna ca 121/24 = 5,041111 - Numarul fiind diferit de 5. Adica de n => algoritmul nu calculeaza bine factorialul.

Sper ca m-am facut inteles

[em]

@cmiN, @crs12decoder

Felicit?ri amândurora. Varianta lui crs12decoder e mai eficient? ?i asigur? o încredere mai bun?.

Ca premiu,

+rep.

LE: @cmin, nu pot s? î?i dau rep, cred c? e un bug, ai rep imens?

[unknown.]

@cmiN, @crs12decoder

Felicit?ri amândurora. Varianta lui crs12decoder e mai eficient? ?i asigur? o încredere mai bun?.

Ca premiu,

+rep.

LE: @cmin, nu pot s? î?i dau rep, cred c? e un bug, ai rep imens?

I-am dat eu pentru tine:))