Class Uint128

java.lang.Object
de.tilman_neumann.jml.base.Uint128

public class Uint128
extends java.lang.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.
  • Constructor Summary

    Constructors
    Constructor Description
    Uint128​(long high, long low)  
  • Method Summary

    Modifier and Type Method Description
    Uint128 add​(Uint128 other)
    Add two unsigned 128 bit integers.
    long add_getHigh​(Uint128 other)
    Compute the sum of this and other, return the high part.
    Uint128 add_v1​(Uint128 other)
    Add two unsigned 128 bit integers.
    long and​(long other)
    Bitwise "and" operation with a long.
    double doubleValue()  
    long getHigh()  
    long getLow()  
    static void main​(java.lang.String[] args)
    Test.
    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.
    static Uint128 mul64​(long a, long b)
    Multiplication of unsigned 64 bit integers with simplified carry recognition.
    static long mul64_getLow​(long a, long b)
    Computes the low part of the product of two unsigned 64 bit integers.
    static Uint128 mul64_MH​(long a, long b)
    Multiplication of two unsigned 64-bit integers using Math.multiplyHigh().
    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.
    Uint128 shiftLeft​(int bits)
    Shift this 'bits' bits to the left.
    Uint128 shiftRight​(int bits)
    Shift this 'bits' bits to the right.
    long[] spDivide​(long v)
    Compute quotient and remainder of this / v.
    long[] spDivide_MH​(long v)
    Compute quotient and remainder of this / v.
    static Uint128 square64​(long a)
    The square of an unsigned 64 bit integer.
    Uint128 subtract​(Uint128 other)
    Subtract two unsigned 128 bit integers.
    java.math.BigInteger toBigInteger()
    Convert this to BigInteger.
    java.lang.String toString()  

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Constructor Details

    • Uint128

      public Uint128​(long high, long low)
  • Method Details

    • 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.
      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. Faster than v1 except for N>=52 bit in PollardRhoBrentMontgomery64 (strange)
      Parameters:
      a - unsigned long
      b - unsigned long
      Returns:
      a*b
    • mul64_MH

      public static Uint128 mul64_MH​(long a, long b)
      Multiplication of two unsigned 64-bit integers using Math.multiplyHigh(). Pretty fast if supported by intrinsics, which needs newer hardware and Java 10+.
      Parameters:
      a -
      b -
      Returns:
    • 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
    • spDivide_MH

      public long[] spDivide_MH​(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. In this variant we use Math.multiplyHigh() to multiply two unsigned 64 bit integers. This makes hardly a difference in terms of performance, though. Otherwise the implementation does not differ from spDivide().
      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 java.math.BigInteger toBigInteger()
      Convert this to BigInteger.
      Returns:
      this unsigned 128 bit integer converted to BigInteger
    • toString

      public java.lang.String toString()
      Overrides:
      toString in class java.lang.Object
    • main

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