Wie kann ich Mod ohne einen Mod-Operator tun?

Question

Diese dumme Skriptsprache hat kein% oder Mod(). Ich habe eine Fix(), die den Dezimalteil einer Zahl abhebt. Ich brauche nur positive Ergebnisse, also werde nicht zu robust.

Answer 1

Wird

// mod = a % b 

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

tun? Ich gehe davon aus, dass Sie sich hier zumindest teilen können. Alle Wetten sind auf negative Zahlen aus.

Answer 2

Dies kann nicht für Sie leistungsmäßig arbeiten, aber:

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

Answer 3

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

Answer 4

Welche Sprache ist das?

könnte ein Basis-Algorithmus sein:

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

Für die Nachwelt BrightScript nun eine Modulo-Operator hat, sieht es wie folgt aus:

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

Wenn jemand kommt später an, hier sind ein paar aktuelle Algorithmen (mit Fehlern ... lesen Sie sorgfältig)

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

Es gibt zwei Haupt Art von Reduktion Formeln: Barett und Montgomery. Das Papier von eprint Wiederholung sowohl in verschiedenen Versionen (Algorithmen 1-3) und geben eine „verbesserte“ Version in Algorithmus 4.

Übersicht

Ich gebe jetzt einen Überblick über den 4. Algorithmus:

1.) Berechne "A * B" und speichere das gesamte Produkt in "C", dass C und der Modulus $ p $ die Eingabe für diesen Algorithmus ist.

2.) Berechnen Sie die Bitlänge von $ p $, sagen wir: die Funktion "Width (p)" gibt genau diesen Wert zurück.

3.) Teilen Sie die Eingabe $ C $ in N "Blöcke" der Größe "Breite (p)" und speichern Sie sie jeweils in G. Beginnen Sie in G [0] = lsb (p) und enden Sie in G [N- 1] = Msb (p). (Die Beschreibung ist wirklich fehlerhaft des Papiers)

4.) Starten Sie die while-Schleife: Sets N = N-1 (das letzte Element zu erreichen) Precompute $ b: = 2^{Breite (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 

Das ist viel. Nicht wir müssen nur rekursiven G reduzieren [0]:

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

Die anderen drei Algorithmen sind gut definiert, aber das fehlt einige Informationen oder präsentieren es wirklich falsch. Aber es funktioniert für jede Größe;)