ABCDEFGHIJKLMNOPQRSTUVWXYZ
Bombela
Messages postés
225
Date d'inscription
mardi 4 mars 2003
Statut
Membre
Dernière intervention
30 juillet 2008
-
1 oct. 2004 à 15:05
pYrAnNa Messages postés 3 Date d'inscription samedi 8 février 2003 Statut Membre Dernière intervention 12 novembre 2006 - 24 août 2005 à 17:38
pYrAnNa Messages postés 3 Date d'inscription samedi 8 février 2003 Statut Membre Dernière intervention 12 novembre 2006 - 24 août 2005 à 17:38
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/26494-abcdefghijklmnopqrstuvwxyz
https://codes-sources.commentcamarche.net/source/26494-abcdefghijklmnopqrstuvwxyz
24 août 2005 à 17:38
J'ai fait avec des tests de rapidité, ca ne m'apporte rien pour l'addition, mais pour la multiplication et la division c'est évident que je vais y gagner en calculant en Héxadécimal.
Merci encore.
19 août 2005 à 18:16
19 août 2005 à 18:07
Ce qu'elle fait ? Tout. T'as essayé de taper 2^128^2 !
Pour tout savoir su bc ==> tape "man bc"
@+
19 août 2005 à 17:42
19 août 2005 à 16:21
Tu connais la calculatrice console "bc" de linux ?
Elle est terrible !
19 août 2005 à 09:15
bonne journée!
Twis
18 août 2005 à 18:19
Je me rappelle même pas de ce que j'ai fais de ma source qui additionne en décimal ;) Enfin, je l'ai pas effacer, je pense pas... Mais vus que je tourne sous linux maintenant, j'ai un peux laché delphi :D
TheWhiteShadow si tu veux la source suffit de le dire ! ;)
@+
18 août 2005 à 13:37
18 août 2005 à 13:22
ah ouiiiii... je viens de relire le code et je m'en rappelle maintenant, c'est vrai que c pas mal lol :) je te décris une itération:
en fait tu lis les caractères de ta string 1 par 1 (tu soustrais par 0x30 pour avoir le chiffre en binaire d'abord), et pour chaque caractère, tu multiplies le reste, c'est a dire eax (initialisé à 0) par 10 et tu y additionnes le chiffre binaire courant. maintenant l'astuce: si le fait de multiplier par 10 te donne un nombre plus grand que 2^32-1, alors tu as l'"extra" dans dl. si le fait d'additionner par le chiffre donne un eax plus petit, tu rajoutes 1 à dl. du coup, s'il n'y avait pas eu de sépération en deux registres, un shift de 32 à droite (= une division par 2^32) te donnerai exactement ce qu'il y'a dans dl (sauf que nous on l'a direct, si c pas beau :)) et ensuite ton dl tu le mets à la place du chiffre que du vient de lire, et tu recommences jusqu'à ce que tu ai fait toute la string. tu obtient ainsi ta string (en chiffres binaires) divisé par 2^32 par rapport à l'itération précédente. maintenant, ton dernier eax (dernier reste) forme 32 bits de ton nombre binaire.
et voilà, tu réitères ça sur ta string jusqu'à ce qu'elle soit inférieur à 2^32 ou dès qu'elle est à 0 je sais plus, et là tu as fini, en récupérant les eax à la fin de chaque itération, tu as ton nombre binaire. relis le code maintenant et ça devrait sembler clair :) (fait bien attention là où y'a des push et pop notamment un avec edx)
en fait, pour revenir à niveau de réfléxion plus abstrait, il faut se dire: je veux convertir un nombre décimal en nombre binaire, donc je vais faire des divisions successives par deux, et le reste de la division forme mon nombre binaire. mais comme on veut optimiser comme des oufs et qu'on a des registres 32 bits, on divise par 2^32 pour aller plus vite (héhé). sauf qu'on fait même pas les divisions puisque on tire parti de la multiplication par 10 qui fou l'extra dans un autre registre (héhéhé) donc franchement, je crois que j'y avais bien pensé à l'époque, je vois pas comment on peut faire mieux (héhéhéhé). bon bref lol =)
en tout cas si jsuis pas clair sur qqch hésite pas, et jveux bien que tu me montres ton projet à l'occaz (tu fais signes ou tu postes un commentaire ici pour me le dire pcq jai pu le temps de trainer sur codes sources). assembleur en force!!!!
TheWhiteShadow, Twis, guinux, bref comme vous voulez
18 août 2005 à 12:07
Par contre je n'ai pas compris comment tu faisais la division d'un tres grand nombre décimal par 2^32.
Peux tu me donner plus de détail ? (juste sur ce point)
Merci d'avance.
(pour info je programme en ASM (masm32) une DLL de calcul rapide pour utiliser en VB).
10 avril 2005 à 18:22
Je l'utilise beaucoup :D
@+
10 avril 2005 à 15:56
sinon ça va chez toi? <- lol
bon jretourne à mes prbs d'algorithmiques... dailleurs ça msera vachement util pour cte source...
aller ++ twis
22 nov. 2004 à 20:32
22 nov. 2004 à 19:15
je pensais utiliser nasm pour compiler et visual c++ pour la partie C, mais bon ça reste à voir. mais je pense rester en .asm.
bref, ok ++Twis;
21 nov. 2004 à 22:45
That's good idea ;0)
Comme tu veux !
Le but, c'est que ça soit rapide et fonctionnel !
Mais si tu compile avec GCC, pas la peine de faire toi même de l'asm si tu compile en optimisation maximale. GCC fais mieu qu'un être humain ! J'ai vérifié.
@+
21 nov. 2004 à 21:25
question, ça te dérange que jécrive la partie algorithmique en pure assembleur (fichier .asm) et l'autre (fenetre etc...) en C?
personnellement je pense que c mieux, mais c pas encore sur que je vais le faire et je voulais juste savoir ce que tu en pensais.
++Twis;
5 nov. 2004 à 20:55
d = [log(n)]+1 longueur du nombre n en base 10 ([] partie entière).
b longueur du nombre n en base 2 (par "longueur" on entend le nombre de chiffres qu'il faut pour écire le nombre).
n = 2^x avec x élément de réel.
on ne connait que b et [x]=b-1, et on cherche d.
on a donc 2^[x] <= n <= 2^([x]+1)
équivalent à log(2^[x]) <= log(n) <= log(2^([x]+1)) car log fct croissante
équivalent à ln(2)/ln(10)*[x] <= log(n) <= ln(2)/ln(10)*([x]+1)
or ln(2)/ln(10)*([x]+1) - ln(2)/ln(10)*[x] = ln(2)/ln(10) ~= 0.3 < 1
donc la longueur du nombre n en décimal (d [log(n)]+1) peut s'exprimer par: [ln(2)/ln(10)*([x]+1)]+1 [ln(2)/ln(10)*b]+1 avec au pire une erreur de 1.
Voilà! la conclusion c'est que maintenant on sait quelle taille allouer pour le nombre en décimal grâce à ce petit calcul, avec dans certains cas 1 octet en trop (ce qui entrenera un "0" devant le nombre décimal, mais ce n'est pas génant du tout).
Apres, un bidon calcul de conversion d'une base à l'autre et s'en est fini pour bin->str. ainsi on aura deja str->bin et bin->str... une rapide fonction d'addition et on pourra commencer les tests. jespere que je trouverai le temps de coder ces qq ptits trucs avant 2005... ;-)
aller ++, Twis
15 oct. 2004 à 10:46
Je vais voir le commentaire !
@+
14 oct. 2004 à 17:34
donc pour l'instant voilà quoi, je pense que je pourrai continuer pendant les vacances qui viennent (qui sont proches quand même ;)), au moins de quoi faire l'addition et la conversion en string, de quoi faire des tests de rapidité entre les deux algos.
Twis++;
14 oct. 2004 à 17:19
v aller voir ça, 2s ;-)
14 oct. 2004 à 17:10
T'as regardé ma source sur DelphiFr ?
@+
14 oct. 2004 à 16:56
- Virer la fonction ReverBin(). Ainsi, tous les dword seront en little endian, eux-même "à l'envers" dans le buffer. Il suffirait donc d'inverser l'ordre des octets pour avoir le nombre entier en binaire dans "l'ordre". Mais on ne perd pas de temps à inverser quoi que ce soit, tout reste retourné en mémoire. Il faudra donc en tenir compte pour les opérations.
- Améliorer les boucles de la source. Pour l'instant elles se présentent comme suit:
xor ecx,ecx
@loop:
cmp ecx,value_max
je @end
[...]
inc ecx
jmp @loop
@end:
Il serait préférable de les transformer en:
xor ecx,ecx
@loop:
[...]
inc ecx
cmp ecx,value_max
je @loop
Comme on peut voir, le code est un peu moins long, du fait qu'il y a un jmp en moins dans le code. Cette modification peut sembler peu significative quant au temps mis par le processeur pour traiter la boucle, mais notre but et de faire une source entièrement fonctionnelle et la plus rapide possible, donc le gain peut être senti si on applique ce changement à toutes les boucles du programme (sachant qu'il y en a qui sont très très longues à exécuter suivant la taille des nombres mis en jeu).
Mais attention, il faudra traiter le cas où (value_max = 0) AVANT d'exécuter la boucle.
- Le dernier problème majeur reste la conversion de binaire à string. En fait, je pense que le mieux est de calculer (via une fonction) la taille de la string à partir de la taille du nombre binaire. Ensuite, dans le code principal, le programmeur alloue la mémoire nécessaire pour la string (indiqué par la fonction), et enfin appelle BinToStr pour convertir le nombre binaire en string dans la mémoire qui vient juste d'être allouée.
A ce propos, la longueur d'un nombre x en binaire s'exprime par ln(x)/ln(2)+1 (en bits), et en décimal par ln(x)/ln(10)+1. Or, si on ne considère par les "+1", en faisant le rapport de l'un et l'autre on trouve (ln(x)/ln(2))/(ln(x)/ln(10)) ln(10)/ln(2) cste. Ce qui veut dire qu'on peut exprimer la longueur du nombre en décimal par la longueur du nombre en binaire multiplié par une constante, la classe nan? Mais ça reste une approximation (déjà pas mal), parce qu'il se peut que dans certains cas il y ai un (ou plusieurs?) zéros tout à gauche de notre string... C'est quand même très satisfaisant comme algorithme et puis le programme pourra le reconvertir en binaire, même s'il y a des zéros en trop devant la string. Bien sûr s'il y a mieux je suis preneur...
Pour la veritable conversion en décimal après, ce n'est pas trop dur, c'est une succession de division par 10 etc... comme toute conversion d'une base vers une autre ;-).
- Introduire les entiers négatifs peut aussi être utile... à voir.
Voilà, et pour les opérations de bases il ne devrait pas y avoir de problème, toutes marchent sur le papier (à part la division ou ça se corse :s), mais on verra déjà...
Je ne peux coder que pendant les vacances, en période scolaire je n'ai pas de temps à accorder à la programmation. Au pire ce sera pour les grandes vacances, mais je serai là, je n'abandonne jamais un projet si bien commencé :D.
Twis++;
3 oct. 2004 à 19:35
Vu que le but est d'avoir la plus grande vitesse, et le plus grand nombre possible, optimize au maximum !
Mais faut pas non plus que ça soit bloqué !
Alors, pour partir avec des chance égale, je vais faire comme toi, un prog Delphi, qui prend un fichier et ressort dans un autre et optimisé en assembleur.
Voilà !
Et vraiment merci de jouer le jeux !
Et t'inquiète pour le temps libre, j'attendrais ;0)
@+
2 oct. 2004 à 21:48
maintenant, l'addition (le truc le plus facile, franchement je pense pas avoir de mal à le coder), je fais comment? deux buffers qui en donnent un troisième? ou deux buffers qui donnent deux buffers? (la première soluce me plaît mieux...) enfin tu vois faut réfléchir à ce genre de question avant de se lancer.
mais le pire, c'est pour le bin->str. en effet il est possible de foutre le nombre binaire dans la string pcq le nombre binaire est bcp plus petit. mais l'inverse... 2^32-1 = 4 milliards, 9 chiffres, ça rentre mal dans 4 octets... encore on pourrait faire deux chiffres par octet et on est que à la possibilité de mettre 8 chiffres. bref on l'a dans le c*l si tu vois ce que je veux dire. je serai donc obligé de passer par un autre buffer et ça va pas être du gateau, pcq je ne connais pas à priori la taille que fera la string... en str->bin c t moins complexe pcq tout est plus petit quand tu passes à binaire. pour conclure ça va pas se faire aussi simplement que ça, faut que j'y réfléchisse pendant un bon moment... bien sûr toute proposition est la bienvenue ;-)
mais j'en suis pas encore venu au problème majeur: jai pas de temps!!!!!!!!!!! ouain... et ouais c'est la vie, demain je dois faire une p*tain de dissert de philo et en plus je bosse pour les TPE sur un mot 3d en C, alors les nombres en binaire... mais comme ça m'interesse à fond et que t'es partant pour faire un truc pour comparer et tout et tout, je vais appliquer ma phrase de toujours: si tu n'as pas le temps, donne toi le temps. d'autant que je devrais avoir plus d'heures de dispo à partir de WE prochain... ça va, elle t'interesse ma vie? lol
Twis++;
"Ensuite, sache que pour moi, une string, c'est une suite d'octets, terminé par un 0.
Donc, pas le type string de delphi !"
> ben heureusement, là c'est l'appelation que je lui donne qui est abusive, en fait c'est un buffer de bytes dont la taille est contrôlée par une constante.
2 oct. 2004 à 16:25
Alors, pour le Big Endian, les octets sont codé à l'endroit.
C'est à dire que :
0xF5 > 0xF5
0xF5AB > 0xF5AB
0xF5ABCD10 > 0xF5ABCD10
C'est le principe des processeurs Motorola. (Si tu sais ce que c'est, moi pas ;)
Les PC sur la base d'Intel fonctionnent en Little Endian,
et donc les octets sont inversé :
0xF5 > 0xF5
0xF5AB > 0xABF5
0xF5ABCD10 > 0x10CDABF5
Alors un moyen simple pour ne pas faire l'invertion soit même, c'est de mettre les octets dans un registre 32 bits, puis de le mettre dans un petit buffer de 32 bits et l'envoyer dans le fichier !
C'est le CPU qui feras la convertion pour la mémoire en little endian.
Pour ce qui est des calculs en 32 bits, t'as tout à fais raison !
Je t'avoue, honteusement, avoir lu tas source en diagonale... J'atais pressé (escuse minable) ...
Je n'avais pas vu que tu fesais l'invertion dans la string elle même, sans un autre buffer !
Ensuite, sache que pour moi, une string, c'est une suite d'octets, terminé par un 0.
Donc, pas le type string de delphi !
De plus, je me demande vraiment quelle est la courbe de gain de vitesse entre les string décimale (les opérations comme à l'école ;) et les string binaire (les opération en 32 bits).
Faudrais faire un calcul de vitesse...
Si tu veux bien coder le myen de faire une addition, et calculer le temps qu'il faut pour décoder, additionner, et recoder (Vu que tu l'as pas codé le recodage ;0), il suffit de multiplier par 2 le le temps de décodage).
Si tu veux bien faire ça, je code une addition en décimale.
Ensuite, on feras un truc du style multiplication, ce qui consisterais pour moi en plein d'addition, et pour toi en multiplication du proc.
Ca nous permettra de trouver l'équilibre entre les deux méthode... très utile pour le future !
@+
1 oct. 2004 à 17:15
et deuxio, je ne passe pas par un buffer temporaire: le résultat est foutue au fur et à mesur dans la string (mais à l'envers) donc la derniere etape consiste à copier les octets dans le dernier buffer dans le bon ordre. Ptet qu'on peut le faire direct dans le bon sens mais se serait un peu plus complexe... sinon tu peux tjrs passer par un fichier (ok ok pas la meilleure soluce) mais bon ça régle le prb de mémoire si tu veux et retourner des octets c'est pas le truc le plus long/dur à faire pour un pc... si? lol. Aussi, le nombre en pure binaire est bien moins long qu'en string...
et trisio (ou je sais plus comment on dit), si tu n'es pas convaincu qu'un calcul en assembleur par paquets de 32 bits est plus rapide qu'une string alors là je sais pas ce qui faut faire... d'autant que si tu veux faire un algo avec des longues boucles (genre calcul si un nombre est premier), tu crois pas que le mieux est l'assembleur plutôt qu'une pauvre string? Mais même pour des caluculs simples... je t'accorde un point: sûrement que pour des chaînes pas trop longues les string sont plus rapides (aucune idée d'estimation), mais pour des nombres d'une longueur vraiment considérable, pas l'ombre d'un doute que le 32 bits est (bcp) plus rapide.
Merci pour tes commentaires, mais détaille certains points.
++Twis;
1 oct. 2004 à 15:09
Je pense qu'au final, un calcul sur des chifre décimaux serais quand même plus rapide !
Parce qu'il n'y aurais par de perte de temps de convertion de nombre décimal en binaire !
De plus, tas fonctions passe par un buffer temporaire, et si ton nombre fais 3 go de long, et bien sur un Iintel 32, t'es fini...
@+
1 oct. 2004 à 15:05
Tu sort ton binaire en... big endian !
Alors que sur les pc à base d'intel (Sur quoi tu fais mumuze avec Delphi ;) sont en little endian !
Faudrait faire une petite update là ;)
@+