BIGMATH - OPERATIONS SUR DES TRES GRANDS NOMBRES

cuq Messages postés 345 Date d'inscription mardi 3 juin 2003 Statut Membre Dernière intervention 21 mars 2008 - 6 oct. 2005 à 14:53
Renfield Messages postés 17287 Date d'inscription mercredi 2 janvier 2002 Statut Modérateur Dernière intervention 27 septembre 2021 - 30 juil. 2009 à 16:57
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/34102-bigmath-operations-sur-des-tres-grands-nombres

Renfield Messages postés 17287 Date d'inscription mercredi 2 janvier 2002 Statut Modérateur Dernière intervention 27 septembre 2021 71
30 juil. 2009 à 16:57
les projets s'enchainent et fichtre le temps passe, j'ai toujours ca en chantier, en attente de mon interet changeant (mais c'est cyclique ^^)
us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 10
30 juil. 2009 à 11:59
Bonjour Renfield, et aux autres...

Est-ce que le temps est venu ? ... maintenant...

Très amicalement à tous,
Us.
Renfield Messages postés 17287 Date d'inscription mercredi 2 janvier 2002 Statut Modérateur Dernière intervention 27 septembre 2021 71
28 févr. 2008 à 17:10
Bonjour, je voulais juste signaler qu'en ce moment, je crypte...

j'ai donc, a mon tour besoin de pouvoir calculer avec de longs entiers.
dans mon code j'ai actuellement les additions/soustractions, comparaison, et quelques choses du genre.
les performances me semblent pas mal, même avec plus de 200 000 chiffres.

je posterai cela le moment venu.
us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 10
23 oct. 2005 à 15:43
Bonjour à tous,

J'ai étudié très attentivement (et longuement) les différentes versions déjà proposées.

=

Mais avant une réponse sur les tests. Comme déjà dit (le 8/10), j'utilise la petite routine ess() et en mode interprêté.

Pourquoi en interprêté ?
Vous me direz si je me trompe, mais pour moi, j'utilise VBA (Excel), donc mon objectif c'est d'avoir le plus rapide en mode interprêté, puisque c'est de cette façon que j'utilise les fonctions... Et bien sur, pour ceux qui utilise VB6, leur intérêt final, c'est d'avoir le plus rapide en compilé !

Les objectifs n'étant pas les mêmes, pas la peine de se lancer dans un débat stérile, comme j'ai (hélas) lu sur VBF sur le sujet...

Comme l'optimisation fine, dépends de la manière donc on veut utiliser les fonctions, je ne sais plus comment faire pour mettre tout le monde d'accord... En effet, après compilation, les classements s'en trouvent toujours un peu boulverssé...

Pour bien faire, il faut présenter les deux versions, interprêté et compilé... J'ajoute que perso, pour me guider sur l'optimisation je test en priorité en interprêté, avant un test final en compilé... A chacun de voir ! et de dire ce qui est mieux en compilé...

De plus, je ne possède pas VB6, mais VB4... alors j'espère que les classements en compilé seront conservés d'une version à l'autre... (je n'ai pas les moyens de faire mieux, désolé...)

-

Petit changement, pour la suite, j'utilise la "dll" proposé par Warny, qui donne des résultats plus stables que Timer... (bien que, tout à fait similaire en moyenne...) De plus, pour accentuer les différences, je prends maintenant dans ess() la borne 18 au lieu de 17.

=

La dernière version de Warny comporte des bugs.
"Dim t As Long, k As Long, " Virgule en trop...
La boucle IF suivante à "ElseIf" au lieu de "Else"
"offset = lenB(v) - lenB(w)" ne marche pas car v et w sont des tableaux. J'ai remplacé Len par Ubound. Ensuite, il reste encore un bug dans le calcul.

La dernière version de Renfield, ne permet pas toujours un calcul exact si les 2 nombres ont des tailles différentes. La raison vient d'un arrêt prématuré sans report de la retenue. Par exemple : 9999999 + 9 donne 19999998. Dans la version de Warny, la boucle DO sert justement à tenir compte de cette retenue.

=

J'ai essayé de reprendre les 2 versions en les simplifiant au cas d'une somme de deux nombres de même taille, puis de les optimiser pour faire une comparaison avec aussi ma version AGN (qui tient compte correctement des tailles différentes). IL me semble naturel, comme comencer par là, avant de compliquer...

Voici les listing de base (fonctionnel) :

=

Ma première version du début :

=

Function som0(n As String, m As String) As String

Dim temps As Long: temps = GetTickCount

Dim v() As Byte, w() As Byte
Dim t As Long, k As Long

v = "0" & n
w = "0" & m

k = UBound(v) - 1
For t = k To 0 Step -2
v(t) = v(t) + w(t) - 48
If v(t) > 57 Then
v(t) = v(t) - 10
v(t - 2) = v(t - 2) + 1
End If
Next t
som0 = v

MsgBox (GetTickCount - temps) / 1000
End Function

=

Version de Renfield :

=

Function BigSum0(ByRef vn1 As String, ByRef vn2 As String) As String

Dim temps As Long: temps = GetTickCount

Dim x1() As Byte, x2() As Byte
Dim i As Long, nLength2 As Long, nBuffer As Long, nRest As Long

x1 = vn1
x2 = vn2

nLength2 = UBound(x2) - 1
For i = nLength2 To 0 Step -2
nBuffer = x1(i) + x2(i) - 48 + nRest
If nBuffer > 57 Then
x1(i) = nBuffer - 10
nRest = 1
Else
x1(i) = nBuffer
nRest = 0
End If
Next i
If nRest = 0 Then
BigSum0 = x1
Else
BigSum0 = 1 & CStr(x1)
End If

