如何在没有模运算符的情况下进行取模操作？

Question

这种脚本语言没有 % 或 Mod() 运算符。我有一个 Fix() 函数，可以将一个数的小数部分截取掉。我只需要正数结果，所以不需要太复杂。

- tladuke

---

你能否提及并标记一下你所说的“愚蠢”脚本语言是哪个？ - Stephen P

我认为“homework”是一个愚蠢的编程语言。 - Gareth

嘿，这是Roku数字标牌视频播放器上的一些嵌入式语言。它可能有一个Mod，但我肯定找不到它，而且它还有像Arctan()和NaturalLog()这样的函数，所以我真的很困惑他们是如何跳过Mod的。 - tladuke

GLSL 3.0 以前的版本也不支持整数取模运算。 - Soylent Graham

Answer 1

将会

// mod = a % b

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

你会做除法吗？我默认你至少会在这里进行除法运算。但是如果涉及到负数，一切皆有可能。

- John Källén

---

根据您对负数的要求，可以进行调整。有一个fix()函数，它总是截断小数部分，还有一个int()函数，它总是向下舍入（int(-2.5)=-3）。 - Nas Banov

Answer 2

为了后人，BrightScript现在有一个模运算符，它看起来像这样：

c = a mod b

- Nas Banov

---

这并没有回答问题。 - MD XF

@MDXF这段话并没有直接回答问题的标题，但是实质上回答了问题。如果你仔细阅读正文，可以看到它说“这个愚蠢的脚本语言没有%或Mod()函数”——这是2010年的情况，但现在已经不是了。 - Nas Banov

Answer 3

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

- Strelok

Answer 4

如果有人迟到了，这里有一些更多的实际算法（带有错误...请仔细阅读）。

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

实际上有两种主要的约减公式：Barett 和 Montgomery。eprint 上的论文在不同版本（算法1-3）中重复了这两种公式，并在算法4中给出了一种“改进”的版本。

概述

现在我将对第四个算法进行概述：

1.) 计算“A*B”，并将整个乘积存储在“C”中，其中C和模$p$是该算法的输入。

2.) 计算$p$的位数，即函数“Width(p)”返回确切的值。

3.) 将输入$C$分成N个大小为“Width(p)”的“块”，并将每个块存储在G中。从G[0] = lsb(p)开始，以G[N-1] = msb(p)结束。（论文描述真的很有问题）

4.) 开始while循环： 设置N=N-1（达到最后一个元素） 预计算$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

那很有用。现在我们只需要递归地减少G [0]：

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

另外三个算法都很明确，但这个缺少一些信息或者表述得不太准确。但它适用于任何大小的数据 ;)

- Shalec

---

嗨@shalec - 我们不鼓励只包含外部资源链接的答案。这些仅链接答案被反对。 - Lix

你能否将链接PDF中的相关部分复制粘贴到你的回答中吗？这将极大地提高本帖的质量。 - JonathanDavidArndt

当然。提到了4个算法。我会进行编辑。 - Shalec

Answer 5

这是什么语言？

一个基本的算法可能是：

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

- user97410

---

我认为在target==modulo的情况下存在错误。会导致无限循环。 - Ice-Blaze

Answer 6

这个可能在性能方面对你不起作用，但是：

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

- tloflin

---

@tloflin，希望你不介意，但应该是“> =”而不是“>”。 - paxdiablo

不工作效率方面的意思是指当 num 约为 2**63 且 mod_limit 为 3 时吗？ - President James K. Polk

Answer 7

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

- momo1319

---

虽然这段代码片段可能解决了问题，但包括解释真的有助于提高您的文章质量。请记住，您正在回答未来读者的问题，而这些人可能不知道您建议使用代码的原因。同时，请尽量避免在代码中添加过多的解释性注释，这会降低代码和解释的可读性！ - kayess