Discussion :

[Marco85]

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

[Baptiste Wicht]

Je te propose quelque chose comme ca :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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,

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

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

Cela me semble plus simple,
Jc

[Jean-Marc.Bourguet]

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

[fearyourself]

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:

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

[Marco85]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Merci encore,

Marco85

[Baptiste Wicht]

ohlalala, je me suis complétement loosé

mais j'ai pas du tout comprendre le problème...

[2Eurocents]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ...

[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 :

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

Pour le résoudre, il faurait donc faire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Ce qui donnerait:

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

Jc

[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

[Jean-Marc.Bourguet]

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.

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

(y/abs(y)) * y

est un moyen bien compliqué de dire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

abs(y)

A+
--
Jean-Marc

[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

[SaintAmand]

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

[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.

[sigetek]

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. }