Come posso fare mod senza un operatore mod?

Question

Questo linguaggio di script sciocco non ha un% o Mod(). Ho una correzione() che taglia fuori la parte decimale di un numero. Ho solo bisogno di risultati positivi, quindi non diventare troppo robusto.

Answer 1

Will

// mod = a % b 

c = Fix(a/b) 
mod = a - b * c 

fare? Suppongo che tu possa almeno dividere qui. Tutte le scommesse sono disattivate su numeri negativi.

Answer 2

Questo non può funzionare per voi prestazioni-saggio, ma:

while (num >= mod_limit) 
    num = num - mod_limit 

Answer 3

a mod n = a - (n * Fix(a/n))

Answer 4

Che lingua è?

Un algoritmo di base potrebbe essere:

hold the modulo in a variable (modulo); 
hold the target number in a variable (target); 
initialize modulus variable; 

while (target > 0) { 
    if (target > modulo) { 
    target -= modulo; 
    } 
    else if(target < modulo) { 
    modulus = target; 
    break; 
    } 
} 

Answer 5

Ai posteri, BrightScript ha ora un operatore modulo, sembra che questo:

c = a mod b 

Answer 6

in JavaScript:

function modulo(num1, num2) {  
    if (num2 === 0 || isNaN(num1) || isNaN(num2)) { 
    return NaN; 
    } 

    if (num1 === 0) { 
    return 0; 
    } 

    var remainderIsPositive = num1 >= 0; 

    num1 = Math.abs(num1); 
    num2 = Math.abs(num2); 

    while (num1 >= num2) { 
    num1 -= num2 
    } 

    return remainderIsPositive ? num1 : 0 - num1; 
} 

Answer 7

Se qualcuno arriva più tardi, ecco alcuni algoritmi più effettivi (con errori ... leggi attentamente)

https://eprint.iacr.org/2014/755.pdf

realtà ci sono due tipi principali di formule di riduzione: Barett e Montgomery. La carta da ripetere ePrint sia in diverse versioni (algoritmi 1-3) e dare una versione "migliorata" in algoritmo 4.

Panoramica

do ora una panoramica del 4. dell'algoritmo:

1.) Calcola "A * B" e memorizza l'intero prodotto in "C" che C e il modulo $ p $ è l'input per quell'algoritmo.

2.) Calcola la lunghezza di bit di $ p $, ad esempio: la funzione "Larghezza (p)" restituisce esattamente quel valore.

3.) Dividere l'ingresso $ C $ in N "blocchi" di dimensione "Larghezza (p)" e memorizzarli in G. Inizio in G [0] = lsb (p) e finire in G [N- 1] = msb (p). (La descrizione è molto difettosa della carta)

4.) Avviare il ciclo while: Set N = N-1 (per raggiungere l'ultimo elemento) Precompute $ b: = 2^{width (p)} \ BMOD p $

while N>0 do: 
    T = G[N] 
    for(i=0; i<Width(p); i++) do: //Note: that counter doesn't matter, it limits the loop) 
     T = T << 1 //leftshift by 1 bit 
     while is_set(bit(T, Width(p))) do // (N+1)-th bit of T is 1 
      unset(bit(T, Width(p))) // unset the (N+1)-th bit of T (==0) 
      T += b 
     endwhile 
    endfor 
    G[N-1] += T 
    while is_set(bit(G[N-1], Width(p))) do 
     unset(bit(G[N-1], Width(p))) 
     G[N-1] += b 
    endwhile 
    N -= 1 
endwhile 

che fa molto. Non abbiamo solo bisogno di ridurre i recursivly G [0]:

while G[0] > p do 
    G[0] -= p 
endwhile 
return G[0]// = C mod p 

Gli altri tre algoritmi sono ben definiti, ma questo manca di alcune informazioni o presentiamo veramente sbagliato. Ma funziona per qualsiasi dimensione;)