Int128.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.statistics.descriptive;
import java.math.BigInteger;
import java.nio.ByteBuffer;
import org.apache.commons.numbers.core.DD;
/**
* A mutable 128-bit signed integer.
*
* <p>This is a specialised class to implement an accumulator of {@code long} values.
*
* <p>Note: This number uses a signed long integer representation of:
*
* <pre>value = 2<sup>64</sup> * hi64 + lo64</pre>
*
* <p>If the high value is zero then the low value is the long representation of the
* number including the sign bit. Otherwise the low value corresponds to a correction
* term for the scaled high value which contains the sign-bit of the number.
*
* @since 1.1
*/
final class Int128 {
/** Mask for the lower 32-bits of a long. */
private static final long MASK32 = 0xffff_ffffL;
/** low 64-bits. */
private long lo;
/** high 64-bits. */
private long hi;
/**
* Create an instance.
*/
private Int128() {
// No-op
}
/**
* Create an instance.
*
* @param x Value.
*/
private Int128(long x) {
lo = x;
}
/**
* Create an instance using a direct binary representation.
* This is package-private for testing.
*
* @param hi High 64-bits.
* @param lo Low 64-bits.
*/
Int128(long hi, long lo) {
this.lo = lo;
this.hi = hi;
}
/**
* Create an instance. The initial value is zero.
*
* @return the instance
*/
static Int128 create() {
return new Int128();
}
/**
* Create an instance of the {@code long} value.
*
* @param x Value.
* @return the instance
*/
static Int128 of(long x) {
return new Int128(x);
}
/**
* Adds the value.
*
* @param x Value.
*/
void add(long x) {
final long y = lo;
final long r = y + x;
// Overflow if the result has the opposite sign of both arguments
// (+,+) -> -
// (-,-) -> +
// Detect opposite sign:
if (((y ^ r) & (x ^ r)) < 0) {
// Carry overflow bit
hi += x < 0 ? -1 : 1;
}
lo = r;
}
/**
* Adds the value.
*
* @param x Value.
*/
void add(Int128 x) {
// Avoid issues adding to itself
final long l = x.lo;
final long h = x.hi;
add(l);
hi += h;
}
/**
* Compute the square of the low 64-bits of this number.
*
* <p>Warning: This ignores the upper 64-bits. Use with caution.
*
* @return the square
*/
UInt128 squareLow() {
final long x = lo;
final long upper = IntMath.squareHigh(x);
return new UInt128(upper, x * x);
}
/**
* Convert to a BigInteger.
*
* @return the value
*/
BigInteger toBigInteger() {
long h = hi;
long l = lo;
// Special cases
if (h == 0) {
return BigInteger.valueOf(l);
}
if (l == 0) {
return BigInteger.valueOf(h).shiftLeft(64);
}
// The representation is 2^64 * hi64 + lo64.
// Here we avoid evaluating the addition:
// BigInteger.valueOf(l).add(BigInteger.valueOf(h).shiftLeft(64))
// It is faster to create from bytes.
// BigInteger bytes are an unsigned integer in BigEndian format, plus a sign.
// If both values are positive we can use the values unchanged.
// Otherwise selective negation is used to create a positive magnitude
// and we track the sign.
// Note: Negation of -2^63 is valid to create an unsigned 2^63.
int sign = 1;
if ((h ^ l) < 0) {
// Opposite signs and lo64 is not zero.
// The lo64 bits are an adjustment to the magnitude of hi64
// to make it smaller.
// Here we rearrange to [2^64 * (hi64-1)] + [2^64 - lo64].
// The second term [2^64 - lo64] can use lo64 as an unsigned 64-bit integer.
// The first term [2^64 * (hi64-1)] does not work if low is zero.
// It would work if zero was detected and we carried the overflow
// bit up to h to make it equal to: (h - 1) + 1 == h.
// Instead lo64 == 0 is handled as a special case above.
if (h >= 0) {
// Treat (unchanged) low as an unsigned add
h = h - 1;
} else {
// As above with negation
h = ~h; // -h - 1
l = -l;
sign = -1;
}
} else if (h < 0) {
// Invert negative values to create the equivalent positive magnitude.
h = -h;
l = -l;
sign = -1;
}
return new BigInteger(sign,
ByteBuffer.allocate(Long.BYTES * 2)
.putLong(h).putLong(l).array());
}
/**
* Convert to a {@code double}.
*
* @return the value
*/
double toDouble() {
long h = hi;
long l = lo;
// Special cases
if (h == 0) {
return l;
}
if (l == 0) {
return h * 0x1.0p64;
}
// Both h and l are non-zero and can be negated to a positive magnitude.
// Use the same logic as toBigInteger to create magnitude (h, l) and a sign.
int sign = 1;
if ((h ^ l) < 0) {
// Here we rearrange to [2^64 * (hi64-1)] + [2^64 - lo64].
if (h >= 0) {
h = h - 1;
} else {
// As above with negation
h = ~h; // -h - 1
l = -l;
sign = -1;
}
} else if (h < 0) {
// Invert negative values to create the equivalent positive magnitude.
h = -h;
l = -l;
sign = -1;
}
final double x = IntMath.uint128ToDouble(h, l);
return sign < 0 ? -x : x;
}
/**
* Convert to a double-double.
*
* @return the value
*/
DD toDD() {
// Don't combine two 64-bit DD numbers:
// DD.of(hi).scalb(64).add(DD.of(lo))
// It is more accurate to create a 96-bit number and add the final 32-bits.
// Sum low to high.
// Note: Masking a negative hi number will create a small positive magnitude
// to add to a larger negative number:
// e.g. x = (x & 0xff) + ((x >> 8) << 8)
return DD.of(lo).add((hi & MASK32) * 0x1.0p64).add((hi >> Integer.SIZE) * 0x1.0p96);
}
/**
* Convert to an {@code int}; throwing an exception if the value overflows an {@code int}.
*
* @return the value
* @throws ArithmeticException if the value overflows an {@code int}.
* @see Math#toIntExact(long)
*/
int toIntExact() {
return Math.toIntExact(toLongExact());
}
/**
* Convert to a {@code long}; throwing an exception if the value overflows a {@code long}.
*
* @return the value
* @throws ArithmeticException if the value overflows a {@code long}.
*/
long toLongExact() {
if (hi != 0) {
throw new ArithmeticException("long integer overflow");
}
return lo;
}
/**
* Return the lower 64-bits as a {@code long} value.
*
* <p>If the high value is zero then the low value is the long representation of the
* number including the sign bit. Otherwise this value corresponds to a correction
* term for the scaled high value which contains the sign-bit of the number
* (see {@link Int128}).
*
* @return the low 64-bits
*/
long lo64() {
return lo;
}
/**
* Return the higher 64-bits as a {@code long} value.
*
* @return the high 64-bits
* @see #lo64()
*/
long hi64() {
return hi;
}
}