Diviser et Obtenir le Reste en même temps?

Apparemment, x86 (et probablement beaucoup d'autres jeux d'instructions) de mettre à la fois le quotient et le reste d'une opération de division dans des registres distincts.

Maintenant, nous pouvons probablement faire confiance à des compilateurs pour optimiser un code comme celui-ci par un seul appel à la fracture:

( x /6 )
( x % 6 )

Et ils n'ont probablement. Encore, n'importe quel langues (ou les bibliothèques, mais surtout à la recherche pour les langues) de soutien donnant à la fois la division et modulo résultats en même temps? Si oui, quelles sont-elles et Quelle est la syntaxe ressemble?

Votre extrait de code n'est pas un exemple de quelque chose qui ne pourrait jamais être optimisé dans ce mode...
Je viens de réaliser que j'avais la mauvaise extrait de code. Mis à jour il.
Excellentes réponses de tout le monde. Suce que je ne peux en choisir un comme la "réponse" quand beaucoup d'entre eux sont des réponses valables.

InformationsquelleAutor Ben | 2010-10-09

46

C a div et ldiv. Si ces générer des instructions pour le quotient et le reste dépendra de votre bibliothèque standard de mise en œuvre et le compilateur et les paramètres d'optimisation. En commençant par le C99, vous avez également lldiv pour un plus grand nombre.
- Il est surprenant de voir pourquoi ce n'est pas acceptée réponse — il correspond exactement à ce qu'est posée.
- Intéressant de noter que modulo seul n'est pas mis en œuvre avec div en 4.8: stackoverflow.com/questions/4361979/...
- Allé de l'avant et a accepté cette réponse. Je sais qu'il y a encore beaucoup de réponses valables ici, il est donc difficile de dire que l'on est "plus à droite" que les autres, mais C est un bon point de départ pour parler de ces choses.
- Ne pas utiliser ce avec les compilateurs gcc, en particulier pour la division par une constante: il n'a pas d'optimiser. Voir godbolt.org/g/ydL27q: div(var, 10) compile en un véritable appel de la fonction, et la div mise en œuvre de bibliothèque n'a pas les informations que le diviseur est une constante 10. Donc il ne peut pas utiliser les un inverse multiplicatif. Même avec un temps d'exécution variable diviseur, vous obtenez la plus grande taille de code et non en ligne de l'appel de fonction sur x86.
- Si ces fonctions sont nécessaires ou couramment utilisés, les compilateurs aurait builtin versions d'entre eux (comme ils le font pour memcpy), mais ils ne sont pas, de sorte qu'ils n'optimisent pas presque aussi bien qu'ils le pourraient. Ainsi, il est beaucoup mieux d'utiliser n / d et n % d à proximité, avec exactement le même n et d, de sorte que le compilateur peut optimiser de manière fiable la division par une constante, la constante de propagation, et la portée de l'information. (par exemple, le compilateur connaît le résultat de la division par 10, c'est une plage plus petite que la pleine int gamme, peut-être permettant d'optimiser par la suite.)
- De toute façon, c'est une bonne réponse à cette question, mais il est important de souligner que vous ne devriez pas utiliser cette partie de la langue, à moins que vous d'abord de mettre en œuvre une assistance rapide dans le compilateur que vous utilisez. Pour la version 64 bits de la division sur une machine 32 bits, ou d'autres cas où il ne peut pas simplement inline quelque chose d'infime, gcc déjà appels internes libgcc.a de la fonction, de sorte que vous n'avez probablement jamais même enregistrer le code de taille avec ces fonctions.
- Attention à ne pas trop généraliser. Si quelque chose est optimisé ou pas dépend de la mise en œuvre de votre compilateur et/ou de la bibliothèque standard. J'ai vu des implémentations avec une optimisation des div et d'autres sans. Toujours test votre spécifiques de mise en œuvre avant de supposer que quelque chose est ou n'est pas optimisé.
- Juste point de, je voulais actuel x86 compilateurs (et à condition d'un Godbolt lien pour tester gcc/clang/CPI/MSVC). Existe-il des implémentations où vous obtenez mieux code à partir de l'appelant div que de l'écriture r = x%y; q = x/y;? C'est répandu, la plupart des bons compilateurs de l'optimiser à moins d'aliasing analyse s'arrête CST de travail (par exemple, x et y ne sont pas de simples variables locales). Si l'appel de div est la meilleure manière sur cette plate-forme, c'est ce que les compilateurs pouvait faire pour ouvrir codée % et /. Assurez-vous qu'il est bon de tester, mais je pense que l'open de codage est le plus sûr pari à travers plusieurs mises en œuvre.
- J'ai vraiment vu une div() appel de fonction optimisée pour obtenir les deux résultats à partir d'un seul DIV instruction, où séparée / et % états fonctionnement efficace de l'ensemble du calcul deux fois (je ne me souviens pas le compilateur, c'était une plate-forme intégrée, quoique). Si x est volatile, vos résultats peuvent changer pour des raisons distinctes. De nouveau, toujours la mise à l'essai un comportement spécifique à votre cas d'utilisation spécifiques avant de les optimiser pour le/autour d'elle.
InformationsquelleAutor bta

