Ensemble de fonction mathématique (pour tres grand nombres)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 076 fois - Téléchargée 36 fois

Contenu du snippet

Voici quelques fonctions qui permettent de réliser des opérations mathématiques pour de très grands nombres, comme des multiplications, des additions, des soustractions, des modulos, des transformations de Decimal en binaire et des division euclidiennes. J'ai aussi fait une petite fonction mgmod qui permet de calculer le modulo d'une expression mathématique du genre: (2555 x 3251^5585) mod 5223
Bon certaines sont rapide (multiplication, addition, soustraction) d'autres sont plus lentes (division, modulo, conversion binaire)
Je vais sans doute encore faire quelques fonctions et alors je les ajouterai.

Voici un exemple de ce que j'ententds par "opération sur de grands nombres":

7467636322858211413420378952487507706693561915417437336022
8558108410407266652454504706493231612117134305999525878380
1997265629154474676363228582114134203789524875077066935619
1554174373360228581084104072666524545047064932316121171343
0559995258783801972656291544746763632285821141342037895248
7550770669356191541743733602285810841040726665245450470649
3223161211713430599952587838019726562915447467636322858211
4113420378952487507706693561915417437336022858108410407266
6552454504706493231612117134305999525878380197265629154474
6776363228582114134203789524875077066935619154174373360228
5881084104072666524545047064932316121171343059995258783801
9772656291544746763632285821141342037895248750770669356191
5441743733602285810841040726665245551571749433261312724531
6009063598848010737672026558578647323968212413431379053598
5118717704662925428548446023968219411408376752565515717494
3332613127245316090635988480107376720265585786473239682124
1334313790535985187177046629254285484460239682194114083767
525655157174943326131272453160

.

6859610553647623715964088665892371829439866709240283944117
9881257041327422001125735162772203142673516307553314590384
6660055334469068596105536476237159640886658923718294398667
0992402839441179812570413274220011257351627722031426735163
0775533145903846600553344690685961055364762371596408866589
2337182943986670924028394411798125704132742200112573516277
2220314267351630755331459038466005533446906859610553647623
7115964088665892371829439866709240283944117981257041327422
0001125735162772203142673516307553314590384660055334469068
5996105536476237159640886658923718294398667092402839441179
8112570413274220011257351627722031426735163075533145903846
6000553344690685961055364762371596408866589237182943986670
9224028394411798125704132742200112674526387320324368462731
8665332569149576116644556917950611664758624725074199775893
4882830449977810340293054227081367151338522001236745263873
2003243684627318653325691495761166445569179506116647586247
2550741997758934828304499778103402930542270813671513385220
012367452638732032436846273186

=

5122507693108052051908131512143089045229455175415561596741
4115663320922257779260847962552493629779254239908654457854
7659795059380401223878952817987873561967046683029218298414
2704888506355992220892718575858943821306020756928844917260
1496814741818629561724705921381618263940050903619971854955
8685128375567898616549668937396924474582292644083436280903
0812870055701817042120421461679454734263999108523374019658
6451150982120163378294892403702165186723504158521072906024
6649698023514459288310117204608799822735728798496294238718
1147617418805786043572392261647334696163781388547460987364
4126572600108078453271243617959223979304080406789433849922
8721700389844931997521438450798888152626132814848278783337
0708589556746040135130413611298116349872506712381092875331
6592897730971005286272040682228164590074535276472462380813
0290545735206587837092572751966838238347537089649127846050
1830690921868944930970943856770232612588229711802688655297
5277728524770351930009639830735857517804884275056341862026
1780535718109234418975292625952006076532656341063155337236
9181818656271974786119575839913894460868983639415262361546
8628770034899869858134004265662959464460657710892791284199
2367933788551152642524731528591847313677658077563349536155
6958583181392908498982119042700711601422928494954019211302
8551618783638472295513187440508782932175625878859575724470
2770007373414614404038449764618772060968878805298799649963
0607464601924005523355181576069452428773049062276275473456
5984580465841995786232172038971629630393927037411751117589
0164283174838692441834322539844525548518624048521840196103
6322686398713324751121414517540671701985694791213661014416
9398035099467589087299833087745203938775943418268558517359
7281873777374123921416215478295480002635918638207617728518
5512862839991918173933460492085976528134262265139816140734
9210686480183532557992081615581198053269887141629694325327
9572052414638358668481018444618982740877554078670905523641
1634934575218662724812951391323540645910814578206660365482
2101632180174420242263665512029199613137209596909297489677
60

Cette multiplication n'a mis que quelques secondes à être calculée par la fonction multi(term1,term2) et ici, les deux termes font chacun 1000 chiffres.

Source / Exemple :


