Trouver un maximum entre 2 chiffres sans tests

Version imprimable

20/03/2005, 16h02
orichimaru

Trouver un maximum entre 2 chiffres sans tests

alors voila j'ai un exo assez particulier : je dois construire une fonction qui renvoie entre 2 nombres entier le plus grand des 2
sans aucun test cad pas de if, pas de while pas < pas de > rien du tout juste des + des - des * des / des >> et des <<

la je suis largué, je me demande meme si c'est possible ....;
20/03/2005, 16h13
KORTA
euh
Code:

1 2 m =random(a,b)
ca marche qu'une fois sur 2 , héhé :wink:
20/03/2005, 16h15
orichimaru

c impossible alors ?
packe dans ce cas c'est que le prof se fout de nous
20/03/2005, 16h18
KORTA

Citation:

Envoyé par orichimaru

c impossible alors ?
packe dans ce cas c'est que le prof se fout de nous

je suis en train d'y réfléchir plus sérieusement que dnas mon précédent post, mais il semble qu'à ma connaissance ca ne soit pas possible sans utiliser de structure conditionellle.
si j'ai une idée je te la communqiue
20/03/2005, 16h19
Giovanny Temgoua

salut!

Sans condition, cà risque être chaud :?

En effet, on aurais pu utiliser la différence entre les deux nombres et suivant que le résultat de l'opération sera négatif ou non dire quel est le plus grand.

Donc, je pense que c'est tout simplement pas possible.

A+
20/03/2005, 16h24
KORTA

ton probleme revient a trouver le max de deux nombres à partir d'opérations élementaires mathématiques; à ma connaissance c'est impossible..
Une des raisons qui me poussent a dire ca et qui est purement informelle est que pour trouver le maximum il faut à un moment ou un autre comparer les deux nombres, ce qui reveint a utiliser une structure conditionnelle
20/03/2005, 16h29
orichimaru

hmmm pourtant j'ai bien devant mes yeux le dm d'info
et la question est : "determiner une fonction qui retournera un maximum entre 2 nombres sans user de structures conditionnelles (if,while,...) ni les operateurs > et <"

donc je me demande si il ne ve pas qu'on trouve une fonction deja existante qui le fait
20/03/2005, 16h47
Laurent Gomila
Si la valeur absolue est autorisée :
Code:

1 2 max(a, b) = ((a + b) + |a - b|) / 2 min(a, b) = ((a + b) - |a - b|) / 2
Informatiquement on peut coder la valeur absolue sans conditionnelle, mais mathématiquement ça s'en rapproche tout de même.
20/03/2005, 17h01
Le Furet

en codant |x|=sqrt(x^2)

Ca n'a bien sûr strictement aucun intérêt.
20/03/2005, 17h02
Neo82

Et comment fais tu pour calculer une valeur absolue sans tests?

C'est possible en considérant la représentation des nombres en mémoire.. mais bon je ne sais pas si c'est ce que le professeur demande

Sinon c'est vrai que c'est curieux comme question :)

Ou alors sqrt((a - b)*(a - b)) mais bon encore faut'il pouvoir utiliser la fonction racine carré

Bizare....

Si la machine utilise le complément à 2 pour représenter les entiers négatifs, alors on peut écrire (en C++) ceci:
Code:

1 2 3 4 5 6 7 8 9 10 const int BITS_PER_INT; typedef unsigned int uint; uint abs ( int x ) { uint sign = (uint)x >> ( BITS_PER_INT - 1 ); return ( (uint)x ^ ~( sign - 1 ) ) + sign; }
Si la machine utilise un bit de signe, on peut écrire ceci:
Code:

1 2 3 4 5 6 uint abs ( int x ) { return ( x << 1 ) >> 1; }

20/03/2005, 17h36
Neo82

Mais ca dépend de la machine alors non?
20/03/2005, 17h39
Selenite

Citation:

Envoyé par Neo82

Mais ca dépend de la machine alors non?

Oui... Mais c'est tout ce que j'ai trouvé :?
20/03/2005, 17h49
Neo82

Bah oui...

quelqu'un sait comment est calculée une racine carrée?

Si on trouve un moyen de la calculer uniquement avec des opérations, c'est gagné, mais je pense que c'est encore plus dur :) LOL

Bien curieux de voir la solution
20/03/2005, 17h52
Laurent Gomila

Je sais qu'il existe une formule récursive pour calculer une racine carrée, mais je ne m'en souviens jamais.

De toute façon je suppose que ça se règle comme d'habitude avec un développement limité.
20/03/2005, 17h56
Selenite

Pour la racine carrée, tu peut toujours utilisé u_(n+1) = ( u_n + a/u_n ) / 2 et déroullé la boucle, mais bon... c'est pas terrible comme solution.
20/03/2005, 17h56
Neo82

Oui surement

Il faut voir... on sait jamais des fois que ca serait possible de passer par la :)

