Discussion :

[Jlmat]

Bonjour,

Je teste une limite dans une fonction qui ne doit pas dépasser la valeur d'un QWord, soit 18 446 744 073 709 551 615.

Voici la fonction qui plante sur la dernière ligne de result et qui devrait également planter sur l'instruction Limite := QWord(Trunc(ResVal)) qui utilise également Trunc(ResVal)!;

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
 
{--- fCellMax ------------------------------------------------------------------
Les limites (nombre maximum de la population des cellules identifiables de manière
unique sont celles du type des varaibles X,Y,Z et T selon la dimension
Si l'on prend une seule limite et que l'on prend :
1. Type Word pour X,Y,Z, T
    => Limite Max = 65535×65535×65535×65535 = 1 853 020 188 851 841;
    => c'est donc un UInt64 ou un QWord =  0 .. 18 446 744 073 709 551 615
    => Le Longword n'est pas assez grand : (0 .. 4 294 967 295)
-------------------------------------------------------------------------------}
function fCellMax(aDim : Tdim) : QWord;
  var Limite : QWord;
    ResVal   : Extended;
    Fmt      : string;
begin
  result := 0;
  ResVal := IntPower(65535, 4);
 
  {Vérification limite du Qword}
  if (ResVal < 0) or (ResVal > High(QWord)) then
     begin
       Limite := QWord(Trunc(ResVal));
       Fmt    := Format('%d', [Limite]); // Afficher sans décimales
       MessageDlg('Dépassement des limites du nombre de cellules individuelles : ' +
                 Fmt + #13#10 + 'Valeur Maximale autorisée = 1 853 020 188 851 841'
                 , mtError, [mbOk], 0);
       exit;
     End;
  Result := Trunc(ResVal);
end;

L'erreur à l'exécution est :



Note : Je souhaite un résultat numérique et non pas un string qui a déjà été suggéré sur ce site!

merci

[tourlourou]

Bonjour,
Si je reprends :

Code :

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

1
2
3
4
18 446 744 073 709 551 615 = High(QWord)
18 445 618 199 572 250 625 = 65535 ^ 4
 9 223 372 036 854 775 807 = High(int64)
     1 853 020 188 851 841 = limite max <> 65535^4

Il est à mon avis impossible de comparer fiablement en faisant autant de conversions entre types : Trunc renvoie la partie entière d'un Float dans la limite d'un Int64.
Enfin, tu fais un test sur une constante, évalué toujours faux, donc le compilateur omet probablement le code conditionnel, puisque inutile, et l'erreur se manifeste sur la seule expression compilée.
Je ne conçois pas de solution en dehors des bibliothèques de calculs sur grands entiers.

[Jlmat]

Merci tourlourou,

Oui, merci Tourlourou, je suis d'accord avec ton analyse! Je pensais que je pouvais utiliser Trunc..., Mais il détecte l'erreur effectivement avant...
J'avais pensé qu'il y aurait peut être une astuce! De toute façon, cette fonction n'est utilisée que pour un paramétrage, donc pas de problème de temps d'exécution...
Je vais donc faire des comparaisons de String des valeurs et ne faire le calcul et la conversion qu'après validation si je suis en dessous des limites.

A+

[Guesset]

Bonjour,

Il y a quelque chose qui me chagrine un peu : une confusion possible entre valeur max et nombre.

X, Y, Z, T sont censés être des Words, ils désignent donc chacun une cellule numérotée de 0 à 65535 soit 2¹⁶ cellules et non 2¹⁶-1 = 65535. Donc 2⁶⁴ cellules de 0 à 2⁶⁴-1.

Par ailleurs, s'ils sont effectivement de type word l'espace des quatre tient naturellement dans un uint64 :

Code :

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

1
2
3
4
5
TUnion = packed record
   case Integer of
      0 : (Q : UInt64);
      1 : (X, Y, Z, T : UInt16);
   end;

En résumé, le problème de dépassement ne semble exister que si X, Y, Z, T sont d'un type plus grand que word, mais que (X, Y, Z, T) ne doit pas sortir d'un espace plus grand que UInt64. Dans ce cas là, la vérification pourrait suivre le schéma suivant :

• Max = High(QWord);
• prendre la coordonnée la plus grande U dans (X, Y, Z, T)
• si U < 2¹⁶ alors Exit[OK]
• sinon Max = Max div U
• prendre la 2^e coordonnée la plus grande U dans (X, Y, Z, T)
• si U > Max alors Exit[KO] sinon si U = 0 alors Exit[OK]
• sinon Max = Max div U
• prendre la 3^e coordonnée la plus grande U dans (X, Y, Z, T)
• si U > Max alors Exit[KO] sinon si U = 0 alors Exit[OK]
• sinon Max = Max div U
• prendre la dernière coordonnée U dans (X, Y, Z, T)
• si U > Max alors Exit[KO] sinon Exit[OK]

En utilisant un tableau pour noter le résultat du tri des coordonnées on peut traiter cela par une simple boucle.

Salutations

[Jlmat]

Bonjour Guesset et merci.

Je viens de découvrir ton exemple, je pense qu'il me sera utile...

En attendant, j'ai essayé de compiler ton programme sous windows et Lazarus 3.4. ça plante en plusieurs endroits:


Apparamment, je ne suis pas sur un processeur intel car il plante dans l'assembleur...

J'ai un autre travail à finir avant, mais ton test aux conditions aux limites devrait me servir, c'est trop tôt pour le dire...
En tout cas, Grand Merci
A+

[Guesset]

Bonjour Jlmat,

...j'ai essayé de compiler ton programme sous windows et Lazarus 3.4. ça plante en plusieurs endroits: Apparemment, je ne suis pas sur un processeur intel car il plante dans l'assembleur...

Ce code, compilé en 64 bits, fonctionne sur AMD comme Intel. Je suis sous Windows 11 64 bits avec Lazarus 3.4.

Si le code a été repris sans modification, je ne comprends pas le problème. Les erreurs asm ressemblent à l'absence de la directive {$ASMMODE intel} sans laquelle le compilateur attend une syntaxe ATT. Comme il tique sur les instructions utilisant des registres 64 bits, il est également possible qu'on essaye de le compiler en 32 bits au lieu de 64 bits.

L'exécutable (en 64 bits) : CellsCount.7z

Salut

[Jlmat]

Bonjour Jlmat,

Ce code, compilé en 64 bits, fonctionne sur AMD comme Intel. Je suis sous Windows 11 64 bits avec Lazarus 3.4.
Si le code a été repris sans modification, je ne comprends pas le problème. Les erreurs asm ressemblent à l'absence de la directive {$ASMMODE intel} sans laquelle le compilateur attend une syntaxe ATT. Comme il tique sur les instructions utilisant des registres 64 bits, il est également possible qu'on essaye de le compiler en 32 bits au lieu de 64 bits.
L'exécutable (en 64 bits) : CellsCount.7z
Salut

Je n'ai pas essayé ton dernier code. Je suis en 64 bits mais sur un processeur Intel(R) Core(TM) i3-4160 CPU. Voici les codes corrigés. J'ai testé deux versions que vous trouverez dans le Zip.
1. version traditionnelle de ta fonction en assembleur AMD revue en code pascal => fonctionne :
2. version assembleur corrigée non acceptée sur ma machine. Etant donné que cet aspect du problème est important dans mon futur projet, j'ai pris le temps de me pencher sur le code assembleur. C'est très vieux pour moi!
pour les x86 version 64 bits, on peut apparemment utiliser les registres rcx, rax et bsr
Pour x86 version 32 bits, il faut donc diviser en deux parties : partie basse dans eax, partie haute dans edx. Je vérifie d'abord la partie haute, puis la partie basse. j'ajoute 32 au résultat si le bit est trouvé dans la partie haute32 bits. Ne semble pas fonctionner

Donc voici ces deux fonctions:

1. Code traditionnel:

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
 
{ Retourne n tel que 2^n <= i < 2^(n+1) ----------------------------------------
  Version pascal traditionnel
-------------------------------------------------------------------------------}
function iLog2(i: UInt64): Int64;
var
  n: Int64;
begin
  if i = 0 then
    Result := -1
  else
  begin
    n := 0;
    while i > 1 do
    begin
      i := i shr 1;
      Inc(n);
    end;
    Result := n;
  end;
end;

Version Assembleur 32 bits : (ne marche pas, résult faux dès l'entrée d'une valeur). C'est vrai qu'une fonction assembleur serait mieux adaptée en termes de vitesse!

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
 
{ version avec les instructions assembleur compatibles 32 bits  }
function iLog2(i: UInt64): Int64; assembler; nostackframe;
asm
  {$IFDEF CPUX86_64}
    mov   rax, -1
    test  rcx, rcx
    jz    @done
    bsr   rax, rcx
  @done:
  {$ELSE}
    mov   eax, -1
    test  edx, edx
    jnz   @high
    test  eax, eax
    jz    @done
    bsr   eax, eax
    jmp   @done
  @high:
    bsr   eax, edx
    add   eax, 32
  @done:
  {$ENDIF}
end;

Capture écran des trois tests clés:


Et voici mon code : CellsCount Jlmat.zip retravailler de l'appli de Guesset, merci à toi:

[Jlmat]

Merci Guesset

1. Pour cette réponse Top et qui m'a fait réfléchir, même si je n'ai pas tout compris dans ton algorithme.

Les limites (nombre maximum de la population des cellules identifiables de manière unique sont celles du type des variables X,Y,Z et T selon la dimension.
Donc effectivement Type Word pour X,Y,Z,T
Valeur minimale : 0
Valeur maximale : 65 535 (ou 2^16 − 1)
=> Population de 65 536 cellules

Type QWord => C'est donc un UInt64 ou un QWord = 0 .. 18 446 744 073 709 551 615
Valeur minimale : 0
Valeur Maximale : 2^64 − 1, soit 18 446 744 073 709 551 615
mais => Population de 18 446 744 073 709 551 616 cellules

La contrainte vient des nombres dans leurs valeurs pratique. Donc, dans les
calculs le produit P = X * Y * Z * T doit être < ou = QWord
Produit = 18 445 618 199 572 250 625
Q Max = 18 446 744 073 709 551 615
Donc, c'est bien possible de générer un QWord

2. Bon en attendant, j'ai fait ma solution avec des comparaisons sur chaîne, les calculs de débordements sur le valeurs numériques ont tendance à me hérisser les poils, tant il y a de conversions de conversions et de définition à des endroits différents...

Je vous donne le code en Pièce jointe 657460 en faisant un extrait de mon projet sans la présentation et les contrôles.
pour faire les tests, il suffit de changer les variables dans le Creat de la form1 ou dans l'évènement" Onchange" du SpinEdit de la Dimension!

Et ci-dessous le code :

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
 
Unit Unit1;
 
{$mode objfpc}{$H+}
 
Interface
 
Uses
  Classes, Sysutils, Forms, Controls, Graphics, Dialogs, ExtCtrls, StdCtrls,
  Spin;
 
Const
  CR = #13#10;
  CoulFond  = $0085ACF7;
  CoulPanel = $000003E2;
  CoulCel   = clBlack;
 
Type
  TDim = 1..3;
  { Tform1 }
 
  Tform1 = Class(Tform)
    SpEdDim: Tspinedit;
    Statictext3: Tstatictext;
    Sttmax: Tstatictext;
    Sttpop: Tstatictext;
    Procedure Formcreate(Sender: Tobject);
    Procedure Speddimchange(Sender: Tobject);
  private
  Public
    Dim : TDim;
    Xc,Yc,Zc,Tc  : Word; //
    NCellMax     : QWord;
    NCellMaxStr  : String;
  End;
 
Var
  Form1: Tform1;
 
function NumStrToSepMil(const NumStr: string): string;
 
 
{==============================================================================}
 
Implementation
{$R *.lfm}
 
{--- CompareStrNumbers ---------------------------------------------------------
Compare deux chaines de carctères qui sont des nombres entiers positifs
Resultat = -1 => Str1 est plus petit
Resultat = +1 => Str1 est plus grand
Resultat = 0 => Str1 = Str2
-------------------------------------------------------------------------------}
function CompareStrNumbers(Const Str1, Str2 : string) : Integer;
begin
  {Vérifier si les chaines ont la même longueur}
  if Length(Str1) < Length(Str2)
     then Result := -1 // Str1 < Str2
     else if Length(Str1) > Length(Str2)
             then Result := 1  // Str1 > Str2
             else begin
               {L(Str1) = L(Str2) => Comparaison caractère par caractère}
               Result := CompareStr(Str1, Str2);
             end;
end;
 
{--- NumStrSepMil --------------------------------------------------------------
Sépare les milliers dans un nombre en string
-------------------------------------------------------------------------------}
function NumStrToSepMil(const NumStr: string): string;
var
  i, L : Integer;
begin
  Result := '';
  L := Length(NumStr);
  for i := L downto 1 do
  begin
    Result := NumStr[i] + Result;
    if (L - i) mod 3 = 2 then Result := ' ' + Result;
  end;
end;
 
{--- fCellMax2 -----------------------------------------------------------------
 Fonction calculant le population maximale selon la dimension demandée et les
 valeurs dans chaque dimension (Utilisation de UIntToStr)
 On donne les résultats sous forme numérique et également sous forme de String
 pour gagner des recoversions à faire pour l'affichage
-------------------------------------------------------------------------------}
function [ATTACH]657460[/ATTACH](aDim : Tdim; X,Y,Z,T : Word; Var ResStr : String) : QWord;
const
  CR = #13#10;
var
  P,QM : QWord; // Produit des quatre variables
  P64,QWStr  : String; // Produit et Qmax convertis en string
 
  procedure MsgER;
    var FmtP, FmtQM : String;
  begin
    FmtP := NumStrToSepMil(UIntToStr(P));
    FmtQM:= NumStrToSepMil(UIntToStr(QM));
    MessageDlg('Dépassement des limites :'+CR+CR
              +'Nbre de cellules demandées : ' +FmtP+CR
              +'Valeur Maximale autorisée  : ' +FmtQM
              , mtError, [mbOk], 0);
  end;
 
begin {---}
  {initialisation des resultats fournis}
  result := 0;
  resStr := '';
 
  {Selon la dimension du système pour éviter les X par 0}
  Case aDim of
  2 : begin P := X * Y;         QM := 65535 * 65535; end;
  3 : begin P := X * Y * Z;     QM := 65535 * 65535 * 65535; end;
  4 : begin P := X * Y * Z * T; QM := 65535 * 65535 * 65535 * 65535; end;
  end;
 
  // pour test débordement P :=  QM + 2;
  if P > QM then
  begin
    MsgER;
    Exit;
  end;
 
  {Comparaison des Chaines :
   1. Si L(QWstr)= 20 > L(P64) => P64 est évidemment un QWord autorisé
   2. Si LQWstr = L(P64) => Il faut regarder chaque digit jusqu'à ce qu'il y ait
      une différence}
 
   P64   := UIntToStr(P);
   QWStr := UIntToStr(QM);
 
   If CompareStrNumbers(QWStr,P64) > -1 then
   begin
     Result := P; // C'est OK, On peut calculer la suite
     ResStr := QWStr;
   end else
   begin
     MsgER;
     ResStr := '';
   end;
end;
 
 
{--- Tform1 -------------------------------------------------------------------}
 
Procedure Tform1.Formcreate(Sender: Tobject);
Begin
  {1. Dimensions de la Grille par défaut et position dans la Fiche}
  Dim := 2;
  Xc  := 65535;
  Yc  := 65535;
  Zc  := 65535;
  Tc  := 65535;
 
  {2. Variables}
  NCellMax       := fCellMax2(Dim,Xc,Yc,Zc,Tc,NCellMaxStr);
 
  {3. Affichages}
  StTPop.Caption := 'Population Effective : '+ NumStrToSepMil(UIntToStr(NCellMax));
  StTMax.Caption := 'Popul. Max Théorique : '+ NumStrToSepMil(NCellMaxStr);
 
End;
 
Procedure Tform1.Speddimchange(Sender: Tobject);
Begin
  Dim := SpEdDim.Value;
  Xc  := 65535;
  Yc  := 65535;
  Zc  := 65535;
  Tc  := 65535;
 
  {2. Variables}
  NCellMax       := fCellMax2(Dim,Xc,Yc,Zc,Tc,NCellMaxStr);
 
  {3. Affichages}
  StTPop.Caption := 'Population Effective : '+ NumStrToSepMil(UIntToStr(NCellMax));
  StTMax.Caption := 'Popul. Max Théorique : '+ NumStrToSepMil(NCellMaxStr);
 
End;
 
 
End.

3. Je ne suis pas sûr que ce soit vraiment optimisé. Si vous avez des améliorations, je suis preneur. Mais testez svp avec le code fourni car il y a quand même des surprises avec les conversions...

Bon, je mets résolu, il faut que j'avance...
A+

[Guesset]

Bonjour,

Je ne comprends pas le programme.

Dans le programme X, Y, Z, T sont des Word. Chacun est donc compris entre 0 et 65535 (inclus) et le produit de n d'entre eux ne peut excéder 65535ⁿ. En résumé, P <= QM dans tous les cas. Aussi la fonction fCellMax2 retournera systématiquement P.

Autre chose, peut être sans importance, une dimension < 4, par exemple 3, peut être obtenue avec (X, Y, Z) mais aussi (X, Y, T), (Y, Z, T), (X, Z, T).

Enfin, la dimension peut être égale à 1 (car TDim = 1..3) or elle n'est pas traitée dans le programme. En revanche, il traite le cas d'une dimension 4 qui n'appartient pas à la gamme de TDim.

Salutations

[Jlmat]

Bonjour Guesset,

Je comprends ton questionnement. J’apprécie tes remarques et j'essaye de te répondre...

Bonjour,
Je ne comprends pas le programme.... le produit de n d'entre eux ne peut excéder 65535n. En résumé, P <= QM dans tous les cas.

- C'est parce qu'au départ je me battais avec les problèmes de conversions des types. Dans mon idée de départ, je désirais limiter (théoriquement) le nombre de possibilités à une map gigantesque que je ne pouvais afficher à l'écran qu'en partie.
- Donc il fallait prévoir un scan ou un zoom d'une partie de la map seulement.
- Pour le test, je me suis limitér à des Word ce qui donne déjà pas mal de possibilités, mais tu as raison, même si j'ai au minimum Dim = 2, c'est tout simplement pour ne pas avoir une seule ligne mais un tableau.
- Par contre je pouvais admettre la possibilité d'afficher une partie de la Map (Tableau) avec des dimensions > 65535 pour certains axes mais en controlant que l'ensemble ne dépasse pas les possibilités d'un QWord.
J'ai dû oublié de le dire, ce qui entraine ta remarque du début à savoir que P<=QM dans tous les cas.
Ce qui entraine une autre info que je n'ai pas donnée, c'est que les variables X,Y,Z et T peuvent être de type integer ou même peut-être plus grand, je ne sais pas encore. Par exemple X = 250 000 Y = 150 Z = 1 000 000 (j'ai pas vérifié ce que ça donne, mais ça devra être possible si QM n'est pas dépassé.

Autre chose, peut être sans importance, une dimension < 4, par exemple 3, peut être obtenue avec (X, Y, Z) mais aussi (X, Y, T), (Y, Z, T), (X, Z, T).
Enfin, la dimension peut être égale à 1 (car TDim = 1..3) or elle n'est pas traitée dans le programme. En revanche, il traite le cas d'une dimension 4 qui n'appartient pas à la gamme de TDim.
Salutations

Là, c'est OK, je ne me suis pas encore penché sur le problème auquel je vais effectivement être confronté suivant l'angle de projection de la Map.
La dim 1 ne parait pas pertinente, ça serait juste une variable de distance... Pas d'intérêt à priori.

Merci Guesset pour tes reflexions qui me sont précieuses.

Je travaille par à coup, car j'ai d'autres activités, mais j'avance bien. Et je partagerais mon travail sur ce suite. Je pense que certains de mes codes seront utiles à la communauté... et pour les débutants...

A+

[Guesset]

Bonjour,

Petit programme (sous Windows) illustrant le calcul de population et le contrôle d'un volume <= 2⁶⁴ : cellscountmain.zip

Comme la population peut atteindre 2⁶⁴ cellules cela ne peut être exprimé par un uint64. Le calcul retourne alors le plus petit premier > 2³². Comme j'ai remplacé les uint16 par des uint32 pour tester la souplesse de l'algorithme face à des grands volumes très éloignés des formes cubiques, le produit ne peut faire apparaître de premiers > 2³². En en utilisant un, il est facile de détecter qu'en fait le retour est 2⁶⁴.

Le code n'utilise pas la dimension même s'il pourrait aisément la déduire (4 - nombre de coordonnee_max = 0).

L'utilisation du log₂ entier est très rapide et différencie la grande majorité des cas.

Un test rapide sur les puissance de 2 permet d'affiner la discrimination : log₂(x) = n et isPower2(x) = true => x = 2ⁿ tandis que log₂(x) = n et isPower2(x) = false => x > 2ⁿ.

Pour calculer le nombre de cellules, le code utilise Xmax + 1 (respectivement Ymax,...) en supposant que le Xmin (respectivement Ymin,...) vaut 0. Outre que cela paraît plus logique, cela à l'avantage d'éviter tout problème de division et de ne pas différencier les cas selon leur dimension :

Salutations