Python n'.

>>> divmod(9, 4)
(2, 1)

Ce qui est étrange, parce que Python est un langage de haut niveau.

Ne sorte de Rubis:

11.divmod(3) #=> [3, 2]

* EDIT *

Il convient de noter que le but de ces opérateurs est sans doute de ne pas faire le travail aussi efficacement que possible, il est plus probable que les fonctions de l'exactitude de l'/des raisons de portabilité.

Pour ceux qui sont intéressés, je crois c'est le code du Python de mise en œuvre pour l'entier divmod:

static enum divmod_result
i_divmod(register long x, register long y,
     long *p_xdivy, long *p_xmody)
{
long xdivy, xmody;

if (y == 0) {
    PyErr_SetString(PyExc_ZeroDivisionError,
                    "integer division or modulo by zero");
    return DIVMOD_ERROR;
}
/* (-sys.maxint-1)/-1 is the only overflow case. */
if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))
    return DIVMOD_OVERFLOW;
xdivy = x /y;
/* xdiv*y can overflow on platforms where x/y gives floor(x/y)
 * for x and y with differing signs. (This is unusual
 * behaviour, and C99 prohibits it, but it's allowed by C89;
 * for an example of overflow, take x = LONG_MIN, y = 5 or x =
 * LONG_MAX, y = -5.)  However, x - xdivy*y is always
 * representable as a long, since it lies strictly between
 * -abs(y) and abs(y).  We add casts to avoid intermediate
 * overflow.
 */
xmody = (long)(x - (unsigned long)xdivy * y);
/* If the signs of x and y differ, and the remainder is non-0,
 * C89 doesn't define whether xdivy is now the floor or the
 * ceiling of the infinitely precise quotient.  We want the floor,
 * and we have it iff the remainder's sign matches y's.
 */
if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
    xmody += y;
    --xdivy;
    assert(xmody && ((y ^ xmody) >= 0));
}
*p_xdivy = xdivy;
*p_xmody = xmody;
return DIVMOD_OK;
}

Ne divmod s'exécute qu'une seule opération? Qu'est-ce que le code de cette fonction?
Me battre pour elle. divmod() est une fonction intégrée dans Python.
Je serais prêt à parier une grande quantité de [insérer la boisson préférée] que divmod simplement effectue les deux opérations séparément et les paquets les résultats, mais n'ont aucune preuve à offrir.
La VM appelle une fonction native, qui j'espère ne un natif div instruction.
Merde, pourrait avoir remporté une boisson si j'avais vu le commentaire d'Andrew plus tôt...
hehe; en fait je libelle mon potentiel pari incorrectement! Ce que je voulais dire, je ne pense pas que c'est en essayant de tirer tout bas niveau de "trucs" pour rendre l'opération plus efficace, mais au lieu de cela n'est qu'un moyen pour enregistrer quelques séquences de touches pour le dev. 😛

InformationsquelleAutor Eloff

10