Bourrin mais bon, si ca marche

Ceci marche. Mais niveau élegance, il y a mieux ;-)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
uint abs ( int x )
{
 
	float fx = x*x;
	float fr = 1;
 
	fr = ( fr + fx/fr ) / 2;
	fr = ( fr + fx/fr ) / 2;
	fr = ( fr + fx/fr ) / 2;
	fr = ( fr + fx/fr ) / 2;
	fr = ( fr + fx/fr ) / 2;
	fr = ( fr + fx/fr ) / 2;
 
	return (uint) fr;
 
}

Pour les grands nombre, il faut augmenter le nombre d'itération.

20/03/2005, 18h04
Le Furet

Citation:

Envoyé par Loulou24

Je sais qu'il existe une formule récursive pour calculer une racine carrée, mais je ne m'en souviens jamais.

De toute façon je suppose que ça se règle comme d'habitude avec un développement limité.

Ca ne se règle quasiment jamais par des développements limités 8)
20/03/2005, 18h23
orichimaru

a uéééééééé
putain loulou24 tu dechires
ct evident
sinon pour la valeur absolu ct une question o dessus

aaaaaaa
merchi a tous
merci infiniment a tous :ave: :ave: :ave:
20/03/2005, 18h29
orichimaru

a ui et pour moi g utilisé |x|=sqrt(x²)
et pis g utilisé que la somme des n premiers nombre impair=n²
mais j'utilise une condition
20/03/2005, 18h31
Selenite

Citation:

Envoyé par orichimaru

a ui et pour moi g utilisé |x|=sqrt(x²)
et pis g utilisé que la somme des n premiers nombre impair=n²
mais j'utilise une condition

Le plus simple pour n², n'est-il pas n*n ?
20/03/2005, 18h34
Neo82

LOL

non mais le but du jeu il faut croire que c'est de se compliquer la vie :D

Faut deja etre fou pour se poser des questions comme ca!!

g mal au crane la .... keske g fé ....

fais chier ce dm a la noix :roll:

bon voila le resultat :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unsigned short sqrt_(short x) 
{ 
	unsigned short s=0,i=0;
	while(s<=x)
	s+=2*(i++)+1;
	return i-1;
} 
unsigned short abs_(short x)
{return sqrt_((x*x));}
short max(short x, short y)
{
	return ((x+y)+abs_(x-y))/2;
}
int main (void)
{
	printf("%d",max(35,24));
	return 0;
}

[/code]

20/03/2005, 19h31
Laurent Gomila

Citation:

Envoyé par Le Furet

Citation:

Envoyé par Loulou24

Je sais qu'il existe une formule récursive pour calculer une racine carrée, mais je ne m'en souviens jamais.

De toute façon je suppose que ça se règle comme d'habitude avec un développement limité.

Ca ne se règle quasiment jamais par des développements limités 8)

Ah, autant pour moi. Ca se règle comment alors, les sqrt, cos, sin, exp, etc... ?
20/03/2005, 20h22
Le Furet

La racine carrée, par l'algorithme de Newton, qui donne la suite donnée par Sélénite (y'en a aussi des faciles à implémenter pour les racines n-ièmes ou l'inverse).

Pour les autres fonctions, je ne sais pas. Je crois que les approximants de Padé (approximation de la fonction par une fonction rationnelle) sont beaucoup plus performants que les Développements en Série Entière (et pas les DL, ça se ressemble mais c'est pas pareil). Il y a aussi des développements de ces fonctions en produit qui je crois sont plus performants.
20/03/2005, 20h23
orichimaru

ben pour les fonctions trigo si je me souviens bien il existe un algo connu pour tangente (je crois que c briggson mais je suis pas sur)
un truc qu'on demontre avec mapple en sup
ensuite on exprimer cos sin arccos arcsin et arctan avec tan et le tour est joué

voici un lien http://www.trigofacile.com/trigo/cordic.htm
edit1 [cross]
edit2 [lien]

Citation:

Envoyé par Neo82

Bah oui...

quelqu'un sait comment est calculée une racine carrée?

Si on trouve un moyen de la calculer uniquement avec des opérations, c'est gagné, mais je pense que c'est encore plus dur :) LOL

Bien curieux de voir la solution

C'est possible avec des multiplications et des soustraction, mais il faut des tests bien sûr : :?

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
exemple pour 16384 :
On groupe les chiffres par 2 à partir de l'unité.
On prend le plus grand nombre dont le carré est inférieur au nombre le plus a gauche (avec les groupements par deux), ici 1
1 63 84 | 1
        | 1 x 1 = 1
On fait la soustraction, on obtient 0
 1 63 84 | 1
-1       | 1 x 1 = 1
 0 63    | 2 
 
