Discussion :

[Invité]

Comme vous le savez peut être, l'opérateur % en Java, ne calcule pas le modulo, mais le reste de la division euclidienne.

Pour a%b
Si a >=0, pas de problème, % calcule bien le modulo
Mais si a<0 , le résultat est négatif ! (Ce qui ne devrait pas être le cas du modulo)

L'opérateur % est assez problématique, lors d'un calcul d'index dans un tableau "cyclique".

J'ai cherché assez longtemps (sur internet) une "opération sur une seule ligne" qui fasse l'équivalent du modulo.
Finalement, je suis tombé sur une formule toute bête :

a mod b == (a % b + b) % b

Je n'ai vu cette solution quasiment nul part.
Elle pose un problème ?

[polymorphisme]

Bonjour,

Comme vous le savez peut être, l'opérateur % en Java, ne calcule pas le modulo, mais le reste de la division euclidienne.
...
Mais si a<0 , le résultat est négatif ! (Ce qui ne devrait pas être le cas du modulo)

Quelles sont tes sources pour écrire ca ?

Pourrais tu nous rappeler les définitions mathématiques, dans l'ensemble des entiers naturels N puis dans l'ensemble des entiers relatifs Z, de :
-- l'opérateur binaire modulo
-- la division euclienne

Puis faire le liens entre les deux ... ton sujet m'interresse bien puisque je compte implémenter cette opération ...

[tchize_]

Quelles sont tes sources pour écrire ca ?

Java language specifications, section 15.17.3

5%3 produces 2 (note that 5/3 produces 1)
5%(-3) produces 2 (note that 5/(-3) produces -1)
(-5)%3 produces -2 (note that (-5)/3 produces -1)
(-5)%(-3) produces -2 (note that (-5)/(-3) produces 1)

Si tu ne vois jamais d'implémentation de ton code, c'est que c'est souvent plus lisible et plus facile à faire de rester dans des entiers (et ça diminue le nombre d'opérations)

[Invité]

Si tu ne vois jamais d'implémentation de ton code, c'est que c'est souvent plus lisible et plus facile à faire de rester dans des entiers (et ça diminue le nombre d'opérations)

?
un peu de mal à comprendre là ^^

[tchize_]

mal exprimé désolé, je réitère

Si tu ne vois jamais d'implémentation de ton code, c'est que c'est souvent plus lisible et plus facile à faire de rester dans des nombres positifs (et ça diminue le nombre d'opérations) en ne travaillant que par des incrémentations dans les boucles. (Puisque souvent le modulo est utilisé par des boucles)

[Invité]

Dans mon cas, la décrémentation est utile :
Je parcours un tableau contenant des File (obtenu en listant un dossier),
en me décalant par rapport au File actuellement sélectionné (grâce à la molette de la souris : avant ou arrière).

Comme "%" ne permet pas de traiter les modulo négatif, "(a % b + b) % b" m'est particulièrement utile.
ça m'évite juste de devoir traiter manuellement 2 cas.

