Opération sur des grands nombres [Sources]

[Melem]

Voici quelques fonctions permettant de faire des calculs exacts sur des nombres qui peuvent être très grands. En fait, les nombres ici sont représentés par des chaînes de caractères (dynamiques), donc on calcule exactement comme à la main (évident). J'ai décidé de représenter les nombres directement par des chaînes de caractères pour faciliter la saisie et l'affichage, mais évidemment ça consomme ...

J'ai utilisé le programme greatns (Great Numbres) pour calculer 2008! (factorielle de 2008), ça donne (valeur exacte !) :

Code :

1
2
 
86436418576710702052555578574491386694770540285523412910903059692816181130349289654529502697509195384231172407798480676210473050254653691699885279619245952822594012734390812458748353272564818698306040468726686655355253240523812935015796694812755460929496689864855526801652406249629760778341920027535998111210845585964312245693430012395000661489449928161006308033871728370145842246861435772708335038622005088265738001660110686538245591442792241095871228519683836955221666591082301000711402578316615245912503303481063484360194291155475095251479532568985201843715592475296563523965687904014012277135693563336958691836319444117997054946850233712029434978495733990090226426502186589205092198706420491359084266171703996893802908188757275003705451966898754426626540504022877591340013537360816392625285550205556674469154535014420626307845473997558226565852647783174137467009137094593393857513748626042743545982011696406345144441399446551021007377429398027588025078414902618925877174109178713616585883813127441215817744537984855398722728731835030978830425196401370289991477269886035396799071879482695065001236211551469108130256145975512878144064434834334373086710590845710751358220602437618170589142947688283381784656639872244935255566827664460508479975701579529434757642065678947395386984845744346685582774364492480219196423141762909953312579045507499275924487172047850688893904805496951106713573426205804974787275962863122614649846513477956582766956906773049290860520738459517136292090770680593948010505996068102373947936258241209566250186095013872603462999109326053258345530862617052441013778446303287936991791763742984739361380924623277280331788303538360759304344858941257488019030605336589732950575604342817992071219794527370640861123238301730744401848545940145960901606555558946416648902885833103387278242425171929954205560372493987394263644594298235046185276630553428253214957271925962381310501114090642524593399720427280264840254600012176086327745759164130116692429880645249925674526572534506135896743526501234409624632090110527982616742323819443555752358238517825021925542073290133320668020487717870620306588951645434150036246170781664054813282131947168311550967858719216665160767489074971198744876106919336680584473613772717855991969058562481629694565905839682691742925454042012086650317697125503855691538838461035764481347803239635098795473177512906611484431263082994495195498377863721609890444127503572207700153391551850136305608035222614291380584050537056119749476816087800085245882225242031698925903699326408071302699879908568007093205806603442944961861973054452259367641108753128647553662101777252448401275590884240761995287181963339849956100618224018569062674675529709923431907194990638116801717198601285338686641138617095674661597070763512310914724726885367302158783017861151308558718642047626567202879059551320533807984703900791760989115941055636615657982373825335214695344513876739778204112649673879863660663444263026226169651341794693396516454208886956564801050963513875083227186461611789287959865051487896052042016184267434161795555478573262329730168025408483100818310699279269178637790986558033176293101527031718460572398330918449944245930209723927758692971617393894624459137371962064966418709908292002436251528962853185187569850000279031611239980870151403162689999383235270121952409244998779461369834591452550130254268916803260548508733278035082530876288879687645828769539752771547700615922352572203491341721741256362607822359501863305940628945023919326327437252032293952678761393051391203518166386006199444263128689308874660786932602667068832148526198024738938396246779749844904853648630977522063013865194417468043786501356034251922914016707357204620764153568601821272169208957251576372861357091345967702160527466166478955380088730675601459205206634269786077235350615235760626039325950025907729164095058314396814856148234936360416333032988944406160131236912294382693996216039370753560701861595697879975938657188335301827507508063645396334348681402713815806614829629274666329563013061479954135054973515426036936501677961592367155368024381450891251325410477205396327017775256491946647075720779256342567731928509122912333044525105712698880192889400166721123125103407568627276005753706590784666942672410697818381317060772523164522571635913108879531066003544735162494713021204409260660739852726909076958910528004744856601625449491251362902756417192030133778218470833206299701640176132133643851413170004909388617805775572654075230351717777713864837969537814491762741307511008896330551403167679284720590826817969636536910377271219141827668305763171501554820721580934151715242772452696270578881462563888423252706666425754509263011477580486648310418050276983946893813040436904052974195883249053853674931443289555686148177933625844678119361892105072224322463807751282854217610167683146136685169605916204780758319952300084321871544913787679792669196213689218641256062163432971676954007227178698431081344335589082515718828012892951669544226914300286838317645800817213672386929031354288989112296322409203785165254842566916469513223138134378137518774407909023800609231268275864827640124213894539054953100800469952255731863332460263060949662017734372213076687369778402830809043730023746066167836523101149707072303033132800537988641184751400091504560375275821465600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

[komput]

Oui ça marche mais j'ai fait un programme qui va plus vite. Je n'ai pas les sources sous la main tout de suite désolé, je les donnerai bientôt si ça peut intéresser quelqu'un.

Voilà quelques pistes qui marchent pour l'optimisation :

utiliser plutôt les vraies valeurs pour représenter les chiffres ça évite de calculer (i-'0') à chaque fois
et faire moins de malloc() dans la multiplication ça aussi ça prend pas mal de temps cpu
Pour toutes les opérations qui nécessitent d'allouer de la mémoire temporaire, en général on peut passer en paramètre un pointeur (mémoire déjà allouée) où la fonction travaille tranquillement. Comme ça même plusieurs instructions peuvent utiliser cet espace alloué au début du programme.
En envoyant en paramètre la longueur des nombres on évite d'utiliser strlen() trop souvent (du coup les structures sont intéressantes)
Il y a d'autres optimisations, que je n'ai pas toutes faites (représentation en binaire au lieu du décimal...)

avec ça j'ai programmé le cryptage RSA sur des nombres de taille arbitraire (500 chiffres, en 10s) et ça va assez vite (enfin tout est relatif)

[Melem]

Merci de tes remarques. En effet je n'ai pas cherché à optimiser, c'est juste un programme que j'ai fait pour m'amuser. Mais d'accord je vais le modifier quand j'en aurai le temps, et si tu peux poste également le tiens.

[komput]

VOilà mes sources, mais je n'ai pas acherché à faire une version "grand public" donc c'est un peu pas propre du tout. Désolé.

j'ai donné avant les quelques optimisations que j'ai apportées, jette un coup d'oeil si ça t'intéresse. Certaines fonctions ne sont pas encore finalisées mais ça arrive.
En fait partout où il y a "dec" dans les noms de fonctions/fichiers/structures c'est que les nombres sont représentés en décimal. Je suis en train de faire une petite version pour la représentation binaire, histoire de voir si on y gagne, mais j'en doute.

Sinon le code est assez simple, je vais bientôt rajouter la fonction racine.
Si tu compiles mon programme tel quel tu as le cryptage RSA : rentre un nombre, la puissance, le modulo et il donne le reste.

Lien vers le code : ici