Algo

Comment faire x^n ?

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : Comment faire x^n ?

Kalimuxo

Reprise du message précédent :
Personne n'a d'idée ?

---------------
/* Signature */

Publicité

Chronoklazm

La masturbation de neurones un dimanche soir, defois c'est pas evident

Kalimuxo

c'est vrai ^^

---------------
/* Signature */

pascal_

Kalimuxo a écrit :

Personne n'a d'idée ?

Le code de HelloWorld ne marche pas :??: ?

Chronoklazm

Kalimuxo a écrit :

Merci les gens ^^

Sinon autre problème :

a<--- a +1 OK
a<---- a + b MAL
a<----- a + 2 MAL

En gros faire x^n avec uniquement des manipulations avec des 1...

pascal_ => Same player play again ! :wahoo:

Message édité par Chronoklazm le 13-12-2004 à 00:08:23

Ace17

Chronoklazm a écrit :

pascal_ => Same player plays again ! :wahoo:

:ange:

Lam's

Profil: bas.

Ace17 a écrit :

:ange:

C'est de l'impératif, pas de l'indicatif.

En anglais, l'impératif et le subjonctif s'expriment de la même façon que la forme infinitive, sans la préposition "to".

Donc, same player, play again.

Ace17

Au temps pour moi, mais dans ce cas il faut mettre la virgule!

Lam's

Profil: bas.

Pas forcément. C'était peut-être du subjonctif, comme dans:

God save the queen !

nick-nitro

dynamite

on peut utiliser des tablaux

---------------
boom

Publicité

gilou

Modérateur
Modzilla

Chronoklazm a écrit :

Code :

int somme(int x, int n){
if (n == 1)
return x;
else
return x + somme(x, (n - 1));}
int pow-iter(int x, int n, int k){
if (n == 0) return 1;
else if (n == 1) return x;
else if (n == 2) return k;
else return pow-iter(x, (n - 1), somme(x, k));}

Voilà quoi ! :kaola:

EDIT : C'est sur :jap: et bien c'est ce que je fais .

On pete la pile pour quelle valeur de n?
A+,

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

chrisbk

gilou a écrit :

On pete la pile pour quelle valeur de n?
A+,

tu feras un overflow d'entier avant de peter la pile, je crois bien

spokup

et l'algo d'exponentiation rapide ??

Pow(x, n);

result = x;
p = n;

while p
p pair (p%2==0) -> result*=result; p>>=1;
p impair (p%n!=0) -> result*=x; p--;
end loop

un truc du style ...

spokup

arf sans utilisé les multiplication

excusez moi je suis hors sujet !

Taz

bisounours-codeur

ça change rien, ta méthode est quand même logarithmique

masklinn

í dag viðrar vel til loftárása

je comprend pas ce que le premier prog d'helloworld a de mal (sauf ptet une ou deux bornes dans les boucles), il fonctionne nickel pour x^n avec n > 0 et x >= 0
(et avec une valeur absolue bien placée il fonctionne même pour x < 0)

