¿Cómo puedo hacer mod sin un operador de mod?

Question

Este lenguaje de scripting tonto no tiene un% o Mod(). Tengo un Fix() que corta la parte decimal de un número. Solo necesito resultados positivos, así que no seas demasiado fuerte.

Answer 1

va a hacer

// mod = a % b 

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

? Supongo que al menos puedes dividir aquí. Todas las apuestas están apagadas en números negativos.

Answer 2

Esto puede no funcionar para usted en cuanto al rendimiento, pero:

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

Answer 3

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

Answer 4

Qué idioma es?

Un algoritmo básico podría ser:

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

Para la posteridad, BrightScript tiene ahora un operador de módulo, que se parece a esto:

c = a mod b 

Answer 6

En 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

Si alguien llega más tarde, aquí hay algunos algoritmos más reales (con errores ... lea con atención)

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

En realidad, hay dos tipos principales de las fórmulas de reducción: Barett y Montgomery. El papel de repetición ePrint tanto en diferentes versiones (algoritmos 1-3) y dar una versión "mejorada" en el algoritmo 4.

general

Doy ahora una visión general de la 4. algoritmo:

1.) Calcule "A * B" y Almacene el producto completo en "C" que C y el módulo $ p $ es la entrada para ese algoritmo.

2.) Calcule la longitud de bit de $ p $, por ejemplo: la función "Ancho (p)" devuelve exactamente ese valor.

3.) Dividir la entrada $ C $ en N "bloques" de tamaño "Ancho (p)" y almacenar cada uno en G. Comience en G [0] = lsb (p) y termine en G [N- 1] = msb (p). (La descripción es muy defectuosa del papel)

4.) Iniciar el bucle while: conjunto N = N-1 (para llegar al último elemento) precomputamos $ b: = 2^{Ancho (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 

Eso hace mucho. No sólo tenemos que reducir recursivamente G [0]:

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

Los otros tres algoritmos están bien definidos, pero esto carece de algunas informaciones o presentamos lo que realmente mal. Pero funciona para cualquier tamaño;)