Efficiente (cicli saggio) algoritmo per calcolare il modulo 25?

Ho un codice in cui ho il calcolo di x % 25. x assume sempre un valore positivo, ma la sua gamma dinamica è di grandi dimensioni.

Ho scoperto che questo particolare codice pezzo di elaborazione di un x % 25 è l’assunzione di grandi cicli. Ho bisogno di ottimizzazione.

Pre-calcolate tabella di ricerca è esclusa a causa del possibile di memoria di grandi dimensioni della tabella.

Come secondo approccio ho codificato un frammento di seguito(codice C) –

mod(a, b)
{   
    int r = a;  
    while(r >= b)
    {      
        r = r - b;
    }   
    return r;
}

1.) Come posso ottimizzare questo codice per cicli(spremere al max)?

2.) C’è completamente diverso ottimizzata per ottenere x % 25( so che la sua non è un’operazione comune, ma ancora, cercando intelligente ingressi di persone potrebbero essere state utilizzate per la loro esperienza che potrebbe nelp me.).

Grazie.

-ANNUNCIO

EDIT:

Penso che utilizzando un nativo operatore modulo % in C , internamente utilizza una operazione di divisione ( /), che è costosa sul processore sto usando.(Nessuna istruzione div). quindi, cercando di vedere se l’opzione di implementazione può battere inerenti il calcolo utilizzando operatore%.

-ANNUNCIO

  • Pensi che è possibile ottimizzare % operatore scrivendo codice C? Forse ci sono alcuni collegamenti in assemblea, ma dubito paio di righe di C in grado di eseguire meglio operatore predefinito.
  • Così che cosa è la gamma dinamica, all’incirca? Si dice che non è possibile utilizzare una tabella di ricerca, ma anche una piccola tabella di ricerca sarebbe di aiuto.
  • i compilatori dei compromessi. Non cercare sempre per la velocità più veloce. È di solito abbastanza facile da battere di un compilatore per un caso specifico, perché il compilatore gestisce il caso generale.
  • “Ho scoperto che questa … è l’assunzione di grandi cicli. Ho bisogno di ottimizzazione.” Questa è una cosa piacevole da ascoltare! Un’ottimizzazione domanda dove è stato effettivamente eseguito attraverso un profiler.
  • Se si identifica il processore, che non dispone di una operazione di divisione – poi devi avere migliori risposte più veloce.
  • non è possibile ottimizzare %, ma potrebbe essere in grado di ottimizzare il 25%. Non più di tanto in quanto il relativo costo di divisione (e modulo) è sceso sensibilmente nei sistemi desktop e la dimensione del codice, è diventato un problema. Per le altre piattaforme, questi trucchi funzionano ancora.
  • Infatti è usuale che i compilatori di gestire il caso specifico. E. g. GCC/X86 produce molto efficiente divisione-meno codice per il 25%. Sono sicuro che questo è vero per molti altri compilatori.
  • Non abbiamo mai fatto capire che processore usa. Solo che manca di un div. C’era stato un enorme quantità di lavoro fatto su x86, la generazione del codice. Compilatori per altri processori, spesso, non hanno avuto quel tipo di attenzione.
  • È probabile che un BRACCIO.
  • Down-votato – a causa di tutti i grandi, grandi input di persone hanno messo in questa domanda, senza nemmeno un soffio di cura da parte del poster originale, figuriamoci un segno V per l’cercato di risposta (stackoverflow.com/a/980973/451461).
  • dopo un lungo periodo di tempo, ancora non ha accettato di rispondere

InformationsquelleAutor goldenmean | 2009-06-11



