How can I do mod without a mod operator?

Question

This scripting language doesn't have a % or Mod(). I do have a Fix() that chops off the decimal part of a number. I only need positive results, so don't get too robust.

Answer 1

Will

// mod = a % b

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

do? I'm assuming you can at least divide here. All bets are off on negative numbers.

Answer 2

For posterity, BrightScript now has a modulo operator, it looks like this:

c = a mod b

Answer 3

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

Answer 4

If someone arrives later, here are some more actual algorithms (with errors...read carefully)

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

There are actually two main kind of reduction formulae: Barett and Montgomery. The paper from eprint repeat both in different versions (algorithms 1-3) and give an "improved" version in algorithm 4.

Overview

I give now an overview of the 4. algorithm:

1.) Compute "A*B" and Store the whole product in "C" that C and the modulus $p$ is the input for that algorithm.

2.) Compute the bit-length of $p$, say: the function "Width(p)" returns exactly that value.

3.) Split the input $C$ into N "blocks" of size "Width(p)" and store each in G. Start in G[0] = lsb(p) and end in G[N-1] = msb(p). (The description is really faulty of the paper)

4.) Start the while loop: Set N=N-1 (to reach the last element) 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

That does alot. Not we only need to recursivly reduce G[0]:

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

The other three algorithms are well defined, but this lacks some information or present it really wrong. But it works for any size ;)

Answer 5

What language is it?

A basic algorithm might be:

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 6

This may not work for you performance-wise, but:

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

Answer 7

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;
}