Suite de Syracuse

**Akhey** · 02/10/2009, 17h40

Bonjour,
Je suis sur Borland Pascal, et je galère avec mon petit machin, à savoir la suite de Syracus où je dois afficher seulement les suites où les itérations sont plus élevées que les suites précédentes...
On m'a dit de mettre une autre boucle après la première pour afficher seulement les compteurs plus élevés, mais j'ai pas dû tout capter...
Pourriez-vous m'aider svp ?
Merci

**darrylsite** · 02/10/2009, 19h38

Sans code, je ne vois pas du tout comment on peut te répondre. Le mieux c'est de montrer ce que tu as dejà fait, et exposer ensuite clairement ta pré-ocupation.

Je crois avoir dejà lu quelques posts sur la suite de syriacus dans ce forum. Une petite recherche pourra peut etre t'aidé.

**Akhey** · 03/10/2009, 18h28

Voilà ce que j'ai fait pour le moment. Ca affiche toutes les suites, alors que je souhaite afficher seulement celles qui ont des itérations plus élevées.
(merci d'avance ^^)

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
program suite_de_syracuse;
 
  uses
    WinText;
 
  var
    n, i, vMax : Integer;                         {-suite, terme initial de la suite, valeur max}
    cpt: Integer;                                 {-compteur de boucles}
    depass: boolean;                              {-quand il devient vrai on arrête la boucle}
                                                  {si elle ne finit pas par 1 : avant de dépasser les capacités de Integer}
begin
    Writeln('Suite de naturels de Syracuse');
    Writeln('Determination des suites les plus longues');
 
    n := 1;
    i := 0;
    vMax := (maxInt - 1) div 3;
    depass := False;
    repeat
       i := i + 1;
       n := i;
       cpt := 0;
       repeat
          Write(n: 8);
          if n mod 2 = 0 then
            begin
              n := n div 2;
            end
          else if n > (maxInt - 1) div 3 then
            begin
              depass := True
            end
          else
            begin
              n := n * 3 + 1;
            end;
          cpt := cpt + 1
       until (n = 1) or depass;
       Writeln(n: 8);
 
 
       if depass then
         Writeln('----------------- dépassement après');
         Writeln('----------------- ', cpt, ' itérations pour ', i)
    until depass;
end.

**darrylsite** · 05/10/2009, 16h48

Qu'appelles tu iterations plus elements? Sont elles qui ont le max d'iteration? ou fixes tu une limite pour savoir si une iteration est elevée ou pas?

Pour connaitre le nombre d'iteration d'une suite donnée, tu peux la mettre dans une fonction qui te donne le nombre de son iteration.

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
 
function iteration(i : byte) : integer;
 var n, cpt : integer;
      depass: boolean;
begin
       n := i;
       cpt := 0;
      depass:=false;
 
       repeat
          if n mod 2 = 0 then
            begin
              n := n div 2;
            end
          else if n > (maxInt - 1) div 3 then
            begin
              depass := True
            end
          else
            begin
              n := n * 3 + 1;
            end;
          cpt := cpt + 1
       until (n = 1) or depass;
 
    iteration:=cpt;
end;

il te suffit d'appeler cette fonction pour un i donnée pour savoir le nombre d'iteration que ça fait. Ensuite, si la valeur est elevé tu peux l'afficher.

**Dr.Who** · 07/10/2009, 15h23

on peut faire une toute petite amélioration qui multiplie les performances par 2 :

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
const
  MaxIntS1D3 = (MaxInt-1) div 3;
 
function iteration(const i : byte) : integer;
var n, cpt : integer;
    depass : boolean;
begin
  n      := i;
  cpt    := 0;
  depass := false;
 
  repeat
    if (n and $1) = 0 then // si n est pair
      n := n shr 1            // n divisé par 2
    else
    if n > MaxIntS1D3 then
      depass := True
    else
      n := n * 3 + 1;
 
    cpt := cpt + 1;
  until (n = 1) or depass;
 
  iteration := cpt;
end;

pourquoi AND $1 au lieu de MOD 2 :

MOD fait appel à une division en premier puis retourne le reste de cette division. il y a donc plusieurs instructions assembleur qui sont appelée et .. ça prend du temps :

if (n and $1) = 0 then n := n shr 1 else ...

desassemblage :
test al,$01;
jnz @jump if not zero :to: if n > MaxInt...;
shr eax,1;
jmp @jump :to: Cpt := Cpt + 1...;

2 instructions sur faux, 4 sur vrai

if (n mod 2) = 0 then n := n div 2 else ...

desassemblage :
mov eax,esi;
and eax,$80000001;
jns @jump if no sign :to: test eax, eax;;
dec eax;
or eax,-$02;
inc eax;
test eax,eax;
jnz @jump if not zero :to: if n > MaxInt...;
mov ecx,$00000002;
mov eax,esi;
cdq;
idiv ecx;
mov esi,eax;
jmp @jump :to: Cpt := Cpt + 1...;

8 instructions sur faux, 14 sur vrai

voila, 14 instructions contre 4 ... de -6 à -10 instructions par itérations...
sans compter le reste.

pourquoi $1 ?

c'est simple, toute les puissances de 2 sont paire (sauf 2^0 = 1)

donc le seul moyen de faire un 7, un 9, un 1215 est de mettre le bit 0 de l'entier à 1!

exemple :

0000 = 0 &1=0
0001 = 1 &1=1
0010 = 2 &1=0
0100 = 4 &1=0
1000 = 8 &1=0

donc

3 = 0011 (2+1) &1= 1
5 = 0101 (4+1) &1= 1
9 = 1001 (8+1) &1= 1
11 (0xB) = 1011 (8+2+1) &1= 1
13 (0xD) = 1101 (8+4+1) &1= 1
256891 (0x3EB7B) = 0xB = 1101 &1= 1

pourquoi shr 1 ?

le binaire est basé sur les puissances de 2, glisser les bits vers la droite (SHR) fait passer tout les bits à 1 aux puissances inférieures et comme ce sont des puissances de 2 ... cela reviens à diviser par 2 (pour shl 1) ou par une puissance de 2. inversement quand on glisse les bits vers la gauche (SHL) fait passer les bits à 1 aux puissances supérieures et donc cela reviens à multiplier par 2 (pour shl 1) ou par une puissance de 2.

souviens toi : 1 2 4 8 16 32 64 128 256
chaque nombre suivant est le double du précédent, ce sont les puissances de 2.
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16

si j'ai :
1000 (8) : 1000 shr 1 = 0100 = 4
1100 (8+4=12) : 1100 shr 1 = 0110 = 4+2 = 6
plus dur avec un nombre impaire :
1011 (8+2+1=11) : 1011 shr 1 = 0101 = 4+1 = 5 = 11 div 2 = round(11/2)

et on peut faire pareil pour toutes les puissances de 2
diviser par 4 :: shr 2
diviser par 8 :: shr 3
diviser par 16 :: shr 4
diviser par 32 :: shr 5
diviser par 1024 :: shr 10

etc.

et inversement pour les multiplications : on utilise SHL :
shl 1 = *2
shl 2 = *4
shl 3 = *8
shl 4 = *16
shl 10 = *1024

etc.

**darrylsite** · 07/10/2009, 18h02

Envoyé par Dr.Who

on peut faire une toute petite amélioration qui multiplie les performances par 2 :

J'aime ça

Tu n'as pas de lien à me proposer sur le sujet?

**Dr.Who** · 07/10/2009, 18h33

non désolé, l'optimisation à ce niveau se fait en évitant les pièges du genre :

mod 2 > and $1

div 2^n > shr n
* 2^n > shl n
sqr(v) > v*v

while do > repeat ... until / for do

if i = 1 then .. else if i = 2 then .. else if i = 3 then .. else .. :
case of (si possible)

mises en cache des variables "constante" :
length(S), high(matrix), low(table), list.count-1, stream.size, stream.position

pré-calcul des valeurs dans des tableaux, surtout en contexte entiers (non flottant) :
sinus, cosinus, racine carrée, etc.

convertion statique en tableaux :
HexByteToChar : array[0..$f] of char = '0123456789ABCDEF';
CharToByte : array['0'..'9'] of byte = (0,1,2,3,4,5,6,7,8,9);
FastDiv3 : array[0..8] of byte = (0,0,0,1,1,1,2,2,2);
FastMod3: array[0..8] of byte = (0,1,2,0,1,2,0,1,2);

voila, c'est ce genre de petites choses.

et bien sur, toujours mesurer les performances des routines comme ceci par exemple :

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
procedure TForm1.Button1Click(...);
var PS, PE: int64;
     N, GT : cardinal;
     D : integer; 
begin
  GT := GetTickCount;
  QueryPerformanceCounter(PS);
 
  for N := 1 to 100000 do
  begin
    D := N;
    GimmeGimme(D, BA);
    GimmeGimme(D, AB);
  end;
 
  QueryPerformanceCounter(PE);
  GT := GetTickcount-GT;
 
  (sender as TButton).caption := format('%.2n Kc / %3n Sec',[(PE-PS)*0.001, GT*0.001]);
end;

ici on aurat une chaine du genre :
420 Kc / 1.215 Sec
ce qui donne le nombres de cycles cpu et le temps d'execution approximatif de la boucle (soit 100000*2 appels à GimmeGimme).
note l'optimisation dans format (*0.001 au lieu de /1000).

voila.

**droggo** · 08/10/2009, 17h52

Sio,

Oui pour l'amélioration.

Cependant, si un compilateur Pascal était correctement optimisé, il verrait le test par rapport à mod 2, et le remplacerait par un test de bit, ce que font les bons compilateurs C ou C++.

Qui veut tester ça avec FreePascal ou autre(s) (pas TurboPascal et autres dinosaures, trop vieux pour implémenter de telles optimisations).

**darrylsite** · 09/10/2009, 14h24

Envoyé par Dr.Who

while do > repeat ... until / for do

J'aii fait quelque verification sous fpc, et c'est bien le contraire L'utilisation d'un repeat est bien plus lent qu'un while ou un for.

**Dr.Who** · 09/10/2009, 16h53

Envoyé par darrylsite

J'aii fait quelque verification sous fpc, et c'est bien le contraire L'utilisation d'un while est bien plus lent qu'un repeat ou un for.

le > n'etait pas pour "superieur a" mais pour "remplacer part"

j'aurais du mettre -> plutot que >

tout comme j'avais ecris :

mod 2 > and $1

div 2^n > shr n
* 2^n > shl n
sqr(v) > v*v

...