[Captain'Flam]

Une petite remarque avec 2 ans de retard :

ta solution calcule 2 fois un modulo... bof !

Je te propose celle-ci

Code :

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

1
2
3
4
int mod ( int x , int y )
    {
    return x >= 0 ? x % y : y - 1 - ((-x-1) % y) ;
    }

qui ne calcule qu'un seul modulo.
Il y a un test en plus, mais en terme de performance, c'est quand même mieux.

[Invité]

T'as fait un benchmark?

[tchize_]

Si on fais un benchmark, on verra pas de différence.

Si on fait un calcul de tête, on va voir que d'un coté on a un modulo, de l'autre on a une comparaison et deux sauts conditionnel. Aucun gain, mais un code au final devenu illisible.

[Captain'Flam]

J'ai fait un bench sous Visual Studio 2005 Pro, sur un PC équipé d'un Intel Core 2 duo - 6400 à 2.13 GHz.

Voici le code

Code :

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

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
int mod1 ( int x , int y )
    {
    return (x % y + y) % y ;
    }
 
int mod2 ( int x , int y )
    {
    return x >= 0 ? x % y : y - 1 - ((-x-1) % y) ;
    }
 
void test_mod ( void )
    {
    int n,x,y,z = 0 ;
    int t0,t1 ;
 
    t0 = get_time_ms() ;
    for ( n = 0 ; n < 1000 ; ++n )
        for ( y = 1 ; y < 1000 ; ++y )
            for ( x = -1000 ; x < 1000 ; ++x )
                z += mod1( x,y ) ;
    t1 = get_time_ms() ;
    printf("mod1 : %d\n",t1-t0,z ) ;
 
    t0 = get_time_ms() ;
    for ( n = 0 ; n < 1000 ; ++n )
        for ( y = 1 ; y < 1000 ; ++y )
            for ( x = -1000 ; x < 1000 ; ++x )
                z += mod2( x,y ) ;
    t1 = get_time_ms() ;
 
    printf("mod2 : %d\n",t1-t0,z ) ;
    }

(get_time_ms est une fonction qui renvoie le nb de millisecondes écoulées depuis le lancement)

et après une compilation en Release, voici l'affichage

Code :

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

1
2
mod1 : 22329
mod2 : 11727

J'ai relancé le bench plusieurs fois et les résultats sont toujours (quasiment) les mêmes.

On voit qu'on a un rapport presque 2, ce qui signifie que le modulo prend quasiment la totalité du temps d’exécution des fonctions mod1 et mod2.

Ça ne me surprend pas, car un modulo n'est autre qu'une division (connue pour son coût CPU) alors qu'un test par rapport à 0 et un saut ne coûtent presque rien sur les processeurs modernes.
Dans certains cas, le saut peut même être "gratuit".

[tchize_]

On aurait préféré un bench en java mais j'admet mon erreur d'estimation

Cependant, ce bench n'est vraisemblablement pas représentatif du code de l'utilisateur (qui semble avoir besoin de son modulo en réaction à un mouvement de molette), Je constate surtout qu'on gagne en rendant le code illisible 11 secondes toutes les 2E19 opérations. A part dans les cas critiques où la perte de perfs peut être reportées sur la dites méthode de calcul, il n'y a aucun raison de prématurément rendre le code illisible pour gagner 0,0055µs par calcul.

Surtout que depuis 2 ans, la méthode précédente semble lui convenir .

[thelvin]

Nous sommes en section Java, pas C.
Passer par le bytecode et sa compilation JIT, ça fait une différence.

Par contre, en ce qui me concerne je trouve qu'aucune des deux méthodes n'est bien lisible, et j'ai une préférence pour la seconde.

[-gma-]

C'est vrai que le bench en C ça pourrait être sujet à polémique

D'ailleurs je ne suis pas un grand spécialiste de l'algèbre mais pour moi il n'y a pas une ligne moins illisible que l'autre.
Dans tous les cas je préfère avoir une méthode (ou une fonction ) qui s'appelle "modulo" dont le comportement est précisé en commentaire et que je peux appeler les yeux fermés. Et à ce moment là autant qu'elle soit optimisée, même si elle prend 6 lignes au lieu d'une seule

[Captain'Flam]

Je vous présente mes humbles doubles excuses :
- je suis tombé sur ce forum via Google et j'y ai posté mon message sans même me rendre compte qu'il s'agissait de java...
- en tant que vieux briscard du code c/c++, j'ai toujours un vieux réflexe de recherche de perf plus tellement d'actualité avec des langages super évolués comme java.

Toutefois, je suis bien d'accord avec -gma- : ce genre de fonction super bas niveau doit être optimisée + testée + commentée à mort, puis utilisée sans se soucier des détails de son implémentation.
Une fois qu'on a une couche d'outils génériques bien au point, le code de plus haut niveau doit, lui, être super lisible, car c'est lui qu'on aura à débugger...

Enfin, ce n'est que mon avis.

[Logan Mauzaize]

T'as oublié de la mettre en DEFINE ou sinon en inline

Avis partagé par bien des gens. Surtout ceux de notre "espèce" (les javaistes) habitués des langages haut niveau.

[tchize_]

Le language n'a pas grande importance malgré tout dans ce cas, les résultat sont les mêmes avec java

Mais en java, il est déconseillé de présupposé des performances du processeur à l'arrière. Dans ce cas si vous tomber juste chez moi et probablement chez d'autre. Mais souvent des optimisations de ce style, marchent chez un utilisateur, on l'effet inverse chez un autre et, de toutes façons, n'ont qu'un effet marginal sur le code global.


Ici vous avez présenté un code qui ne fait que des calculs du modulo. En pratique, le modulo ne sera probablement qu'une infime partie de l'algorithme final. Tant qu'on a pas identifié que le code nécessite une optimisation, c'est une très mauvaise habitude de vouloir à tout prix l'optimiser.


D'ailleurs je serais curieux de tester ce code sur les serveur de calcul vectoriel à mon boulot pour comparer .