如何在我的数学运算中移除模数？

Question

我的教授不喜欢使用取模运算，因为它不够高效，但我不确定如何使用逻辑运算符或其他方法得到同样的答案。有人可以帮我解决如何做吗？

j = (j + 1) % a.length;

- user1730056

---

叹气 对着教授。 - Richard Tingle

我同意。教授的担忧没有根据。在许多语言中，除了特定应用程序外，取模运算通常比条件跳转更快，即使它更慢，这种微小优化仍然比磁盘访问或网络延迟慢几个数量级。 - nanofarad

转学或者退掉这门课程，等新的教授上课再选。取模运算可以提供一些最优雅、高效和易读的代码。 - Cruncher

@Cruncher 或者与教授交谈，并引用这里的讨论和其他证据。 - nanofarad

j和a.length有没有任何假设？否则，我非常怀疑是否有人能找到更快的代码。因为如果有的话，Java就会执行它。 - Richard Tingle

Answer 1

这应该可以解决问题。

 int k = a.length;
 int d = (j+1)/k;
 j = (j+1) - d*k

- Ankit Rustagi

---

这种解决方案的问题在于，在大多数系统上，“/”和“%”本来就应该是相同的操作，只是存储结果的不同部分，因此实际上根本没有改变速度。 - qaphla

如果教授讨厌取模运算，那么他或她一定会非常讨厌除法加乘法。 - Lee Meador

这可能比百分号慢，但无关紧要，这都是荒谬的微观优化。 - Richard Tingle

Answer 2

如果没有取模的话，我唯一能想到的办法仍然不是很好：

j = (++j < a.length)? j : (j - a.length);

更易读的方式如下：

j++;
j = (j < a.length)? j : (j - a.length);

或者

j++;
if (j >= a.length) {
    j -= a.length;
}

此外，我不完全确定Java在循环预测方面的表现如何，但至少在C语言中，以下代码速度稍微快一些，但可读性较差，因为一般假设if语句的参数为真，并且j < a.length通常情况下也是成立的（除非a.length <= 2，这似乎不太可能）。

j++;
if(j < a.length) {
}
else {
    j -= a.length;
}

如果j的初始值超出了范围0到a.length（包括0但不包括a.length），那么唯一的解决方案要么使用模数或除法，这两种操作速度相同；要么使用减法循环，这实际上与早期处理器上的模数运算基本相同，而目前我所知道的任何处理器上的内置模数运算都比它快。

- qaphla

---

抱歉，尝试阅读一个同时对变量进行自增和在同一语句中其它地方使用的语句会让我头疼，即使它能正常工作。除非你正在使用 APL，否则将所有内容塞到一行中并不值得加分。 :) - ajb

@ajb 我可以为此负责，那是我的想法。当时似乎是个好主意，但我理解你的观点。 - Cruncher

我担心可能会有遗漏，如果j很大，比如1000000？而a.length很小，比如5。 - Richard Tingle

j 的大小并不重要，只有它与 a.length 的比较才是关键。这个解决方案（和其他大多数解决方案一样）假设 j 始终保持在 0 和 a.length 之间（包括左端点，不包括右端点），因为如果没有使用 divmod 操作或者以更低效的方式实现这样的操作，就无法完成此操作。 - qaphla

Answer 3

您可以这样做：

j = j + 1;
if (j >= a.length) {
    j = j - a.length; // assumes j was less than length before increment
}

@ajp提出了另一种解决方案，实际上可以很好地工作。

j = j + 1;
if (j >= a.length) { // assumes j was less than length before increment
    j = 0; 
}

如果我要编写这段代码，我会按照这种方式编写，以防万一。它几乎没有额外的开销，且可以避免“假设”的情况。

j = j + 1;
while (j >= a.length) {
    j = j - a.length;
}

当然，%也是一种不错的方法。除非你的教授要求不用它。

相比于除法和取余的效率，这个方法要么更快，要么更慢，这取决于跳转操作的成本（以及对指令流水线/前瞻的影响）和整数除法指令的效率。

旧处理器使用跳转操作可能会更好。而现代处理器则使用除法更优。

- Lee Meador

---

我建议在有时间的时候运行一些基准测试，以加强你的回答。 - nanofarad

注意：如果在增量之前j小于长度，那么您的条件将始终失败。您可能意味着“假设j <= length”，或者您可能意味着if (j >= a.length)。 - ajb

另外，如果假设是正确的，那么你可以说if (j >= a.length) j = 0;。有时这样会更清楚地表明正在发生什么。 - ajb

@LeeMeador 像6502这样的吗？我曾经为它们编写汇编语言。它们没有除法指令。 - ajb

如果这比使用模运算慢，那么除非你正在对某个特定数字进行模运算（例如2的幂），否则你可能无法得到更好的结果。 - qaphla

Answer 4

想一想你在做什么。实际上，你正在说：

if j + 1 is smaller than a.length, set j to j + 1
otherwise, we set j to a value smaller than a.length

这个伪代码应该能给你一个非常清晰的解决方案提示。

- RaptorDotCpp

---

“a.length” 的值比某个值小是什么意思？ - Richard Tingle

@RichardTingle 我认为他的意思是“一个值，它是a.length减去j或a.length的某个因子，使得该值小于a.length”。 - Cruncher