21 Replies
  1. 30

    Vi suggerisco di leggere Hacker Delizia. Descrive molto veloce resto algoritmi per la costante divisori. Avrebbero quasi certamente battere un algoritmo generale.

    Aggiornamento: Ecco un esempio di codice… probabilmente può essere rielaborato per evitare la temporanea lungo.

    unsigned mod25(unsigned n)
    {
        unsigned reciprocal = 1374389535; //2^35 /25
        unsigned div25 = ((unsigned long long)n * reciprocal) >> 35;
        return n - div25 * 25;
    }
    • Sì c’è una veloce divisione per 5 c’. Farlo due volte e sei a posto se avete un rapido moltiplicarsi. Tutto dipende dai dettagli della sua di videoscrittura (word dimensioni, istruzioni) e la gamma di ingressi. C’è anche un fresco modulo 5, che sarebbe probabilmente aiutare.
    • GCC su x86 utilizzare questo algoritmo per il calcolo del % 25 – se si controlla lo smontaggio, troverete il numero magico, un mull e un shrl istruzione (il passaggio sarà solo da 3 e non 35, perché del valore di posizionamento nei registri)
    • Questa è la risposta corretta.
    • GCC dovrebbe ottimizzare il modulo da un costante come in questo caso, su tutta la piattaforma supporta
  2. 8

    Ecco un’altra soluzione che mi è venuta:

    int mod25(int x){
      /* 25 * (all powers of 2 <= INT_MAX), descending */
      if (x >= 1677721600) x -= 1677721600;
      if (x >=  838860800) x -=  838860800;
      if (x >=  419430400) x -=  419430400;
      if (x >=  209715200) x -=  209715200;
      if (x >=  104857600) x -=  104857600;
      if (x >=   52428800) x -=   52428800;
      if (x >=   26214400) x -=   26214400;
      if (x >=   13107200) x -=   13107200;
      if (x >=    6553600) x -=    6553600;
      if (x >=    3276800) x -=    3276800;
      if (x >=    1638400) x -=    1638400;
      if (x >=     819200) x -=     819200;
      if (x >=     409600) x -=     409600;
      if (x >=     204800) x -=     204800;
      if (x >=     102400) x -=     102400;
      if (x >=      51200) x -=      51200;
      if (x >=      25600) x -=      25600;
      if (x >=      12800) x -=      12800;
      if (x >=       6400) x -=       6400;
      if (x >=       3200) x -=       3200;
      if (x >=       1600) x -=       1600;
      if (x >=        800) x -=        800;
      if (x >=        400) x -=        400;
      if (x >=        200) x -=        200;
      if (x >=        100) x -=        100;
      if (x >=         50) x -=         50;
      if (x >=         25) x -=         25;
      return x;
    }

    Questo non uso divide o multiplys, a soli 27 confronto e un massimo di 27 sottrazioni.

    È un po ‘ difficile convincersi che questo funziona, ma (almeno per i non-valori negativi di x).

    Il codice di cui sopra è davvero un srotolato la versione di questo:

    int mod25(int x){
      int divisor;
      for(int divisor = 1677721600; divisor >= 25; divisor >>= 1) {
        if (x >= divisor) x -= divisor;
      }
      return x;
    }

    Da srotolare possiamo evitare di fare il loop di confronto e anche gli spostamenti a spese di codice più. Si potrebbe anche parzialmente srotolare utilizzando Duff dispositivo se si sentiva così inclinato, ma solo il 27 iterazioni totale, e un po ‘ di codice per ogni iterazione, sarei propenso a soli srotolare tutto il modo.

    Ecco come funziona: Ogni numero intero non negativo x può essere espresso come (n * 25) + k, dove n è un numero intero non negativo e k è un numero intero da 0 a 24. k avviene anche per essere il risultato che vogliamo, quindi, se possiamo calcolare x – (n * 25), ci piacerebbe avere una risposta. Vogliamo essere in grado di fare questo senza sapere n up-front, però.

    Pensare di n in binario. Se si potesse disattivare il bit a 1 ci saremmo 0. Un modo per farlo è quello di iniziare a grandi potenze di 2 e lavorare il nostro modo in giù, sottraendo ogni potenza di 2 solo se il valore corrente di n è maggiore o uguale alla potenza di 2.

    Dal momento che abbiamo a che fare con (n * 25) di cui abbiamo effettivamente bisogno decrescente potenze di 2 tempi di 25. Poiché k è strettamente minore di 25, e il più piccolo divisore abbiamo mai preso in considerazione è di 25, questo funziona anche quando abbiamo a che fare con (n * 25) + k.

    In modo che ogni confronto + sottrazione è l’azzeramento di un bit di n, e alla fine siamo lasciati con la k, il resto.

  3. 7

    Dal momento che si desidera che il modulo da un costante, probabilmente si può battere utilizzando reciproco moltiplicazione. Questa carta mostra come si può dividere da una costante in modo tale, e verso la fine, come ottenere il resto di esso.

    • Prima di ottimizzare nulla, controllare sempre lo smontaggio. Ho scoperto di recente reciproco trucco con il seguente codice : int a = x % 3; int b = x / 3; Questo codice è finito come un singolo di moltiplicazione e di un turno.
  4. 7

    Ecco il meglio che ho potuto venire con:

    int mod25(int x)
    {
        while((x = (x & 31) + 7 * (x >> 5)) >= 25)
            x -= 25;
    
        return x;
    }

    Si avvicina x % 25 con x % 32 + 7 * (x/32). Il valore di superamento di un multiplo di 25, il che permette di ricorsione.

    Prestazioni sembra essere adeguata: Un valore di x = 2147483647 (aka INT_MAX) ha bisogno di 11 iterazioni.

  5. 7

    Mi è stata ispirata da Pax risposta e fece una fine più generale di algoritmo.

    int mod(int a, int b) {
        int s = b;
        while (s <= a) {
            s <<= 1;
        }
        int r = a;
        while (r >= b) {
            s >>= 1;
            if (s <= r) {    
                r -= s;
            }
        }
        return r;
    }

    Sottrae potenza di due multipli di b da a finché il risultato non è stato trovato.

    EDIT: aggiunto il if condizione per farlo funzionare correttamente.

    Come un esempio, se questo è fare il 100% 7, si scopre che 7 * 2 * 2 * 2 * 2 = 112. Quindi divide 112 (s) da 2 e sottrarre che dal 100 (r) (quando s <= r) e continuamente fa questo fino a quando il modulo è stato trovato. Pertanto,

    s = 112 / 2 = 56, r = 100 - 56 = 44
    s = 56 / 2 = 28, r = 44 - 28 = 16
    s = 28 / 2 = 14, r = 16 - 14 = 2

    pertanto, 100 % 7 = 2

    • Sto lasciando questo commento come un segnalibro così mi ricordo di controllare e provare a dimostrare formalmente questo più tardi 😉
  6. 6

    Oh mio <divinità di scelta>. Io non posso credere che alcune di queste risposte.

    Prima cosa, ripetute sottrazioni, anche Pax versione, mai, mai essere ottimale. Si consideri la seguente:

    20 % 25

    facile e veloce utilizzo ripetuto di sottrazione, ma:

    65535 % 25

    sarà terribilmente lenti, 600+ iterazioni. Che è una media di 300 iterazioni per il 16 bit di numeri. Come per il numero a 32 bit, beh, non anche andare lì.

    Il modo più veloce per farlo è quello di utilizzare divisione lunga. Vedere Niki risposta.

    Ma, questo è ciò che il compilatore genera comunque, almeno, si spera è che il compilatore non è in grado di generare. È sempre meglio controllare se si utilizza un compilatore per una nicchia di processore.

    Il modo migliore per accelerare questo è non fare il modulo, in primo luogo. Perché avete bisogno per ottenere il modulo e la possibile re-fattore di codice /algoritmo per evitare il modulo, o almeno, di rendere il modulo banale.

  7. 5

    Il problema con il loop che è O(n) – sarà molto lento per grandi valori di r. Io suggerirei qualcosa di simile a questo:

    for (int s = MAX_SHIFT; s>=0; s--)
      if (r > (b<<s)) r -= (b<<s);

    Ma dubito che il compilatore sta facendo qualcosa di molto più costoso di quello.

    • Presumo che è necessario impostare MAX_SHIFT dinamica per garantire che (b<<s) non overflow, sì?
  8. 3

    Su molti processori, moltiplicazione di numeri interi è più veloce della divisione intera. Questo post del blog mostra come sostituire una costante intera divisione con una costante di moltiplicazione di numeri interi. Riordinando la matematica un po ‘ si può ottenere il resto invece del quoziente. Si noti, tuttavia, che se si utilizza una moderata sofisticati compilatore, quindi questo è già fatto per voi. Basta scrivere x % 25 e il compilatore funziona il resto. Si dovrebbe controllare il codice assembly generato per il codice, verificando che il compilatore non ha già fatto, prima di fare questo ottimizzazione in C. Inoltre, si dovrebbe misurare (profilo) le prestazioni prima e dopo per assicurare che sei davvero fare le cose più velocemente.

    Loop sarà molto più lento di una divisione utilizzando le istruzioni native per ragionevolmente grande operandi.

    Edit: vedi anche questa carta.

  9. 3

    Se il compilatore C è di targeting una CPU senza dividere istruzione, è possibile modificare il codice come segue:

    mod(a, b) {
        int s = b + b + b + b;
        int r = a;
        while(r >= s) {
            r -= s;
        }
        while(r >= b) {
            r -= b;
        }
        return r;
    }

    Questo funziona sottraendo i valori in blocchi di quattro, piuttosto che uno, fino all’ultimo, poi si passa alla sottrazione di porzioni di uno.

    Questo dovrebbe rendere il codice eseguito circa quattro volte più veloce (supponendo 4*b non è al di fuori dell’intervallo dei numeri interi). Si potrebbe anche inserire più loop (diciamo 8*b uno) prima che il 4*b una per una velocità ancora maggiore.

    Oltre a questo, la scrittura manuale del codice assembler può aiutare ma penso che troverai anche una spinta in più con il codice di cui sopra senza di essa.

    Se si conoscono ulteriori dettagli sul modo in cui sarete utilizzando il mod chiamata, è possibile ottimizzare per casi particolari. Per esempio, se vuoi solo conoscere il modulo 25 di un intero a 16 bit, il codice riportato di seguito sarà molto più veloce di un semplice ciclo con la variabile denominatore.

    int mod25 (int a) {                //a has maximum value of 2^15-1 = 32767
        while (a >= 15625) a-= 15625;  //at most 2 times.
        while (a >= 625) a-= 625;      //at most 24 times.
        while (a >= 25) a-= 25;        //at most 24 times.
        return a;
    }

    L’esecuzione di un test, trovo che devi fare 10 milioni di iterazioni prima di una notevole differenza tra il modulo di codice e l’uso del % operatore (2 secondi e 0 secondi). Fino a quel momento, erano entrambi a 0 secondi, anche se è stato eseguito su una macchina veloce (meglio per mod25) e con un div istruzione (meglio per % operatore) quindi avresti bisogno di un parametro di riferimento sul proprio hardware.

    Questo è circa veloce come è probabile che per ottenere senza rendere il codice illeggibile (anche se non dovrebbe interrompere voi, se siete disposti ad aggiungere un sacco di commenti di spiegare come funziona).

    Una soluzione più generale per qualsiasi denominatore è di primo doppio il denominatore (con un po ‘ di turni per la velocità), per quanto possibile, in modo che le successive sottrazioni sono ridotti al minimo. Poi, come il numeratore si riduce al di sotto della aumento del denominatore, dimezzare il denominatore e andare avanti (fino a quando il denominatore è tornato all’inizio).

    int mod (int n, int d) {
        /* dx is the adjusted denom, don't let it overflow though. */
        int dx = d;
        while (((dx << 1) >>1) == dx)
            dx <<= 1;
    
        /* This loop processes the dx values until they get too small. */
        while (dx >= d) {
            /* This loop subtracts the large dx value. */
            while (n >= dx)
                n -= dx;
            dx >>= 1;
        }
        return n;
    }

    Questo esegue effettivamente alla pari con la versione ottimizzata di mod25 soprattutto fornendo una soluzione più generale.

    • Considerando i grandi numeri si potrebbe desiderare di avere s = b*16 invece che 4. Si può fare con 4 bit shift shift di sinistra istruzione.
  10. 2

    si prega di impegnarsi un po ‘ di buonsenso.

    Se si potrebbe scrivere codice C che calcolato x il 25% più veloce di quanto il compilatore è in grado, quindi il compilatore sarebbe usare quel metodo più veloce.

    Il poster originale realizzato questo fantastico presupposto che il compilatore sarebbe utilizzare una divisione. Nessun compilatore che ho usato negli ultimi dieci anni sarebbe fare che. E ‘una moltiplicazione per una costante vicino a (2^32 /25) oltre ad alcuni po’ con le mani in mano, che non sarà in grado di migliorare la mano.

    C’è una remota possibilità che è in grado di produrre codice più veloce di quanto il compilatore per scoprire se x % 25 == 0, perché non avete davvero bisogno di codice che calcola x % 25 correttamente, solo il codice che calcola x % 25 correttamente se è 0 e non produrre un 0 se x % 25 != 0. Il risparmio sarà probabilmente sub-nanosecondi.

    “Come faccio a calcolare x % c in modo ottimale per le varie costanti c” è un bel puzzle. Compilatore scrittori come un bel puzzle. E sono più bravi a risolvere bel puzzle come questo di te. Soprattutto dal momento che solo bisogno di una soluzione che funziona per uno macchina dove sarebbe necessario per produrre una soluzione generale.

  11. 1

    Se non ti piace % operatore:

    int mod(int a, int b) {
        int integral = a / b;
        return a - (b*integral);
    }
    • Perché downvote? Cosa c’è di sbagliato con il codice?
    • Credo che dal momento che l’OP cerca di evitare l’uso di divisione, un algoritmo della divisione non aiuta molto (io non downvote). OP solo chiarito questo dopo la tua risposta anche se
    • Esattamente. OP non ha menzionato inizialmente che la divisione dovrebbe essere evitato pure.
    • Bene, ha detto di dire che la CPU non ha un div operatore. Certo che sarebbe stato un indizio? 🙂
    • Non ha detto inizialmente – è apparso solo dopo la modifica.
  12. 1

    Se si sa che b sarà una potenza di 2, è possibile utilizzare bit per bit AND invece che l’operatore modulo. Tuttavia, il pagina di wikipedia per modulo sembra indicare che qualsiasi compilatore C sarebbe accorto di questo e di ottimizzare il modulo in ogni caso.

    • 25 non è una potenza di due, hth.
    • Meh, era solo offrendo l’unico ottimizzazione potrei pensare; forse aiuterà qualcun altro.
  13. 1

    Forse non è la più veloce, ma ragionevolmente efficiente. Non ho il tempo per verificare, ma utilizzare una tabella di (potenze di 2) * 25 fino alla portata massima/2. Poi fare un ciclo. E. g. portata fino a 3199 esigenze 7 iterazioni.

    static int pow[] = {25, 50, 100, 200, 400, 800, 1600};
    
    int mod25(int x)
    {    
        int i = sizeof pow /sizeof pow[0];
    
        while (i--)
        {
            if (x >= pow[i])
                x -= pow[i];    
        }    
        return x;
    }

    Se si dispone di una gamma molto ampia, ma i valori bassi sono più comuni, allora potrebbe essere la pena usng un binario tritare per trovare il punto di partenza.

  14. 1
    int mod25(int x) {
      static int divisors[] = {2147483625, 244140625, 9765625, 390625, 15625, 625, 25};
      int i;
      for (i = 0; i < sizeof(divisors)/sizeof(int); i++) {
        int divisor = divisors[i];
        while (x >= divisor) {
          x -= divisor;
        }
      }
      return x;
    }

    Come funziona: vogliamo decremento x da grandi multipli di 25 a ridurre il valore più velocemente possibile. Quando il divisore è troppo grande, si passa ad un più piccolo più di 25. Se il divisore è già giù a 25 e poi abbiamo finito.

    Si potrebbe provare a sperimentare con diverse divisori. Si vuole solo assicurarsi che:

    • stanno scendendo
    • sono tutti multipli di 25
    • l’ultimo valore è 25

    Nel codice sopra ho usato la più grande firmato-32-bit multiplo di 25 più i poteri di 25, che sembra ragionevole, anche se devo ammettere che io non sono sicuro che sia ottimale.

    (BTW: se il tuo compilatore non costanti — che dovrebbe essere molto sorprendente, allora si potrebbe desiderare di sostituire il limite superiore di i con un hard-coded costante).

    • Che è molto simile alla mia prima risposta, ma dopo un po ‘ di pensiero ho deciso che si potrebbe finire loop fino a 24 volte nel ciclo interno per ogni ciclo esterno.
    • Sì, è vero. Ho postato un’altra risposta che fa esattamente 27 iterazioni, e quando srotolato fa 27 confronti e fino al 27 sottrazioni, e funziona per tutti i non-negativo (firmato 32-bit) ingressi.
  15. 0

    Perché non si può semplicemente utilizzare l’operatore %? Se questo è il codice C, e i numeri sono ordinarie “nativo” int:s, poi, che dovrebbe essere il modo più veloce, da lontano.

    • il secondo argomento è fissa, come un algoritmo in grado di superare i generici, a mano codice ottimizzato potrebbero sovraperformare il compilatore
  16. 0

    C’è un motivo per cui si può utilizzare il C integrato di operatore di modulo?

    int a = x % 25;

    A seguito di modifica;

    Se il tuo rpocessor non hanno costruito in modulo di supporto quindi vorrei ancora usare l’operatore % per il semplice motivo che il compilatore sa che il processore in questione non hanno un nativo % funzione, suscettibile di produrre codice asm ottimale di emulare.

    Messo questo modo – sarei affascinato se si può venire con un genarl algoritmo che supera whatevr il compilatore produce utilizzando il built in, operatore, notwithsatanding casi specifici (ad esempio semplicemente prendendo il 2 cifre più basse per modulo 100 ecc)

    • “probabilmente produrre codice asm ottimale di emulare” – mi viene il dubbio che il compilatore ha ottimizzato il codice per ogni valore costante. Ho il sospetto che sarebbe solo di utilizzare uno standard di dividere/modulo algoritmo (tranne che per potenze di due) – dubito che questo sarebbe ottimale per noto costanti.
    • Effettivamente … ha 🙂
  17. 0

    Come su:

    int y = 0, x = (x & 0x7f); 
    while (x > 25) { x -= 25; y++; }

    Aggiornamento: è abbastanza sbagliato 🙂 Ma l’idea c’è.

  18. 0

    Lo trovo abbastanza strano che l’operazione x % 25 prende molto tempo (se si sta utilizzando il built-in % operatore, che è). Processori più moderni dovrebbe fare questo in una singola istruzione. Mi piacerebbe guardare per altri motivi che questo codice prende così a lungo.

    MODIFICA:
    Ecco un algoritmo che potrebbe almeno dare alcune idee:

    256 = 6 (mod 25)

    Questo significa che se si scrive un numero x come byte x3 x2 x1 x0 abbiamo che x = 6^3*x3 + 6^2*x2 + 6*x1 + x0 (mod 25)

    Questo dà un algoritmo per ridurre le dimensioni del x:

    int x0 = x & 0xFF, x1 = (x>>8) & 0xFF, x2 = (x>>16) & 0xFF, x3 = (x>>24) & 0xFF;
    
    int y = x4;
    y = (y << 2) + (y << 1) + x3;
    y = (y << 2) + (y << 1) + x2;
    y = (y << 2) + (y << 1) + x1;
    y = (y << 2) + (y << 1) + x0;

    (qui (y << 2) + (y << 1) = 4*y + 2*y = 6*y)

    Dopo questo y avrà lo stesso resto come x mod 25.
    L’iterazione di questo 1, 2 o 3 volte, y 17, 11 o 9 numero di bit, rispettivamente. Una di queste dimensioni potrebbe essere abbastanza piccolo per fare una tabella di ricerca di.

    Dubito SERIAMENTE che questo sarebbe stato più veloce di builtin % operatore, però.

    • In molte piccole piattaforme, la divisione (e, per estensione, modulo) è molto lento rispetto ad altre operazioni. Ricordate, la vostra piattaforma di destinazione potrebbe essere un tostapane! Questo è stato vero per un lungo periodo di tempo, anche per le piattaforme desktop – IIRC 26 cicli per un DIV su 486 o primi Pentium, rispetto ad 1 ciclo per l’aggiunta e un paio per la moltiplicazione.
    • Sì, ma non era chiaro dalla domanda originale se il problema era davvero una mancanza di istruzione DIV o non. E io continuo a pensare che se il codice è lento, il primo pensiero non dovrebbe essere quello di sostituire i compilatori C built-in di operatori aritmetici.
    • div istruzione è spesso (anche su x86) implementata nel microcodice, e quindi, slow.
  19. 0

    Se hai tenuto i tuoi numeri in BCD o un array di byte di cifre, questo sarebbe abbastanza facile. Purtroppo, non ho idea di che cosa si sta facendo nel vostro programma con questi numeri. A volte vale la pena di guardare a come si rappresentano i dati, piuttosto che solo bang distanza in algoritmi.

  20. 0

    Heres un’Idea

    static int table0[256];
    static int table1[256];
    static int table2[256];
    static int table3[256];
    
    //ran just once to initialize the tables
    void initialMod25Tables() {
        for (int i = 0; i < 256; ++i) {
            table0[i] = i % 25;
        }
        for (int i = 0; i < 256; ++i) {
            table1[i] = (i << 8) % 25;
        }
        for (int i = 0; i < 256; ++i) {
            table2[i] = (i << 16) % 25;
        }
        for (int i = 0; i < 256; ++i) {
            table3[i] = (i << 24) % 25;
        }
    }
    
    int mod25(int x) {
        int y = table0[x & 0xFF];
        x >>= 8;
        y += table1[x & 0xFF];
        x >>= 8;
        y += table2[x & 0xFF];
        x >>= 8;
        y += table3[x & 0xFF];
        y = table0[y];
        return y;
    }
  21. -1

    Se sono solo considerando il numero 25 è possibile utilizzare il fatto che il 25 divies un numero intero se e solo se le ultime due cifre dell’intero siano 00, 25, 50 o 75. Quindi, per ottenere il modulo si considerano le ultime due cifre e quindi sottrarre il più vicino 00, 25, 50 o 75.

    • E si dovrebbe ottenere le ultime due cifre come? Modulo-100? 🙂
    • I numeri sono rappresentati in forma binaria, quindi non è che sia facile lavorare con cifre decimali. E come si fa a trovare il più vicino corretto divisore? È ovvio umana, ma non vi è nessuna di tali istruzioni della CPU.
    • Forse il suo processore ha una modalità BCD. 🙂
    • Lo fa naturalmente dipende dal contesto. Per esempio, i dati potrebbero essere inizialmente provenienti da un file di testo. Anche se ormai è chiaro dalla sua modifica che questo è probabilmente non è ciò che stava cercando un modo ma la vera.

Lascia un commento