Private Function mgmod(term1 As String, term2 As String, expon As String, modul As String)
Do While expon <> "1"
    term1 = modulo(term1, modul)
    term2 = modulo(term2, modul)
    If Val(Right(expon, 1)) Mod 2 = 0 Then
        term1 = multi(term1, term1)
        expon = divis(expon, "2", False)
    Else
        term2 = multi(term1, term2)
        term1 = multi(term1, term1)
        expon = soustraction(expon, "1")
        expon = divis(expon, "2", False)
    End If
Loop
term1 = modulo(term1, modul)
term2 = modulo(term2, modul)
total = multi(term1, term2)
total = modulo(Mid$(total, 1), modul)
mgmod = total
End Function

Private Function modulo(term1 As String, modul2 As String)
lediv = divis(term1, modul2, True)
modulo = Mid$(lediv, InStr(1, lediv, "r") + 1)
End Function

Private Function addition(term1 As String, term2 As String)
Dim nbd, nbt, nbu As Integer
st1 = Len(term1): st2 = Len(term2)
If st1 < st2 Then term1 = String(st2 - st1, "0") & term1
If st1 > st2 Then term2 = String(st1 - st2, "0") & term2
For i = 0 To Len(term1) - 1
    nb1 = Mid$(term1, Len(term1) - i, 1): nb2 = Mid$(term2, Len(term2) - i, 1)
    nbt = Val(nb1) + Val(nb2) + nbd
    nbd = nbt \ 10: nbu = nbt Mod 10
    total = nbu & total
Next i
addition = zero(Mid$(nbd & total, 1))
End Function

Private Function soustraction(term1 As String, term2 As String)
If pgdd(term1, term2) = 0 Then soustraction = "0": Exit Function
If pgdd(term1, term2) = 2 Then soustraction = "-" & soustraction(term2, term1): Exit Function
Dim nbd, nbt, nbu As Integer
st1 = Len(term1): st2 = Len(term2)
If st1 < st2 Then term1 = String(st2 - st1, "0") & term1
If st1 > st2 Then term2 = String(st1 - st2, "0") & term2
For i = 0 To Len(term1) - 1
    nb1 = Mid$(term1, Len(term1) - i, 1): nb2 = Mid$(term2, Len(term2) - i, 1)
    If Val(nb1) - Val(nb2) - nbd2 < 0 Then
        nbd = Abs(nb1 - nb2) \ 10 + 1
        nb1 = Val(nb1) + nbd * 10
    End If
    nbu = nb1 - nb2 - nbd2
    nbd2 = nbd: nbd = 0
    total = nbu & total
Next i
soustraction = zero(Mid$(total, 1))
End Function

Private Function multi(term1 As String, term2 As String)
total2 = "0"
Dim nbd, nbt, nbu As Integer
For i = 0 To Len(term2) - 1
    nbd = 0
    total = ""
    nbr2 = Mid(term2, Len(term2) - i, 1)
    For a = 0 To Len(term1) - 1
        nb1 = Mid(term1, Len(term1) - a, 1)
        nbt = nb1 * nbr2 + nbd
        nbd = nbt \ 10: nbu = nbt Mod 10
        total = nbu & total
    Next a
    total2 = addition(nbd & total & String(i, "0"), Mid$(total2, 1))
Next i
multi = zero(Mid$(total2, 1))
End Function

Private Function divis(term1 As String, term2 As String, rest As Boolean)
total = "0"
Do While Len(term1) > Len(term2)
nbz = Len(term1) - Len(term2) - 1
nbr1 = term2 & String(nbz, "0")
term1 = soustraction(term1, Mid$(nbr1, 1))
total = addition(Mid$(total, 1), "1" & String(nbz, "0"))
Loop
For i = 1 To 20
    If term1 = term2 Then
        total = addition(Mid$(total, 1), "1")
        reste = "0"
    Exit For
    ElseIf pgdd(term1, term2) = 2 Then
        reste = term1
    Exit For
    ElseIf pgdd(term1, term2) = 1 Then
        term1 = soustraction(term1, term2)
        total = addition(Mid$(total, 1), "1")
    End If
Next i
If rest = True Then total = total & "r" & reste
divis = zero(Mid$(total, 1))
End Function

Private Function pgdd(term1 As String, term2 As String)
st1 = Len(term1): st2 = Len(term2)
If st1 > st2 Then pgdd = 1: Exit Function
If st1 < st2 Then pgdd = 2: Exit Function
For i = 1 To Len(term1)
If Mid(term1, i, 1) > Mid(term2, i, 1) Then pgdd = 1: Exit Function
If Mid(term1, i, 1) < Mid(term2, i, 1) Then pgdd = 2: Exit Function
Next i
pgdd = 0
End Function

Function zero(term1 As String)
For i = 1 To Len(term1) - 1
If Mid$(term1, 1, 1) = "0" Then term1 = Mid$(term1, 2) Else GoTo nom
Next i
nom:
zero = term1
End Function

