Клубове

n!

12 отговора 561 прегледа
luke #1

n!

pisha edna funkcia za presmiatane na n!.tipat,koito vrashta funkciata sam go slojil float.pri n<=170 raboti bez problem no pri n>170 garmi.
daite niakoia ideia.mersi predvaritelno.

Отговор
Пporpaмиcт в отговор на luke #2

Re: n!

Използвай някоя библиотека за работа с големи числа или си я напиши сам (трябва ти само операция умножение все пак)....

И защо ти е факториел над 170?

Отговор
luke в отговор на Пporpaмиcт #3

Re: n!

triabva mi.

osven tova problema ne e v umnojenieto na chislata,a vav vrashtania rezultat.i po-tochno v negovata razmernost.

Редактирано от luke на

Отговор
Гeнчo в отговор на luke #4

Re: n!

Каквато и библиотека с плаваща запетая да ползваш, ще препълни при определено число. И освен това губиш много от краиното число битове, с което се изразява числото - например валидни са ти първите 14-20 цифри от резултата, останалото е по 10 на степен някоя си.

Ако ти трябват точно n! за големи числа, ползвай специални библиотеки за работа с големи числа или програми за символно пресмятане - Matematika или Maple. Там ограниченията са само от паметта, но до 30000! няма проблеми!

Отговор
lndependent в отговор на luke #5

Re: n!

направи го long double. обхвата му е на порядъци по-голям от този на float.

Type Minimum value Maximum value
float 1.175494351 E – 38 3.402823466 E + 38
double 2.2250738585072014 E – 308 1.7976931348623158 E + 308
long double –1.2 E - 4932 1.2 E + 4932

stoj, ta gledaj
Отговор
luke в отговор на lndependent #6

Re: n!

mersi za savetite,momcheta.

Отговор
b в отговор на luke #7

Re: n!

Познай как го получих!
Ако не вярваш в резултата, можеш да си го провериш сам :)

==> (transcript-on "x.txt")
()

