Package de.tilman_neumann.jml.base

Class Uint128

  • public class Uint128
extends Object
    An incomplete 128 bit unsigned int implementation. Implementation notes: * a+Long.MIN_VALUE <> b+Long-MIN_VALUE is an inlined compareUnsigned(a, b) <> 0.
    Author:
    Tilman Neumann

    • Constructor Detail

      • Uint128

        public Uint128​(long high,
               long low)

    • Method Detail

      • getHigh

        public long getHigh()

      • getLow

        public long getLow()

      • add_v1

        public Uint128 add_v1​(Uint128 other)
        Add two unsigned 128 bit integers.
        Parameters:
        other -
        Returns:
        this + other

      • add

        public Uint128 add​(Uint128 other)
        Add two unsigned 128 bit integers. Simpler carry recognition and thus much faster than the first version, thanks to Ben, see https://www.mersenneforum.org/showpost.php?p=524300&postcount=173.
        Parameters:
        other -
        Returns:
        this + other

      • add_getHigh

        public long add_getHigh​(Uint128 other)
        Compute the sum of this and other, return the high part.
        Parameters:
        other -
        Returns:
        high part of this + other

      • subtract

        public Uint128 subtract​(Uint128 other)
        Subtract two unsigned 128 bit integers. XXX experimental, probably wrong...
        Parameters:
        other -
        Returns:
        this - other

      • mul63

        public static Uint128 mul63​(long a,
                            long b)
        Multiplication of unsigned 63 bit integers, following https://stackoverflow.com/questions/18859207/high-bits-of-long-multiplication-in-java. This method ignores overflows of the "middle term". As such it won't work for 64 bit inputs but is otherwise faster than mul64().
        Parameters:
        a -
        b -
        Returns:
        a*b accurate for inputs <= 63 bit

      • mul64_v1

        public static Uint128 mul64_v1​(long a,
                               long b)
        Multiplication of unsigned 64 bit integers, following https://stackoverflow.com/questions/18859207/high-bits-of-long-multiplication-in-java. This method takes notice of overflows of the "middle term". As such it works for 64 bit inputs but is slightly slower than mul63().
        Parameters:
        a - unsigned long
        b - unsigned long
        Returns:
        a*b

      • mul64

        public static Uint128 mul64​(long a,
                            long b)
        Multiplication of unsigned 64 bit integers with simplified carry recognition. This is the fastest version so far, with the strange exception that it falls behind version 1 for N>=52 bit in PollardRhoBrentMontgomery64.
        Parameters:
        a - unsigned long
        b - unsigned long
        Returns:
        a*b

      • square64

        public static Uint128 square64​(long a)
        The square of an unsigned 64 bit integer.
        Parameters:
        a - unsigned long
        Returns:
        a^2

      • mul64_getLow

        public static long mul64_getLow​(long a,
                                long b)
        Computes the low part of the product of two unsigned 64 bit integers. Overflows of the "middle term" are not interesting here because they'ld only affect the high part of the multiplication result.
        Parameters:
        a -
        b -
        Returns:
        (a*b) & 0xFFFFFFFFL

      • spDivide

        public long[] spDivide​(long v)
        Compute quotient and remainder of this / v. The quotient will be correct only if it is <= 64 bit. Ported from https://codereview.stackexchange.com/questions/67962/mostly-portable-128-by-64-bit-division.
        Parameters:
        v - 64 bit unsigned integer
        Returns:
        [quotient, remainder] of this / v

      • shiftLeft

        public Uint128 shiftLeft​(int bits)
        Shift this 'bits' bits to the left.
        Parameters:
        bits -
        Returns:
        this << bits

      • shiftRight

        public Uint128 shiftRight​(int bits)
        Shift this 'bits' bits to the right.
        Parameters:
        bits -
        Returns:
        this >>> bits

      • and

        public long and​(long other)
        Bitwise "and" operation with a long.
        Parameters:
        other -
        Returns:
        this & other

      • doubleValue

        public double doubleValue()

      • toBigInteger

        public BigInteger toBigInteger()
        Convert this to BigInteger.
        Returns:
        this unsigned 128 bit integer converted to BigInteger

      • main

        public static void main​(String[] args)
        Test.
        Parameters:
        args - ignored