Package cc.redberry.libdivide4j

Class FastDivision

java.lang.Object
cc.redberry.libdivide4j.FastDivision
public final class FastDivision extends Object
Fast integer division and modulo operation (both signed and unsigned).

Usage example: 


 long[] someData = ...
 long denominator = 45;
 FastDivision.Magic magic = FastDivision.magicSigned(denominator);

 long[] reduced = new long[someData.length];
 for (int i = 0; i < someData.length; ++i) {
     // this is the same as someData[i] / denominator but 3 times faster
     reduced[i] = FastDivision.divideSignedFast(someData[i], magic);
 }

The code for fast division with preconditioning is adapted from C libdivide library ( http://github.com/ridiculousfish/libdivide)

  • Constructor Details

    • FastDivision

      private FastDivision()

  • Method Details

    • multiplyHighSigned

      public static long multiplyHighSigned(long x, long y)
      Returns highest 64 bits of (signed) long multiplication.
      Parameters:
      x - the number
      y - the number
      Returns:
      highest 64 bits of (signed) long multiplication.

    • multiplyHighUnsigned

      public static long multiplyHighUnsigned(long x, long y)
      Returns highest 64 bits of (unsigned) long multiplication.
      Parameters:
      x - the number
      y - the number
      Returns:
      highest 64 bits of (unsigned) long multiplication.

    • multiplyLow

      public static long multiplyLow(long x, long y)
      Returns lowest 64 bits of either signed or unsigned long multiplication.
      Parameters:
      x - the number
      y - the number
      Returns:
      lowest 64 bits of long multiplication.

    • divideAndRemainder128

      public static long[] divideAndRemainder128(long u1, long u0, long v)
      Return's quotient and remainder of 128 bit integer division by 64 bit integer.

      Code taken from Hacker's Delight: http://www.hackersdelight.org/HDcode/divlu.c.

      Parameters:
      u1 - highest 64 dividend bits
      u0 - lowest 64 dividend bits
      v - the divider
      Returns:
      {quotient, remainder}

    • magicUnsigned

      public static FastDivision.Magic magicUnsigned(long d)
      Computes magic for fast unsigned integer division.
      Parameters:
      d - the divider
      Returns:
      the magic

    • magicUnsigned

      public static FastDivision.Magic magicUnsigned(long d, boolean branchfree)
      Computes magic for fast unsigned integer division.
      Parameters:
      d - the divider
      branchfree - branching free
      Returns:
      the magic

    • divideUnsignedFast

      public static long divideUnsignedFast(long dividend, FastDivision.Magic divider)
      Returns unsigned dividend / divider using fast integer division
      Parameters:
      dividend - the dividend
      divider - the divider
      Returns:
      dividend / divider

    • magicSigned

      public static FastDivision.Magic magicSigned(long d)
      Computes magic for fast signed integer division.
      Parameters:
      d - the divider
      Returns:
      the magic

    • magicSigned

      public static FastDivision.Magic magicSigned(long d, boolean branchfree)
      Computes magic for fast integer division.
      Parameters:
      d - the divider
      branchfree - use branch free computation
      Returns:
      the magic

    • divideSignedFast

      public static long divideSignedFast(long dividend, FastDivision.Magic divider)
      Returns signed dividend / divider using fast integer division
      Parameters:
      dividend - the dividend
      divider - the divider
      Returns:
      dividend / divider

    • remainderSignedFast

      public static long remainderSignedFast(long dividend, FastDivision.Magic divider)
      Calculates the remainder using fast integer division
      Parameters:
      dividend - the dividend
      divider - the divider
      Returns:
      dividend % divider

    • remainderUnsignedFast

      public static long remainderUnsignedFast(long dividend, FastDivision.Magic divider)
      Calculates the remainder using fast integer division
      Parameters:
      dividend - the dividend
      divider - the divider
      Returns:
      dividend % divider

    • floorDivideFast

      public static long floorDivideFast(long dividend, FastDivision.Magic divider)
      Computes floor division of the dividend by the divider using fast integer division returning (meaningful for signed operations)
      Parameters:
      dividend - the dividend
      divider - the divider
      Returns:
      dividend / divider
      See Also:

    • modSignedFast

      public static long modSignedFast(long dividend, FastDivision.Magic divider)
      Calculates the modulus using fast integer division
      Parameters:
      dividend - the dividend
      divider - the divider
      Returns:
      dividend % divider

    • modUnsignedFast

      public static long modUnsignedFast(long dividend, FastDivision.Magic divider)
      Calculates the modulus using fast integer division
      Parameters:
      dividend - the dividend
      divider - the divider
      Returns:
      dividend % divider

    • magic32ForMultiplyMod

      public static FastDivision.Magic magic32ForMultiplyMod(long divider)
      Computes magic for fast mulmod operation.
      Parameters:
      divider - the divider (must be positive)
      Returns:
      the magic

    • multiplyMod128Unsigned

      public static long multiplyMod128Unsigned(long a, long b, long divider, FastDivision.Magic magic32)
      Returns unsigned (a*b)%divider
      Parameters:
      a - the first multiplier
      b - the second multiplier
      divider - the divider
      magic32 - magic for fast division magic32ForMultiplyMod(long)
      Returns:
      (a*b)%divider

    • multiplyMod128Unsigned0

      public static long multiplyMod128Unsigned0(long high, long low, long divider, FastDivision.Magic magic32)
      Returns unsigned (low|(high<<64))%divider
      Parameters:
      high - the highest bits
      low - the lowest bits
      divider - the divider
      magic32 - magic for fast division magic32ForMultiplyMod(long)
      Returns:
      (low|(high<<64))%divider