Comment calculer le module d'un nombre entier non signé de 64 bits ?

Question

Note : Cette question est différente de Méthode la plus rapide pour calculer un entier de 128 bits modulo un entier de 64 bits .

---

Voici un violon en C# :

https://dotnetfiddle.net/QbLowb

---

Étant donné le pseudo-code :

UInt64 a = 9228496132430806238;
UInt32 d = 585741;

Comment puis-je calculer

UInt32 r = a % d?

Le problème, bien sûr, c'est que je ne suis pas dans un compilateur qui supporte l'option UInt64 type de données. 1 Mais j'ai accès au système Windows ULARGE_INTEGER syndicat :

typedef struct ULARGE_INTEGER {
   DWORD LowPart;
   DWORD HighPart;
};

Ce qui signifie vraiment que je peux transformer mon code ci-dessus en :

//9228496132430806238 = 0x80123456789ABCDE
UInt32 a = 0x80123456; //high part
UInt32 b = 0x789ABCDE; //low part
UInt32 r = 585741;     

Comment s'y prendre

Mais maintenant, il s'agit de faire le calcul proprement dit. Je peux commencer par la division longue au crayon et au papier :

       ________________________  
585741 ) 0x80123456  0x789ABCDE

Pour simplifier, nous pouvons travailler en variables :

Maintenant, nous travaillons entièrement avec des types non signés 32 bits, que mon compilateur fait soutien.

u1 = a / r; //integer truncation math

v1 = a % r; //modulus

Mais maintenant, je suis dans l'impasse. Parce que maintenant je dois calculer :

v1||b / r

En d'autres termes, je dois effectuer la division d'une valeur de 64 bits, ce que je n'ai pas pu faire en premier lieu !

Ce problème doit déjà être résolu. Mais les seules questions que je trouve sur Stackoverflow sont des gens qui essaient de calculer :

a^b mod n

ou d'autres opérations multiprécises cryptographiquement importantes, ou en virgule flottante approximative.

Lecture en prime

• Microsoft Research : Division et modulus pour les informaticiens
• https://stackoverflow.com/questions/36684771/calculating-large-mods-by-hand
• Méthode la plus rapide pour calculer un entier de 128 bits modulo un entier de 64 bits (question sans rapport ; je vous déteste, vous autres)

1 Mais il soutient Int64 mais je ne pense pas que cela m'aide.

Travailler avec le support Int64

J'espérais une solution générique pour le module d'exécution par rapport à un module d'action. ULARGE_INTEGER (et même LARGE_INTEGER ), dans un compilateur sans support natif 64 bits. Ce serait la réponse correcte, bonne, parfaite et idéale, que d'autres personnes pourront utiliser en cas de besoin.

Mais il y a aussi la réalité du problème i ont. Et cela peut conduire à une réponse qui n'est généralement utile à personne d'autre :

• la tricherie en appelant une des fonctions Win32 pour les grands nombres entiers (bien qu'il n'y en ait pas pour le module)
• en utilisant le support 64 bits pour signé nombres entiers

Je peux vérifier si a est positif. Si c'est le cas, je sais que le support intégré de mon compilateur pour Int64 s'occupera :

UInt32 r = a % d; //for a >= 0

Ensuite, il y a la façon de traiter l'autre affaire : a est négatif

UInt32 ModU64(ULARGE_INTEGER a, UInt32 d)
{
   //Hack: Our compiler does support Int64, just not UInt64.
   //Use that Int64 support if the high bit in a isn't set.
   Int64 sa = (Int64)a.QuadPart;
   if (sa >= 0) 
      return (sa % d);

   //sa is negative. What to do...what to do.

   //If we want to continue to work with 64-bit integers,
   //we could now treat our number as two 64-bit signed values:
   // a == (aHigh + aLow)
   //       aHigh = 0x8000000000000000
   //       aLow  = 0x0fffffffffffffff
   //
   // a mod d = (aHigh + aLow) % d
   //         = ((aHigh % d) + (aLow % d)) % d //<--Is this even true!?

   Int64 aLow  = sa && 0x0fffffffffffffff;
   Int64 aHigh =       0x8000000000000000;

   UInt32 rLow  = aLow  % d; //remainder from low portion
   UInt32 rHigh = aHigh % d; //this doesn't work, because it's "-1 mod d"

   Int64 r = (rHigh + rLow) % d;

   return d;
}

Réponse :