==> (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
fact

==> (fact 170)

72574156153079989673967282111292631147169916812964513765435777989
00561843401706157852350749242617459511490991237838520776666022565
44275302532890077320751090240043028005829560396661259965825710439
85582942575689663134396122625710949468067112055688804571933402126
61452800000000000000000000000000000000000000000

==> (fact 1700)

GCing... 503912 bytes collected, 296072 bytes used, heapsize 800000 bytes.
GCing... 407520 bytes collected, 392448 bytes used, heapsize 800000 bytes.

... тука малко сърдене ... и след по-малко от 30 секунди ...

GCing... 563928 bytes collected, 233568 bytes used, heapsize 800000 bytes.
GCing... 565272 bytes collected, 233832 bytes used, heapsize 800000 bytes.

29983532055584180947011311156646134598501714384095830701693144965
31140242247368919694363792466983858311481231384824780959878108306
82771126161384495073949263666572170077241175214409824116748830572
94459365742154945194589014091828309300524321528885343724987190318
22059189856486665368978846365916661190594744982844200865289620103
87551074080597272404249528952101663133040610950702406770791535073
51271223602410280560958540974134405813252964508637784013191472821
78998472716588603052487921303646737473677644631686179918257946503
31266855016057932639143340617147626239959108777265211392410150892
02424854120209008084854042921209840520332416173062553125332074848
32128428195892676872105110140425556455696529279622032604660056325
28175453603052462341749826707858694700437817740901992396719491569
66289921576972788690861269270328330117119555483812265275248121384
47954742569945776938385311777767433547406086141485401850467176039
46388337902828788685861351347917494081728876675773582960200203335
07895255821061921327609103473428880177875648994114706364336645840
27199788416867503748374613661323468015256415459848591528917807037
87952361192820004217394304430063621536290592702975874526852318391
79027368129928121160214629119141580531099919704922735740631009781
64267137822925925750887236251141544140977729807763929738072205138
41872738440173639879829302194795381849615953681919792032387419279
08045348116821398863807388660462983878084459639827408170940443474
46194416861486682286669874036824997312223696043267667524355036285
10537369935813418337281609613053484890662601835431948018557436002
79461221904043323858035748643710709044649318720608344979816885500
24104868739797741032409568429873434135618867622987851822414549096
26919023082057996425091080370453756502230797745784864968420407338
36185157505920734480119542376787778271909168557906938317511400550
32069717791825641145765238359129184568155465082398021387458757620
93472432152279547937134512524551563099576456086086217723176769637
02635711795909074277253346520497187146914344152456786774876454419
30874298204422913067827541850501885062300561585783037593795556535
80667520705790388475950031807537077757849294738135383794896794928
67075256419720390744293239581516488007815667429971064275166892258
41502764672105477104043382243019765946354325876422058090805188201
79086991837864560905159580979440361644108351689252572199254294605
25925864636522558229642261485339045610644486253659495679324341400
75846561831396505495737084626283083536723968347249473678956686493
40678849395288705142404994375368686062334602469987977389626425852
50164685692966977451181834331246339208171409141100139999203628179
95623302805517872734433183900413959556688890727800342538355059327
50843709645515397992823150628425530559287212126092216222624630864
98326397325131263849722783554224365373949803754359602292889144817
92794160724330203530033050984956555476368473697189674393388904870
22631603476284949400243655289001508623039803714113383732246998204
45917341209144303990094047359535412657451487836794710712388822650
06972882149508542806168239526629026007353045918384421414627048521
77065546647117083832713634989023168397140613883953766222567075038
02943968645387298371139535388346620250337125329407852799605146696
47190161970629158868087745892654708607537079992778103346600668423
02547730998057787939040128248576446385331822659639420194614476990
82716911003108766821928845987485983093474814476332109894484294332
14875408830118136815583374910637973420215675516805056868951875737
63054716111031519329775819286698485504449316830681123408573995670
81420977947023357960350004263115908983192441384974310000934703017
66845294541173428415111902926621489060722506907902037324215357470
91610936734416088468187262680901076274405600029963461150474402221
70131382362255131770495436918046492739761604438977378474944981859
29082013187196360218603243891156037661848297391553314018511623058
18976200286806845265811079655490261741235162405487666474369316810
86057183839377995292275446698308268905326272676704549542963855969
37136498550423995897097114268502182819280701871121326174020025039
57181061471134087360759110243776250896180545157303550921503039922
07126197715886194610054619717563431423973281433345408708488540469
12720665114562295663970751651201719187953580622932267380854578541
83037520790365367809454465190343636310959176449406442475178951726
58879824230800627238791256928576988155740160000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000
00000000000

==> (transcript-off)

Отговор
aquarin в отговор на luke #8

Re: n!

Ako pishesh na C pogledni GNU Scientific Library ima dosta polezni neshta. Mojesh da polzvash niakoi ot specialnite tipove za rabota s golemi chisla.
[линк]

Отговор
aquarin в отговор на aquarin #9

Re: n!

Uff che sam zaspal, ne ti triabva tova
ami edna druga bibliotkeka [линк]
tia ti pozvoliava da smiatash s "bezkraina" tochnost.

Отговор
Colombino в отговор на b #10

Re: n!

Пробвал съм и по тоя начин, но с вътрешен итератор дава по-голям обхват.

Отговор
aquarin в отговор на luke #11

Re: 50000!

Ako pishesh na C ei tova neshto smiata n!
s gmc-lib

#include <gmp.h>
#include <stdio.h>

main (int argc, char **argv){
mpz_t b;
unsigned long int a;
a = atol(argv[1]);
mpz_init (b);
mpz_fac_ui(b, a);
gmp_printf ("%Zd\n", b);
exit (0);
}

Na P500 uspiava da smetne 50'000! za 19s

I pri tova rezultata e bez zakragliane.

A tuka mojesh da vidish rezultata
[линк]

Редактирано от aquarin на

Отговор
b в отговор на Colombino #12

The speed of Scheme Lisp


Tova e iasno, n! se pravi s opashna recursia (obiknoven cycul) bez da pulni steka.

S onazi LIB za C sigurno e po-burzo, ama v Scheme si go ima vutre i e po-lesno.

Eto testove za vremeto (bez samite stoinosti na n!)

// programa

(define fact (lambda (n)

  (let loop ((m 1)(k 1))

    (if (> k n)

        m

        (loop (* m k) (+ k 1))))))

// Izmereno vreme

(time (fact   1000))         20 ms

(time (fact  10000))       2204 ms

(time (fact  20000))       9685 ms

(time (fact  50000))      71099 ms  (71 sec)

(time (fact 100000))     338130 ms  (5 min 38 sec)

// Computer

Pentium 333MHz

RAM 128M

Windows 2000

// Interpretator na Scheme Lisp

Petite Chez Scheme, [линк]


Отговор
aquarin в отговор на b #13

Re: The speed of Scheme Lisp

Prav si che go ima v shcheme ama pitashtia edva li ima interpretator, kato gledam i moia interpretator na shchme dava podobni vremena.

Отговор
Отговор в темата