MsgBox (GetTickCount - temps) / 1000
End Function

=

Ici, j'ai inclu nRest 0 dans la boucle IF> gain de temps en évitant de toujours le mettre à zéro. Les variables muettes, ont été mise en Long après plusieurs essais.

=

Version de Warny, où j'ai mis mes lignes en alternatives en remarque car la strucutre est identique.

=

Function som00(n As String, m As String) As String

Dim temps As Long: temps = GetTickCount

Dim v() As Byte, w() As Byte
Dim t As Long, k As Long, result As Long, retenue As Long

v = n
w = m

k = UBound(v) - 1
For t = k To 0 Step -2
result = v(t) + w(t) + retenue - 96 'Warny A
retenue = result \ 10 'Warny A
v(t) = (result Mod 10) + 48 'Warny A

' result = v(t) + w(t) - retenue - 96 'us B
' retenue = (result > 9) 'us B
' v(t) = (result Mod 10) + 48 'Warny B
' v(t) = result + retenue * 10 + 48 'us (alternative moins rapide)
Next t

If retenue = 0 Then 'A
som00 = v
Else
som00 = 1 & CStr(v)
End If

' If retenue Then 'B
' som00 = 1 & CStr(v)
' Else
' som00 = v
' End If

MsgBox (GetTickCount - temps) / 1000
End Function

=

Idem, ici j'ai remis les variables en Long = plus rapide. La dernière retenue a été calquée sur la version de Renfield, donnant un léger gain par rapport à :
v = "0" & n
w = "0" & m

Mon alternative avait donné en cours d'élaboration de meilleurs résultats, puis au final se rélève un poil de rien moins bien... On est ici dans l'ordre du détail, mais je vous l'indique car rien n'empêche qu'une autre petite modif puisse donner un p'tit avantage pour la suite...

=

Ma version AGN, traitant correctement les nb de tailles différentes donc fait un peu plus que les deux versions précédentes.

=

Function AGN2(ByVal nb1 As String, ByVal Nb2 As String) As String
'ADDITION DE 2 GRANDS NOMBRES ENTIERS POSITIFS

Dim temps As Long: temps = GetTickCount

'Variables
Dim Total As String, z As String
Dim V1 As Double, V2 As Double, r As Double, Ret As Long
Dim t As Long, lr As Long, Multiple As Long, L1 As Long, L2 As Long, lgmul As Long
Dim ln10 As Double

ln10 = Log(10)
z = "0"
Multiple = 14

'trouve longueurs
L1 = Len(nb1)
L2 = Len(Nb2)

'Transformation en longueur multiple de Multiple
lgmul = (IIf(L1 < L2, L2, L1) \ Multiple + 1) * Multiple
nb1 = String$(lgmul - L1, z) & nb1
Nb2 = String$(lgmul - L2, z) & Nb2

'Addition
Total = String$(lgmul, z)
For t = lgmul - Multiple + 1 To 1 Step -Multiple
V1 = Mid$(nb1, t, Multiple)
V2 = Mid$(Nb2, t, Multiple)
r = V1 + V2 + Ret
lr = Fix(Log(r + 0.11) / ln10) + 1
If lr Multiple + 1 Then Ret 1 Else Ret = 0
Mid$(Total, t - lr + Multiple, lr) = CStr(r)
Next t

'Boucle de recherche des zéros inutiles dans partie entière et Renvoi du résultat
For t = 1 To Len(Total)
If Mid$(Total, t, 1) <> "0" Then Exit For
Next t
AGN2 = Mid$(Total, t)
If Total "" Then AGN2 "0" 'traite le cas d'un nombre nulle

'Affichage du temps
MsgBox (GetTickCount - temps) / 1000

End Function

=

Voilà, les résultats du temps obtenu :

........|VBA.. | VB4 IDE | VB4 EXE
som0 | 6,14 | 7,8...... | 7,17
bigsum0|4,7 | 4,4...... | 3,73
som00 | 4,9 | 4,6.......| 4,22
agn2 .| 3,96 | 3,8.......| 4,16

Donc en version IDE, AGN2 est la plus rapide. Une fois compilé c'est celle de Renfield qui passe en tête. Mais il reste tout de même à leur faire tenir compte correctement des tailles différentes.

La dernière version de Warny, même si elle donne pas encore correctement le bon calcul, si les 2 nb sont de tailles différentes donne en terme de temps :

........|VBA.. | VB4 IDE | VB4 EXE
som . | 5,98 | 5,43...... | 4,80

=

Amicalement,
Us.
cs_Warny Messages postés 473 Date d'inscription mercredi 7 août 2002 Statut Membre Dernière intervention 10 juin 2015
22 oct. 2005 à 09:52
il y a un bug dans mon code précédent, je ne reporte pas la retenue au delà du premier chiffre du nombre le plus court :


Function som(n As String, m As String) As String

Dim v() As Byte
Dim w() As Byte
Dim t As Long, k As Long,

dim result as Integer, retenue As Integer
dim offset as long

if len(n) > len(m) then
v = "0" & n
w = m
elseif
v = "0" & m
w = n
end if

offset = lenB(v) - lenB(w) 'positif parce len(v) > len(w)

k = UBound(w) - 1
retenue = 0
For t = k To 2 Step -2
result = v(t + offset) + w(t) + retenue - 96
retenue = result \ 10
v(t + offset) = (result mod 10) + 48
Next t
t = offset
do until retenue = 0
result = v(t) + retenue - 48
retenue = result \ 10
v(t) = (result mod 10) + 48
t = t - 2
loop
som = v
End Function
Afficher les 39 commentaires