On abaisse le 63 et on double le nombre de la première ligne et on cherche par quel nombre le compléter et le multiplier pour obtenir le plus grand produit inférieur à 63, ici 2 (car 3 donnerait 23 x 3 = 69)
 1 63 84 | 1
-1       | 1 x 1 = 1
 0 63    | 22 x 2 = 44
  -44
   19
 
Le 2 complète le 1, on double 12 = > 24, on abaisse le 84, et on complète le 24 avec un 8
 1 63 84 | 12
-1       | 1 x 1 = 1
 0 63    | 22 x 2 = 44
  -44    | 248 x 8 = 1984
   19 84
  -19 84
   00 00 
 
La racine carrée de 16 384 est 128.

21/03/2005, 11h15
maamar

je croix l'idée se trourne auteur de ca

2 / 9 ( 2 div 9 )

| 9
2 |__
|
| 0

A = 2
B = 9

si B est max => le resultat de la division = 0
sinon
A

la question à resoudre comment je sache que ce resultat égale à Zero :?: :arf:
21/03/2005, 14h53
Nemerle

Effectivement, le plus simple et très rapidement la suite

U(0)="what you want!"
U(n+1)=(U(n)+A/U(n))/2

qui converge vers sqr(A), mais je n'ai plus la vitesse de convergence en tête (go goole!).

Concernant le développement de Padé, la vitesse de convergence est effectivement incomparable! Pour rappel , un dèv. de Padé (U0,U1,U2,...) signifie

U0/(U1+1/(U2+1/(U3+1/....

Par exemple, (2,3,5) signifie 2/(3+1/5). Sous certaines conditions, il y a des opérations de base sur cette écriture rapidement implémentables.
:wink:
21/03/2005, 18h31
ceugniet

Citation:

Envoyé par Nemerle

Effectivement, le plus simple et très rapidement la suite

U(0)="what you want!"
U(n+1)=(U(n)+A/U(n))/2

qui converge vers sqr(A), mais je n'ai plus la vitesse de convergence en tête (go goole!).

La réponse est "vite". En fait le nombre de bits corrects est plus que doublé à chaque étape. Donc, meilleure est la première approximation, plus rapidement survient la convergence.

Euh, ça dépend de ce que l'on appelle vite. Il faut se ramener à un intervalle entre 1 et 4 par des divisions ou des multiplications par 4. Et puis il faut partir d'une première évaluation aussi précise que possible. Je viens de faire un petit test :
Pour x=2
eval init= 1.49804687500000000 = 3ff7f80000000000 erreur relative : 0.06
eval = 1.41655929147653192 = 3ff6aa3a135bc943 erreur relative : 0.0017
eval = 1.41421550455972289 = 3ff6a0a06fd9484a erreur relative : 0.0000014
eval = 1,41421356237442875 = 3ff6a09e667f5343 erreur relative : 0.000000000001
eval = 1.41421356237309515 = 3ff6a09e667f3bcd erreur relative : 0.0
eval = 1.41421356237309515 = 3ff6a09e667f3bcd erreur relative : 0.0

Pour x=3.999 (le pire des cas, en ce qui concerne ma "première approximation")

eval init= 2.49414062500000000 = 4003f40000000000 erreur relative : 0.25
eval = 2.04874924750391552 = 400063d6a53ddf15 erreur relative : 0.025
eval = 2.00033593401776111 = 400000b0204cf58d erreur relative : 0.0003
eval = 1.99975007019287832 = 3ffffef9edfa6f12 erreur relative : 0.00000004
eval = 1.99974998437304841 = 3ffffef9d6f0f0a8 erreur relative : 0.000000000000001
eval = 1.99974998437304663 = 3ffffef9d6f0f0a0 erreur relative : 0.0
eval = 1.99974998437304663 = 3ffffef9d6f0f0a0 erreur relative : 0.0
racine de 3.99900000000000011 = 1.99974998437304663

Mais bien sûr, il faut détecter la convergence, et pour cela, il faut un test !!!!! Bon, peut-être certains tests sont possibles...faut voir
24/03/2005, 10h57
Karim RACHEDI

Si tu n'as pas trouvé la solution, je t'en propose une:
en suposant que (a div b) retourne la partie entière de la division de a par b:
Max(a,b)=(a*(a div b) + b* (b div a))/ ( a div b + b div a)

si ça pose un problème penses à me le dire :wink:
25/03/2005, 11h05
David.V

Citation:

Envoyé par Karim RACHEDI

Si tu n'as pas trouvé la solution, je t'en propose une:
en suposant que (a div b) retourne la partie entière de la division de a par b:
Max(a,b)=(a*(a div b) + b* (b div a))/ ( a div b + b div a)

si ça pose un problème penses à me le dire :wink:

J'ai un contre exemple avec a=-5 et b=5. Sinon ça avait l'air de tenir la route.

Edit : un autre avec a=-2 et b=-5. En clair, dès qu'il y a au moins un nombre négatif, ça ne marche plus.