UInt192.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;
/**
* A mutable 192-bit unsigned integer.
*
* <p>This is a specialised class to implement an accumulator of squared {@code long} values.
*
* @since 1.1
*/
final class UInt192 {
/** Mask for the lower 32-bits of a long. */
private static final long MASK32 = 0xffff_ffffL;
// Data is stored using integers to allow efficient sum-with-carry addition
/** bits 32-1 (low 32-bits). */
private int f;
/** bits 64-33. */
private int e;
/** bits 96-65. */
private int d;
/** bits 128-97. */
private int c;
/** bits 192-129 (high 64-bits). */
private long ab;
/**
* Create an instance.
*/
private UInt192() {
// No-op
}
/**
* Create an instance using a direct binary representation.
* This is package-private for testing.
*
* @param hi High 64-bits.
* @param mid Middle 64-bits.
* @param lo Low 64-bits.
*/
UInt192(long hi, long mid, long lo) {
this.f = (int) lo;
this.e = (int) (lo >>> Integer.SIZE);
this.d = (int) mid;
this.c = (int) (mid >>> Integer.SIZE);
this.ab = hi;
}
/**
* Create an instance using a direct binary representation.
*
* @param ab bits 192-129 (high 64-bits).
* @param c bits 128-97.
* @param d bits 96-65.
* @param e bits 64-33.
* @param f bits 32-1.
*/
private UInt192(long ab, int c, int d, int e, int f) {
this.ab = ab;
this.c = c;
this.d = d;
this.e = e;
this.f = f;
}
/**
* Create an instance. The initial value is zero.
*
* @return the instance
*/
static UInt192 create() {
return new UInt192();
}
/**
* Adds the squared value {@code x * x}.
*
* @param x Value.
*/
void addSquare(long x) {
final long lo = x * x;
final long hi = IntMath.squareHigh(x);
// Sum with carry.
long s = (lo & MASK32) + (f & MASK32);
f = (int) s;
s = (s >>> Integer.SIZE) + (lo >>> Integer.SIZE) + (e & MASK32);
e = (int) s;
s = (s >>> Integer.SIZE) + (hi & MASK32) + (d & MASK32);
d = (int) s;
s = (s >>> Integer.SIZE) + (hi >>> Integer.SIZE) + (c & MASK32);
c = (int) s;
ab += s >>> Integer.SIZE;
}
/**
* Adds the value.
*
* @param x Value.
*/
void add(UInt192 x) {
// Avoid issues adding to itself
final int ff = x.f;
final int ee = x.e;
final int dd = x.d;
final int cc = x.c;
final long aabb = x.ab;
// Sum with carry.
long s = (ff & MASK32) + (f & MASK32);
f = (int) s;
s = (s >>> Integer.SIZE) + (ee & MASK32) + (e & MASK32);
e = (int) s;
s = (s >>> Integer.SIZE) + (dd & MASK32) + (d & MASK32);
d = (int) s;
s = (s >>> Integer.SIZE) + (cc & MASK32) + (c & MASK32);
c = (int) s;
ab += (s >>> Integer.SIZE) + aabb;
}
/**
* Multiply by the unsigned value.
* Any overflow bits are lost.
*
* @param x Value.
* @return the product
*/
UInt192 unsignedMultiply(int x) {
final long xx = x & MASK32;
// Multiply with carry.
long product = xx * (f & MASK32);
final int ff = (int) product;
product = (product >>> Integer.SIZE) + xx * (e & MASK32);
final int ee = (int) product;
product = (product >>> Integer.SIZE) + xx * (d & MASK32);
final int dd = (int) product;
product = (product >>> Integer.SIZE) + xx * (c & MASK32);
final int cc = (int) product;
// Possible overflow here and bits are lost
final long aabb = (product >>> Integer.SIZE) + xx * ab;
return new UInt192(aabb, cc, dd, ee, ff);
}
/**
* Subtracts the value.
* Any overflow bits (negative result) are lost.
*
* @param x Value.
* @return the difference
*/
UInt192 subtract(UInt128 x) {
// Difference with carry.
// Subtract common part.
long diff = (f & MASK32) - (x.lo32() & MASK32);
final int ff = (int) diff;
diff = (diff >> Integer.SIZE) + (e & MASK32) - (x.mid32() & MASK32);
final int ee = (int) diff;
diff = (diff >> Integer.SIZE) + (d & MASK32) - (x.hi64() & MASK32);
final int dd = (int) diff;
diff = (diff >> Integer.SIZE) + (c & MASK32) - (x.hi64() >>> Integer.SIZE);
final int cc = (int) diff;
// Possible overflow here and bits are lost containing info on the
// magnitude of the true negative value
final long aabb = (diff >> Integer.SIZE) + ab;
return new UInt192(aabb, cc, dd, ee, ff);
}
/**
* Convert to a BigInteger.
*
* @return the value
*/
BigInteger toBigInteger() {
final ByteBuffer bb = ByteBuffer.allocate(Integer.BYTES * 6)
.putLong(ab)
.putInt(c)
.putInt(d)
.putInt(e)
.putInt(f);
// Sign is always positive. This works for zero.
return new BigInteger(1, bb.array());
}
/**
* Convert to a double.
*
* @return the value
*/
double toDouble() {
final long h = hi64();
final long m = mid64();
final long l = lo64();
if (h == 0) {
return IntMath.uint128ToDouble(m, l);
}
// For correct rounding we use a sticky bit to represent magnitude
// lost from the low 64-bits. The result is scaled by 2^64.
return IntMath.uint128ToDouble(h, m | ((l == 0) ? 0 : 1)) * 0x1.0p64;
}
/**
* 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() {
// Test if we have more than 63-bits
if ((ab | c | d) != 0 || e < 0) {
throw new ArithmeticException("long integer overflow");
}
return lo64();
}
/**
* Return the lower 64-bits as a {@code long} value.
*
* @return the low 64-bits
*/
long lo64() {
return (f & MASK32) | ((e & MASK32) << Integer.SIZE);
}
/**
* Return the middle 64-bits as a {@code long} value.
*
* @return bits 128-65
*/
long mid64() {
return (d & MASK32) | ((c & MASK32) << Integer.SIZE);
}
/**
* Return the higher 64-bits as a {@code long} value.
*
* @return bits 192-129
*/
long hi64() {
return ab;
}
}