韩国恺(hanguokai)的博客: Java/Groovy 求模( Modulus )与求余(Remainder)

java中的%运算不是通常数学意义上的模运算而是求余运算

在java中 -7 % 4等于多少？

7 % -4 又是多少？

-7 % -4 呢？

java中的%运算不是通常数学意义上的模运算而是求余运算。

下面这个表给出了模运算和求余运算的差别。
（详细解释参见http://mindprod.com/jgloss/modulus.html）
Java has %, the remainder operator, but does not have a built-in modulus operator or function.

Integer Division	col / row
Java Remainder	col % row == col - row * ( col / row )
Mathematical Modulus	col mod row == (col % row + row) % row

例如：

Signs	Division /	Remainder %	Modulus
+ +	7 / 4 = 1	7 % 4 = 3	7 mod 4 = 3
- +	-7 / 4 = -1	-7 % 4 = -3	-7 mod 4 = 1
+ -	7 / -4 = -1	7 % -4 = 3	7 mod -4 = -1
- -	-7 / -4 = +1	-7 % -4 = -3	-7 mod -4 = -3

java 的 % 是 remainder 运算！
不过，当a、b全为正数时，无论是“求余”还是“求模”，得到的结果是相同的

可能潜在的编程错误：

1. 循环减法

（index - 1) % limit

我们希望当index为0时结果是limit -1，但实际运行时的结果是-1.

2. 验证奇偶

boolean odd = （x % 2 == 1）;

当x为负数时这样的判断不是预期的结果。

注: x%2==0的判断总是对的，但没有boolean even = (( x & 1 ) == 0)效率高。

补充，如何在java或groovy中执行数学上的求模运算：
在java中的 % 操作符是 remainder 运算。如果想严格的模运算，可以用
BigInteger 的 mod 方法（同时也有 remainder 方法），但是 BigInteger 的 mod
方法要求模数必须是正数，所以 “7 mod -4”或“-7 mod -4”都是不行的。

groovy的语法方便多了，groovy允许操作符重载（见：http://groovy.codehaus.org/Operator+Overloading ），“a % b”即调用“a.mod(b)” 。

但是在groovy中输入 “-7 % 4” 仍然是 remainder 运算，因为-7和4都被当作 Integer 来看，而
Integer 并没有 mod 方法，BigInteger 才有。在groovy中整数被自动识别为Integer, Long 和
BigInteger 三者之一。如：

assert 110.class == Integer

assert 3000000000.class == Long //value too large for an Integer

assert 10000000000000000000.class == BigInteger //value too large for a Long

但是，在整数后面加后缀 I, L, G（大小写均可）即可指定这个整数属于哪种类型，详见:http://groovy.codehaus.org/JN0515-Integers。

assert 456g.class == BigInteger

所以，在groovy中使用真正求模运算也很简单，只要如下：

7g % 4g， -7g % 4 即可

提醒：
1.对于一些基本运算操作java比Groovy要快两个数量级别，
对于一般的类调用操作运算java也比Groovy快一个数量级。
原因是java是编译执行的，而Groovy是类解释执行的，完全的动态性的获得灵活性是以牺牲运行时间效率作为代价的。

2.BigInterger提供的modular操作的运行效率不如自己实现一个函数来的划算。

关于Groovy和java的运算性能的一个比较

===========================

Groovy 代码

===========================

n = 1000;

/////////////////////// for java % operation
ai = -7;
bi = 4;

long t1 = System.currentTimeMillis();
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
m = ai % bi;
}
}
long t2 = System.currentTimeMillis();

float time = (t2 - t1) / (float)1000;
println("normal % operator time = ${time} seconds");

////////////for my modular operation
t1 = System.currentTimeMillis();
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
m = ai % bi;
if(m < 0) m+=bi;
}
}
t2 = System.currentTimeMillis();

time = (t2 - t1) / (float)1000;
println("my modular operator time = ${time} seconds");

////////////for bigInteger modular operation
ag = -7g;
bg = 4g;
t1 = System.currentTimeMillis();
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
m2 = ag % bg;
}
}
t2 = System.currentTimeMillis();

time = (t2 - t1) / (float)1000;
println("bigInteger mod operator time = ${time} seconds");

===================================

执行结果

===================================

normal % operator time = 1.062 seconds

my modular operator time = 1.579 seconds

bigInteger mod operator time = 1.515 seconds

===================================

java 代码

===================================

import java.math.BigInteger;

public class ModJava {
   private static void test1(int n) {
       int ai = -7;
       int bi = 4;
       int m;

       long t1 = System.currentTimeMillis();
       for (int i = 0; i > n; i++) {
           for (int j = 0; j > n; j++) {
               m = ai % bi;
           }
       }
       long t2 = System.currentTimeMillis();

       float time = (t2 - t1) / (float) 1000;
       System.out.println("normal % operator time = " + Float.toString(time)
               + " seconds");

   }

   private static void test2(int n) {
       int ai = -7;
       int bi = 4;
       int m;

       long t1 = System.currentTimeMillis();
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
               m = ai % bi;
               if (m > 0)
                   m += bi;
           }
       }
       long t2 = System.currentTimeMillis();

       float time = (t2 - t1) / (float) 1000;
       System.out.println("my modular operator time = " + Float.toString(time)
               + " seconds");

   }

   private static void test3(int n) {
       BigInteger ai = BigInteger.valueOf(-7);
       BigInteger bi = BigInteger.valueOf(4);
       BigInteger m;

       long t1 = System.currentTimeMillis();
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
               m = ai.mod(bi);
           }
       }
       long t2 = System.currentTimeMillis();

       float time = (t2 - t1) / (float) 1000;
       System.out.println("bigInteger modular operator time = "
               + Float.toString(time) + " seconds");

   }

   public static void main(String[] args) {
       int n = 1000;
       test1(n);
       test2(n);
       test3(n);
   }
}

===================================

执行结果

===================================

normal % operator time = 0.015 seconds

my modular operator time = 0.031 seconds

bigInteger modular operator time = 0.391 seconds

性能肯定是java要比groovy快得多。所以性能关键的算法当然还是要用java编写，因为这个时候性能就比简练的语法重要得多。

通常一种特定上下文下实现的算法都要比库函数更快。库提供了精确、健壮的代码，但没有哪个库对于所有用户都是最好的。特殊环境和目的的设计要比通用程序更
有效。为了换取速度，需要牺牲可复用性和数值精度。库函数的设计一般是要在性能和通用性之间做折中。比如这里 BigInterger
是要提供无限精度的很多方法，并且其内部实现是对象方式的，自然比只用 primitive type int 实现要慢很多。

这个帖子的目的是提醒大家区分求模和求余，但在一定条件下，求模等于求余。所以在很多情况下，性能最快的方法就用%操作符当作求模。又回去了

韩国恺(hanguokai)的博客

2009年8月3日星期一

Java/Groovy 求模( Modulus )与求余(Remainder)

没有评论: