IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Contribuez Discussion :

Opération sur des grands nombres [Sources]


Sujet :

Contribuez

  1. #1
    Expert éminent
    Avatar de Melem
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Janvier 2006
    Messages
    3 656
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Janvier 2006
    Messages : 3 656
    Points : 8 389
    Points
    8 389
    Par défaut Opération sur des grands nombres
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    86436418576710702052555578574491386694770540285523412910903059692816181130349289654529502697509195384231172407798480676210473050254653691699885279619245952822594012734390812458748353272564818698306040468726686655355253240523812935015796694812755460929496689864855526801652406249629760778341920027535998111210845585964312245693430012395000661489449928161006308033871728370145842246861435772708335038622005088265738001660110686538245591442792241095871228519683836955221666591082301000711402578316615245912503303481063484360194291155475095251479532568985201843715592475296563523965687904014012277135693563336958691836319444117997054946850233712029434978495733990090226426502186589205092198706420491359084266171703996893802908188757275003705451966898754426626540504022877591340013537360816392625285550205556674469154535014420626307845473997558226565852647783174137467009137094593393857513748626042743545982011696406345144441399446551021007377429398027588025078414902618925877174109178713616585883813127441215817744537984855398722728731835030978830425196401370289991477269886035396799071879482695065001236211551469108130256145975512878144064434834334373086710590845710751358220602437618170589142947688283381784656639872244935255566827664460508479975701579529434757642065678947395386984845744346685582774364492480219196423141762909953312579045507499275924487172047850688893904805496951106713573426205804974787275962863122614649846513477956582766956906773049290860520738459517136292090770680593948010505996068102373947936258241209566250186095013872603462999109326053258345530862617052441013778446303287936991791763742984739361380924623277280331788303538360759304344858941257488019030605336589732950575604342817992071219794527370640861123238301730744401848545940145960901606555558946416648902885833103387278242425171929954205560372493987394263644594298235046185276630553428253214957271925962381310501114090642524593399720427280264840254600012176086327745759164130116692429880645249925674526572534506135896743526501234409624632090110527982616742323819443555752358238517825021925542073290133320668020487717870620306588951645434150036246170781664054813282131947168311550967858719216665160767489074971198744876106919336680584473613772717855991969058562481629694565905839682691742925454042012086650317697125503855691538838461035764481347803239635098795473177512906611484431263082994495195498377863721609890444127503572207700153391551850136305608035222614291380584050537056119749476816087800085245882225242031698925903699326408071302699879908568007093205806603442944961861973054452259367641108753128647553662101777252448401275590884240761995287181963339849956100618224018569062674675529709923431907194990638116801717198601285338686641138617095674661597070763512310914724726885367302158783017861151308558718642047626567202879059551320533807984703900791760989115941055636615657982373825335214695344513876739778204112649673879863660663444263026226169651341794693396516454208886956564801050963513875083227186461611789287959865051487896052042016184267434161795555478573262329730168025408483100818310699279269178637790986558033176293101527031718460572398330918449944245930209723927758692971617393894624459137371962064966418709908292002436251528962853185187569850000279031611239980870151403162689999383235270121952409244998779461369834591452550130254268916803260548508733278035082530876288879687645828769539752771547700615922352572203491341721741256362607822359501863305940628945023919326327437252032293952678761393051391203518166386006199444263128689308874660786932602667068832148526198024738938396246779749844904853648630977522063013865194417468043786501356034251922914016707357204620764153568601821272169208957251576372861357091345967702160527466166478955380088730675601459205206634269786077235350615235760626039325950025907729164095058314396814856148234936360416333032988944406160131236912294382693996216039370753560701861595697879975938657188335301827507508063645396334348681402713815806614829629274666329563013061479954135054973515426036936501677961592367155368024381450891251325410477205396327017775256491946647075720779256342567731928509122912333044525105712698880192889400166721123125103407568627276005753706590784666942672410697818381317060772523164522571635913108879531066003544735162494713021204409260660739852726909076958910528004744856601625449491251362902756417192030133778218470833206299701640176132133643851413170004909388617805775572654075230351717777713864837969537814491762741307511008896330551403167679284720590826817969636536910377271219141827668305763171501554820721580934151715242772452696270578881462563888423252706666425754509263011477580486648310418050276983946893813040436904052974195883249053853674931443289555686148177933625844678119361892105072224322463807751282854217610167683146136685169605916204780758319952300084321871544913787679792669196213689218641256062163432971676954007227178698431081344335589082515718828012892951669544226914300286838317645800817213672386929031354288989112296322409203785165254842566916469513223138134378137518774407909023800609231268275864827640124213894539054953100800469952255731863332460263060949662017734372213076687369778402830809043730023746066167836523101149707072303033132800537988641184751400091504560375275821465600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    Fichiers attachés Fichiers attachés

  2. #2
    Membre du Club
    Profil pro
    Inscrit en
    Janvier 2008
    Messages
    39
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2008
    Messages : 39
    Points : 47
    Points
    47
    Par défaut
    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)

  3. #3
    Expert éminent
    Avatar de Melem
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Janvier 2006
    Messages
    3 656
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Janvier 2006
    Messages : 3 656
    Points : 8 389
    Points
    8 389
    Par défaut
    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.

  4. #4
    Membre du Club
    Profil pro
    Inscrit en
    Janvier 2008
    Messages
    39
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2008
    Messages : 39
    Points : 47
    Points
    47
    Par défaut Source
    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

Discussions similaires

  1. [XL-2007] Opérations sur les grands nombres dans Q
    Par KenDev dans le forum Contribuez
    Réponses: 4
    Dernier message: 22/03/2011, 05h05
  2. Réponses: 2
    Dernier message: 09/02/2011, 09h10
  3. Optimisation des opérations sur les grands nombres, algorithme de Knuth
    Par Jackyzgood dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 21/10/2010, 21h27
  4. Modulos sur des grands nombres
    Par DjPoke dans le forum Mathématiques
    Réponses: 2
    Dernier message: 07/08/2007, 16h32
  5. Réponses: 3
    Dernier message: 10/03/2006, 17h41

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo