Additions avec + de 20 chiffres significatifs avec une fonction en Asm à optimiser

**Gilbert Geyer** · 01/08/2007, 16h45

Bonjour

Pour faire des additions avec plus de 20 chiffres significatifs sans être pénalisé par des lenteurs je souhaite faire en Asm une fonction à laquelle je donne en entrée deux chaînes-numériques de longueur non limitée et qui renvoie le résultat de l’addition sous forme d’une autre chaîne dont les caractères numériques sont obtenus comme on apprend à l’école dans le style « 8 + 9 = JePose 7 et JeRetiens 1 ». A cet effet les chaînes envoyées en entrée sont des chaînes calibrées de même longueur et commençant par au moins un ‘0’ (ou davantage s’il faut ajuster l’une à l’autre).

Bien que je sois nul en Asm j’ai réussi à bidouiller une fonction qui réalise ce résultat très très maladroitement avec un fonction que j’aimerais donc optimiser sous plusieurs aspects :
- extension aux calculs sur des chaines-numériques du type String ou Pchar (au lieu des ShortString’s)
- soulagement des calculs par des précalculs résumés dans les deux tableaux suivants :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
type   TTabPoseRetiens = array['0'..'9','0'..'9'] of Char;
 
const  AdditionJePose : TTabPR = 
(('0','1','2','3','4','5','6','7','8','9'),
('1','2','3','4','5','6','7','8','9','0'),
('2','3','4','5','6','7','8','9','0','1'),
('3','4','5','6','7','8','9','0','1','2'),
('4','5','6','7','8','9','0','1','2','3'),
('5','6','7','8','9','0','1','2','3','4'),
('6','7','8','9','0','1','2','3','4','5'),
('7','8','9','0','1','2','3','4','5','6'),
('8','9','0','1','2','3','4','5','6','7'),
('9','0','1','2','3','4','5','6','7','8'))
 
const AdditionJeRetiens : TTabPR =
(('0','0','0','0','0','0','0','0','0','0'),
('0','0','0','0','0','0','0','0','0','1'),
('0','0','0','0','0','0','0','0','1','1'),
('0','0','0','0','0','0','0','1','1','1'),
('0','0','0','0','0','0','1','1','1','1'),
('0','0','0','0','0','1','1','1','1','1'),
('0','0','0','0','1','1','1','1','1','1'),
('0','0','0','1','1','1','1','1','1','1'),
('0','0','1','1','1','1','1','1','1','1'),
('0','1','1','1','1','1','1','1','1','1'))

La fonction Asm à optimiser :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
function  AdditionAsm(str1,str2 : shortString; Len : Integer) : shortString;
//        str1 et str2 en entrée : de même longueur avec mini un 0 au début
//        str1     = '09123457891235469785743258714586027895'
//        str2     = '01234568524563759158521739582461397461'
//        Resultat = '10358026415799228944264998297047425356'
var       Pose,Retiens : byte; Res : shortString;
begin     Retiens:=0; Res:=StringOfChar(' ',Len);
  asm     PUSHFD
          PUSHAD
 
          PUSH  ESI
          PUSH  EDX
          PUSH  EDI
          PUSH  ECX
 
          LEA   ESI, str1  // source
          LEA   EDX, str2  // 2ème source
          LEA   EDI, res   // destination
 
          STD   // incrémenter de la fin vers le début
          ADD   ESI, Len  // Initialisation à l'offset de
          ADD   EDI, Len  // début des chaînes + Len
          ADD   EDX, Len  // idem
          MOV   ECX, Len
 
@Boucle:
          LODSB                    // Calcul de Pose:="s1[i] + s2[i] + retenue"
          MOV   Pose,AL            // caractère de str1
          MOV   AH,Retiens
          ADD   Pose,Ah
          MOV   AH, Byte ptr[EDX]  // caractère de str2
          ADD   Pose,AH
          SUB   Pose,96
          CMP   Pose,10
          JB   @Inf
          SUB   Pose,10
          MOV   AL,Pose
          MOV   Retiens,1          //retenue = 1
          JMP  @Suite
 
@Inf:     MOV   AL,Pose
          MOV   Retiens,0          //retenue = 0
 
@Suite:   ADD   AL,48
          DEC   EDX                //caractère précédent de str2
          STOSB
          LOOP @Boucle
 
@Sors:    POP   ECX
          POP   EDI
          POP   EDX
          POP   ESI
 
          POPAD
          POPFD
end; //asm
          //res:=trim(res);
          Result:=res;
end; // AdditionAsm

Ayant testé les performances de rapidité des fonctions utilisées par la calculatrice-pour-grands-nombres proposée dans les codes-source il s’avère que celles-ci sont fortement sanctionnées dans le cas d’appels répétitifs dans des boucles du fait de la lenteur des conversions des chaînes-numériques vers des Array Of Int64 et réciproquement, inutile donc de me proposer ce type de solution (qui reste néanmoins valable pour une calculatrice utilisée hors boucle)

Par contre si quelqu’un a de bonnes idées pour rectifier le code de la fonction ci-dessus en Asm cela m’enlèverait une épine du pied et peut-être que d’autres seraient également intéressés par la fonction rectifiée.

Merci par avance.
A+

**CapJack** · 01/08/2007, 20h41

Tu n'utilises pas la bonne démarche : les processeurs de la famille x86 ont depuis toujours un jeu d'instructions arithmétiques BCD (Binary Coded Decimal), parfaitement adapté à ce genre d'opérations. Tu devrais te renseigner sur ce jeu d'instructions.

**Eric Boisvert** · 02/08/2007, 12h26

bon déjà ca c'est mieux que le code ASM, sans limite aux niveaux des
strings en entrée et c'est très rapide sur les CPU d'aujourd'hui avec cache etc.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
function Addition(const s1:string;const s2:String;Len:integer):string;
var
  i:integer;
  t:integer;
  r:integer;
begin
  result:=StringOfChar(' ',Len);
  r:=0;
  for i:=len downto 1 do
  begin
    t:=byte(S1[i])+byte(S2[i])+r;
    if t>=106 then
    begin
      r:=1;
      result[i]:=char(t-58);
    end
    else
    begin
      r:=0;
      result[i]:=char(t-48);
    end;
  end;
end;

Si tu tien à utilisé des tableaux pré calculé, je te propose plutot ceci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
//0+0=48+48=96
//9+9=57+57=114 (+1) pour la retenue= 115
const PreCalcResult : Array [0..115] of char =
('0','0','0','0','0','0','0','0','0','0'
,'0','0','0','0','0','0','0','0','0','0'
,'0','0','0','0','0','0','0','0','0','0'
,'0','0','0','0','0','0','0','0','0','0'
,'0','0','0','0','0','0','0','0','0','0'
,'0','0','0','0','0','0','0','0','0','0'
,'0','0','0','0','0','0','0','0','0','0'
,'0','0','0','0','0','0','0','0','0','0'
,'0','0','0','0','0','0','0','0','0','0'
,'0','0','0','0','0','0',{96}'0','1','2','3'
,'4','5','6','7','8','9','0','1','2','3'
,'4','5','6','7','8','9');
 
const PreCalcRet : Array [0..115] of Integer =
(0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,{96}0,0,0,0
,0,0,0,0,0,0,1,1,1,1
,1,1,1,1,1,1);
 
function Addition2(const s1:string;const s2:String;Len:integer):string;
var
  i:integer;
  retenue:integer;
begin
  result:=StringOfChar(' ',Len);
  retenue:=0;
  for i:=len downto 1 do
  begin
    result[i]:=PreCalcResult[byte(S1[i])+byte(S2[i])+retenue];
    retenue:=PreCalcRet[byte(S1[i])+byte(S2[i])+retenue];
  end;
end;

Il n'y a selon moi pas beacoup de gain à utiliser la 2ème solution...
pour test en entrée

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
const
 str1 = '09123457891235469785743258714586027895';
 str2 = '01234568524563759158521739582461397461';
 
Const
  NbrCall = 100000;

ca donne:
Addition Asm-----0.31 secondes
Addition Delphi---0.23 secondes
Addition2 Delphi--0.22 secondes

En faite, pourquoi en ASM?

**Eric Boisvert** · 02/08/2007, 13h04

si j'allonge les chaines en entrée, ca devient plus évident que la 2ème est plus rapide...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
function Addition2(const s1:string;const s2:String;Len:integer):string;
var
  i:integer;
  retenue:integer;
  offset:integer;
begin
  result:=StringOfChar(' ',Len);
  retenue:=0;
  for i:=len downto 1 do
  begin
    offset:=integer(S1[i])+integer(S2[i])+retenue;
    result[i]:=PreCalcResult[offset];
    retenue:=PreCalcRet[offset];
  end;
end;

Toujours pour NbrCall = 100000;

Longueur de chaine:228
Addition Asm-----0.67 secondes
Addition Delphi---0.45 secondes
Addition2 Delphi--0.33 secondes

Longueur de chaine:11400
Addition Asm-----n/a (Out of range)
Addition Delphi---15.72 secondes
Addition2 Delphi--12.60 secondes

**Gilbert Geyer** · 02/08/2007, 13h54

Bonjour,

A CapJack :

Tu n'utilises pas la bonne démarche : les processeurs de la famille x86 ont depuis toujours un jeu d'instructions arithmétiques BCD (Binary Coded Decimal), parfaitement adapté à ce genre d'opérations. Tu devrais te renseigner sur ce jeu d'instructions.

Merci pour cette info : j'ai passé la matinée à fouiller Internet sur les instructions arithmétiques BCD j'en ai pris une migraine mais c'est bien instructif sans toutefois savoir par quel bout je pourrais démarrer.

Au fait quand j'ai vu que tu étais le premier à répondre je m'attendais à une proposition similaire à la function CJ9 que tu avais créée récemment en Asm pour convertir des chaînes accentuées en majuscules non accentuées à partir de la constante tableau de conversion. J'ai essayé de m'en inspirer mais comme je suis nul en Asm je n'ai pas abouti et la fonction AdditionAsm que j'ai bidouillée n'a marché qu'après de nombreux tâtonnements et ça doit sauter aux yeux d'un connaisseur.

A Eric Boisvert :

A) / message de 12h26

Merci mille fois pour tes codes c'est vraiment sympa.

En faite, pourquoi en ASM?

... tout simplement parceque dans le cadre d'une autre discussion qui portait sur l'optimisation de l'enlèvement d'accents sur des chaînes CapJack avait crée en Asm la fonction CJ9 précitée et qui lorsqu'elle était utilisée dans certaines conditions était nettement plus rapide que sa version homologue basée sur l'utilisation de PChar.

Const
NbrCall = 100000;
ca donne:
Addition Asm-----0.31 secondes
Addition Delphi---0.23 secondes
Addition2 Delphi--0.22 secondes

... bigre, les codes en Delphi sont nettement plus rapides qu'en Asm !
... d'une certaine façon ça m'arrange de pouvoir coder en Delphi car après l'addition, faudra que je fasse la soustraction, la multiplication, etc
... l'objectif de ma demande concernant l'addition étant surtout de commencer sur la meilleure piste.
... vu les temps d'exécution obtenus je vais me jeter à mon tour sur des tests comparatifs.

B) / message de 13h04

Dis donc t'est bien rapide, j'ai pas eu le temps de terminer ma réponse à ton 1er message que je découvre ton 2ème

Toujours pour NbrCall = 100000;

Longueur de chaine:228
Addition Asm-----0.67 secondes
Addition Delphi---0.45 secondes
Addition2 Delphi--0.33 secondes

