BIGMATH - OPERATIONS SUR DES TRES GRANDS NOMBRES

Signaler
Messages postés
345
Date d'inscription
mardi 3 juin 2003
Statut
Membre
Dernière intervention
21 mars 2008
-
Messages postés
17288
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
27 septembre 2021
-
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

Messages postés
17288
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
27 septembre 2021
71
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 ^^)
Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
10
Bonjour Renfield, et aux autres...

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

Très amicalement à tous,
Us.
Messages postés
17288
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
27 septembre 2021
71
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.
Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
10
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.
Afficher les 39 commentaires