1 /*
2 * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
26 * @bug 4851777
27 * @summary Tests of BigDecimal.sqrt().
28 */
29
30 import java.math.*;
31 import java.util.*;
32
33 public class SquareRootTests {
34
35 public static void main(String... args) {
36 int failures = 0;
37
38 failures += negativeTests();
39 failures += zeroTests();
40 failures += evenPowersOfTenTests();
41 failures += squareRootTwoTests();
42 failures += lowPrecisionPerfectSquares();
43
44 if (failures > 0 ) {
45 throw new RuntimeException("Incurred " + failures + " failures" +
46 " testing BigDecimal.sqrt().");
47 }
48 }
49
50 private static int negativeTests() {
51 int failures = 0;
52
53 for (long i = -10; i < 0; i++) {
54 for (int j = -5; j < 5; j++) {
55 try {
56 BigDecimal input = BigDecimal.valueOf(i, j);
57 BigDecimal result = input.sqrt(MathContext.DECIMAL64);
58 System.err.println("Unexpected sqrt of negative: (" +
59 input + ").sqrt() = " + result );
60 failures += 1;
61 } catch (ArithmeticException e) {
62 ; // Expected
80 expected, true, "zeros");
81 }
82
83 return failures;
84 }
85
86 /**
87 * sqrt(10^2N) is 10^N
88 * Both numerical value and representation should be verified
89 */
90 private static int evenPowersOfTenTests() {
91 int failures = 0;
92 MathContext oneDigitExactly = new MathContext(1, RoundingMode.UNNECESSARY);
93
94 for (int scale = -100; scale <= 100; scale++) {
95 BigDecimal testValue = BigDecimal.valueOf(1, 2*scale);
96 BigDecimal expectedNumericalResult = BigDecimal.valueOf(1, scale);
97
98 BigDecimal result;
99
100
101 failures += equalNumerically(expectedNumericalResult,
102 result = testValue.sqrt(MathContext.DECIMAL64),
103 "Even powers of 10, DECIMAL64");
104
105 // Can round to one digit of precision exactly
106 failures += equalNumerically(expectedNumericalResult,
107 result = testValue.sqrt(oneDigitExactly),
108 "even powers of 10, 1 digit");
109 if (result.precision() > 1) {
110 failures += 1;
111 System.err.println("Excess precision for " + result);
112 }
113
114
115 // If rounding to more than one digit, do precision / scale checking...
116
117 }
118
119 return failures;
120 }
121
122 private static int squareRootTwoTests() {
123 int failures = 0;
124 BigDecimal TWO = new BigDecimal(2);
125
126 // Square root of 2 truncated to 65 digits
127 BigDecimal highPrecisionRoot2 =
128 new BigDecimal("1.41421356237309504880168872420969807856967187537694807317667973799");
129
130
131 RoundingMode[] modes = {
132 RoundingMode.UP, RoundingMode.DOWN,
133 RoundingMode.CEILING, RoundingMode.FLOOR,
134 RoundingMode.HALF_UP, RoundingMode.HALF_DOWN, RoundingMode.HALF_EVEN
135 };
136
137 // For each iteresting rounding mode, for precisions 1 to, say
138 // 63 numerically compare TWO.sqrt(mc) to
139 // highPrecisionRoot2.round(mc)
140
141 for (RoundingMode mode : modes) {
142 for (int precision = 1; precision < 63; precision++) {
143 MathContext mc = new MathContext(precision, mode);
144 BigDecimal expected = highPrecisionRoot2.round(mc);
145 BigDecimal computed = TWO.sqrt(mc);
146
147 equalNumerically(expected, computed, "sqrt(2)");
148 }
149 }
150
151 return failures;
152 }
153
154 private static int lowPrecisionPerfectSquares() {
155 int failures = 0;
156
157 // For 5^2 through 9^2, if the input is rounded to one digit
158 // first before the root is computed, the wrong answer will
159 // result. Verify results and scale for different rounding
160 // modes and precisions.
161 long[][] squaresWithOneDigitRoot = {{ 4, 2},
162 { 9, 3},
163 {25, 5},
164 {36, 6},
165 {49, 7},
166 {64, 8},
167 {81, 9}};
178 MathContext mc = new MathContext(precision, rm);
179 BigDecimal computedRoot = scaledSquare.sqrt(mc);
180 failures += equalNumerically(expected, computedRoot, "simple squares");
181 int computedScale = computedRoot.scale();
182 if (precision >= expectedScale + 1 &&
183 computedScale != expectedScale) {
184 System.err.printf("%s\tprecision=%d\trm=%s%n",
185 computedRoot.toString(), precision, rm);
186 failures++;
187 System.err.printf("\t%s does not have expected scale of %d%n.",
188 computedRoot, expectedScale);
189 }
190 }
191 }
192 }
193 }
194
195 return failures;
196 }
197
198 private static int compare(BigDecimal a, BigDecimal b, boolean expected, String prefix) {
199 boolean result = a.equals(b);
200 int failed = (result==expected) ? 0 : 1;
201 if (failed == 1) {
202 System.err.println("Testing " + prefix +
203 "(" + a + ").compareTo(" + b + ") => " + result +
204 "\n\tExpected " + expected);
205 }
206 return failed;
207 }
208
209 private static int equalNumerically(BigDecimal a, BigDecimal b,
210 String prefix) {
211 return compareNumerically(a, b, 0, prefix);
212 }
213
214
215 private static int compareNumerically(BigDecimal a, BigDecimal b,
216 int expected, String prefix) {
217 int result = a.compareTo(b);
218 int failed = (result==expected) ? 0 : 1;
219 if (failed == 1) {
220 System.err.println("Testing " + prefix +
221 "(" + a + ").compareTo(" + b + ") => " + result +
222 "\n\tExpected " + expected);
223 }
224 return failed;
225 }
226
227 }
|
1 /*
2 * Copyright (c) 2016, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
26 * @bug 4851777 8233452
27 * @summary Tests of BigDecimal.sqrt().
28 */
29
30 import java.math.*;
31 import java.util.*;
32
33 import static java.math.BigDecimal.TEN;
34 import static java.math.BigDecimal.ZERO;
35 import static java.math.BigDecimal.valueOf;
36
37 public class SquareRootTests {
38 private static BigDecimal TWO = new BigDecimal(2);
39
40 public static void main(String... args) {
41 int failures = 0;
42
43 failures += negativeTests();
44 failures += zeroTests();
45 failures += evenPowersOfTenTests();
46 failures += squareRootTwoTests();
47 failures += lowPrecisionPerfectSquares();
48 failures += almostFourRoundingDown();
49 failures += almostFourRoundingUp();
50
51 if (failures > 0 ) {
52 throw new RuntimeException("Incurred " + failures + " failures" +
53 " testing BigDecimal.sqrt().");
54 }
55 }
56
57 private static int negativeTests() {
58 int failures = 0;
59
60 for (long i = -10; i < 0; i++) {
61 for (int j = -5; j < 5; j++) {
62 try {
63 BigDecimal input = BigDecimal.valueOf(i, j);
64 BigDecimal result = input.sqrt(MathContext.DECIMAL64);
65 System.err.println("Unexpected sqrt of negative: (" +
66 input + ").sqrt() = " + result );
67 failures += 1;
68 } catch (ArithmeticException e) {
69 ; // Expected
87 expected, true, "zeros");
88 }
89
90 return failures;
91 }
92
93 /**
94 * sqrt(10^2N) is 10^N
95 * Both numerical value and representation should be verified
96 */
97 private static int evenPowersOfTenTests() {
98 int failures = 0;
99 MathContext oneDigitExactly = new MathContext(1, RoundingMode.UNNECESSARY);
100
101 for (int scale = -100; scale <= 100; scale++) {
102 BigDecimal testValue = BigDecimal.valueOf(1, 2*scale);
103 BigDecimal expectedNumericalResult = BigDecimal.valueOf(1, scale);
104
105 BigDecimal result;
106
107 failures += equalNumerically(expectedNumericalResult,
108 result = testValue.sqrt(MathContext.DECIMAL64),
109 "Even powers of 10, DECIMAL64");
110
111 // Can round to one digit of precision exactly
112 failures += equalNumerically(expectedNumericalResult,
113 result = testValue.sqrt(oneDigitExactly),
114 "even powers of 10, 1 digit");
115 if (result.precision() > 1) {
116 failures += 1;
117 System.err.println("Excess precision for " + result);
118 }
119
120 // If rounding to more than one digit, do precision / scale checking...
121 }
122
123 return failures;
124 }
125
126 private static int squareRootTwoTests() {
127 int failures = 0;
128
129 // Square root of 2 truncated to 65 digits
130 BigDecimal highPrecisionRoot2 =
131 new BigDecimal("1.41421356237309504880168872420969807856967187537694807317667973799");
132
133 RoundingMode[] modes = {
134 RoundingMode.UP, RoundingMode.DOWN,
135 RoundingMode.CEILING, RoundingMode.FLOOR,
136 RoundingMode.HALF_UP, RoundingMode.HALF_DOWN, RoundingMode.HALF_EVEN
137 };
138
139
140 // For each interesting rounding mode, for precisions 1 to, say
141 // 63 numerically compare TWO.sqrt(mc) to
142 // highPrecisionRoot2.round(mc) and the alternative internal high-precision
143 // implementation of square root.
144 for (RoundingMode mode : modes) {
145 for (int precision = 1; precision < 63; precision++) {
146 MathContext mc = new MathContext(precision, mode);
147 BigDecimal expected = highPrecisionRoot2.round(mc);
148 BigDecimal computed = TWO.sqrt(mc);
149 BigDecimal altComputed = BigSquareRoot.sqrt(TWO, mc);
150
151 failures += equalNumerically(expected, computed, "sqrt(2)");
152 failures += equalNumerically(computed, altComputed, "computed & altComputed");
153 }
154 }
155
156 return failures;
157 }
158
159 private static int lowPrecisionPerfectSquares() {
160 int failures = 0;
161
162 // For 5^2 through 9^2, if the input is rounded to one digit
163 // first before the root is computed, the wrong answer will
164 // result. Verify results and scale for different rounding
165 // modes and precisions.
166 long[][] squaresWithOneDigitRoot = {{ 4, 2},
167 { 9, 3},
168 {25, 5},
169 {36, 6},
170 {49, 7},
171 {64, 8},
172 {81, 9}};
183 MathContext mc = new MathContext(precision, rm);
184 BigDecimal computedRoot = scaledSquare.sqrt(mc);
185 failures += equalNumerically(expected, computedRoot, "simple squares");
186 int computedScale = computedRoot.scale();
187 if (precision >= expectedScale + 1 &&
188 computedScale != expectedScale) {
189 System.err.printf("%s\tprecision=%d\trm=%s%n",
190 computedRoot.toString(), precision, rm);
191 failures++;
192 System.err.printf("\t%s does not have expected scale of %d%n.",
193 computedRoot, expectedScale);
194 }
195 }
196 }
197 }
198 }
199
200 return failures;
201 }
202
203 /**
204 * Test around 3.9999 that the result doesn't not improperly
205 * round-up to a numerical value of 2.
206 */
207 private static int almostFourRoundingDown() {
208 int failures = 0;
209 BigDecimal nearFour = new BigDecimal("3.999999999999999999999999999999");
210
211 // Sqrt root is 1.9999...
212
213 for (int i = 1; i < 64; i++) {
214 MathContext mc = new MathContext(i, RoundingMode.FLOOR);
215 BigDecimal result = nearFour.sqrt(mc);
216 BigDecimal expected = BigSquareRoot.sqrt(nearFour, mc);
217 failures += equalNumerically(expected, result, "near four rounding down");
218 failures += (result.compareTo(TWO) < 0) ? 0 : 1 ;
219 }
220
221 return failures;
222 }
223
224 /**
225 * Test around 4.000...1 that the result doesn't not improperly
226 * round-down to a numerical value of 2.
227 */
228 private static int almostFourRoundingUp() {
229 int failures = 0;
230 BigDecimal nearFour = new BigDecimal("4.000000000000000000000000000001");
231
232 // Sqrt root is 2.0000....<non-zero digits>
233
234 for (int i = 1; i < 64; i++) {
235 MathContext mc = new MathContext(i, RoundingMode.CEILING);
236 BigDecimal result = nearFour.sqrt(mc);
237 BigDecimal expected = BigSquareRoot.sqrt(nearFour, mc);
238 failures += equalNumerically(expected, result, "near four rounding down");
239 failures += (result.compareTo(TWO) > 0) ? 0 : 1 ;
240 }
241
242 return failures;
243 }
244
245 private static int compare(BigDecimal a, BigDecimal b, boolean expected, String prefix) {
246 boolean result = a.equals(b);
247 int failed = (result==expected) ? 0 : 1;
248 if (failed == 1) {
249 System.err.println("Testing " + prefix +
250 "(" + a + ").compareTo(" + b + ") => " + result +
251 "\n\tExpected " + expected);
252 }
253 return failed;
254 }
255
256 private static int equalNumerically(BigDecimal a, BigDecimal b,
257 String prefix) {
258 return compareNumerically(a, b, 0, prefix);
259 }
260
261
262 private static int compareNumerically(BigDecimal a, BigDecimal b,
263 int expected, String prefix) {
264 int result = a.compareTo(b);
265 int failed = (result==expected) ? 0 : 1;
266 if (failed == 1) {
267 System.err.println("Testing " + prefix +
268 "(" + a + ").compareTo(" + b + ") => " + result +
269 "\n\tExpected " + expected);
270 }
271 return failed;
272 }
273
274 /**
275 * Alternative implementation of BigDecimal square root which uses
276 * higher-precision for a simpler set of termination conditions
277 * for the Newton iteration.
278 */
279 private static class BigSquareRoot {
280 /**
281 * The value 0.1, with a scale of 1.
282 */
283 private static final BigDecimal ONE_TENTH = valueOf(1L, 1);
284
285 /**
286 * The value 0.5, with a scale of 1.
287 */
288 private static final BigDecimal ONE_HALF = valueOf(5L, 1);
289
290 private static boolean isPowerOfTen(BigDecimal bd) {
291 return BigInteger.ONE.equals(bd.unscaledValue());
292 }
293
294 public static BigDecimal sqrt(BigDecimal bd, MathContext mc) {
295 int signum = bd.signum();
296 if (signum == 1) {
297 /*
298 * The following code draws on the algorithm presented in
299 * "Properly Rounded Variable Precision Square Root," Hull and
300 * Abrham, ACM Transactions on Mathematical Software, Vol 11,
301 * No. 3, September 1985, Pages 229-237.
302 *
303 * The BigDecimal computational model differs from the one
304 * presented in the paper in several ways: first BigDecimal
305 * numbers aren't necessarily normalized, second many more
306 * rounding modes are supported, including UNNECESSARY, and
307 * exact results can be requested.
308 *
309 * The main steps of the algorithm below are as follows,
310 * first argument reduce the value to the numerical range
311 * [1, 10) using the following relations:
312 *
313 * x = y * 10 ^ exp
314 * sqrt(x) = sqrt(y) * 10^(exp / 2) if exp is even
315 * sqrt(x) = sqrt(y/10) * 10 ^((exp+1)/2) is exp is odd
316 *
317 * Then use Newton's iteration on the reduced value to compute
318 * the numerical digits of the desired result.
319 *
320 * Finally, scale back to the desired exponent range and
321 * perform any adjustment to get the preferred scale in the
322 * representation.
323 */
324
325 // The code below favors relative simplicity over checking
326 // for special cases that could run faster.
327
328 int preferredScale = bd.scale()/2;
329 BigDecimal zeroWithFinalPreferredScale =
330 BigDecimal.valueOf(0L, preferredScale);
331
332 // First phase of numerical normalization, strip trailing
333 // zeros and check for even powers of 10.
334 BigDecimal stripped = bd.stripTrailingZeros();
335 int strippedScale = stripped.scale();
336
337 // Numerically sqrt(10^2N) = 10^N
338 if (isPowerOfTen(stripped) &&
339 strippedScale % 2 == 0) {
340 BigDecimal result = BigDecimal.valueOf(1L, strippedScale/2);
341 if (result.scale() != preferredScale) {
342 // Adjust to requested precision and preferred
343 // scale as appropriate.
344 result = result.add(zeroWithFinalPreferredScale, mc);
345 }
346 return result;
347 }
348
349 // After stripTrailingZeros, the representation is normalized as
350 //
351 // unscaledValue * 10^(-scale)
352 //
353 // where unscaledValue is an integer with the mimimum
354 // precision for the cohort of the numerical value. To
355 // allow binary floating-point hardware to be used to get
356 // approximately a 15 digit approximation to the square
357 // root, it is helpful to instead normalize this so that
358 // the significand portion is to right of the decimal
359 // point by roughly (scale() - precision() +1).
360
361 // Now the precision / scale adjustment
362 int scaleAdjust = 0;
363 int scale = stripped.scale() - stripped.precision() + 1;
364 if (scale % 2 == 0) {
365 scaleAdjust = scale;
366 } else {
367 scaleAdjust = scale - 1;
368 }
369
370 BigDecimal working = stripped.scaleByPowerOfTen(scaleAdjust);
371
372 assert // Verify 0.1 <= working < 10
373 ONE_TENTH.compareTo(working) <= 0 && working.compareTo(TEN) < 0;
374
375 // Use good ole' Math.sqrt to get the initial guess for
376 // the Newton iteration, good to at least 15 decimal
377 // digits. This approach does incur the cost of a
378 //
379 // BigDecimal -> double -> BigDecimal
380 //
381 // conversion cycle, but it avoids the need for several
382 // Newton iterations in BigDecimal arithmetic to get the
383 // working answer to 15 digits of precision. If many fewer
384 // than 15 digits were needed, it might be faster to do
385 // the loop entirely in BigDecimal arithmetic.
386 //
387 // (A double value might have as much many as 17 decimal
388 // digits of precision; it depends on the relative density
389 // of binary and decimal numbers at different regions of
390 // the number line.)
391 //
392 // (It would be possible to check for certain special
393 // cases to avoid doing any Newton iterations. For
394 // example, if the BigDecimal -> double conversion was
395 // known to be exact and the rounding mode had a
396 // low-enough precision, the post-Newton rounding logic
397 // could be applied directly.)
398
399 BigDecimal guess = new BigDecimal(Math.sqrt(working.doubleValue()));
400 int guessPrecision = 15;
401 int originalPrecision = mc.getPrecision();
402 int targetPrecision;
403
404 // If an exact value is requested, it must only need about
405 // half of the input digits to represent since multiplying
406 // an N digit number by itself yield a 2N-1 digit or 2N
407 // digit result.
408 if (originalPrecision == 0) {
409 targetPrecision = stripped.precision()/2 + 1;
410 } else {
411 targetPrecision = originalPrecision;
412 }
413
414 // When setting the precision to use inside the Newton
415 // iteration loop, take care to avoid the case where the
416 // precision of the input exceeds the requested precision
417 // and rounding the input value too soon.
418 BigDecimal approx = guess;
419 int workingPrecision = working.precision();
420 int loopPrecision = Math.max(Math.max(2 * targetPrecision + 2, workingPrecision),
421 34); // Force at least
422 // two Netwon
423 // iterations on the
424 // Math.sqrt result.
425 do {
426 int tmpPrecision = Math.max(Math.max(guessPrecision, targetPrecision + 2),
427 workingPrecision);
428 MathContext mcTmp = new MathContext(loopPrecision, RoundingMode.HALF_EVEN);
429 // approx = 0.5 * (approx + fraction / approx)
430 approx = ONE_HALF.multiply(approx.add(working.divide(approx, mcTmp), mcTmp));
431 guessPrecision *= 2;
432 } while (guessPrecision < loopPrecision);
433
434 BigDecimal result;
435 RoundingMode targetRm = mc.getRoundingMode();
436 if (targetRm == RoundingMode.UNNECESSARY || originalPrecision == 0) {
437 RoundingMode tmpRm =
438 (targetRm == RoundingMode.UNNECESSARY) ? RoundingMode.DOWN : targetRm;
439 MathContext mcTmp = new MathContext(targetPrecision, tmpRm);
440 result = approx.scaleByPowerOfTen(-scaleAdjust/2).round(mcTmp);
441
442 // If result*result != this numerically, the square
443 // root isn't exact
444 if (bd.subtract(result.multiply(result)).compareTo(ZERO) != 0) {
445 throw new ArithmeticException("Computed square root not exact.");
446 }
447 } else {
448 result = approx.scaleByPowerOfTen(-scaleAdjust/2).round(mc);
449 }
450
451 if (result.scale() != preferredScale) {
452 // The preferred scale of an add is
453 // max(addend.scale(), augend.scale()). Therefore, if
454 // the scale of the result is first minimized using
455 // stripTrailingZeros(), adding a zero of the
456 // preferred scale rounding the correct precision will
457 // perform the proper scale vs precision tradeoffs.
458 result = result.stripTrailingZeros().
459 add(zeroWithFinalPreferredScale,
460 new MathContext(originalPrecision, RoundingMode.UNNECESSARY));
461 }
462 return result;
463 } else {
464 switch (signum) {
465 case -1:
466 throw new ArithmeticException("Attempted square root " +
467 "of negative BigDecimal");
468 case 0:
469 return valueOf(0L, bd.scale()/2);
470
471 default:
472 throw new AssertionError("Bad value from signum");
473 }
474 }
475 }
476 }
477 }
|