Function DecToBin(nombre As String)
Do While nombre <> "0"
bini = Val(Right(nombre, 1)) Mod 2
biny = bini & biny
nombre = divis(nombre, "2", False)
Loop
DecToBin = biny
End Function

Conclusion :


Petite précision sur l'utilisation de certaines fonctions:

::MULTIPLICATION::
-----------------------

multi(term1,term2)

exemple: multi("250","4") donne "1000" ;-) evidement

::DIVISION::
---------------

divis(term1,term2,reste)

divise le term1 par term2 et renvoie le résultat, si reste est TRUE, la fonction renvoie le résultat suivit du caractère r et du reste de la division (Evite de devoir utiliser 2 fonction pour diviser et trouver le reste)

exemple: multi("201","4") donne "50r1" si reste = TRUE, "50" sinon

::ADDITION::
---------------

addition(term1,term2)

exemple: addition("250","4") donne "254" ;-) evidement

::SOUSTRACTION::
----------------------

soustraction(term1,term2)

exemple: soustraction("250","4") donne "246" ;-) evidement

::MODULO::
----------------------

modulo(term,modul)

exemple: modulo("203","4") donne "3"

::BINARISATION ;)::
-----------------------

DecToBin(nombre)

exemple: DecToBin("5232145") donne "10011111101011000010001"

::MegaModulo::
------------------

MgMod(term1,term2,expon,modul)

calcul (term2 * term1 ^ expon) mod modul

exemple: mgmod("255","571","5","50") donne "25"

-------------------

Voilà, j'espère que ces fonctions vous seront utiles.

A voir également

Ajouter un commentaire

Commentaires

Renfield
Messages postés
17280
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
21 juillet 2019
57 -
je suis interessé.... si cela s'appuie sur les methodes de comptages utilisé pour les bouliers, j'imagine le gain !! c'est tellement puissant un boulier (multiplication, fraction, logaritmes.... on peut tout faire avec, avec une simplicité !)
rambc
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009
-
Si cela intéresse quelqu'un, je peux envoyer un document "brouillon" PDF expliquant très rapidement la méthode de KARATSUBA qui permet d'accélerer le calcul d'un produit de deux entiers.

Je l'ai programmé en VBA et j'obtiens les résultats suivants (en comparant avec les fonctions proposées ici) :


TEST 1

Le nombre N°1 a 100 chiffres et le nombre N°1 en a 100 .

6484248312346612074105273760496739610942355566742758968174151648322635582372470331999558423228628481
*
1555663255817789031175479074284241314593219940713073894960142813748389321087844775216920735501994733

Méthode KARATSUBA :
10087306841116134372680082506415637898883854900237796828632595647838609649093338128643978796027761503021598342153354294739841108195251474445576484928399010914458114657131027176771624927009887275790573

Méthode Scolaire :
10087306841116134372680082506415637898883854900237796828632595647838609649093338128643978796027761503021598342153354294739841108195251474445576484928399010914458114657131027176771624927009887275790573

Temps KARATSUBA : 0,6601563 s

Temps Scolaire : 4,890625 s

Egalité entre les deux méthodes : Vrai

TEST 2

Le nombre N°1 a 1000 chiffres et le nombre N°1 en a 1000 .

7530808389504628596216512239214761097264590965322031259514500306814190443594822072202595699349055869464842483123466120741052737604967396109423555667427589681741516483226355823724703319995584232286284814625902810395107355255559949106133838746279620952704449561045006595707377296600505473476477728192678833516619350817445296873453368696762523543610747007848425670963242501328326385683234289861635320603232759276495174401364042552654311208856242167372943510797256015282098264823994503311282829558879745383543887020952150623383600340271225693842043724187053131084097961981097081041630748732739439733289838750961416040981728412337129627352650987958805416486836605827375553812536602937841932140064132119972673761800706365667179811741307287760234469564978358992421004009075655317825125834690324993073229835585109833861133524932254304392372418729165386199637563945504238285330992151102647471247368280204645923972003577259352923942772368388562004475046506809676534367075531103895623087003862782713678618730799
*
5277747903752628929590170394164325423960685454409344616377821155063757420102760324348730416121394873415556632558177890311754790742842413145932199407130738949601428137483893210878447752169207355019947331061447811187287482334029882631252344695542832765850649502157435374129604690992803540558761092227737252608447466343771023310401795135775549501136432847284385022333266602585019216608688729546800496579335259844116670541924491330385017165903638451092139587243647109348189690165577404649077949847168771489970589829232682489765581488006826130495851237452666984725600961612328826692209444320846815693716751408093982960242838590667011927118422002044857967912701365918833472211922396342712073397677906844471952269646458236199329997994530029423468460014528824082696841395631289678640981203373592748027346483041698984846056243392695184054881146057695499834546084512755663132823016626114739116818168810252005494418227869397103807627114863887317377473536637669524328064458817246594685144225064843841059929020616

Méthode KARATSUBA :
39745708191270765039617074821012702211274572320801541337412950186793191420738885588409350771865302407072843673572095931411356793703160920922613185652753216248966186948217074446872921027715118749794090734120313131619361559193295032822663289768454698421263845234558902589485803259193500283815783257467382997630380737302002685174738084207889428593362490885095394871675965364590649943753124750144030447000170065403737893663530940822231986623801745609605929616844224799492139998662022593652313493011562838611653039720797745983334765520111143277909182810903953545431996951248984785954951943508946566925797469990973278643669204115629232154809149324552705918604474465292806076253021778565143054422943464679877826350845418140093739500173294006897298471178466477440586516009340207530058922198550078200222628591455818805334681705315147103628812300509276907412866552017130026063654209544793870163798890139728826886562756048528389462496306368369218622896040486283188194812675881364530876522278859218973590293908354971084564312714345374034308414724960069616482391175491285422296220038272829305133359646459487395995830667042383183751129687962569763850827101132083384979675870250451815973328303780895741869051194204195847349718093984172467442830196749434676882543510125033233773627785881876882067138354272742138314003049582016567970000024509287826983100280162503833046534339444528826443122654165043710093361991778772247264503722749968816869467866022935539664154133613546469410416915332436256303920140110052686549074178849608702407782676882434946876128957866439893062724506708234634579141286362494285096333266038284494733560198666737997922442156677849704123910181391796623791221390686755811470049081165575486582433994221128698647782936328246522784880265261584329796795237100352611896792128019027359185412619436182198664851418424807373450678443677196201001693774465238185873076099774643360336410785100179295329616591891671117756810790553368215275547766685536849302830733567683136498339313143740737726526075457025152184

Méthode Scolaire :
39745708191270765039617074821012702211274572320801541337412950186793191420738885588409350771865302407072843673572095931411356793703160920922613185652753216248966186948217074446872921027715118749794090734120313131619361559193295032822663289768454698421263845234558902589485803259193500283815783257467382997630380737302002685174738084207889428593362490885095394871675965364590649943753124750144030447000170065403737893663530940822231986623801745609605929616844224799492139998662022593652313493011562838611653039720797745983334765520111143277909182810903953545431996951248984785954951943508946566925797469990973278643669204115629232154809149324552705918604474465292806076253021778565143054422943464679877826350845418140093739500173294006897298471178466477440586516009340207530058922198550078200222628591455818805334681705315147103628812300509276907412866552017130026063654209544793870163798890139728826886562756048528389462496306368369218622896040486283188194812675881364530876522278859218973590293908354971084564312714345374034308414724960069616482391175491285422296220038272829305133359646459487395995830667042383183751129687962569763850827101132083384979675870250451815973328303780895741869051194204195847349718093984172467442830196749434676882543510125033233773627785881876882067138354272742138314003049582016567970000024509287826983100280162503833046534339444528826443122654165043710093361991778772247264503722749968816869467866022935539664154133613546469410416915332436256303920140110052686549074178849608702407782676882434946876128957866439893062724506708234634579141286362494285096333266038284494733560198666737997922442156677849704123910181391796623791221390686755811470049081165575486582433994221128698647782936328246522784880265261584329796795237100352611896792128019027359185412619436182198664851418424807373450678443677196201001693774465238185873076099774643360336410785100179295329616591891671117756810790553368215275547766685536849302830733567683136498339313143740737726526075457025152184

Temps KARATSUBA : 3,898438 s

Temps Scolaire : 26,25 s

Egalité entre les deux méthodes : Vrai
cs_Pingouin
Messages postés
262
Date d'inscription
lundi 26 août 2002
Statut
Membre
Dernière intervention
24 août 2005
-
Ok ben ya pas de koi lol. Bon courage et jspr voir tres bientot le resultat...
MadM@tt
Messages postés
2215
Date d'inscription
mardi 11 novembre 2003
Statut
Membre
Dernière intervention
16 juillet 2009
-
C'est vrai que je ne saurais meme pas le faire du tout alors..héhé
je l'ai trouvé sur une autre source,
mais pas avec les chaines de caractères...
Je vais m'adapter.
Merci quand même @ +
cs_Pingouin
Messages postés
262
Date d'inscription
lundi 26 août 2002
Statut
Membre
Dernière intervention
24 août 2005
-
Whaou t exigeant la !! C pas evident un algo pour la racine carrée a la main. Yen a un ki repose sur le fait que la somme des n premiers entiers impairs donne le n² mais pour les décimales c plus coton koike faisable, mais si c pour ton algo sur les nombres premiers un approximation grossiere ca doit suffire non ?

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.