快速整數除法中的Java

衆所周知整數除法是（比整數乘法慢通常數次）緩慢的操作。但是，如果一個人需要用一個固定除數執行許多除法運算，可以做一些預處理對除數和替換「/」與乘法和位操作（第10章Hacker's Delight）。我測試過，如果除數是一個編譯時間常量（例如static final long DIVISOR = 12345L;），JVM就會執行這個技巧，並用乘法和位操作替換所有除數DIVISOR。我在同一種技巧中很有趣，但是隻有在運行時才知道除數。快速整數除法中的Java

例如，下面的（慢）方法：

void reduceArrayFast(long[] data, long denominator){ 
    SomeMagicStructure magic = computeMagic(denominator); 
    for(int i = 0; i < data.length; ++i) 
     // computes data[i]/denominator 
     data[i] = doFastDivision(data[i], magic); 
}

必須更快地完成工作，因爲所有/操作與更快的更換：

void reduceArraySlow(long[] data, long denominator){ 
    for(int i = 0; i < data.length; ++i) 
     data[i] = data[i]/denominator; 
}

可以用什麼來代替操作（也因爲除法在CPU中不流水線）。

來源

2017-03-16 Stanislav Poslavsky

有一個衆所周知的C/C++ libdivide快速整數除法庫，我有這個庫的改編爲Java libdivide4j。

與libdivide4j快速分裂看起來如下：

void reduceArrayFast(long[] data, long denominator){ 
    FastDivision.Magic magic = FastDivision.magicSigned(denominator); 
    for(int i = 0; i < data.length; ++i) 
     // computes data[i]/denominator 
     data[i] = FastDivision.divideSignedFast(data[i], magic); 
}

一個簡單的基準

public void benchmark() throws Exception { 
    Random rnd = new Random(); 
    int nIterations = 10000; 
    //let the JIT to optimize something 
    for (int att = 0; att < nIterations; att++) { 
     long[] data = new long[1000]; 
     for (int i = 0; i < data.length; i++) 
      data[i] = rnd.nextLong(); 

     long denominator = rnd.nextLong(); 

     long[] slow = data.clone(); 
     long start = System.nanoTime(); 
     reduceArraySlow(slow, denominator); 
     long slowTime = System.nanoTime() - start; 


     long[] fast = data.clone(); 
     start = System.nanoTime(); 
     reduceArrayFast(fast, denominator); 
     long fastTime = System.nanoTime() - start; 

     Assert.assertArrayEquals(slow, fast); 

     // print last 100 timings (JVM already warmed up) 
     if (att > nIterations - 100) { 
      System.out.println("\"/\" operation: " + slowTime); 
      System.out.println("Fast division: " + fastTime); 
      System.out.println(""); 
     } 
    } 
}

示出用於普通/和快速除法以下定時（納秒）（酷睿i7，jdk8 64位）：

"/" operation: 13233 
Fast division: 5957 

"/" operation: 13148 
Fast division: 5103 

"/" operation: 13587 
Fast division: 6188 

"/" operation: 14173 
Fast division: 6773 
...

來源

2017-03-16 17:18:33

快速整數除法中的Java

回答

相關問題