Java - 是否有欧几里得或落地模的方法问题杂项

operators modulo java modulus negative-number

2022-09-04 22:23:35

Java模运算符基于截断除法（参见维基百科：模运算）。%

5%3生产（注意，产生25/31)
5%(-3)生产（注意，产生25/(-3)-1)
(-5)%3生产（注意，产生-2(-5)/3-1)
(-5)%(-3)生产（注意，产生-2(-5)/(-3)1)

在计算科学中，给定两个整数和，>0，有时获得与模一致的唯一整数是有用的。annr[a,n[an

问题

Java中是否有一个有效的泛型运算符/方法尊重这个模规范？

这是为了避免在每个需要它的项目中重写它...

杂项

我在stackoverflow上发现了很多关于这个问题的问题，其中大多数都混淆了不同的模实现。如果您只是对负数的模运算结果感到困扰，以下是一些基于 Java % 运算符的可能有用的实现。

常见黑客

由于我们几乎不使用负除数，因此此实现在 .n > 0

static int mod(int a, int n){    
  return a<0 ? (a%n + n)%n : a%n;
}

mod( 5, 3)生产2
mod(-5, 3)生产1

欧几里得模

static int euclideanModulo(int a, int n){
  return n<0 ? euclideanModulo(a, -n) : mod(a, n);
}

euclideanModulo( 5, 3)生产2
euclideanModulo(-5, 3)生产1
euclideanModulo( 5,-3)生产2
euclideanModulo(-5,-3)生产1

地板模量

static int flooredModulo(int a, int n){
  return n<0 ? -flooredModulo(-a, -n) : mod(a, n);
}

flooredModulo( 5, 3)生产2
flooredModulo(-5, 3)生产1
flooredModulo( 5,-3)生产-1
flooredModulo(-5,-3)生产-2

答案 1

+----+----+-----------+---------+-----------+-----------+---------+-----------+
| x mod y |           quotient 'q'          |          remainder 'r'          |
| x  | y  | truncated | floored | Euclidean | truncated | floored | Euclidean |
+----+----+-----------+---------+-----------+-----------+---------+-----------+
|  5 |  3 |         1 |       1 |         1 |         2 |       2 |         2 |
| -5 |  3 |        -1 |      -2 |        -2 |        -2 |       1 |         1 |
|  5 | -3 |        -1 |      -2 |        -1 |         2 |      -1 |         2 |
| -5 | -3 |         1 |       1 |         2 |        -2 |      -2 |         1 |
+----+----+-----------+---------+-----------+-----------+---------+-----------+

它们中的任何一个至少满足。x = yq + r

截断除法和模数

static int truncatedDiv(int x, int y) {    
    return x / y;
}

static int truncatedMod(int x, int y) {    
    return x % y;
}

落地除法和模数

您可以使用 Java 8 中的方法。请参阅 floorDiv 和 floorMod。java.lang.Math

static int floorDiv(int x, int y) {    
    return Math.floorDiv(x, y);
}

static int floorMod(int x, int y) {    
    return Math.floorMod(x, y);
}

欧几里得除法和模

a）基于截断除法

import static java.lang.Math.*;

static int euclideanDiv(int x, int y) {
    int r = x / y;
    // if the divident is negative and modulo not zero, round down for positive divisor, otherwise round up
    if (x < 0 && r * y != x) {
        r -= signum(y);
    }
    return r;
}

static int euclideanMod(int x, int y) {
    int r = x - euclideanDiv(x, y) * y;
    return r;
}

b）基于地板划分

import static java.lang.Math.*;

static int euclideanDiv(int x, int y) {
    int r = floorDiv(x, y);
    // if the divisor is negative and modulo not zero, round up
    if (y < 0 && r * y != x) {
        r++;
    }
    return r;
}

static int euclideanMod(int x, int y) {
    int r = x - euclideanDiv(x, y) * y;
    return r;
}

c）基于绝对模

import static java.lang.Math.*;

static int euclideanMod(int x, int y) {
    int r = abs(x) % abs(y);
    // apply the sign of divident and make sure the remainder is positive number
    r *= signum(x);
    r = (r + abs(y)) % abs(y);
    return r;
}

答案 2

这个代码怎么样

public static int gcd(int p, int q) {
    if(count == 0) 
        System.out.print("Gcd for " + p + " and " + q);
    if (q == 0) {
           System.out.println(" returns " + p + " after " + count + " iterations");
        return p;
    }
    count++;
    return gcd(q, p % q);
}
public static void main(String[] args) {
    count = 0;
    gcd(4, 16);
    count = 0;
    gcd(4, 16);
    count = 0;
    gcd(16, 4);
    count = 0;
    gcd(15, 60);
    count = 0;
    gcd(15, 65);
    count = 0;
    gcd(1052, 52);
}