Longueur de chaine:11400
Addition Asm-----n/a (Out of range)
Addition Delphi---15.72 secondes
Addition2 Delphi--12.60 secondes

... cette fois çi cela devient clair qu'Addition2 est plus rapide.

En tous cas merci. Je vais me lancer dans les tests.

A+

**Eric Boisvert** · 02/08/2007, 14h08

Peut-être que c'est pas de mes affaires...mais par curiosité....
à quoi ca peut bien servir? des additions,soustraction de nombre tel que
1 000 000 000 000 000 000 000
Si c'est des $...humm, tu m'engage j'espère!

**sovitec** · 02/08/2007, 14h58

Envoyé par Eric Boisvert

Si c'est des $...humm, tu m'engage j'espère!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
v := Addition2('7', '5', 1);
writeln(v); // -> 2

Euh, moi je ne t'engage pas

**Montor** · 01/06/2009, 15h27

il y a un erreur la fonction ne donne pas le bon calcul

**Montor** · 01/06/2009, 19h52

je ne voulait pas que la discussion remonte jusqu'ici mais je voulait signaler cet erreur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
  712518543152
+ 856985587519
= 569504130671

**Eric Boisvert** · 01/06/2009, 19h58

C'est pourquoi les chaines d'entrées doivent commencer par 0...

Envoyé par Gilbert Geyer

Bonjour
A cet effet les chaînes envoyées en entrée sont des chaînes calibrées de même longueur et commençant par au moins un ‘0’

donc...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
  0712518543152
+ 0856985587519
= 1569504130671

**Montor** · 02/06/2009, 12h28

Probleme de retenue
essaie

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function Somme(a,b:string;c:Pointer) :integer ; register
asm
      push ebx
      push esi
      mov ebx,[eax]-4
      mov esi,eax
      xor eax,eax
@boucle:
      mov al,ah
      xor ah,ah
      add al,byte ptr[esi]
      add al,byte ptr[edx]
      sub ax,$60  //DAS
      cmp al,10   //aaa
      jnae @suite
      sub al,10
      mov ah,1
@suite:
      or al,$30
      mov byte ptr[ecx],al
      inc esi
      inc edx
      inc ecx
      dec ebx
      jnz @boucle
      or ah,$30
      mov byte ptr[ecx],ah
      pop esi
      pop ebx
end ;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
  h1:='712512543152';
  h2:='856984587519';
  h3:=StringOfChar(' ',Length(h1)+1);
  Somme(h1,h2,@h3[1]);

**tourlourou** · 02/06/2009, 21h43

pour les férus de vitesse, il existe une unité - au développement de laquelle Gilbert Geyer a participé - disponible ici : http://www.phidels.com/php/index.php...ip.php3&id=617

**Gilbert Geyer** · 03/06/2009, 09h31

Bonjour,

Tiens je n'avais pas remarqué que cette discussion, interrompue il y a 2 ans, avait repris.

J'en profite pour signaler que l'unité citée par Tourlourou "pour les férus de vitesse" permet en plus de franchir allègrement la barrière des 20 chiffres sigificatifs vu qu'elle manipule des strings numériques codées en base 256, et qui dit "string" dit capacité théorique maximale de 2 Go de chiffres significatifs pour chaque nombre : de quoi prendre le vertige :

Pour fixer les idées, une telle string imprimée recto-verso sur des feuilles A4 avec marges de 2,5 cm en Arial 10 normal (10856 caractères par feuille) nécessiterait l'utilisation de 395,6 paquets de 500 feuilles A4 et comme un seul paquet est épais de 5 cm cela repésente une pile de papier de presque 20 mètres de haut !!!. (un immeuble de 7 étages)

En bref avec nos bécanes poussives il est impossible d'exploiter à fond les capacités de l'unit : faudrait un Cray pour les exploiter à fond.

Cordialement et à +.

Additions avec + de 20 chiffres significatifs avec une fonction en Asm à optimiser

Langage Delphi

Vue hybride

Discussions similaires

Partager

Partager