En C#/.NET, vous avez Math.DivRem:
http://msdn.microsoft.com/en-us/library/system.math.divrem.aspx

Mais selon ce fil ce n'est pas beaucoup d'une optimisation.

InformationsquelleAutor Stringer
3

Common Lisp n': http://www.lispworks.com/documentation/HyperSpec/Body/f_floorc.htm

InformationsquelleAutor Pedro Rodrigues
3

Comme Stringer Bell mentionné qu'il y avait DivRem qui n'est pas optimisé jusqu'à .NET 3.5.

Sur .NET 4.0 il utilise NGen.

Les résultats que j'ai obtenu avec Math.DivRem (debug; version = ~11000ms)
```
11863
11820
11881
11859
11854
```
Résultats que j'ai obtenu avec MyDivRem (debug; version = ~11000ms)
```
29177
29214
29472
29277
29196
```
Projet ciblé pour x86.

Math.DivRem Exemple d'utilisation
```
int mod1;
int div1 = Math.DivRem(4, 2, out mod1);
```
Signatures de méthode
```
DivRem(Int32, Int32, Int32&) : Int32
DivRem(Int64, Int64, Int64&) : Int64
```
.NET 4.0 Code
```
[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
public static int DivRem(int a, int b, out int result)
{
    result = a % b;
    return (a /b);
}
```
.NET 4.0 IL
```
.custom instance void System.Runtime.TargetedPatchingOptOutAttribute::.ctor(string) = { string('Performance critical to inline across NGen image boundaries') }
.maxstack 8
L_0000: ldarg.2 
L_0001: ldarg.0 
L_0002: ldarg.1 
L_0003: rem 
L_0004: stind.i4 
L_0005: ldarg.0 
L_0006: ldarg.1 
L_0007: div 
L_0008: ret 
```
Référence MSDN
- Cette réponse est un peu trompeur parce que le temps qui vous sautent aux yeux semblent montrer des Mathématiques.DivRem être optimisé .Net 4.0, mais comme vous le notez sur le côté un peu, en fait c'est pas optimisé du tout. En fait, dans mes tests de Mathématiques.DivRem() est légèrement plus LENTE que la naïve div et mod ops seul, sur toutes les versions de .Net. En d'autres termes, il n'est pas du tout optimisé.
InformationsquelleAutor BrunoLM
2

L' .NET framework a Math.DivRem:
```
int mod, div = Math.DivRem(11, 3, out mod);
//mod = 2, div = 3
```
Bien que, DivRem est juste un wrapper autour de quelque chose comme ceci:
```
int div = x /y;
int mod = x % y;
```
(Je n'ai aucune idée de savoir si ou non la gigue peut/veut optimiser ce genre de chose en une seule instruction.)

InformationsquelleAutor LukeH
1

FWIW, Haskell a deux divMod et quotRem que ce qui correspond directement à l'instruction machine (selon Partie intégrante des opérateurs quot vs div), tandis que divMod peut pas.

InformationsquelleAutor Jon Wolski

    int result,rest;
    _asm
    {
        xor edx, edx //pone edx a cero; edx = 0
        mov eax, result//eax = 2AF0
        mov ecx, radix //ecx = 4
        div ecx
        mov val, eax
        mov rest, edx
    }

InformationsquelleAutor Ernesto Alfonso

Cette déclaration est le résultat d'une de reste

        int result,rest;
    _asm
    {
        xor edx, edx //pone edx a cero; edx = 0
        mov eax, result//eax = 2AF0
        mov ecx, radix //ecx = 4
        div ecx
        mov val, eax
        mov rest, edx
    }

InformationsquelleAutor

0

En Java la classe BigDecimal a l'opération divideAndRemainder renvoyer un tableau de 2 éléments du résultat et de reste de la division.
```
BigDecimal bDecimal = ...
BigDecimal[] result = bDecimal.divideAndRemainder(new BigDecimal(60));
```
Javadoc: https://docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html#divideAndRemainder(java.math.BigDecimal)

InformationsquelleAutor Iván

Vous devez vous connecter pour publier un commentaire.