Arrondi au multiple le plus proche ...

Version imprimable

07/03/2006, 11h30
Marco85

Arrondi au multiple le plus proche ...

Bonjour,

J'ai un nombre X (par exemple 1004) et un nombre Y (par exemple 500). Je souhaiterais trouver un algorithme me permettant d'arrondir X au multiple le plus proche de Y (dans ce cas 1000).

Auriez-vous des pistes vers lesquelles chercher ?

Merci d'avance,

Marco85

Je te propose quelque chose comme ca :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
différencePrécédente = y - x
i = 2
tant que l'on a pas trouvé : 
     différenceSuivante = (y*i) - x
     si différenceSuivante n'est pas plus petit que différencePrécédente
          alors besti = i - 1
          on termine la boucle
     sinon
          différencePrécédente = différenceSuivante
          on incrémente i et on recommence une fois la boucle
fin de la boucle
newx = y * besti

07/03/2006, 13h17
fearyourself

J'ai loupé quelque chose? Parce qu'il me semble qu'on n'a pas besoin d'une boucle, en utilisant la division entière,

Citation:

floor = (X/Y) * Y;
ceil = floor + Y;

if( X-floor< ceil-X)
return floor;
else
return ceil;

Cela me semble plus simple,
Jc
07/03/2006, 14h51
Jean-Marc.Bourguet

y*floor((x+y/2)/y)
07/03/2006, 14h59
fearyourself

Citation:

Envoyé par Jean-Marc.Bourguet

y*floor((x+y/2)/y)

Exact, sauf que si on utilise un langage acceptant la division entière (et que nos arguments soient entiers!) cela peut donc se simplifier en cela:

Citation:

y * ((x+y/2)/y)
07/03/2006, 15h06
Marco85

Citation:

Envoyé par fearyourself

Code:

y * ((x+y/2)/y)

Merci beaucoup !!! Cette solution me plaît énormément !!!

Merci encore,

Marco85
07/03/2006, 17h26
Baptiste Wicht

ohlalala, je me suis complétement loosé :oops:

mais j'ai pas du tout comprendre le problème...
08/03/2006, 16h38
2Eurocents

Si je peux me permettre, on peut envisager ...

Code:

y * ((x + ((x/abs(x)) * y) / 2) / y)

Cela aura l'avantage de trouver le multiple le plus proche aussi pour les entiers négatifs. C'est l'objectif du facteur (x/abs(x)) appliqué à y/2 ...
08/03/2006, 17h51
fearyourself

On pourrait aussi ajouter le problème du y négatif ou non...

Le seul cas qui pose problème est justement lorsque x est négatif...

-1024 -500 rendrait :

Citation:

-500 * (( -1024 + 250) / -500) = -500 * (-774/500) = -500

Pour le résoudre, il faurait donc faire:

Code:

y * ((x + ((x/abs(x)) * (y/abs(y)) * y) / 2) / y)

Ce qui donnerait:

Citation:

-500 * (( -1024 - 250) / -500) = -500 * (-1274/-500) = -1000

Jc
12/03/2006, 08h37
SaintAmand

Marco85 est peut-être satisfait, mais moi à sa place je ne le serais pas :-) et ce pour les raisons suivantes.
1) Vos formules sont très compliquées, et en tout cas peu efficaces (4 divisions et 3 multiplications !!!!) et passent sous silence les difficultés. Un bon point pour fearyourself dont la première réponse est presque parfaite. Cela dit j'ai là une idée de problème. A mon prochain devoir, je donnerais l'une de vos formules et il faudra deviner ce qu'elle calcule.
2) Vous ne précisez pas quelle convention vous utilisez pour vos divisions entières. En effet, le théorème de la division euclidienne dans ZxZ* dit que pour tous entiers (a,b) de ZxZ*, il existe au moins un couple (q,r) de ZxZ tel que a = bq + r et |r| < |b|.
Il faudrait donc préciser quelle condition vous imposez à r pour avoir l'unicité. En général 0 <= r < b ou -b/2 < r <= b/2.
Suivant les langages, et même pour un même langage (par ex. le C), suivant les implémentations on pourra avoir des variations à se sujet.

Moi ce que je propose c'est de partir de la 1ère idée de fearyourself. Pour avoir un résultat indépendant du choix de la convention pour la division euclidienne, je considérerais la division dans R et [x] désignera la partie entière (le plus grand entier inférieur ou égal à x).
Dans ce cas m = [x/y] * y est le plus grand multiple de y inférieur ou égal à x et n = m + y est le plus petit multiple de x supérieur ou égal à x. Il suffit maintenant de considérer les distances de x à m et n soit x - m et n - x. Enfin que fait-on si x est équidistant de m et n? Il faut définir une convention. Au final on s'en tire avec une division, un produit et une comparaison.

--
SaintAmand
12/03/2006, 10h34
Jean-Marc.Bourguet

Citation:

Envoyé par SaintAmand

