1 /*
   2  * Copyright 2018-2019 Raffaello Giulietti
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20  * THE SOFTWARE.
  21  */
  22 
  23 package jdk.internal.math;
  24 
  25 import java.math.BigInteger;
  26 
  27 import static java.math.BigInteger.*;
  28 import static jdk.internal.math.DoubleToDecimal.*;
  29 import static jdk.internal.math.MathUtils.*;
  30 
  31 public class MathUtilsChecker extends BasicChecker {
  32 
  33     private static final BigInteger THREE = BigInteger.valueOf(3);
  34 
  35     /*
  36     Let
  37         10^e = beta 2^r
  38     for the unique integer r and real beta meeting
  39         2^125 <= beta < 2^126
  40     Further, let g = g1 2^63 + g0.
  41     Checks that:
  42         2^62 <= g1 < 2^63,
  43         0 <= g0 < 2^63,
  44         g - 1 <= beta < g,    (that is, g = floor(beta) + 1)
  45     The last predicate, after multiplying by 2^r, is equivalent to
  46         (g - 1) 2^r <= 10^e < g 2^r
  47     This is the predicate that will be checked in various forms.
  48      */
  49     private static void testG(int e, long g1, long g0) {
  50         // 2^62 <= g1 < 2^63, 0 <= g0 < 2^63
  51         assertTrue(g1 << 1 < 0 && g1 >= 0 && g0 >= 0, "g");
  52 
  53         BigInteger g = valueOf(g1).shiftLeft(63).or(valueOf(g0));
  54         // double check that 2^125 <= g < 2^126
  55         assertTrue(g.signum() > 0 && g.bitLength() == 126, "g");
  56 
  57         // see javadoc of MathUtils.g1(int)
  58         int r = flog2pow10(e) - 125;
  59 
  60         /*
  61         The predicate
  62             (g - 1) 2^r <= 10^e < g 2^r
  63         is equivalent to
  64             g - 1 <= 10^e 2^(-r) < g
  65         When
  66             e >= 0 & r < 0
  67         all numerical subexpressions are integer-valued. This is the same as
  68             g - 1 = 10^e 2^(-r)
  69          */
  70         if (e >= 0 && r < 0) {
  71             assertTrue(
  72                     g.subtract(ONE).compareTo(TEN.pow(e).shiftLeft(-r)) == 0,
  73                     "g");
  74             return;
  75         }
  76 
  77         /*
  78         The predicate
  79             (g - 1) 2^r <= 10^e < g 2^r
  80         is equivalent to
  81             g 10^(-e) - 10^(-e) <= 2^(-r) < g 10^(-e)
  82         When
  83             e < 0 & r < 0
  84         all numerical subexpressions are integer-valued.
  85          */
  86         if (e < 0 && r < 0) {
  87             BigInteger pow5 = TEN.pow(-e);
  88             BigInteger mhs = ONE.shiftLeft(-r);
  89             BigInteger rhs = g.multiply(pow5);
  90             assertTrue(rhs.subtract(pow5).compareTo(mhs) <= 0 &&
  91                     mhs.compareTo(rhs) < 0, "g");
  92             return;
  93         }
  94 
  95         /*
  96         Finally, when
  97             e >= 0 & r >= 0
  98         the predicate
  99             (g - 1) 2^r <= 10^e < g 2^r
 100         can be used straightforwardly as all numerical subexpressions are
 101         already integer-valued.
 102          */
 103         if (e >= 0) {
 104             BigInteger mhs = TEN.pow(e);
 105             assertTrue(g.subtract(ONE).shiftLeft(r).compareTo(mhs) <= 0 &&
 106                     mhs.compareTo(g.shiftLeft(r)) < 0, "g");
 107             return;
 108         }
 109 
 110         /*
 111         For combinatorial reasons, the only remaining case is
 112             e < 0 & r >= 0
 113         which, however, cannot arise. Indeed, the predicate
 114             (g - 1) 2^r <= 10^e < g 2^r
 115         implies
 116             (g - 1) 10 <= (g - 1) 2^r 10^(-e) <= 1
 117         which cannot hold.
 118          */
 119         assertTrue(false, "g");
 120     }
 121 
 122     /*
 123     Verifies the soundness of the values returned by g1() and g0().
 124      */
 125     private static void testG() {
 126         for (int e = -MAX_K; e <= -MIN_K; ++e) {
 127             testG(e, g1(e), g0(e));
 128         }
 129     }
 130 
 131     /*
 132     Let
 133         k = floor(log10(3/4 2^e))
 134     The method verifies that
 135         k = flog10threeQuartersPow2(e),    |e| <= 2_000
 136     This range amply covers all binary exponents of doubles and floats.
 137 
 138     The first equation above is equivalent to
 139         10^k <= 3 2^(e-2) < 10^(k+1)
 140     Equality never holds. Henceforth, the predicate to check is
 141         10^k < 3 2^(e-2) < 10^(k+1)
 142     This will be transformed in various ways for checking purposes.
 143 
 144     For integer n > 0, let further
 145         b = len2(n)
 146     denote its length in bits. This means exactly the same as
 147         2^(b-1) <= n < 2^b
 148      */
 149     private static void testFlog10threeQuartersPow2() {
 150         /*
 151         First check the case e = 1
 152          */
 153         assertTrue(flog10threeQuartersPow2(1) == 0,
 154                 "flog10threeQuartersPow2");
 155 
 156         /*
 157         Now check the range -2_000 <= e <= 0.
 158         By rewriting, the predicate to check is equivalent to
 159             3 10^(-k-1) < 2^(2-e) < 3 10^(-k)
 160         As e <= 0, it follows that 2^(2-e) >= 4 and the right inequality
 161         implies k < 0, so the powers of 10 are integers.
 162 
 163         The left inequality is equivalent to
 164             len2(3 10^(-k-1)) <= 2 - e
 165         and the right inequality to
 166             2 - e < len2(3 10^(-k))
 167         The original predicate is therefore equivalent to
 168             len2(3 10^(-k-1)) <= 2 - e < len2(3 10^(-k))
 169 
 170         Starting with e = 0 and decrementing until the lower bound, the code
 171         keeps track of the two powers of 10 to avoid recomputing them.
 172         This is easy because at each iteration k changes at most by 1. A simple
 173         multiplication by 10 computes the next power of 10 when needed.
 174          */
 175         int e = 0;
 176         int k0 = flog10threeQuartersPow2(e);
 177         assertTrue(k0 < 0, "flog10threeQuartersPow2");
 178         BigInteger l = THREE.multiply(TEN.pow(-k0 - 1));
 179         BigInteger u = l.multiply(TEN);
 180         for (;;) {
 181             assertTrue(l.bitLength() <= 2 - e && 2 - e < u.bitLength(),
 182                     "flog10threeQuartersPow2");
 183             if (e == -2_000) {
 184                 break;
 185             }
 186             --e;
 187             int kp = flog10threeQuartersPow2(e);
 188             assertTrue(kp <= k0, "flog10threeQuartersPow2");
 189             if (kp < k0) {
 190                 // k changes at most by 1 at each iteration, hence:
 191                 assertTrue(k0 - kp == 1, "flog10threeQuartersPow2");
 192                 k0 = kp;
 193                 l = u;
 194                 u = u.multiply(TEN);
 195             }
 196         }
 197 
 198         /*
 199         Finally, check the range 2 <= e <= 2_000.
 200         In predicate
 201             10^k < 3 2^(e-2) < 10^(k+1)
 202         the right inequality shows that k >= 0 as soon as e >= 2.
 203         It is equivalent to
 204             10^k / 3 < 2^(e-2) < 10^(k+1) / 3
 205         Both the powers of 10 and the powers of 2 are integer-valued.
 206         The left inequality is therefore equivalent to
 207             floor(10^k / 3) < 2^(e-2)
 208         and thus to
 209             len2(floor(10^k / 3)) <= e - 2
 210         while the right inequality is equivalent to
 211             2^(e-2) <= floor(10^(k+1) / 3)
 212         and hence to
 213             e - 2 < len2(floor(10^(k+1) / 3))
 214         These are summarized as
 215             len2(floor(10^k / 3)) <= e - 2 < len2(floor(10^(k+1) / 3))
 216          */
 217         e = 2;
 218         k0 = flog10threeQuartersPow2(e);
 219         assertTrue(k0 >= 0, "flog10threeQuartersPow2");
 220         BigInteger l10 = TEN.pow(k0);
 221         BigInteger u10 = l10.multiply(TEN);
 222         l = l10.divide(THREE);
 223         u = u10.divide(THREE);
 224         for (;;) {
 225             assertTrue(l.bitLength() <= e - 2 && e - 2 < u.bitLength(),
 226                     "flog10threeQuartersPow2");
 227             if (e == 2_000) {
 228                 break;
 229             }
 230             ++e;
 231             int kp = flog10threeQuartersPow2(e);
 232             assertTrue(kp >= k0, "flog10threeQuartersPow2");
 233             if (kp > k0) {
 234                 // k changes at most by 1 at each iteration, hence:
 235                 assertTrue(kp - k0 == 1, "flog10threeQuartersPow2");
 236                 k0 = kp;
 237                 u10 = u10.multiply(TEN);
 238                 l = u;
 239                 u = u10.divide(THREE);
 240             }
 241         }
 242     }
 243 
 244     /*
 245     Let
 246         k = floor(log10(2^e))
 247     The method verifies that
 248         k = flog10pow2(e),    |e| <= 2_000
 249     This range amply covers all binary exponents of doubles and floats.
 250 
 251     The first equation above is equivalent to
 252         10^k <= 2^e < 10^(k+1)
 253     Equality holds iff e = 0, implying k = 0.
 254     Henceforth, the predicates to check are equivalent to
 255         k = 0,    if e = 0
 256         10^k < 2^e < 10^(k+1),    otherwise
 257     The latter will be transformed in various ways for checking purposes.
 258 
 259     For integer n > 0, let further
 260         b = len2(n)
 261     denote its length in bits. This means exactly the same as
 262         2^(b-1) <= n < 2^b
 263      */
 264     private static void testFlog10pow2() {
 265         /*
 266         First check the case e = 0
 267          */
 268         assertTrue(flog10pow2(0) == 0, "flog10pow2");
 269 
 270         /*
 271         Now check the range -2_000 <= e < 0.
 272         By inverting all quantities, the predicate to check is equivalent to
 273             10^(-k-1) < 2^(-e) < 10^(-k)
 274         As e < 0, it follows that 2^(-e) >= 2 and the right inequality
 275         implies k < 0.
 276         The left inequality means exactly the same as
 277             len2(10^(-k-1)) <= -e
 278         Similarly, the right inequality is equivalent to
 279             -e < len2(10^(-k))
 280         The original predicate is therefore equivalent to
 281             len2(10^(-k-1)) <= -e < len2(10^(-k))
 282         The powers of 10 are integer-valued because k < 0.
 283 
 284         Starting with e = -1 and decrementing towards the lower bound, the code
 285         keeps track of the two powers of 10 so as to avoid recomputing them.
 286         This is easy because at each iteration k changes at most by 1. A simple
 287         multiplication by 10 computes the next power of 10 when needed.
 288          */
 289         int e = -1;
 290         int k = flog10pow2(e);
 291         assertTrue(k < 0, "flog10pow2");
 292         BigInteger l = TEN.pow(-k - 1);
 293         BigInteger u = l.multiply(TEN);
 294         for (;;) {
 295             assertTrue(l.bitLength() <= -e && -e < u.bitLength(),
 296                     "flog10pow2");
 297             if (e == -2_000) {
 298                 break;
 299             }
 300             --e;
 301             int kp = flog10pow2(e);
 302             assertTrue(kp <= k, "flog10pow2");
 303             if (kp < k) {
 304                 // k changes at most by 1 at each iteration, hence:
 305                 assertTrue(k - kp == 1, "flog10pow2");
 306                 k = kp;
 307                 l = u;
 308                 u = u.multiply(TEN);
 309             }
 310         }
 311 
 312         /*
 313         Finally, in a similar vein, check the range 0 <= e <= 2_000.
 314         In predicate
 315             10^k < 2^e < 10^(k+1)
 316         the right inequality shows that k >= 0.
 317         The left inequality means the same as
 318             len2(10^k) <= e
 319         and the right inequality holds iff
 320             e < len2(10^(k+1))
 321         The original predicate is thus equivalent to
 322             len2(10^k) <= e < len2(10^(k+1))
 323         As k >= 0, the powers of 10 are integer-valued.
 324          */
 325         e = 1;
 326         k = flog10pow2(e);
 327         assertTrue(k >= 0, "flog10pow2");
 328         l = TEN.pow(k);
 329         u = l.multiply(TEN);
 330         for (;;) {
 331             assertTrue(l.bitLength() <= e && e < u.bitLength(),
 332                     "flog10pow2");
 333             if (e == 2_000) {
 334                 break;
 335             }
 336             ++e;
 337             int kp = flog10pow2(e);
 338             assertTrue(kp >= k, "flog10pow2");
 339             if (kp > k) {
 340                 // k changes at most by 1 at each iteration, hence:
 341                 assertTrue(kp - k == 1, "flog10pow2");
 342                 k = kp;
 343                 l = u;
 344                 u = u.multiply(TEN);
 345             }
 346         }
 347     }
 348 
 349     /*
 350     Let
 351         k = floor(log2(10^e))
 352     The method verifies that
 353         k = flog2pow10(e),    |e| <= 500
 354     This range amply covers all decimal exponents of doubles and floats.
 355 
 356     The first equation above is equivalent to
 357         2^k <= 10^e < 2^(k+1)
 358     Equality holds iff e = 0, implying k = 0.
 359     Henceforth, the equivalent predicates to check are
 360         k = 0,    if e = 0
 361         2^k < 10^e < 2^(k+1),    otherwise
 362     The latter will be transformed in various ways for checking purposes.
 363 
 364     For integer n > 0, let further
 365         b = len2(n)
 366     denote its length in bits. This means exactly the same as
 367         2^(b-1) <= n < 2^b
 368     */
 369     private static void testFlog2pow10() {
 370         /*
 371         First check the case e = 0
 372          */
 373         assertTrue(flog2pow10(0) == 0, "flog2pow10");
 374 
 375         /*
 376         Now check the range -500 <= e < 0.
 377         By inverting all quantities, the predicate to check is equivalent to
 378             2^(-k-1) < 10^(-e) < 2^(-k)
 379         As e < 0, this leads to 10^(-e) >= 10 and the right inequality implies
 380         k <= -4.
 381         The above means the same as
 382             len2(10^(-e)) = -k
 383         The powers of 10 are integer values since e < 0.
 384          */
 385         int e = -1;
 386         int k0 = flog2pow10(e);
 387         assertTrue(k0 <= -4, "flog2pow10");
 388         BigInteger l = TEN;
 389         for (;;) {
 390             assertTrue(l.bitLength() == -k0, "flog2pow10");
 391             if (e == -500) {
 392                 break;
 393             }
 394             --e;
 395             k0 = flog2pow10(e);
 396             l = l.multiply(TEN);
 397         }
 398 
 399         /*
 400         Finally check the range 0 < e <= 500.
 401         From the predicate
 402             2^k < 10^e < 2^(k+1)
 403         as e > 0, it follows that 10^e >= 10 and the right inequality implies
 404         k >= 3.
 405         The above means the same as
 406             len2(10^e) = k + 1
 407         The powers of 10 are all integer valued, as e > 0.
 408          */
 409         e = 1;
 410         k0 = flog2pow10(e);
 411         assertTrue(k0 >= 3, "flog2pow10");
 412         l = TEN;
 413         for (;;) {
 414             assertTrue(l.bitLength() == k0 + 1, "flog2pow10");
 415             if (e == 500) {
 416                 break;
 417             }
 418             ++e;
 419             k0 = flog2pow10(e);
 420             l = l.multiply(TEN);
 421         }
 422     }
 423 
 424     private static void testConstants() {
 425         int qMin = (-1 << Double.SIZE - P - 1) - P + 3;
 426         assertTrue(flog10pow2(qMin) == MIN_K, "MIN_K");
 427         int qMax = (1 << Double.SIZE - P - 1) - P;
 428         assertTrue(flog10pow2(qMax) == MAX_K, "MAX_K");
 429     }
 430 
 431     private static void testPow10() {
 432         int e = 0;
 433         long pow = 1;
 434         for (; e <= H; e += 1, pow *= 10) {
 435             assertTrue(pow == pow10(e), "pow10");
 436         }
 437     }
 438 
 439     public static void test() {
 440         testFlog10pow2();
 441         testFlog10threeQuartersPow2();
 442         testFlog2pow10();
 443         testPow10();
 444         testConstants();
 445         testG();
 446     }
 447 
 448 }