alors non il est pas optimisé ni rien, c'est une forme la plus développée possible (la plus simple au niveau conceptuel), mais ca fonctionne.
(en python ca donne

def pow(a,b):
""" pow(a,b)-> result
Compute and return a^b
b must be > 0"""
r = a
for i in range(b-1):
inter = r
r = 0
for j in range(abs(a)):
r+=inter
return r

(me dites pas que ca fonctionne pas, j'arrive à calculer -564^1567 avec)
(c'est un peu long par contre)

Message édité par masklinn le 15-12-2004 à 16:13:46

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody

Chronoklazm

gilou a écrit :

On pete la pile pour quelle valeur de n?
A+,

Gilou je pige pas là, j'ai une recursivité terminale et ca devrai quand meme peter la pile ?

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !

gilou

Modérateur
Modzilla

Chronoklazm a écrit :

Gilou je pige pas là, j'ai une recursivité terminale et ca devrai quand meme peter la pile ?

non:

Code :

int pow-iter(int x, int n, int k)
{
...
else return pow-iter(x, (n - 1), somme(x, k));
}

Tu as une recursivite en n qui peut faire peter ta pile par depassement du nb d'appels recursifs possibles empiles.
C'est pas parce que tu commences par n et que tu decrois que le nb d'empilements d'appels a pow-iter ne fera pas peter ta pile pour une grande valeur de n (en fait ca se regle en parametrant au moment de la compilation (souvent parametrage par la valeur par defaut, donc non vu par le programmeur), et sous unix, ca peut se modifier apres coup).

chrisbk a écrit :

tu feras un overflow d'entier avant de peter la pile, je crois bien

probablement

A+,

Message édité par gilou le 15-12-2004 à 22:56:12

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

dreameddeath

Petit essai d'algo à chaud sans récursivité.

Code :

int pow(int x,unsigned int n)
{
if(x==0) return 0; // j'ai un doute sur 0^0
if(n==0) return 1;
total=1; //cas général
if((n%2 == 1)&&(x<0)) total=-1; //seul cas ou le resultat sera négatif
for(i=1;i<=n;++i)
{
soustotal=total; //soustotal vaut x^(i-1)
for(j=1;j<=abs(x);++j)// on fait total=x*soustotal
{
total+=soustotal;
}
}
return total;
}

Voilà j'espère que je n'ai pas fait d'erreur

Je suis ouvert à toute critique :hello:

++

Message édité par dreameddeath le 03-01-2005 à 16:01:03

Chronoklazm

N'importe quoi puissance 0 ca rend 1 mais 0 puissance n'importe quoi sauf 0 rend 0 pourtant ta fonction pow(0,0) rend 0 ... pas bon.

Apres tu fait à la ligne 6 un modulo, je crois qu'on veut uniquement des additions de +1 ... donc pas bon.

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !

dreameddeath

bah en fait il suffit donc d'inverser les deux premières lignes pour le pb du 0^0. Pour le coup du modulo je ne pensais pas aller jusque là mais bon.
Voilà la nouvelle version qui n'a que des additions "+="

Code :

int pow(int x,unsigned int n)
{
if(n==0) return 1;
if(x==0) return 0;
total=1; //cas général
tmp=n;
while (tmp>0) tmp+=-2; //boucle pour émuler le modulo 2 et pas de décalages car on a le droit qu'aux additions :)
if((tmp<0)&&(x<0)) total=-1; //seul cas ou le resultat sera négatif
for(i=1;i<=n;++i)
{
soustotal=total; //soustotal vaut x^(i-1)
for(j=1;j<=abs(x);++j)// on fait total=x*soustotal
{
total+=soustotal;
}
}
return total;
}

Voilà, voilà

Chronoklazm

gilou a écrit :

non:

Code :

int pow-iter(int x, int n, int k)
{
...
else return pow-iter(x, (n - 1), somme(x, k));
}

Bon en fait je me suis renseigné et je pense que dans ce cas (ou on a une recursivité terminale) il n'y aura pas de depassement de pile car, à priori le compilateur gcc optimise la recursivité terminale (option de compilation -o9 je sais pas si c'est par defaut). Sinon j'ai appris que les recursivités croisés ne sont pas optimisé par gcc, je doute d'ailleurs qu'ils soient optimisables tout court.
Voila, donc pas de danger pour la pile (avec gcc en tout cas)

fra0

Code :

// lol il y a des endroits plus appropriés pour utiliser la récursivité
int powpowpowpow(int a, unsigned b)
{
if(!b--) return 1;
unsigned x=abs(a),n=b,i,j,k,l;
for(l=x ; i = x, k = 0, n-- ; l=k) while(i)
for(j = i & 1 ? l : 0 , i = j ? i - 1 : i >> 1 , l <<= !j ; j-- ; k++);
return b&1||a>0?l:-l;
}

maximew

Coffee and cigarettes and Cate

fra0 a écrit :

Code :

// lol il y a des endroits plus appropriés pour utiliser la récursivité
int powpowpowpow(int a, unsigned b)
{
if(!b--) return 1;
unsigned x=abs(a),n=b,i,j,k,l;
for(l=x ; i = x, k = 0, n-- ; l=k) while(i)
for(j = i & 1 ? l : 0 , i = j ? i - 1 : i >> 1 , l <<= !j ; j-- ; k++);
return b&1||a>0?l:-l;
}

Magnifique!

---------------
Mon Flickr

matthieu_phpmv

fra0 a écrit :

Code :

// lol il y a des endroits plus appropriés pour utiliser la récursivité
int powpowpowpow(int a, unsigned b)
{
if(!b--) return 1;
unsigned x=abs(a),n=b,i,j,k,l;
for(l=x ; i = x, k = 0, n-- ; l=k) while(i)
for(j = i & 1 ? l : 0 , i = j ? i - 1 : i >> 1 , l <<= !j ; j-- ; k++);
return b&1||a>0?l:-l;
}

maahh qu'est ce ? Comment telle prouesse est elle possible ? :heink: :love:
as tu la théorie derrière ça ?

---------------
développeur de phpMyVisites mesure d'audience de sites Internet

Chronoklazm

matthieu_phpmv a écrit :

maahh qu'est ce ? Comment telle prouesse est elle possible ? :heink: :love:
as tu la théorie derrière ça ?

On dirait du Brainfuck :ouch:

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !

IrmatDen

C'est clair que c'est totalement hallucinant.
>fra0 : c'est sympa de poster un algo qui déchire tout, mais peux-tu nous donner quelques explications stp ?

trictrac

+1, une petite explicationde comment t'es arrivé a ca ne serait pas de refu

dark86

heu, pourquoi je ne comprends aucune ligne du code de fra0???

IrmatDen

parce que ses noms de variables sont hyper explicites?

dark86

et peut-etre aussi que j'avais jamais vu de "boucle" for avec rien deriere....

fra0

c'est ma façon de contourner la contrainte sur l'addition

TOTO=TOTO+TITI;

s'écrit

TOTO+=TITI;

ou encore

for(;TITI--;TOTO++);

après, c'est l'algorithme classique par multiplications successives.
A un moment, il faut multiplier A par B (donc aditionner A; B fois...)
Partant du principe qu'il vaut mieux additionner une fois 2A que deux fois A et à fortiori une fois 4A que quatre fois A...
je décime B, selon sa parité : si B est pair (B&1 == B%2 = faux), je le divise par deux et je multiplie A par 2 (grâce à des décalages (d/g) de 1) ; si B est impair (B&1 == B%2 = vrai), je lui enlève 1 et j'ajoute A au résultat (avec la troisième boucle qui ne se déroule que pour faire ce k+=j). Je recommence tant qu'il en reste dans B (multiplication égyptienne) je fixe le problème du signe à la fin grâce à l'exposant modifié.

Mais l'algo n'est pas optimal (en terme d'incréments) il suppose que 'b' est beaucoup plus petit que 'a' (dans a^b) et n'utilise pas vraiment l'exponentiation rapide.

C'était C3PO au milieu des Ewoks :hello:

IrmatDen

De mon point de vue, c'est plus du R2D2 que C3PO...

Citation :

Mais l'algo n'est pas optimal (en terme d'incréments) il suppose que 'b' est beaucoup plus petit que 'a' (dans a^b) et n'utilise pas vraiment l'exponentiation rapide.

Que veux tu dire par "b beaucoup plus petit que a" ?

Merci de tes eclaircissements...

fra0

J'ai essayé d'écrire l'aglo fonctionnel le plus court possible (pour des types de taille arbitraire) pas le plus rapide. Pour assurer le steak, j'ai fait quelques suppositions sur les valeurs de a et b.

Il y a des façons plus fines d'évaluer 2^2048 par exemple...

Ce que trouvais drôle, c'était de simuler la récursivité avec des structures de contrôle ('l' a deux cycles de vie et est utilisée comme une pile, 'j' contrôle l'élagage de l'arbre) sans branchements ni stockage superflu.

IrmatDen

ok. Merci de tes infos, c'est très instructif de voir d'autres façon de faire... Il me reste plus qu'à prévoir une petite pile d'aspirine pour décomposer et comprendre ton implémentation

slvn

A mon avis, il faut tout sauf lire l'implementation.
c'est du "brain fuck" comme dit Chronoklaz, que seul son auteur peut comprendre

(Merci en tout cas, car au passage, je viens de decouvrir qu'on pouvait mettre plusieurs elements au milieu d'un "for()" )

Pour la comprehension de l'algo, il y a deux choses distinctes:

la multiplication x*y sans utiliser de multiplication :

Il faut ecrire y comme somme de puissance de 2, et calculer chaque puissance de 2 avec un "left shit".
Si on pose y = a*2^0 + b*2^1 + c*2^2 + ... avec a,b,c valant 1 ou 0.
alors x*y vaut a(x<<0) + b(x<<1) + c(x<<2) + ...

Par exemple, x*10 == x<<1 + x<<3 puisque 10 vaut en héxa 0x1010.

Le deuxième algorithme est celui d'exponentionation rapide pour calculer x^y:

si on ecrit y en puissance de 2,
y = a*2^0 + b*2^1 + c*2^2 + ... avec a,b,c valant 1 ou 0. On peut réduire le nombre de multiplication nécessaire.

Par exemple: pour y == 15 == 0x1111
x^y = x * (x^2) * (x^4) * (x^8) //4 multiplication
Mais il faut calculer les carrés:
x^2
(x^2)^2 == x^4
(x^4)^4 == x^8
Soit 3 multiplications. Ce qui au final demande 7 multiplications au lieu des 15 initiales.

Pour calculer x^n sans aucune multiplication, on utilise d'abord l'exponentionation rapide pour reduire le nombre de multiplication, puis on faire chacune de multiplication avec des décalages

Voila, sinon comme le dit fra0, il y a différents petits trucs a checker.. Les overflows qui arrivent rapidement, et pour savoir si un nombre est une puissance de 2, on évaluer l'expression suivante: "0 == x&(x-1)"

++
Sylvain

Message édité par slvn le 15-03-2005 à 18:30:38

IrmatDen

C'est mon tube d'aspi qui va être content
Merci de m'avoir précisé tout ça

papy_danone

faites des reductions logarithmiques. Au lieu d'incrementer que de 1 dans vos boucles à chaque passage, multipliez par 2 (en décalant les bits vers la gauche, comme ca pas de signe * ), la complexité de l'algo passe de n en log(n).

fra0

exemple

fra0

démonstration...

Code :

/// pow (pour les types intégraux)
/// sans addition (autre que +1/-1), ni multiplication,
/// optimisée de haut (exponentiation rapide) en bas (addition binaire en temps constant) en passant presque par le milieu
/// réponses en une fraction* de milliseconde (env 2µs sur un Athlon 1.4GHz dans le type natif).
// ex : ALU <unsigned __int64> boulier;
#define MAXBITS (8*sizeof(uinteger))
#define decimate(x,p) (x=p?x-1:x>>1)
template <class uinteger> class ALU
{
private:
inline bool _getBit(uinteger data,int n) { return data>>n&1; } //
inline void _setBit(uinteger &data, unsigned n, bool value) { data|=(uinteger)value<<n; } //
public:
uinteger add(uinteger a, uinteger b)
{
bool r1,r2,carry=false;
uinteger result=0;
for(unsigned bit=0;bit<MAXBITS;bit++)
{
r1=_getBit(a,bit);
r2=_getBit(b,bit);
_setBit(result,bit,r1==r2==carry); // r1^r2^carry
carry=r1?r2|carry:r2&carry; // r1&r2|r1&carry|r2&carry;
}
#ifdef CHECK
assert(carry==false && "sinon dépassement de capacité dans add" );
#endif
return result;
}
uinteger mult(uinteger a, uinteger b)
{
bool predicate;
uinteger maxi=max(a,b),result=0;
for(uinteger mini=min(b,a);mini>0;decimate(mini,predicate))
{
predicate=_getBit(mini,0);
if(predicate) result=add(result,maxi);
else
{
#ifdef CHECK
uinteger old=maxi;
#endif
maxi<<=1; // ou : maxi=add(maxi,maxi); au quel cas la fonction peut s'écrire comme pow...
#ifdef CHECK
assert(old<=maxi && "sinon dépassement de capacité dans mult" );
#endif
}
}
return result;
}
uinteger pow(uinteger x, unsigned n)
{
bool predicate;
uinteger accu[2]={x,1};
for(unsigned rest=n;rest>0;decimate(rest,predicate))
{
predicate=_getBit(rest,0);
accu[predicate]=mult(accu[predicate],accu[0]);
}
return accu[1];
}
};

edit :

suppression du stockage quadratique des masques binaires
rajout des tests de débordement

C'était pour quoi faire au fait ?

Message édité par fra0 le 19-03-2005 à 19:24:18

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

Algo

Comment faire x^n ?

Sujets relatifs
Plus de sujets relatifs à : Comment faire x^n ?

Page générée en 0.222 secondes