ENSEMBLE DE FONCTION MATHÉMATIQUE (POUR TRES GRAND NOMBRES)

Information sur la source

Catégorie :Maths Niveau : Débutant Date de création : 04/06/2003 Date de mise à jour : 03/02/2004 20:53:35 Vu : 6 083

Auteur : DHKold

Site perso

Ecrire un message privé

Note :

9,50 / 10

Commentaire sur cette source (29)

Ajouter un commentaire et/ou une note

Description

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

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

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.

Sources du même auteur

Toutes les sources de DHKold

Sources de la même categorie

Toutes les sources de la catégorie Maths

Commentaires

Commentaire de Renfield le 04/06/2003 21:33:06 administrateur CS

bravo, c'est que c'est du boulot(et des neurones) tout ca !!!
Commentaire de Jujufouq le 04/06/2003 22:56:43

C'est très bien. Moi aussi j'ai fait un truc comme ça à l'intérieur d'un de mes progs. J'aurais mieux fait de faire une dll... enfin, il est rapide ou pas (j'ai as encore testé)? C'est bien.
Commentaire de Renfield le 04/06/2003 23:00:59 administrateur CS

un portage en c accelererais encore les choses.........
Commentaire de Patrice99 le 05/06/2003 08:49:21

J'ai vu une fois quelqu'un qui avait fait une classe en C++ pour la manipulation de nombres en précision à la demande : allocation dynamique : une super classe, mais je ne sais plus ou la trouver.
Commentaire de sylric le 05/06/2003 11:39:43

Je ne remets pas en cause le côté programmation qui marche apparemment très bien, et relativement vite !
Cependant, je ne vois pas très bien l'intérêt de calculer des nombres aussi grands, ou du moins avec une aussi grande précision.
Enfin, du bon boulo quand même !
Commentaire de Arknoth le 05/06/2003 14:38:38

Ben our le cryptage Sylric, ca sert à fond, surtout, par exemple, en cryptage RSA. La fonction modulo de VB par défaut ne marche pas au delà de la limite des entiers longs --> crash lors des calculs. En plus, cette fonction modulo est assez lente par rapport à son équivalent "fait à la main".

Juste un truc dans ta source : pense à déclarer et typer ;)
Sinon, super boulot, bravo !
Commentaire de Arknoth le 05/06/2003 14:46:16

Pour le calcul du modulo j'ai fait ca dans un prog RSA :
(elle est bien plus rapide que la fonction de vébé ^^)

Function Modulo(ByVal nNumerateur As Double, ByVal nDenom As Long) As Double
Dim nNb As Double
Dim iLenDen As Integer

iLenDen = Len(Format(nDenom))
nNb = nNumerateur

While nNb > nDenom * 10
    nNb = nNb - nDenom * 10 ^ (Len(Format(nNb, "0")) - (iLenDen + IIf(Val(Left(Format(nNb, "0"), iLenDen)) > nDenom, 0, 1)))
Wend

If nNb > nDenom Then
    While nNb > nDenom
        nNb = nNb - nDenom
    Wend
End If

Modulo = nNb

End Function
Commentaire de DHKold le 05/06/2003 16:49:33

C'est en effet pour le cryptage RSA que je calcul de si grands nombre, surtout la fonction mgmod.
Commentaire de Arknoth le 05/06/2003 18:44:49

essaye de comparer les temps de calcul de ta fonction modulo et de la mienne (surtout avec un grand chiffrement) - dsl G pas la motivation de le faire, c juste par curiosité ^^

Si tu cherches un générateur de Nombres premiers, le mien est ultra-rapide (par rapport au temps de calcul avec une itération toute simple). et dsl pour les 2 posts identiques, AOL a chié à ce moment-là (pour changer) :p
Commentaire de DHKold le 05/06/2003 19:43:53

j'ai fait des tests pour comparer ta fonction et la mienne, bien que la tienne soit plus rapide le résultat qu'elle renvoie est faut:

64315721649834214273271 mod 2 = 1 et pas 2
8885447741233655996663214 mod 555555 = 279234 et pas 430813

donc je préfère garder ma fonction ;b
Commentaire de Arknoth le 06/06/2003 03:49:33

oué en effet, G trouvé pkoi : connard de VB ki transforme les nombres très grands placés en variable "Double". Damn.
--> modif, ca travaille maintenant sur les Strings, avec je pense encore moins de temps de calcul (G essayé^^)

