[Algo] A à la puissance B

Version imprimable

Bonjour,

Voila j'ai fait un petit algo pour mettre un nombre A^B.
J'aimerai savoir si cette algo est correct ou non, il me semble que j'ai repris "tous" les cas pour les puissances d'un entier.

Voila l'algo en question (il s'agit d'une fonction)
Code:

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 Fonction puissance (E: A,B : entier) : entier Déclaration I, Pows, Z : entier Début Pows = A Si A ! = 0 et B = 0 Alors Retourner 1 Sinon Si A = 0 et B > 0 Alors Retourner 0 Sinon Si (A = 0 et B = 0) ou (A = 0 et B < 0) Alors Retourner "Je ne sais pas quoi mettre car il faut un entier or c'est une forme inderterminée" Sinon Si A > 0 et B > 0 Alors Pour I allant de 1 à B faire Pows <- Pows*A Fin Pour Retourner Pows Sinon Si A > 0 et B < 0 Alors Z = B * -1 Pour I allant de 1 à Z faire Pows <- Pows/A Fin Pour Retourner Pows Sinon Si A < 0 et B < 0 Alors Pour I allant de 1 à -B faire Pows <- Pows/A Fin Pour Retourner Pows Sinon Si A < 0 et B > 0 Alors Pour I allant de 1 à B faire Pows <- Pows*A Fin Pour Retourner Pows Fin Si Fin Si Fin Si Fin Si Fin Si Fin Si Fin Si Fin puissance
Les questions que je me pose sont les suivantes:
Es-ce que l'algo est correcte ?
Es-ce qu'il n'y a pas plus simple pour calculer des puissances d'entier en "intératif" ?

J'ai aussi un problème pour la forme indeterminée que ce que je peux renvoyer car c'est de l'entier or il faudrait retourner une chaîne de caractère.

Il est vrai que je me suis inspiré d'un programme en C pour faire l'algo (je suis une bille en algo :mouarf: et encore plus en math :aie: )

Merci de votre aide :).

Cordialement,
Darkenshin.

.: Edit :.
Correction au niveau de l'initisalition et de la pagination ;)

Moi je te propse ceci, qui devrait marcher et est plus simple, il y a une erreur dans ton algo, tu n'initialiser jamais pows ! donc tu auras toujours 0 comme résultat !

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
I,Resultat : entier
Resultat = A 
 
Si A = 0 
	si B <= 0
		EXCEPTION //en algo je sais pas lever d'exception moi :cry: 
	Fin si
	retourner 0
Sinon
	si B = 0 
		retourner 0
	sinon
		pour I = 1 à (B - 1 )			
			Resultat = Resultat * A
		fin Pour
	fin si
Fin Si
 
si B < 0 alors
	resultat = 1 / resultat
fin si
 
retourner resultat

21/09/2006, 15h22
Darkenshin

Salut,

J'avoue que je ne peux pas tester mon algo vu le pc que j'ai actuellement
Justement je me suis demander si il ne fallait pas initialiser ma var, ce que j'avais commencé à faire et puis supprimer car je l'ai refait car je me suis rendu compte que je ne gére qu'un seul cas.

Je vais regarder de plus près ton algo ;)

Merci

Cordialement,
Darkenshin.
21/09/2006, 17h02
borisd

Juste une petite correction : pour tout a non nul, a^0=1.
On devrait donc initialiser Resultat à 1 puis effectuer la boucle de 1 à B.
21/09/2006, 17h12
thewho

Bonjour,

Je n'ai pas regardé ton algo, c'est juste pour faire une petite remarque:

Indenter le code, c'est bien.

MAIS, il faut rester raisonnable sur la taille l'incrément d'indentation, car, sincèrement, tu trouves que ton code est facile à lire ?

Une indentation de 2 caractères par bloc suffit normalement, sans avoir besoin ensuite d'un écran 36 pouces pour lire sans avoir à se balader de gauche à droite avec les scrollbars.
21/09/2006, 17h31
Darkenshin

@borisd: j'y penserai merci ;)

@thewho: vu les conditions de travail que j'ai je ne peux pas faire non plus autrement que d'incrémenter de cette façon.
J'avais prévu d'éditer mon code une fois chez moi ;)

Pour un algorithme d'exponentiation entière , c'est pas très efficace en itératif. Le mieux est d'utiliser une forme récursive :

Algo : Exponentiation entière rapide.

Entrée:

Code:

1
2
3
 
x : nombre entier ou réel.
n : nombre entier positif.

Sortie

Code:

x à la puissance n : x^n

Pseudo-Code :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
EXPONENTIATION( x , n )
DEBUT
SI n = 0 ALORS
    RENVOYER 1
