Java程序运行耗时异常：删除ggT方法两行代码后运行时间从0秒增至30秒以上

问题根本原因 #

你遇到的运行速度差异本质是求最大公约数（ggT）的逻辑对负数输入不兼容，那两行取绝对值的代码是保证算法正常运行的必要逻辑，具体原因拆解如下：

• 你使用的暴力递减法求最大公约数，本身仅适用于正整数输入：最大公约数是正整数域的定义，负数不适用该逻辑。
• 你的Bruch构造方法仅处理了「分子、分母同时为负」的符号场景，当执行减法运算得到只有分子为负的结果（比如示例中1/6 - 3/4 = -7/12）时，负数会直接传入ggT方法。
• 去掉取绝对值的代码后，若传入负数参数：
  1. min函数会返回更小的负数作为初始ggTeiler，比如传入ggT(-7,12)时初始值为-7
  2. 循环中你对ggTeiler执行递减操作，负数持续向负方向减小，永远碰不到可以同时整除两个数的负公约数（比如能整除-7和12的-1比初始值-7大，不会被遍历到），直到int溢出转为正整数后才有可能找到符合条件的公约数，整个过程要循环近40亿次，直接导致耗时暴增到30秒以上。
• 保留那两行代码时，输入参数会先被转为正整数，循环最多执行较小正整数的次数（比如7和12最多循环7次），自然耗时接近0秒。

优化建议 #

• 可以将暴力求gcd的逻辑替换为辗转相除法（欧几里得算法），执行效率会大幅提升，示例代码如下：

private int ggT(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

• 可以完善构造方法的符号处理逻辑，统一把负号放在分子位置，避免负号出现在分母：

public Bruch(int zaehler, int nenner){
    // 统一处理符号：负号放分子，分母始终为正
    if (nenner < 0) {
        zaehler *= -1;
        nenner *= -1;
    }
    this.zaehler = zaehler;
    this.nenner = nenner;
    kuerzeDich();
}

内容的提问来源于stack exchange，提问作者alix2414