Function Modulo(ByVal sNumerateur As String, ByVal sDenom As String) As Double
On Error GoTo Erreur

Dim sNb As String
Dim iLenDen As Integer
Dim sTemp As String

iLenDen = Len(Format(sDenom))
sNb = sNumerateur

While CDbl(sNb) >= CDbl(sDenom)
    If CDbl(Left(sNb, iLenDen)) >= CDbl(sDenom) Then
        sTemp = Format(CDbl(Left(sNb, iLenDen)) - CDbl(sDenom))
        sNb = IIf(CDbl(sTemp) = 0, "", sTemp) + Right(sNb, Len(sNb) - iLenDen)
    Else
        sTemp = Format(CDbl(Left(sNb, iLenDen + 1)) - CDbl(sDenom))
        sNb = IIf(CDbl(sTemp) = 0, "", sTemp) + Right(sNb, Len(sNb) - iLenDen - 1)
    End If
Wend

Modulo = CDbl(sNb)

Exit Function

Erreur:
    Modulo = 0
End Function
Commentaire de Arknoth le 06/06/2003 03:51:41

erf G oublié d'enlever le "Format" dans la ligne "Len(Format(sDenom))"
Commentaire de furybond le 25/08/2003 12:26:12

n mod x = n - x * (n x)

Pour travailler sur des grands nombres, il vaudrait mieux conserver ceux-ci en binaires dans des tableux d'integer, et d'ecrire une fonction ToString() pour pouvoir les afficher correctment. Ou alors, conserver 1 digit par indice, ce qui eviterait tous ces appels à left, right, ou mid qui prennent enormement de temps cpu.
Commentaire de furybond le 25/08/2003 13:52:05

l'antislash n'est pas passé : faut lire

n mod x = n - x * (n <division entière> x)
Commentaire de bizmoute le 23/01/2004 01:22:46

Super comme concept...
cependant... t'as essayé ca : multi("16","16") ?

Je ne sais pas si l'erreur est au niveau du processeur, mais ca m'affiche 156 comme résultat... ;oÞ

Si tu as la solution empresse toi de venir la partager stp...
Commentaire de DHKold le 03/02/2004 20:41:50

étrange, moi ca marche correctement
Commentaire de Pingouin le 01/05/2004 12:29:19

Je suis un peu decu ca ne gère pas les nompbres a virgule
Mais sinon tres tres bon boulot Si jamais tu fais quelquechose pour les nombres decimaux averti moi, la j'ai ps le temps de bosser dessus.
Mais bon 9/10 kanm^m parce que la chapeau y a du boulot,

Pingouin
Commentaire de DHKold le 23/07/2004 14:16:47

Je ferai sans doute une amélioration pour supporter les nombre à virgule, mais pour l'instant, j'ai plusieurs client qui attendent leurs scirpts PHP :p
Commentaire de Renfield le 23/07/2004 16:45:48 administrateur CS

J'ai pas touché a tes algos....

mais voici une version qui devrait être sensiblement plus rapide ;)