SINON 
    SI n = 1 ALORS
        RENVOYER x
    SINON
        SI n est pair ALORS
            RENVOYER EXPONENTIATION( x, n/2 ) * EXPONENTIATION( x , n/2 )
        SINON
            RENVOYER x * EXPONENTIATION( x , n/2 ) * EXPONENTIATION( x , n/2 )
        FIN SI
    FIN SI
FIN SI
FIN

Complexité :

Code:

1
2
 
O( ln n )

pour rappel A^B = exp ( B*ln(A)) A > 0
plus rapide que récursif si A, B sont entiers >=0

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
function A_puiss_B( A, B : word) : word;  
var i : word;
   begin
   i:=1;
   while B > 0 do
      begin
      i := i*A;  // ici il faut tout de même s'assurer que i*A reste codable sur le type choisi
      dec (B);
      end;
   A_puiss_B := i;  // ici 0^0 donne 1 comme lim(x^x  lorsque x-> 0 )
   end;

Et pourquoi pas tout simplement (pour x,n >=0) :

Code:

1
2
3
4
5
6
7
8
9
 
EXP( x , n )
DEBUT
SI n = 0 ALORS
    RENVOYER 1
SINON 
    RENVOYER (x * EXP(x, n-1))
FIN SI
FIN

21/09/2006, 23h17
Darkenshin

@PRomu@ld, il est vrai que ça serait plus simple en récursif seulement je ne suis pas encore tout a fait au point à ce niveau là.

Comme dit ce que tu me montre là est très bien le seul problème c'est que je suis une grosse bille en maths :aie:, pour moi ton "EXPONENTIATION( x , n/2 )" ne me parle en rien :s désolé.

@j.p.mignot, ton algo me parle encore moins que celui de PRomu@ld de plus j'avoue ne pas connaitre cette structure d'algorithme.

@Hephaistos007, merci cette algo me parle un peu plus.

Je penses que vous avez remarqué qu'il s'agit d'un exercice de cours basique et j'ai des contraintes comme le fait que les 2 nombres peuvent être positif, négatif, voir null, j'ai fait cette algo depuis un programme en C ce qui explique le fait qu'il ne soit pas forcement le mieux, le plus simple, le plus rapide, le plus optimisé ceci dit en thèorie il fonctionne après quant à savoir si est le bon je ne sais pas trop ^^

J'aimerai quand même rester sur l'algo que j'ai fait, je vous remercie des réponses que vous m'avez donné.

Serait-il possible de corriger celui-ci au lieux de partir sur d'autre algo ?
Merci par avance :)

Cordialement,
Darkenshin.
22/09/2006, 09h58
millie

L'algorithme de Scorpyosis fait les mêmes choses que le tiens, mais avec une notation beaucoup plus propre. Il reste juste les exceptions à gérer (par exemple 0^0 qui n'est pas définie). Je te conseille donc de prendre celui là si tu ne veux pas faire de récursif.

Sinon, pour d'autres personnes qui souhaiteraient faire cela, c'est vrai que l'algo de @PRomu@ld est le mieux de ceux proposé car beaucoup plus rapide.

La fonction de calcul de A^B de @PRomu@ld s'appelle EXPONENTIATION, c'est donc cette fonction qu'il appelle dans son algorithme (donc programmation récursive) mais qui est de bien meilleure complexité comme il l'a fait remarqué.

@millie, Tu parles de "l'algorithme de Scorpyosis" or je ne l'ai pas vu ;)
Je peux aussi simplifié mon algo :) au départ j'avais fait ça:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Fonction puissance (E: A,B : entier) : entier Déclaration I, Pow : entier Début Pows <- A Pour I allant de 1 à B faire Pows <- Pows*A Fin Pour Retourner Pows Fin puissance
Qui est quand même un poil simpliste surtout quand il faut gérer positif, négatif, nulle :aie:

22/09/2006, 10h40
lyxthe

juste pour rajouter
juste pour dire, si j'ai bien compris l'algo de Promu@ld , il manque quelque chose de ce genre là je crois :
Code:

1 2 3 4 SINON n=n-1 RENVOYER x * EXPONENTIATION( x , n/2 ) * EXPONENTIATION( x , n/2 ) FIN SI
enfin je pense que je suis pas le seul à l'avoir remarqué mais c'est quand même interessant de le rajouter...
Ou alors j'ai strictement pas compris l'algo.
22/09/2006, 10h56
PRomu@ld
Citation:
Envoyé par lyxthe

juste pour dire, si j'ai bien compris l'algo de Promu@ld , il manque quelque chose de ce genre là je crois :

Code:

