1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Licensed to the Apache Software Foundation (ASF) under one or more 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * contributor license agreements. See the NOTICE file distributed with 4adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this work for additional information regarding copyright ownership. 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The ASF licenses this file to You under the Apache License, Version 2.0 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (the "License"); you may not use this file except in compliance with 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the License. You may obtain a copy of the License at 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 9adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 10adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 11adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unless required by applicable law or agreed to in writing, software 12adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 13adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * See the License for the specific language governing permissions and 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * limitations under the License. 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.math; 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 21adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Static library that provides all multiplication of {@link BigInteger} methods. 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectclass Multiplication { 24adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Just to denote that this class can't be instantiated. */ 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Multiplication() {} 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // BEGIN android-removed 29adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // /** 30adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // * Break point in digits (number of {@code int} elements) 31adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // * between Karatsuba and Pencil and Paper multiply. 32adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // */ 33adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // static final int whenUseKaratsuba = 63; // an heuristic value 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // END android-removed 35adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 37adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * An array with powers of ten that fit in the type {@code int}. 38adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * ({@code 10^0,10^1,...,10^9}) 39adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 40171dc20afe5071d5cbfad7103903bfa2c1f8d00fElliott Hughes static final int[] tenPows = { 41adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 42adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project }; 437cf86eabacd844cae438db573d45727d7b3374bfJesse Wilson 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 45adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * An array with powers of five that fit in the type {@code int}. 46adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * ({@code 5^0,5^1,...,5^13}) 47adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 48171dc20afe5071d5cbfad7103903bfa2c1f8d00fElliott Hughes static final int[] fivePows = { 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1953125, 9765625, 48828125, 244140625, 1220703125 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project }; 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 54adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * An array with the first powers of ten in {@code BigInteger} version. 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * ({@code 10^0,10^1,...,10^31}) 56adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 57adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static final BigInteger[] bigTenPows = new BigInteger[32]; 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * An array with the first powers of five in {@code BigInteger} version. 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * ({@code 5^0,5^1,...,5^31}) 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static final BigInteger bigFivePows[] = new BigInteger[32]; 647cf86eabacd844cae438db573d45727d7b3374bfJesse Wilson 657cf86eabacd844cae438db573d45727d7b3374bfJesse Wilson 66adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 67adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static { 68adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int i; 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long fivePow = 1L; 707cf86eabacd844cae438db573d45727d7b3374bfJesse Wilson 71adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (i = 0; i <= 18; i++) { 72adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bigFivePows[i] = BigInteger.valueOf(fivePow); 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bigTenPows[i] = BigInteger.valueOf(fivePow << i); 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fivePow *= 5; 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (; i < bigTenPows.length; i++) { 77adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bigFivePows[i] = bigFivePows[i - 1].multiply(bigFivePows[1]); 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bigTenPows[i] = bigTenPows[i - 1].multiply(BigInteger.TEN); 79adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 81adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 82fb0ec0e650bf8be35acb0d47da0311a7c446aa33Elliott Hughes // BEGIN android-note: multiply has been removed in favor of using OpenSSL BIGNUM 83adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // END android-note 84adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 85adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Multiplies a number by a positive integer. 87adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param val an arbitrary {@code BigInteger} 88adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param factor a positive {@code int} number 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code val * factor} 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static BigInteger multiplyByPositiveInt(BigInteger val, int factor) { 92fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bi = val.getBigInt().copy(); 93adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bi.multiplyByPositiveInt(factor); 94adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new BigInteger(bi); 95adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 96adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 97adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 98adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Multiplies a number by a power of ten. 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * This method is used in {@code BigDecimal} class. 100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param val the number to be multiplied 101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param exp a positive {@code long} exponent 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code val * 10<sup>exp</sup>} 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static BigInteger multiplyByTenPow(BigInteger val, long exp) { 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // PRE: exp >= 0 106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return ((exp < tenPows.length) 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ? multiplyByPositiveInt(val, tenPows[(int)exp]) 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project : val.multiply(powerOf10(exp))); 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1107cf86eabacd844cae438db573d45727d7b3374bfJesse Wilson 111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 112adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * It calculates a power of ten, which exponent could be out of 32-bit range. 113adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Note that internally this method will be used in the worst case with 114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * an exponent equals to: {@code Integer.MAX_VALUE - Integer.MIN_VALUE}. 115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param exp the exponent of power of ten, it must be positive. 116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a {@code BigInteger} with value {@code 10<sup>exp</sup>}. 117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static BigInteger powerOf10(long exp) { 119adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // PRE: exp >= 0 120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int intExp = (int)exp; 121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // "SMALL POWERS" 122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (exp < bigTenPows.length) { 123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // The largest power that fit in 'long' type 124adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return bigTenPows[intExp]; 125adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else if (exp <= 50) { 126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // To calculate: 10^exp 127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return BigInteger.TEN.pow(intExp); 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 129df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath 130df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath BigInteger res = null; 131df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath try { 132df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath // "LARGE POWERS" 133df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath if (exp <= Integer.MAX_VALUE) { 134df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath // To calculate: 5^exp * 2^exp 135df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath res = bigFivePows[1].pow(intExp).shiftLeft(intExp); 136df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath } else { 137df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath /* 138df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath * "HUGE POWERS" 139df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath * 140df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath * This branch probably won't be executed since the power of ten is too 141df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath * big. 142df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath */ 143df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath // To calculate: 5^exp 144df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath BigInteger powerOfFive = bigFivePows[1].pow(Integer.MAX_VALUE); 145df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath res = powerOfFive; 146df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath long longExp = exp - Integer.MAX_VALUE; 147df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath 148df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath intExp = (int) (exp % Integer.MAX_VALUE); 149df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath while (longExp > Integer.MAX_VALUE) { 150df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath res = res.multiply(powerOfFive); 151df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath longExp -= Integer.MAX_VALUE; 152df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath } 153df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath res = res.multiply(bigFivePows[1].pow(intExp)); 154df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath // To calculate: 5^exp << exp 155df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath res = res.shiftLeft(Integer.MAX_VALUE); 156df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath longExp = exp - Integer.MAX_VALUE; 157df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath while (longExp > Integer.MAX_VALUE) { 158df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath res = res.shiftLeft(Integer.MAX_VALUE); 159df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath longExp -= Integer.MAX_VALUE; 160df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath } 161df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath res = res.shiftLeft(intExp); 162df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath } 163df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath } catch (OutOfMemoryError error) { 164df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath throw new ArithmeticException(error.getMessage()); 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 166df7e1dbcd0ff712f39b8e80023228ea4eb8531c2Narayan Kamath 167adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return res; 168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1697cf86eabacd844cae438db573d45727d7b3374bfJesse Wilson 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 171adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Multiplies a number by a power of five. 172adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * This method is used in {@code BigDecimal} class. 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param val the number to be multiplied 174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param exp a positive {@code int} exponent 175adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code val * 5<sup>exp</sup>} 176adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static BigInteger multiplyByFivePow(BigInteger val, int exp) { 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // PRE: exp >= 0 179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (exp < fivePows.length) { 180adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return multiplyByPositiveInt(val, fivePows[exp]); 181adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else if (exp < bigFivePows.length) { 182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return val.multiply(bigFivePows[exp]); 183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else {// Large powers of five 184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return val.multiply(bigFivePows[1].pow(exp)); 185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 187adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 188