En quelques mots :
-  TYPER toutes les variables (des Variants, c'est lent)
-  Ne pas recalculer ce qui ne change pas (pgdd & len, par exemple)

Private Function multi(term1 As String, term2 As String)
    Dim total2 As String
    Dim i As Integer, a As Integer
    Dim total As String
    Dim nbr As Integer
    Dim nbr2 As Integer

    Dim nb1 As Integer

    total2 = "0"
    Dim nbd, nbt, nbu As Integer

    Dim L1 As Integer, L2 As Integer
    L1 = Len(term1): L2 = Len(term2)
    For i = 0 To L2 - 1
        nbd = 0
        total = vbNullString
        nbr2 = Mid$(term2, L2 - i, 1)
        For a = 0 To L1 - 1
            nb1 = Mid$(term1, L1 - 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"), total2)
    Next i

    multi = zero(total2)
End Function

Function zero(term1 As String) As String
    Dim i As Integer

    For i = 1 To Len(term1) - 1
        If Mid$(term1, i, 1) <> "0" Then Exit For
    Next i

    zero = Mid$(term1, i)
End Function

Private Function addition(term1 As String, term2 As String)
    Dim nbd, nbt, nbu As Integer
    Dim L1 As Integer, L2 As Integer
    Dim i As Integer
    Dim nb1 As Integer, nb2 As Integer
    Dim total As String

    L1 = Len(term1): L2 = Len(term2)
    If L1 < L2 Then
        term1 = String$(L2 - L1, "0") & term1
        L1 = L2
    ElseIf L1 > L2 Then
        term2 = String$(L1 - L2, "0") & term2
    End If

    For i = 0 To L1 - 1
        nb1 = Mid$(term1, L1 - i, 1)
        nb2 = Mid$(term2, L1 - i, 1)

        nbt = nb1 + nb2 + nbd
        nbd = nbt \ 10: nbu = nbt Mod 10
        total = nbu & total
    Next i
    addition = zero(nbd & total)
End Function

Private Function soustraction(term1 As String, term2 As String)
    Dim mPgdd As Integer:    mPgdd = pgdd(term1, term2)

    If mPgdd = 0 Then
        soustraction = "0"
        Exit Function
    End If

    If mPgdd = 2 Then
        soustraction = "-" & soustraction(term2, term1)
        Exit Function
    End If

    Dim nbd As Integer, nbt As Integer, nbu As Integer

    Dim L1 As Integer, L2 As Integer
    L1 = Len(term1): L2 = Len(term2)

    If L1 < L2 Then
        term1 = String$(L2 - L1, "0") & term1
        L1 = L2
    ElseIf L1 > L2 Then
        term2 = String$(L1 - L2, "0") & term2
    End If

    Dim nb1 As Integer, nb2 As Integer, nbd2 As Integer
    Dim i As Integer
    Dim total As String

    For i = 0 To L1 - 1
        nb1 = Mid$(term1, L1 - i, 1)
        nb2 = Mid$(term2, L1 - i, 1)
        If nb1 - nb2 - nbd2 < 0 Then
            nbd = Abs(nb1 - nb2) \ 10 + 1
            nb1 = nb1 + nbd * 10
        End If
        nbu = nb1 - nb2 - nbd2
        nbd2 = nbd: nbd = 0
        total = nbu & total
    Next i
    soustraction = zero(total)
End Function

Private Function divis(term1 As String, term2 As String, Optional ByRef rest As Boolean)
    Dim total As String:    total = "0"

    Dim L1 As Integer, L2 As Integer
    L1 = Len(term1): L2 = Len(term2)

    Dim nbz As Integer, nbr1 As String

    Do While L1 > L2
        nbz = L1 - L2 - 1
        nbr1 = term2 & String$(nbz, "0")
        term1 = soustraction(term1, nbr1)
        L1 = Len(term1)
        total = addition(total, "1" & String$(nbz, "0"))
    Loop

    Dim i As Integer
    Dim reste As String
    For i = 1 To 20
        Select Case pgdd(term1, term2)
            Case 0
                total = addition(total, "1")
                reste = "0"
                Exit For
            Case 1
                term1 = soustraction(term1, term2)
                total = addition(total, "1")
            Case 2
                reste = term1
                Exit For
        End Select
    Next i

    rest = (0 <> LenB(reste))
    If rest Then total = total & "r" & reste

    divis = zero(total)
End Function

Private Function pgdd(term1 As String, term2 As String) As Integer
    Dim L1 As Integer, L2 As Integer
    L1 = Len(term1): L2 = Len(term2)

    If L1 > L2 Then
        pgdd = 1
        Exit Function
    ElseIf L1 < L2 Then
        pgdd = 2
        Exit Function
    End If

    Dim i As Integer
    For i = 1 To Len(term1)
        L1 = Mid$(term1, i, 1)
        L2 = Mid$(term2, i, 1)

        If L1 > L2 Then
            pgdd = 1
            Exit Function
        ElseIf L1 < L2 Then
            pgdd = 2
            Exit Function
        End If
    Next i
    pgdd = 0
End Function
Commentaire de Renfield le 23/07/2004 17:24:28 administrateur CS

on pourrais même aller un peu plus loin : éviter la réallocation systématique de la chaine total dans les fonctions :

Private Function multi2(term1 As String, term2 As String)
    Dim total2 As String
    Dim i As Integer, a As Integer
    Dim total As String
    Dim nbr As Integer
    Dim nbr2 As Integer

    Dim nb1 As Integer

    total2 = "0"
    Dim nbd, nbt, nbu As Integer

    Dim L1 As Integer, L2 As Integer
    L1 = Len(term1): L2 = Len(term2)

    Dim Ind As Long

    For i = 0 To L2 - 1
        nbd = 0
        total = vbNullString
        nbr2 = Mid$(term2, L2 - i, 1)
        total = Space$(L1)
        For a = 0 To L1 - 1
            Ind = L1 - a
            nb1 = Mid$(term1, Ind, 1)
            nbt = nb1 * nbr2 + nbd
            nbd = nbt \ 10: nbu = nbt Mod 10
            Mid$(total, Ind, 1) = nbu
        Next a
        total2 = addition2(nbd & total & String$(i, "0"), total2)
    Next i

    multi2 = zero2(total2)
End Function

Private Function addition2(term1 As String, term2 As String)
    Dim nbd, nbt, nbu As Integer
    Dim L1 As Integer, L2 As Integer
    Dim i As Integer
    Dim nb1 As Integer, nb2 As Integer
    Dim total As String

    L1 = Len(term1): L2 = Len(term2)
    If L1 < L2 Then
        term1 = String$(L2 - L1, "0") & term1
        L1 = L2
    ElseIf L1 > L2 Then
        term2 = String$(L1 - L2, "0") & term2
    End If

    Dim Ind As Integer
    total = Space$(L1)
    For i = 0 To L1 - 1
        Ind = L1 - i
        nb1 = Mid$(term1, Ind, 1)
        nb2 = Mid$(term2, Ind, 1)

        nbt = nb1 + nb2 + nbd
        nbd = nbt \ 10: nbu = nbt Mod 10
        Mid$(total, Ind, 1) = nbu
    Next i
    addition2 = zero(nbd & total)
End Function

Private Function soustraction(term1 As String, term2 As String)
    Dim mPgdd As Integer:    mPgdd = pgdd(term1, term2)

    If mPgdd = 0 Then
        soustraction = "0"
        Exit Function
    End If

    If mPgdd = 2 Then
        soustraction = "-" & soustraction(term2, term1)
        Exit Function
    End If

    Dim nbd As Integer, nbt As Integer, nbu As Integer

    Dim L1 As Integer, L2 As Integer
    L1 = Len(term1): L2 = Len(term2)

    If L1 < L2 Then
        term1 = String$(L2 - L1, "0") & term1
        L1 = L2
    ElseIf L1 > L2 Then
        term2 = String$(L1 - L2, "0") & term2
    End If

    Dim nb1 As Integer, nb2 As Integer, nbd2 As Integer
    Dim i As Integer
    Dim total As String
    total = Space$(L1)

    Dim Ind As Integer
    For i = 0 To L1 - 1
        Ind = L1 - i
        nb1 = Mid$(term1, Ind, 1)
        nb2 = Mid$(term2, Ind, 1)
        If nb1 - nb2 - nbd2 < 0 Then
            nbd = Abs(nb1 - nb2) \ 10 + 1
            nb1 = nb1 + nbd * 10
        End If
        nbu = nb1 - nb2 - nbd2
        nbd2 = nbd: nbd = 0
        Mid$(total, Ind, 1) = nbu  '& total
    Next i
    soustraction = zero(total)
End Function
Commentaire de Renfield le 23/07/2004 17:26:16 administrateur CS

il faudrais tester une fois compilé, mais le résultat de ce simple test parle de lui même :

Private Sub Form_Load()
    Dim Start As Long
    Start = Timer
Call multi2("746763632285821141342037895248750770669356191541743733602285581084104072666524545047064932316121171343059995258783801997265629154474676363228582114134203789524875077066935619155417437336022858108410407266652454504706493231612117134305599952587838019726562915447467636322858211413420378952487550770669356191541743733602285810841040726665245450470649322316121171343059995258783801972656291544746763632285821141134203789524875077066935619154174373360228581084104072666552454504706493231" & _
"61211713430599952587838019726562915447467763632285821141342037895248750770669356191541743733602285881084104072666524545047064932316121171343059995258783801977265629154474676363228582114134203789524875077066935619154417437336022858108410407266652455515717494332613127245316009063598848010737672026558578647323968212413431379053598511871770466292542854844602396821941140837675256551571749433326131272453160906359884801073767202655857864732396821241334313790535985187177046629254285484460239682194114083767525655157174943326131272453160", _
"68596105536476237159640886658923718294398667092402839441179881257041327422001125735162772203142673516307553314590384666005533446906859610553647623715964088665892371829439866709924028394411798125704132742200112573516277220314267351630775533145903846600553344690685961055364762371596408866589233718294398667092402839441179812570413274220011257351627722203142673516307553314590384660055334469068596105536476237115964088665892371829439866709240283944117981257041327422" & _
"000112573516277220314267351630755331459038466005533446906859961055364762371596408866589237182943986670924028394411798112570413274220011257351627722031426735163075533145903846600055334469068596105536476237159640886658923718294398667092240283944117981257041327422001126745263873203243684627318665332569149576116644556917950611664758624725074199775893488283044997781034029305422708136715133852200123674526387320032436846273186533256914957611664455691795061166475862472550741997758934828304499778103402930542270813671513385220012367452638732032436846273186")
    Debug.Print "New : " & Timer - Start
    Start = Timer
Call multi("746763632285821141342037895248750770669356191541743733602285581084104072666524545047064932316121171343059995258783801997265629154474676363228582114134203789524875077066935619155417437336022858108410407266652454504706493231612117134305599952587838019726562915447467636322858211413420378952487550770669356191541743733602285810841040726665245450470649322316121171343059995258783801972656291544746763632285821141134203789524875077066935619154174373360228581084104072666552454504706493231" & _
"61211713430599952587838019726562915447467763632285821141342037895248750770669356191541743733602285881084104072666524545047064932316121171343059995258783801977265629154474676363228582114134203789524875077066935619154417437336022858108410407266652455515717494332613127245316009063598848010737672026558578647323968212413431379053598511871770466292542854844602396821941140837675256551571749433326131272453160906359884801073767202655857864732396821241334313790535985187177046629254285484460239682194114083767525655157174943326131272453160", _
"68596105536476237159640886658923718294398667092402839441179881257041327422001125735162772203142673516307553314590384666005533446906859610553647623715964088665892371829439866709924028394411798125704132742200112573516277220314267351630775533145903846600553344690685961055364762371596408866589233718294398667092402839441179812570413274220011257351627722203142673516307553314590384660055334469068596105536476237115964088665892371829439866709240283944117981257041327422" & _
"000112573516277220314267351630755331459038466005533446906859961055364762371596408866589237182943986670924028394411798112570413274220011257351627722031426735163075533145903846600055334469068596105536476237159640886658923718294398667092240283944117981257041327422001126745263873203243684627318665332569149576116644556917950611664758624725074199775893488283044997781034029305422708136715133852200123674526387320032436846273186533256914957611664455691795061166475862472550741997758934828304499778103402930542270813671513385220012367452638732032436846273186")
    Debug.Print "Old : " & Timer - Start
End Sub
Commentaire de DHKold le 19/09/2004 18:41:44

ok, je vais voir ca
Commentaire de MadM@tt le 26/11/2004 23:57:50

Merci pour ces fonctions elle vont m'etre très utiles je pense, par contre je suis déçu que ça commence à ramer à environ 1000 chiffres.... Moi qui voulait traiter des nombres possedant des milliers voir des millions, mais bon on peut pas tout avoir :p
Commentaire de MadM@tt le 30/11/2004 19:50:53

Attendez vous n'auriez pas la racine carré ???
Commentaire de Pingouin le 30/11/2004 20:37:35

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 ?
Commentaire de MadM@tt le 30/11/2004 21:17:51

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 @ +
Commentaire de Pingouin le 01/12/2004 20:22:31

Ok ben ya pas de koi lol. Bon courage et jspr voir tres bientot le resultat...
Commentaire de rambc le 28/02/2005 18:23:26

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
Commentaire de Renfield le 01/03/2005 09:20:02 administrateur CS

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é !)

Derniers blogs

Mini Sondage

Derniers logiciels

Comparer les prix

Mes RSS

Stats

Divers

Trouver une ressource (Nouvelle version du moteur, plus rapide & pertinent, essayez le !)

ENSEMBLE DE FONCTION MATHÉMATIQUE (POUR TRES GRAND NOMBRES)

Information sur la source

Description

Source

Conclusion

Sources du même auteur

Sources de la même categorie

Commentaires

Ajouter un commentaire

CONCOURS DE PROG !

Pub

Besoin d'icones ?

Appels d'offres

Côté IT