1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.statistics.examples.jmh.descriptive;
18
19 import java.math.BigInteger;
20 import java.nio.ByteBuffer;
21 import org.apache.commons.numbers.core.DD;
22
23 /**
24 * A 192-bit unsigned integer.
25 *
26 * <p>This is a copy of {@code o.a.c.statistics.descriptive.UInt192} to allow benchmarking.
27 * Additional methods may have been added for comparative benchmarks.
28 *
29 * <p>This is a specialised class to implement an accumulator of squared {@code long} values.
30 *
31 * @since 1.1
32 */
33 final class UInt192 {
34 /** Mask for the lower 32-bits of a long. */
35 private static final long MASK32 = 0xffff_ffffL;
36
37 // Data is stored using integers to allow efficient sum-with-carry addition
38
39 /** bits 32-1 (low 32-bits). */
40 private int f;
41 /** bits 64-33. */
42 private int e;
43 /** bits 96-65. */
44 private int d;
45 /** bits 128-97. */
46 private int c;
47 /** bits 192-129 (high 64-bits). */
48 private long ab;
49
50 /**
51 * Create an instance.
52 */
53 private UInt192() {
54 // No-op
55 }
56
57 /**
58 * Create an instance using a direct binary representation.
59 * This is package-private for testing.
60 *
61 * @param hi High 64-bits.
62 * @param mid Middle 64-bits.
63 * @param lo Low 64-bits.
64 */
65 UInt192(long hi, long mid, long lo) {
66 this.f = (int) lo;
67 this.e = (int) (lo >>> Integer.SIZE);
68 this.d = (int) mid;
69 this.c = (int) (mid >>> Integer.SIZE);
70 this.ab = hi;
71 }
72
73 /**
74 * Create an instance using a direct binary representation.
75 *
76 * @param ab bits 192-129 (high 64-bits).
77 * @param c bits 128-97.
78 * @param d bits 96-65.
79 * @param e bits 64-33.
80 * @param f bits 32-1.
81 */
82 private UInt192(long ab, int c, int d, int e, int f) {
83 this.ab = ab;
84 this.c = c;
85 this.d = d;
86 this.e = e;
87 this.f = f;
88 }
89
90 /**
91 * Create an instance. The initial value is zero.
92 *
93 * @return the instance
94 */
95 static UInt192 create() {
96 return new UInt192();
97 }
98
99 /**
100 * Adds the squared value {@code x * x}.
101 *
102 * @param x Value.
103 */
104 void addSquare(long x) {
105 final long lo = x * x;
106 final long hi = IntMath.squareHigh(x);
107
108 // Sum with carry.
109 long s = (lo & MASK32) + (f & MASK32);
110 f = (int) s;
111 s = (s >>> Integer.SIZE) + (lo >>> Integer.SIZE) + (e & MASK32);
112 e = (int) s;
113 s = (s >>> Integer.SIZE) + (hi & MASK32) + (d & MASK32);
114 d = (int) s;
115 s = (s >>> Integer.SIZE) + (hi >>> Integer.SIZE) + (c & MASK32);
116 c = (int) s;
117 ab += s >>> Integer.SIZE;
118 }
119
120 /**
121 * Adds the squared value {@code x * x}.
122 *
123 * <p>This uses {@code java.lang.Math.multiplyHigh(long, long)} and requires Java 11+.
124 *
125 * @param x Value.
126 */
127 void addSquare2(long x) {
128 final long lo = x * x;
129 final long hi = Math.multiplyHigh(x, x);
130
131 // Sum with carry.
132 long s = (lo & MASK32) + (f & MASK32);
133 f = (int) s;
134 s = (s >>> Integer.SIZE) + (lo >>> Integer.SIZE) + (e & MASK32);
135 e = (int) s;
136 s = (s >>> Integer.SIZE) + (hi & MASK32) + (d & MASK32);
137 d = (int) s;
138 s = (s >>> Integer.SIZE) + (hi >>> Integer.SIZE) + (c & MASK32);
139 c = (int) s;
140 ab += s >>> Integer.SIZE;
141 }
142
143 /**
144 * Adds the value.
145 *
146 * @param x Value.
147 */
148 void add(UInt192 x) {
149 // Avoid issues adding to itself
150 final int ff = x.f;
151 final int ee = x.e;
152 final int dd = x.d;
153 final int cc = x.c;
154 final long aabb = x.ab;
155 // Sum with carry.
156 long s = (ff & MASK32) + (f & MASK32);
157 f = (int) s;
158 s = (s >>> Integer.SIZE) + (ee & MASK32) + (e & MASK32);
159 e = (int) s;
160 s = (s >>> Integer.SIZE) + (dd & MASK32) + (d & MASK32);
161 d = (int) s;
162 s = (s >>> Integer.SIZE) + (cc & MASK32) + (c & MASK32);
163 c = (int) s;
164 ab += (s >>> Integer.SIZE) + aabb;
165 }
166
167
168 /**
169 * Multiply by the unsigned value.
170 * Any overflow bits are lost.
171 *
172 * @param x Value.
173 * @return the product
174 */
175 UInt192 unsignedMultiply(int x) {
176 final long xx = x & MASK32;
177 // Multiply with carry.
178 long product = xx * (f & MASK32);
179 final int ff = (int) product;
180 product = (product >>> Integer.SIZE) + xx * (e & MASK32);
181 final int ee = (int) product;
182 product = (product >>> Integer.SIZE) + xx * (d & MASK32);
183 final int dd = (int) product;
184 product = (product >>> Integer.SIZE) + xx * (c & MASK32);
185 final int cc = (int) product;
186 // Possible overflow here and bits are lost
187 final long aabb = (product >>> Integer.SIZE) + xx * ab;
188 return new UInt192(aabb, cc, dd, ee, ff);
189 }
190
191 /**
192 * Subtracts the value.
193 * Any overflow bits (negative result) are lost.
194 *
195 * @param x Value.
196 * @return the difference
197 */
198 UInt192 subtract(UInt128 x) {
199 // Difference with carry.
200 // Subtract common part.
201 long diff = (f & MASK32) - (x.lo32() & MASK32);
202 final int ff = (int) diff;
203 diff = (diff >> Integer.SIZE) + (e & MASK32) - (x.mid32() & MASK32);
204 final int ee = (int) diff;
205 diff = (diff >> Integer.SIZE) + (d & MASK32) - (x.hi64() & MASK32);
206 final int dd = (int) diff;
207 diff = (diff >> Integer.SIZE) + (c & MASK32) - (x.hi64() >>> Integer.SIZE);
208 final int cc = (int) diff;
209 // Possible overflow here and bits are lost containing info on the
210 // magnitude of the true negative value
211 final long aabb = (diff >> Integer.SIZE) + ab;
212 return new UInt192(aabb, cc, dd, ee, ff);
213 }
214
215 /**
216 * Convert to a BigInteger.
217 *
218 * @return the value
219 */
220 BigInteger toBigInteger() {
221 final ByteBuffer bb = ByteBuffer.allocate(Integer.BYTES * 6)
222 .putLong(ab)
223 .putInt(c)
224 .putInt(d)
225 .putInt(e)
226 .putInt(f);
227 // Sign is always positive. This works for zero.
228 return new BigInteger(1, bb.array());
229 }
230
231 /**
232 * Convert to a double.
233 *
234 * @return the value
235 */
236 double toDouble() {
237 final long h = hi64();
238 final long m = mid64();
239 final long l = lo64();
240 if (h == 0) {
241 return IntMath.uin128ToDouble(m, l);
242 }
243 // For correct rounding we use a sticky bit to represent magnitude
244 // lost from the low 64-bits. The result is scaled by 2^64.
245 return IntMath.uin128ToDouble(h, m | ((l != 0) ? 1 : 0)) * 0x1.0p64;
246 }
247
248 /**
249 * Convert to a double-double.
250 *
251 * @return the value
252 */
253 DD toDD() {
254 // Sum low to high
255 return DD.ofSum(f & MASK32, (e & MASK32) * 0x1.0p32)
256 .add((d & MASK32) * 0x1.0p64)
257 .add((c & MASK32) * 0x1.0p96)
258 .add((ab & MASK32) * 0x1.0p128)
259 .add((ab >>> Integer.SIZE) * 0x1.0p160);
260 }
261
262 /**
263 * Return the lower 64-bits as a {@code long} value.
264 *
265 * @return the low 64-bits
266 */
267 long lo64() {
268 return (f & MASK32) | ((e & MASK32) << Integer.SIZE);
269 }
270
271 /**
272 * Return the middle 64-bits as a {@code long} value.
273 *
274 * @return bits 128-65
275 */
276 long mid64() {
277 return (d & MASK32) | ((c & MASK32) << Integer.SIZE);
278 }
279
280 /**
281 * Return the higher 64-bits as a {@code long} value.
282 *
283 * @return bits 192-129
284 */
285 long hi64() {
286 return ab;
287 }
288
289 /**
290 * Return the higher 32-bits as an {@code int} value.
291 *
292 * @return the high 32-bits
293 */
294 int hi32() {
295 return (int) (ab >>> Integer.SIZE);
296 }
297 }