1 2 3 4 SINON n=n-1 RENVOYER x * EXPONENTIATION( x , n/2 ) * EXPONENTIATION( x , n/2 ) FIN SI

enfin je pense que je suis pas le seul à l'avoir remarqué mais c'est quand même interessant de le rajouter...
Ou alors j'ai strictement pas compris l'algo.
En fait, tu as compris l'algo, je pense, mais ce que tu n'as pas compris, c'est l'opérateur /, il s'agit de la division euclidiène. Ainsi, 5 / 2 vaut 2.
22/09/2006, 11h01
lyxthe

ha oki

au temps pour moi. Mais je suis quand même content d'avoir saisi le truc :p

Citation:

Tu parles de "l'algorithme de Scorpyosis" or je ne l'ai pas vu

Je cite, scorpyosis a écrit à son premier post cet algorithme là.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
I,Resultat : entier
Resultat = A 
 
Si A = 0 
	si B <= 0
		EXCEPTION //en algo je sais pas lever d'exception moi :cry: 
	Fin si
	retourner 0
Sinon
	si B = 0 
		retourner 0
	sinon
		pour I = 1 à (B - 1 )			
			Resultat = Resultat * A
		fin Pour
	fin si
Fin Si
 
si B < 0 alors
	resultat = 1 / resultat
fin si
 
retourner resultat

Et qui gère tous les cas.

22/09/2006, 16h13
Darkenshin

Oups merci autant pour moi millie

Merci à tous c'est réglé ;)
22/09/2006, 16h23
Jean-Marc.Bourguet
Citation:
Envoyé par PRomu@ld

Complexité :

Code:

1 2 O( ln n )
Ah bon? Je serais d'accord si on évitait le double appel récursif, mais comme il est présent deux fois...

L'algo que tu voulais, mais avec la recursivité enlevée:

Pour n entier positif ou nul:
Code:

1 2 3 4 5 6 7 8 9 resultat = 1.0; facteur = a; while n != 1 loop if n mod 2 = 1 then resultat = resultat*facteur; end if; facteur = facteur*facteur; n = n / 2; end loop;
22/09/2006, 19h04
j.p.mignot

Tout à fait d'accord que l'algorithme ci-dessus est en O(ln(n)) et celui que j'ai
donné est en O(n).
Toutefois pour une puissance de 10 on va gagner environ un facteur 3 sur les itérations mais avec un test 'if' et un 'modulo'. Est ont- vraiment encore gagnant ?
Pour des puissances élevées, de toute façon le problème sera un problème de codage.
Même avec n=a = 10, a^n = 1001010100000010111110010000000000 => 34 bits
ce qui dépasse déjà le LongWord...
Donc TRES rapidement il faudra passer en float (=> incertitudes sur résultat ) ou utiliser des manipulations du codage de très grands entiers ( il existe des débats à ce sujet sur ce forum ) ce qui n'est pas forcement si aisé ni sans conséquence sur a vitesse. De plus de tels entiers peuvent vraiment être problématiques sur certains processeurs.
22/09/2006, 19h39
PRomu@ld

Citation:

Envoyé par Jean-Marc.Bourguet

Ah bon? Je serais d'accord si on évitait le double appel récursif, mais comme il est présent deux fois...

Oui, je n'ai fait qu'appliquer une formule mathématique pour produire un algo. Le double appel récursif dépend, il me semble, du langage et/ou du système utilisé. (mapple il me semble mémorise les appels récursifs).

Mais en toute rigueur, tu as raison, ayant personnellement effectué certaines hypothèses
22/09/2006, 20h44
Jean-Marc.Bourguet

Citation:

Envoyé par j.p.mignot

Tout à fait d'accord que l'algorithme ci-dessus est en O(ln(n)) et celui que j'ai donné est en O(n).

J'ai juste corrigé (et enlevé la récursion) un algo donné avant.

Citation:

Toutefois pour une puissance de 10 on va gagner environ un facteur 3 sur les itérations mais avec un test 'if' et un 'modulo'. Est ont- vraiment encore gagnant ?

Question intéressante... le modulo 2, s'il pose problème il vaut mieux changer de compilateur si on est intéressé par les performances: c'est tester le bit le moins significatif.

Le saut est peut-être plus génant surtout qu'il ne peut pas être prédit, mais les multiplications restent quand même coûteuse, surtout quand on ne peut pas les pipeliner avec d'autres choses comme ici; il faudrait mesurer mais je crains que ça dépendent fortement du compilateur et de la cible: correctement schedulé, la deuxième multiplication de la boucle peut être faite avant et son délai masquer le saut ou l'autre multiplicitation. Naturellement, si on est dans un cas où la multiplication est logicielle la question ne se pose pas. On sort de toute manière de l'algorithmique.