Package cc.redberry.libdivide4j

Class FastDivision

  • public final class FastDivision
extends java.lang.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 Detail

      • FastDivision

        private FastDivision()

    • Method Detail

      • 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:
        Math.floorDiv(long, long)

      • 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