Cela a pris du temps, mais j'ai finalement obtenu une réponse. Je voulais la poster en tant que réponse, mais Z29kIGZ1Y2tpbmcgZGFtbiBzcGVybSBidXJwaW5nIGNvY2tzdWNraW5nIHR3YXR3YWZmbGVz les gens ont décidé par erreur que ma question unique était une copie exacte.

UInt32 ModU64(ULARGE_INTEGER a, UInt32 d)
{
   //I have no idea if this overflows some intermediate calculations
   UInt32 Al = a.LowPart; 
   UInt32 Ah = a.HighPart;

   UInt32 remainder = (((Ah mod d) * ((0xFFFFFFFF - d) mod d)) + (Al mod d)) mod d;

   return remainder;
}

Violon

Answer 1

Je viens de mettre à jour le code de ma classe ALU32 dans ce rapport. AQ :

• Impossible de faire propager la valeur par la retenue

Comme CPU code indépendant de l'assemblage pour mul,div a été demandé. Le diviseur résout tous vos problèmes. Cependant, il utilise Division longue binaire C'est donc un peu plus lent que d'empiler les 32 bits. mul/mod/div opérations. Voici la partie pertinente du code :

void ALU32::div(DWORD &c,DWORD &d,DWORD ah,DWORD al,DWORD b)
    {
    DWORD ch,cl,bh,bl,h,l,mh,ml;
    int e;
    // edge cases
    if (!b ){ c=0xFFFFFFFF; d=0xFFFFFFFF; cy=1; return; }
    if (!ah){ c=al/b;       d=al%b;       cy=0; return; }
    // align a,b for binary long division m is the shifted mask of b lsb
    for (bl=b,bh=0,mh=0,ml=1;bh<0x80000000;)
        {
        e=0; if (ah>bh) e=+1;   // e = cmp a,b {-1,0,+1}
        else if (ah<bh) e=-1;
        else if (al>bl) e=+1;
        else if (al<bl) e=-1;
        if (e<=0) break;        // a<=b ?
        shl(bl); rcl(bh);       // b<<=1
        shl(ml); rcl(mh);       // m<<=1
        }
    // binary long division
    for (ch=0,cl=0;;)
        {
        sub(l,al,bl);           // a-b
        sbc(h,ah,bh);
        if (cy)                 // a<b ?
            {
            if (ml==1) break;
            shr(mh); rcr(ml);   // m>>=1
            shr(bh); rcr(bl);   // b>>=1
            continue;
            }
        al=l; ah=h;             // a>=b ?
        add(cl,cl,ml);          // c+=m
        adc(ch,ch,mh);
        }
    cy=0; c=cl; d=al;
    if ((ch)||(ah)) cy=1;       // overflow
    }

Regardez le lien AQ pour la description de la classe et des sous-fonctions utilisées. L'idée derrière a/b est simple :

1. définition

   Supposons que nous ayons une division 64/64 bits (le module sera un produit partiel) et que nous voulions utiliser l'arithmétique 32 bits :

   (ah,al) / (bh,bl) = (ch,cl)

   chaque QWORD 64 bits sera défini comme un DWORD 32 bits haut et bas.

2. aligner a,b

   exactement comme la division informatique sur le papier, nous devons aligner b alors il se divise a donc trouver sh que :

   (bh,bl)<<sh <= (ah,al)
   (bh,bl)<<(sh+1) > (ah,al)

   et calculer m donc

   (mh,ml) = 1<<sh

   attention, au cas où bh>=0x80000000 arrêtez le déplacement ou nous allons déborder...

3. diviser

   résultat du jeu c = 0 et ensuite simplement soustraire b de a tandis que b>=a . Pour chaque soustraction, ajoutez m a c . Une fois que b>a changer les deux b,m droite pour s'aligner à nouveau. Arrêtez si m==0 o a==0 .

4. résultat

   c contiendra le résultat de la division en 64 bits, donc utilisez cl et de la même manière a contient le reste, alors utilisez al comme résultat de votre module. Vous pouvez vérifier si ch,ah sont zéro si aucun débordement ne se produit (car le résultat est plus grand que 32 bits). Il en va de même pour les cas limites comme la division par zéro...

Maintenant, si vous voulez 64bit/32bit, il suffit de définir bh=0 ... Pour ce faire, j'avais besoin d'opérations en 64 bits (+,-,<<,>>) ce que j'ai fait en empilant des opérations 32bit avec des Carry (c'est la raison pour laquelle mon ALU32 a été créée en premier lieu) pour plus d'informations, voir le lien ci-dessus.