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
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
https://codes-sources.commentcamarche.net/source/34102-bigmath-operations-sur-des-tres-grands-nombres
30 juil. 2009 à 16:57
30 juil. 2009 à 11:59
Est-ce que le temps est venu ? ... maintenant...
Très amicalement à tous,
Us.
28 févr. 2008 à 17:10
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.
23 oct. 2005 à 15:43
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.
22 oct. 2005 à 09:52
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
21 oct. 2005 à 21:25
vous etes en train de me faire un super boulot ! continuez !
j'ai pas de compilo sous la main... degoute :o(
je suis dans un cyber cafe a sevilla. des que j'ai VB, je me relance dans le travail d'optimisation que vous m'aurez grandement facilite ! merci.
21 oct. 2005 à 11:53
Private Declare Function GetTickCount Lib "kernel32.dll" () As Long
et
Dim temps As Long
temps = GetTickCount
'code
MsgBox (GetTickCount - temps) / 1000
GetTickCount renvoie le nombre de millisecondes écoulé depuis l'allumage de la machine et est réinitialisé tous les 42,7 jours.
La méthode avec un calcul est 30% plus rapide que la méthode avec un if
soit 0.65s et 0.42s sur ma machine avec un nombre de un million de chiffre
21 oct. 2005 à 10:41
Il faudrait donc enlever ces deux lignes et remplacer les deux suivantes par :
v = "0" & n
w = "0" & m
et en plus ça élimine une affectation (on va y arriver)
21 oct. 2005 à 10:03
n = "0" & n
m = "0" & m
là, tu modifie tes paramètres d'entrée (ByRef)
21 oct. 2005 à 09:32
Function som(n As String, m As String) As String
temps = Timer
Dim v() As Byte
Dim w() As Byte
Dim t As Long, k As Long, retenue As Long
n = "0" & n
m = "0" & m
v = n
w = m
k = UBound(v) - 1
retenue = 0
For t = k To 2 Step -2
result = v(t) + w(t) + retenue - 96
retenue = result \ 10
v(t) = (result mod 10) + 48
Next t
v(0) = retenue + 48 ' -- je l'ai loupé dans le code précédent
som = v
MsgBox Timer - temps
End Function
21 oct. 2005 à 07:26
21 oct. 2005 à 07:24
il est couteux de faire des v(t + 2) ou même v(t) à tour de bras
(regarde dans le listing que j'ai proposé, la variable nBuffer)
tu disais avoir mis 3.6 secondes avec le code que j'ai proposé...
reprend le, et enlève la partie conversion de l'Unicode, pour jouer sur un tableau certes deux fois plus grand, mais sans ces deux étapes de conversion
ce qui donnerait donc :
'# Les chiffres soumis doivent être entiers et positifs.
'# Aucune vérification n'est faite sur le contenu
Public Function BigSum(ByRef vn1 As String, ByRef vn2 As String) As String
Dim x1() As Byte
Dim x2() As Byte
Dim nRest As Byte
Dim nLength2 As Long
Dim nDiff As Long
Dim i As Long
'# Variable utilisée afin de limiter les accès aux tableaux
Dim nBuffer As Long
'# x1 contiendra la chaine la plus longue...
If LenB(vn1) > LenB(vn2) Then
x1 = vn1
x2 = vn2
Else
x1 = vn2
x2 = vn1
End If
nLength2 = UBound(x2) - 1
nDiff = UBound(x1) - nLength2 - 1
For i = nLength2 To 0 Step -2
'# On stocke le calcul dans une variable intermédiaire
nBuffer = x1(i + nDiff) + (x2(i) - 48) + nRest
nRest = 0
'# si > 9
If nBuffer > 57 Then
'# On décrémente, et on place dans le tableau
x1(i + nDiff) = nBuffer - 10
'# Un reste sera appliqué
nRest = 1
Else
'# On affecte simplement
x1(i + nDiff) = nBuffer
End If
Next i
If nRest = 0 Then
'# Pas de reste...
BigSum = x1
Else
'# On ajoute un "1" devant le chiffre
BigSum = 1 & CStr(x1)
End If
End Function
20 oct. 2005 à 21:53
J'ai repris le code proposé par Warny. Voici le listing :
=
Function som(n As String, m As String) As String
temps = Timer
Dim v() As Byte
Dim w() As Byte
Dim t As Long, k As Long, retenue As Long
n = "0" & n
m = "0" & m
v = n
w = m
k = UBound(v) - 1
For t = k To 0 Step -2
v(t) = v(t) + w(t) - 48
Next t
For t = k - 2 To 0 Step -2
retenue = (v(t + 2) - 48) \ 10
v(t + 2) = v(t + 2) - (retenue * 10)
v(t) = v(t) + retenue
Next t
som = v
MsgBox Timer - temps
End Function
=
Après le test, j'ai obtenu 4,6 secondes, donc c'est suprenant... L'optimisation serait sûrement la suppression des deux boucles, en une seule.
Une idée ?
Amicalement,
Us.
18 oct. 2005 à 00:27
J'ai testé "BigSum", de la même façon que les autres avec "ess()" proposé l'autre fois. J'arrive à 3,6 secondes. Donc, dans l'absolu c'est pas mal, mais pas le plus rapide. Ce qui plombe tout, c'est le IF dans la boucle, comme pour ma version...
Pour le code de Warny, il a tout les atouts pour être le plus rapide. Pas de IF en autre. En terme d'optimum, c'est idéal. Seul bémol, il faut 2 boucles FOR tel que proposé. Mais, il me semble qu'on peut les réduire à une seul boucle, en "devançant" les indices du résultat, avant le calcul de la retenue (en espèrant d'être clair)... Comme tu confirmes la justesse du code de la retenue, c'est que j'ai pas dû bien comprendre. JE tenterai de reprendre ton code dans qlq jours (j'suis un peu "surbooké" en ce moment) pour le maîtriser puis le tester...
Très amicalement,
Us.
17 oct. 2005 à 10:23
les performance obtenues me semblent satisfaisantes...
'# Les chiffres soumis doivent être entiers et positifs.
'# Aucune vérification n'est faite sur le contenu
Public Function BigSum(ByRef vn1 As String, ByRef vn2 As String) As String
Dim x1() As Byte
Dim x2() As Byte
Dim nRest As Byte
Dim nLength2 As Long
Dim nDiff As Long
Dim i As Long
'# Variable utilisée afin de limiter les accès aux tableaux
Dim nBuffer As Long
'# x1 contiendra la chaine la plus longue...
If LenB(vn1) > LenB(vn2) Then
x1 = StrConv(vn1, vbFromUnicode)
x2 = StrConv(vn2, vbFromUnicode)
Else
x1 = StrConv(vn2, vbFromUnicode)
x2 = StrConv(vn1, vbFromUnicode)
End If
nLength2 = UBound(x2)
nDiff = UBound(x1) - nLength2
For i = nLength2 To 0 Step -1
'# On stocke le calcul dans une variable intermédiaire
nBuffer = x1(i + nDiff) + (x2(i) - 48) + nRest
nRest = 0
'# si > 9
If nBuffer > 57 Then
'# On décrémente, et on place dans le tableau
x1(i + nDiff) = nBuffer - 10
'# Un reste sera appliqué
nRest = 1
Else
'# On affecte simplement
x1(i + nDiff) = nBuffer
End If
Next i
If nRest = 0 Then
'# Pas de reste...
BigSum = StrConv(x1, vbUnicode)
Else
'# On ajoute un "1" devant le chiffre
BigSum = 1 & StrConv(x1, vbUnicode)
End If
End Function
17 oct. 2005 à 08:53
pour mémoire
retenue = (chresult(i+1) - &h30) \ 10 '&h30 est la valeurs ascii de 0 '\est la division entière
chresult (i+1) = chresult(i+1) - (retenue * 10)
chresult (i) = chresult(i) + retenue
Le gros problème du if, c'est qu'il ne prend pas le même temps quand le test est juste ou faux (il en prend beaucoup plus quand il est faux)
15 oct. 2005 à 14:08
=
D'abord juste un petit point sur les histoires de l'unicode. J'ai pu vérifier le rôle du deuxième octet. Il sert à définir les caractères étendus tels qu'on peut les visualiser dans Word avec les caractères spéciaux (lantin-1, Ciryllique, Grec, etc...)
La fonction StrConv proposée supprime le deuxième caractère, et StrConv ( MaChaine , vbUnicode ) rajoute un deuxième octet à chaque caractère... bon voilà...
=
Maintenant j'ai fait un petit test pour le calcul de l'addition avec les "byte()", dont voici le codage simplifié :
(juste le squelette, donc les 2 nb doivent être de même longueur, et entier positif)
=
Function som(n As String, m As String) As String
temps = Timer
Dim v() As Byte
Dim w() As Byte
Dim t As Long, k As Long
n = "0" & n
m = "0" & m
v = n
w = 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
som = v
MsgBox Timer - temps
End Function
=
Avec le test proposé la dernière fois, cette fonction met 3 secondes... Et le même test avec ma version perso AGN (un peu plus optimisée que celle de santiago, mais reposant sur les mêmes principes) met 2,6 secondes... donc nettement plus rapide car elle prend en charge toutes les opérations sur les nombres (recadrage des longueurs, virgules, etc...)
Je l'ai aussi essayée avec conversion en Ascii, encore un poil de presque rien moins rapide...
Le vrai souci, c'est le If dans la boucle qui plombe tout. IL faudrait arriver à remplacer le If par un calcul direct, comme le codage de principe de Warny, mais, sauf erreur, il n'est pas juste...
Une idée ?
Très amicalement,
Us.
14 oct. 2005 à 10:24
Partant sur cette base, plutôt qu'avec des String, les performances s'en ressentiront, et l'algo reste fort similaire
14 oct. 2005 à 10:22
Elle effectivement est tout à fait adapté à l'utilisation actuelle.
Pour info : elle sert à avoir un tableau ascii (1 caractère 1 octet) plutot qu'un tableau unicode (1 caractère 2 octets)
14 oct. 2005 à 10:16
TabByte = StrConv ( MaChaine , vbFromUnicode )
14 oct. 2005 à 07:53
Ta chaîne de caractère String est en unicode, les caractères sont codés sur 16 bits. Ca explique les impairs. Le vb n'est toutefois pas capable d'afficher ces caractères étendus (sauf ceux accentués, je t'invite à faire l'essai).
Je ne sais absolument plus lequel est l'octet de poids fort, mais effectivement tu peux t'en servir pour les retenus (mais je pense que tu ne devrais pas en avoir besoin si tu poses ton opération comme à l'école).
Pour la division il faut faire aussi pareil qu'à l'école.
Si tu fais la multiplication je t'indique comment calculer une puissance avec le minimum de calculs.
13 oct. 2005 à 23:09
Accéder à une string directement grâce à une référence dans un tableau déclaré en Byte, m'étais totalement inconnu. Cela ouvre effectivement une nouvelle perspective, très intéressante.
Néanmoins, le code qui tu proposes (pour la compréhension), sauf erreur, me semble un peu approximatif. ( Byte() n'existe pas dans cette syntaxe, l'indice 1 semble ne pas bien correspondre au caractère 1)
Une version correcte que j'ai établi de ton exemple :
=
Dim toto() As Byte
Dim tutu As String
tutu = "une chaine"
toto = tutu
MsgBox toto
MsgBox toto(0) 'affiche 117 : soit la valeur ascii de u
toto(0) = 32 'remplace le 1er caractère par espace code 32 en ascii
MsgBox toto
toto(2) = 32 'remplace le second caractère
MsgBox toto
toto(4) = 32 'remplace le troisième
MsgBox toto
=
Mais là, une petite question. De toute évidence, les caractères de la chaine tombent sur les indices pairs. Les indices impairs servent finalement à quoi ? (jeu étendu ?)...
...Une remarque intéressante, c'est qu'on peut stocker dans les indices impairs les retenues pour les opérations comme la multiplication...
Bon, je testerai prochainement une version pour l'addition, en comparaison avec celle que j'ai déposée. Et à la réflexion, il est fortement probable que la rapidité s'en trouve accru...
Merci, et A+
Us.
13 oct. 2005 à 08:44
13 oct. 2005 à 08:43
Dim tutu as String
tutu = "une chaine"
toto = tutu
msgbox toto(1)
toto(1) = 32 'espace
msgbox toto
ca me permet de manipuler les valeurs directement sans passer par un mid$, comme tu ne dépasses pas la valeur 128 (ascii étendu) la manipulation de la chaine ne posera pas de problème
sinon pour ajouter deux chiffres avec retenue tu fais :
chresult est le résultat
ch1 et ch2 sont les nombre à additionner 'imagine la multiplaction
decallage1 et decallage2 sont les décallages pour mettre les nombres l'un en face de l'autre
bien sûr il faut gérer les bornes de ch1 et ch2 ou les recaller avant calcul
for i = lbound (chresult) to ubound(chresult)
chresult(i) = ch1(i + decallage1) + ch(i + decallage2) - &h30 '&h30 est la valeurs ascii de 0
next
ensuite quand tu as calculé ton resultat, tu calcules les restenues
for i = ubound (chresult) -1 to lbound(chresult) step - 1
retenue = (chresult(i+1) - &h30) \ 10 '&h30 est la valeurs ascii de 0 '\est la division entière
chresult (i+1) = chresult(i+1) - (retenue * 10)
chresult (i) = chresult(i) + retenue
next
12 oct. 2005 à 22:38
Votre remarque m'intéresse. Pouvez-vous me donner un code exemple (même simplifié), ou une source dépossée, que je puisse tester pour l'addition...
Amicalement,
Us.
12 oct. 2005 à 09:49
de même, ca évite les concaténations ( => n Allocations de mémoire)
et les découpage (Mid$ & Co => Allocation inutiles)
et en plus, on occupera moins de place en mémoire
12 oct. 2005 à 08:50
Ca peut se manipuler a peu près comme une chaîne, mais avec l'assurance de pouvoir contrôler ses éléments.
12 oct. 2005 à 01:03
en effet, VB travaille en Unicode en interne...
les buffers sont donc deux fois plus grand que ce qui est necessaire
10 oct. 2005 à 22:34
J'ai dit une petite bêtisse, avec Str$. En effet, Str$ converti un Long en String. Ici, SubSum est un Double, c'est donc la fonction CStr qui faut utiliser... Après, plusieurs tests, prendre CStr, ou rien mettre, donne exactement la même durée (absolument aucune différence !)... Donc met CStr, car si le code est compilé, selon les remarques de Warny, cela soulagera le compilateur...
Ceci dit, il semble que VB s'était bien comporté avec Str sans faire d'erreur... c'est presque bizarre... mais bon...
A+
Us.
10 oct. 2005 à 01:51
j'ai pas encore tout lu, mais je prendrais le temps.
je reponds juste rapidement a la premiere question que j'ai lu.
desole de commenter mes code en anglais : je suis moitie espagnol, moitie francais, mais j'ai apris a programmer en anglais et j'ai travaille 2 ans pour Electronic Arts Video Games. je pourrais traduire sans difficultes en francais et en espagnol, mais comme j'echange encore avec des collegues en anglais, c'est plus facile pour moi de garder cette langue. encore desole !
8 oct. 2005 à 21:29
Us.
8 oct. 2005 à 21:19
Oui, tu as raison ! une erreur interne est générée... Puisqu'on fait une égalité entre deux types différents. Mais ici, le traitement interne de l'erreur, est plus rapide que le traitement déclaré des types...
=
Si on voulait être tout à fait "propre" sur le code, alors il faudrait écrire les deux lignes :
SubNum1 Val(Mid$(Number1, I, SubLen)) à la place de : SubNum1 Mid$(Number1, I, SubLen) que je viens de proposer.
et
Mid$(SumNumber, I - Lr + SubLen + 1, Lr) Str$(SubSum) à la place de Mid$(SumNumber, I - Lr + SubLen + 1, Lr) SubSum , que je viens de proposer.
Ainsi, les types sont respectés... mais on perds un peu de temps... et mes remarques étaient justement orientées "rapidité", et rien d'autre... J'aurais peut-être dû mieux le préciser, que j'utilisais finalement une "sorte" d'astuce...
De plus, j'ajoute que ce n'est peut-être pas vrai dans tous les cas. Vigilence et Précaution, donc s'imposent !
=
Pour preuve, j'ai réalisé un petit test :
Le petit programme suivant va créer un grand nb, qui sera additionné à lui-même... LE temps est mesuré dans la fonction sumnumber, avec en début de code : "temps=Timer"; puis en fin de code : "Msgbox Timer-temps" ... Ainsi, on ne mesure vraiment que la fonction.
=
Sub ess()
'Fabrique un grand nb
Dim nb1 As String, t As Long
nb1 = "123456578901"
For t = 1 To 17
nb1 = nb1 & nb1
Next t
'Fait nb1+nb1
Dim resultat As String
resultat = SumNumber(nb1, nb1)
'Longueur du nb
MsgBox " l=" & Len(nb1)
End Sub
=
LE nb généré fait 1 572 864 chiffres. (Rq : si vous voulez augmenter la taille de ce chiffre, faites attention à la borne supérieure 17 de la boucle, car en écrivant 18, on multiple par 2 la longueur de ce nb, c'est exponentiel !)
Le temps selon ma version proposé au début (en générant des erreurs internes) est de 4 secondes environ, sur mon antiquité.
Le temps si on respecte les types avec les instructions citées ci-dessus (val et str$) est de 6 secondes environ.
J'ai fait ce test en mode interprété, mais je pense qu'une fois compilé, le sens du classement doit-être identique... Enfin, je crois... Qui va me donner tord ! JE lance le concours ! (J'suis en forme, ce soir, dites donc... :-); )
Très amicalement,
Us.
8 oct. 2005 à 19:58
Toutes tes remarques sont justes sauf une : la [1]
Il faut toujours faire des conversion explicites en VB.
En fait si tu fais
Dim toto as Double
Dim tutu as String : Tutu = "123.456"
toto = tutu
Ton compilateur va le compiler tel quel
Quand il tombe sur "toto = tutu" il fait une erreur (type incompatible)
mais comme le vb est gentil, il va corriger cette erreur et verifier qu'il peut faire la conversion
Résultat : une affectation, une erreur, une conversion -> une super dépense d'instructions (l'erreur oblige en pus à revenir en arrière sur l'execution)
Si tu fait :
Dim toto as Double
Dim tutu as String : Tutu = "123.456"
toto = CDbl(Val(tutu)))
Le vb va faire directement la conversion sans passer par les erreurs.
Résultat : deux conversions
Le vb est un langage de très haut niveau qui fait des corrections automatiques. Il faut toujours imaginer les instructions qu'on écrirait en C pour obtenir le programme le plus performant. Or en C, les conversions seraient explicites.
8 oct. 2005 à 15:10
Je me suis concentré sur ton calcul de l'addition, et j'ai essayé de trouver les améliorations à apporter pour augmenter la rapidité.
Mais avant une petite critique, que j'ai déjà fait à d'autres sources, qui m'engage que moi. Je trouve domageable d'écrire en anglais, surtout pour les remarques... m'enfin...
Voici, qlq remarques que je peux faire :
[1]
Tu sembles utiliser la fonction Cdec, pour convertir une string en valeur. La bonne fonction dédiée à cela est VAL.
donc :
SubNum1 = CDec(Mid$(Number1, I, SubLen))
devient :
SubNum1 = Val(Mid$(Number1, I, SubLen))
Ensuite, toujours sur SubNum1, tu peux te dispenser d'utiliser VAL. Pourquoi ? parce que tu as déclaré SubNum1 en Double, avec :
Dim SubNum1 as double
Ainsi, si tu fais :
SubNum1 = Mid$(Number1, I, SubLen)
VB va automatiquement convertir ta chaine en nombre, en interne. Un peu moins de fonction c'est toujours un poil plus rapide (surtout hors calcul).
[2]
LA déclaration SubCarry pour la retenue est en double. Or, elle ne peut prendre comme valeur que -1,0 ou 1. Donc le type Long est suffisant.
[3]
La ligne la plus gourmande en temps à optimiser impérativement :
Mid$(SumNumber, I, SubLen + 1) = Format(SubSum, String$(SubLen + 1, "0"))
Déjà Format, existe en format string uniquement, au lieu de Variant, avec Format$ ... c'est presque pas visible sur l'exécution sauf probablement sur des nb gigantesques.
Le mieux, c'est de trouver un moyen de ne pas utiliser de fonction. Par exemple, si tu testes sans rien avec :
Mid$(SumNumber, I, SubLen + 1) = SubSum
tu vas voir un très grand changement dans la rapidité. Environ 3 fois plus rapide. Bien sur, ici le résultat serait faux. IL faut ré-ajuster la position dans Mid$...
ET là, on retombe sur mon code (cité en intro)... Je ne sais pas faire mieux ! :-);
Je te livre le code où j'ai fait cette modification. (c'est fonctionnel, mais incomplet car je n'ai pas traité les cas des nb négatifs) :
=
'Initialize Result (1 digit longer than numbers)
SumNumber = String$(NLen1 + 1, "0")
Dim Lr As Long, ln10 As Double
ln10 = Log(10)
'Calculate sum.
For I = NLen1 - SubLen + 1 To 1 Step -SubLen
SubNum1 = Mid$(Number1, I, SubLen)
SubNum2 = Mid$(Number2, I, SubLen)
Select Case SumType
Case 0 ' A+B
SubSum = SubNum1 + SubNum2 + SubCarry
If SubSum < 10 ^ SubLen Then SubCarry 0 Else SubCarry 1
Lr = Fix(Log(SubSum + 0.11) / ln10) + 1
Mid$(SumNumber, I - Lr + SubLen + 1, Lr) = SubSum
Case 1 ' A-B
SubSum = SubNum1 - SubNum2 + SubCarry
SubCarry = IIf(SubSum < 0, -1, 0)
If SubSum < 0 Then SubSum = SubSum + 10 ^ SubLen
Mid$(SumNumber, I, SubLen + 1) = Format$(SubSum, String$(SubLen + 1, "0"))
Case 2 '-A+B
SubSum = -SubNum1 + SubNum2 + SubCarry
SubCarry = IIf(SubSum < 0, -1, 0)
If SubSum < 0 Then SubSum = SubSum + 10 ^ SubLen
Mid$(SumNumber, I, SubLen + 1) = Format$(SubSum, String$(SubLen + 1, "0"))
End Select
Next I
=
La mesure du temps, me donne avec ta version initiale, pour la somme de deux nb d'environ 32000 chiffres, 0.16 seconde. Avec ma modification j'obtiens 0.05 seconde; soit en gros 3 fois plus rapide. La mesure du temps n'étant pas très fine, il ne faut pas trop se formalisé, disons que cela montre que c'est plus rapide, sans autre prétention...
[4]
LE "select case" est testé à chaque incrémentation de I dans la boucle FOR. Faire l'inverse éviterait ce test, et potentiellement un gain de temps. (j'ai pas regardé ce que cela donne, mais cela me semble logique.)
En clair, au lieu de faire :
FOR I=... TO ...
SELECT CASE
CASE 0
...
CASE 1
...
CASE 2
...
END SELECT
NEXT I
faire :
SELECT CASE
CASE 0
FOR I=... TO ... NEXT I
CASE 1
FOR I=... TO ... NEXT I
CASE 2
FOR I=... TO ... NEXT I
END SELECT
=
Voilà déjà...
Amicalement,
Us.
7 oct. 2005 à 08:26
Number() As Byte
avec Number(n)= 0 à 9 pour les chiffres proprement dit
Number(n) = 128 pour le signe + ou -
Number(n) = 255 pour la position de la virgule
voir même deux tableaux par chiffre : 1 pour la partie entiere, l'autre pour la partie decimal, et un marqueur pour le signe.
Après ya juste a coder une fonction qui converti de string en tableau de bytes pour l'interface (un bon vieux for...next + select case + mid$ suffit) mais toute les opérations maths doivent être fait en octet direct, pas en string!
quote : It is faster to split Number in String rather than in an Array
Ca, lorsque tu compiles ton code c'est pas sûr. Et sinon, utilise l'api RtlMoveMemory pour dupliquer des parties de tableaux.
Ce code à un grand potentiel d'optimisation :)
6 oct. 2005 à 23:06
Je découvre tout juste ton code, qui recèle surement pas mal de chose intéressante, que je regarderai plus en détail ce week-end... Néanmoins, d'emblé si la vitesse est un de tes critères, je pense déjà avoir vu des petites choses, qui sont optimisables...
Par exemple, IIF ou Select Case , sont plus long que IF... ELSE IF... END IF (qu'on peut toujours utiliser à la place)... La boucle DO WHILE.... LOOP est un peu moins rapide que DO... LOOP WHILE... etc... bon, bon... j'arrête là, c'est juste en passant... Je repasserai... non pas les chemises ! -:);
Amicalement,
Us.
6 oct. 2005 à 16:37
- en gestion des multinationales, on se moque eperdument de la difference entre 100 milliards et 100 milliards + 1, pas en comptabilite.
- peut etre qu'en physique astronomique, on s'inquiete du 15e chiffre significatif (peut etre ?).
mais c'est avant tout au cours de certains calculs que cette precision entre en jeu : si on prend un nombre sans pretention de 8 chiffres et qu'on le met au carre dans un calcul pour le redivier par un autre etc... on va peut etre retomber sur un nombre a 8 chiffres, mais au milieu, on sera passe par un nombre a 16 chiffres.
encore une fois dans ce cas, l'arrondi est minuscule et souvent sans importance, mais si on effectue une comparaison (une verification d'erreur par exemple). l'ordinateur n'ayant pas notre capacite a relativiser, il dira que 1852633.815 est different de 1852633.816 et supposera une erreur la ou il n'y en a pas.
autre exemple, dans excel, meme pour mes comptes, certains totaux atteignent 7 chiffres (dont 2 decimales) ; a force de faire des addition sur des milliers de lignes, excel fait des arrondis etonnant par exemple, une cellule affiche 10243.15 comme resultat d'un calcul et si on la copie par valeur, on constate qu'excel a stocke la valeur 10243.1500000002 dans sa memoire (et je ne sais pas pourquoi) et si on fait une verification de solde, forcement, il dit que c'est faux.
je crois qu'il y a une derniere application, et certainement pas des moindre, c'est qu'il faut apprendre, il faut s'entrainer, et realiser ce genre de code, c'est un peu comme faire une dissertation sur l'importance de la femme dans les tragedies grecques antiques. j'appelerais ca un cas d'ecole.
j'espere avoir assouvi tes interrogations et ne pas avoir trop parle.
cordialement
santiago
6 oct. 2005 à 15:16
a la base j'avais besoin d'un code qui soit capable de faire des calculs exacts avec plus de 14 chiffres. or vb utilise les arrondi et les puissance de 10 des que le nombre depasse 14 chiffres.
par exemple : 6,345,815,105.45196 et 5,245,176,914.63548 qui sont enorme certes mais pas invraisemblables ne peuvent pas etre additionnes sans perdre une decimale de precision.
plutot que de coder un module capable d'additionner pile le nombre de chiffres dont j'avais besoin, j'ai directement code un module capable d'additioner n'importe quel nombre positif, negatif, entier ou decimal.
j'espere avoir repondu a ta question. si tu souhaite pousser plus avant le debat, je te propose que nous allions plutot dans le forum math : http://www.vbfrance.com/forum.v2.aspx?TID=9
6 oct. 2005 à 14:53