2) Vous ne précisez pas quelle convention vous utilisez pour vos divisions entières. En effet, le théorème de la division euclidienne dans ZxZ* dit que pour tous entiers (a,b) de ZxZ*, il existe au moins un couple (q,r) de ZxZ tel que a = bq + r et |r| < |b|.
Il faudrait donc préciser quelle condition vous imposez à r pour avoir l'unicité. En général 0 <= r < b ou -b/2 < r <= b/2.
Suivant les langages, et même pour un même langage (par ex. le C), suivant les implémentations on pourra avoir des variations à se sujet.

En C, l'unicité résulte de |bq| <= |a| ce qui revient à dire que le signe de r, si r est non nul, est le signe de a. C'est aussi ce qui est demandé par Fortran et Ada (Ada a deux opérateurs pour le reste, mais un pour la division) et je ne connais pas de processeur ayant une instruction de division ne le faisant pas a part MMIX.

Je n'ai jamais vu -b/2 < r <= b/2 utilisé directement pas un processeur ou un langage. La contrainte que Knuth utilise pour MMIX, a aussi été proposée par Chinal, est l'autre opérateur de reste d'Ada, c'est signe de r est le signe de b pour r non nul.

Citation:

Moi ce que je propose c'est de partir de la 1ère idée de fearyourself. Pour avoir un résultat indépendant du choix de la convention pour la division euclidienne, je considérerais la division dans R et [x] désignera la partie entière (le plus grand entier inférieur ou égal à x).
Dans ce cas m = [x/y] * y est le plus grand multiple de y inférieur ou égal à x et n = m + y est le plus petit multiple de x supérieur ou égal à x. Il suffit maintenant de considérer les distances de x à m et n soit x - m et n - x. Enfin que fait-on si x est équidistant de m et n? Il faut définir une convention. Au final on s'en tire avec une division, un produit et une comparaison.

Contre exemple x = -10 et y = -6

En passant

Code:

(y/abs(y)) * y

est un moyen bien compliqué de dire

Code:

abs(y)

A+
--
Jean-Marc
12/03/2006, 11h37
SaintAmand

Citation:

Envoyé par Jean-Marc.Bourguet

Citation:

Envoyé par SaintAmand

Moi ce que je propose c'est de partir de la 1ère idée de fearyourself. Pour avoir un résultat indépendant du choix de la convention pour la division euclidienne, je considérerais la division dans R et [x] désignera la partie entière (le plus grand entier inférieur ou égal à x).
Dans ce cas m = [x/y] * y est le plus grand multiple de y inférieur ou égal à x et n = m + y est le plus petit multiple de x supérieur ou égal à x. Il suffit maintenant de considérer les distances de x à m et n soit x - m et n - x. Enfin que fait-on si x est équidistant de m et n? Il faut définir une convention. Au final on s'en tire avec une division, un produit et une comparaison.

Contre exemple x = -10 et y = -6

Oups, désolé. J'ai pensé (mais j'ai oublié de l'écrire) que l'on pouvait se ramener au cas ou y est positif (l'ens. des multiples de y est le même que l'ens. des multiples de -y). En effet, si y<0 alors m est le plus petit multiple de y plus grand ou egal à x et n le plus grand multiple de y plus petit ou égal à y. Il faut donc penser à écrire les distances avec les valeurs absolues (|m-x| et |n-y|) si l'on ne remplace pas y par |y|.

--
SaintAmand
12/03/2006, 12h08
SaintAmand

Citation:

Envoyé par Jean-Marc.Bourguet

En C, l'unicité résulte de |bq| <= |a| ce qui revient à dire que le signe de r, si r est non nul, est le signe de a.

Ceci est valable pour la norme C99. Sinon dans le Kernighan & Ritchie, je cite: "The direction of truncature for / and the sign of the result for % are machine-dependent for negative operands...".

--
SaintAmand
12/03/2006, 15h11
Jean-Marc.Bourguet

Citation:

Envoyé par SaintAmand

Citation:

Envoyé par Jean-Marc.Bourguet

En C, l'unicité résulte de |bq| <= |a| ce qui revient à dire que le signe de r, si r est non nul, est le signe de a.

Ceci est valable pour la norme C99. Sinon dans le Kernighan & Ritchie, je cite: "The direction of truncature for / and the sign of the result for % are machine-dependent for negative operands...".

Je sais. J'aimerais confirmation que la latitude laissé par K&R (qui se retrouve dans C90) a été utilisée. Ou même, simplement confirmation de l'existance d'une machine avec une division cablée qui ne suit pas cette règle. J'ai rencontré l'affirmation que ça existe, mais n'ai jamais trouvé le nom d'une telle machine, même pas chez Blaaw et Brooks (Computer Architecture, concepts and evolution) où l'on trouve pas mal de bêtes étranges.
21/07/2009, 13h56
sigetek

définir son multiple exemple 500
bjr , une solution en php
1. function multipleNombre ($val,$mul) {
2. $a = ((float)$val)/((float)$mul);
3. $b = intval($a);
4. if(($a-$b)<=0.5){
5. $r = $b*$mul;
6. }else{
7. $r = ($b+1)*$mul;
8. }
9. $r = max($r,$mul);
10. return $r;
11. }