java - example - parse long to biginteger
Cómo manejar números muy grandes en Java sin usar java.math.BigInteger (7)
¿Cómo voy a hacer aritmética, + - / *%!, Con enteros arbitrariamente grandes sin usar java.math.BigInteger ?
Por ejemplo, el factorial de 90 devuelve 0 en Java. Me gustaría poder resolver eso.
Creo que un programador debería haber implementado su propia biblioteca bignum una vez, así que bienvenido aquí.
(Por supuesto, más tarde obtendrá que BigInteger es mejor y use esto, pero es una experiencia de aprendizaje valiosa).
(Puedes seguir el código fuente de esta vida del curso en github . Además, rehice esto (un poco pulido) en una serie de blog de 14 partes .)
Creando una clase simple de números grandes en Java
¿Entonces, qué necesitamos?
Primero, una representación del número,
basado en los tipos de datos que Java nos da.
Como cree que la conversión decimal es la parte más complicada, permanezcamos en modo decimal. Para mayor eficiencia, almacenaremos dígitos decimales no reales, pero trabajaremos en la base 1 000 000 000 = 10^9 < 2^30 . Esto encaja en Java int (hasta 2^31 o 2^32 ), y el producto de dos de esos dígitos se adapta muy bien en Java long .
final static int BASE = 1000000000;
final static int BASE_DECIMAL_DIGITS = 9;
Luego la matriz de dígitos:
private int[] digits;
¿Almacenamos los dígitos en little- o big endian, es decir, las partes más grandes primero o último? Realmente no importa, así que decidimos en big-endian ya que así es como los humanos quieren leerlo. (Por ahora, nos concentramos en valores no negativos, luego agregaremos un bit de signo para números negativos).
Para propósitos de prueba, agregamos un constructor que permite la inicialización desde tal int [].
/**
* creates a DecimalBigInt based on an array of digits.
* @param digits a list of digits, each between 0 (inclusive)
* and {@link BASE} (exclusive).
* @throws IllegalArgumentException if any digit is out of range.
*/
public DecimalBigInt(int... digits) {
for(int digit : digits) {
if(digit < 0 || BASE <= digit) {
throw new IllegalArgumentException("digit " + digit +
" out of range!");
}
}
this.digits = digits.clone();
}
Como una ventaja adicional, este constructor también se puede usar para una sola int (si es más pequeña que BASE ), e incluso para no int (que interpretaremos como 0). Entonces, ahora podemos hacer esto:
DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345);
System.out.println(d);
Esto nos da de.fencing_game.paul.examples.DecimalBigInt@6af62373 , no tan útil. Entonces, agregamos un método toString() :
/**
* A simple string view for debugging purposes.
* (Will be replaced later with a real decimal conversion.)
*/
public String toString() {
return "Big" + Arrays.toString(digits);
}
La salida ahora es Big[7, 5, 2, 12345] , lo cual es más útil para las pruebas, ¿no es así?
En segundo lugar, la conversión del formato decimal.
Tenemos suerte aquí: nuestra base (10 ^ 9) es una potencia de la base de la que queremos convertir (10). Por lo tanto, siempre tenemos el mismo número (9) de dígitos decimales que representan un dígito de "nuestro formato". (Por supuesto, al principio puede haber algunos dígitos menos.) En el siguiente código, decimal es una cadena de dígitos decimales.
int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;
Esta extraña fórmula es una forma Java int de escribir bigLen = ceil(decLen/BASE_DECIMAL_DIGITS) . (Espero que sea correcto, luego lo probaremos).
int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;
Esta es la longitud del primer bloque de dígitos decimales, debe estar entre 1 y 9 (inclusive).
Creamos nuestra matriz:
int[] digits = new int[bigLen];
Looping a través de los dígitos que se crearán:
for(int i = 0; i < bigLen ; i++) {
Cada uno de nuestros dígitos está representado por un bloque de dígitos en el número original:
String block =
decimal.substring(Math.max(firstSome + (i-1)*BASE_DECIMAL_DIGITS, 0),
firstSome + i *BASE_DECIMAL_DIGITS);
( Math.max se necesita el Math.max para el primer bloque más corto.) Ahora usamos la función de análisis Integer usual y ponemos el resultado en la matriz:
digits[i] = Integer.parseInt(block);
}
Desde la matriz ahora creada, creamos nuestro objeto DecimalBigInt:
return new DecimalBigInt(digits);
Vamos a ver si esto funciona:
DecimalBigInt d2 = DecimalBigInt.valueOf("12345678901234567890");
System.out.println(d2);
Salida:
Big[12, 345678901, 234567890]
Se ve bien :-) Deberíamos probarlo con algunos otros números (de diferente duración) también.
La siguiente parte será el formato decimal, esto debería ser aún más fácil.
En tercer lugar, la conversión a formato decimal.
Necesitamos dar salida a nuestros dígitos individuales como 9 dígitos decimales cada uno. Para esto podemos usar la clase Formatter , que admite cadenas de formato similar a printf.
Una variante simple sería esta:
public String toDecimalString() {
Formatter f = new Formatter();
for(int digit : digits) {
f.format("%09d", digit);
}
return f.toString();
}
Esto devuelve 000000007000000005000000002000012345 y 000000012345678901234567890 para nuestros dos números. Esto funciona para un viaje de ida y vuelta (es decir, alimentarlo con el método valueOf da un objeto equivalente), pero los ceros iniciales no son realmente agradables de observar (y podrían crear confusión con los números octales). Así que tenemos que separar nuestro hermoso bucle for-each y usar una cadena de formato diferente para el primer y el siguiente dígito.
public String toDecimalString() {
Formatter f = new Formatter();
f.format("%d", digits[0]);
for(int i = 1 ; i < digits.length; i++) {
f.format("%09d", digits[i]);
}
return f.toString();
}
Adición.
Comencemos con la suma, ya que es simple (y podemos usar partes de ella para la multiplicación posterior).
/**
* calculates the sum of this and that.
*/
public DecimalBigInt plus(DecimalBigInt that) {
...
}
Quiero nombres de métodos que pueda leer como leería la fórmula, así plus , minus , times lugar de add , subtract , multiply .
Entonces, ¿cómo funciona la adición? Funciona igual que lo aprendimos en la escuela para números decimales superiores a 9: agregue los dígitos correspondientes, y si para algunos de ellos el resultado es más grande que 10 (o BASE en nuestro caso), lleve uno al siguiente dígito. Esto puede hacer que el número resultante tenga un dígito más que los originales.
Primero vemos el caso simple de que ambos números tienen la misma cantidad de dígitos. Entonces se ve así:
int[] result = new int[this.digits.length];
int carry = 0;
for(int i = this.digits.length-1; i > 0; i--) {
int digSum = carry + this.digits[i] + that.digits[i];
result[i] = digSum % BASE;
carry = digSum / BASE;
}
if(carry > 0) {
int[] temp = new int[result.length + 1];
System.arraycopy(result, 0, temp, 1, result.length);
temp[0] = carry;
result = temp;
}
return new DecimalBigInt(result);
(Vamos de derecha a izquierda, así que podemos llevar cualquier desbordamiento al siguiente dígito. Esto sería un poco más bonito si hubiéramos decidido usar el formato Little Endian).
Si ambos números no tienen la misma cantidad de dígitos, se vuelve un poco más complicado.
Para que sea lo más simple posible, lo dividimos en varios métodos:
Este método agrega un dígito a un elemento de la matriz (que puede contener un valor distinto de cero) y almacena el resultado en la matriz. Si hubo desbordamiento, lo llevamos al siguiente dígito (que tiene un índice menos, no uno más) por medio de una llamada recursiva. De esta manera nos aseguramos de que nuestros dígitos permanezcan siempre en el rango válido.
/**
* adds one digit from the addend to the corresponding digit
* of the result.
* If there is carry, it is recursively added to the next digit
* of the result.
*/
private void addDigit(int[] result, int resultIndex,
int addendDigit)
{
int sum = result[resultIndex] + addendDigit;
result[resultIndex] = sum % BASE;
int carry = sum / BASE;
if(carry > 0) {
addDigit(result, resultIndex - 1, carry);
}
}
El siguiente hace lo mismo para una matriz completa de dígitos para agregar:
/**
* adds all the digits from the addend array to the result array.
*/
private void addDigits(int[] result, int resultIndex,
int... addend)
{
addendIndex = addend.length - 1;
while(addendIndex >= 0) {
addDigit(result, resultIndex,
addend[addendIndex]);
addendIndex--;
resultIndex--;
}
}
Ahora podemos implementar nuestro método plus :
/**
* calculates the sum of this and that.
*/
public DecimalBigInt plus(DecimalBigInt that) {
int[] result = new int[Math.max(this.digits.length,
that.digits.length)+ 1];
addDigits(result, result.length-1, this.digits);
addDigits(result, result.length-1, that.digits);
// cut of leading zero, if any
if(result[0] == 0) {
result = Arrays.copyOfRange(result, 1, result.length);
}
return new DecimalBigInt(result);
}
Podríamos mejorar un poco aquí si miramos antes si el desbordamiento es posible y solo entonces creamos la matriz más grande de lo necesario.
Ah, una prueba: d2.plus(d2) le da a Big[24, 691357802, 469135780] , que se ve bien.
Multiplicación.
Recordemos de regreso a la escuela, ¿cómo multiplicamos números más grandes en papel?
123 * 123
----------
369 <== 123 * 3
246 <== 123 * 2
123 <== 123 * 1
--------
15129
Entonces, tenemos que multiplicar cada dígito [i] del primer número con cada dígito [j] del segundo número, y agregar el producto en el dígito [i + j] del resultado (y prestar atención al acarreo). Por supuesto, aquí los índices se cuentan desde la derecha, no desde la izquierda. (Ahora realmente desearía haber usado números little-endian.)
Como el producto de dos de nuestros dígitos puede salir del rango de int , usamos long para la multiplicación.
/**
* multiplies two digits and adds the product to the result array
* at the right digit-position.
*/
private void multiplyDigit(int[] result, int resultIndex,
int firstFactor, int secondFactor) {
long prod = (long)firstFactor * (long)secondFactor;
int prodDigit = (int)(prod % BASE);
int carry = (int)(prod / BASE);
addDigits(result, resultIndex, carry, prodDigit);
}
Ahora podemos ver por qué he declarado mi método addDigits para tomar un parámetro resultIndex . (Y acabo de cambiar el último argumento a un parámetro varargs, para poder escribir esto aquí mejor).
Entonces, aquí el método de multiplicación cruzada:
private void multiplyDigits(int[] result, int resultIndex,
int[] leftFactor, int[] rightFactor) {
for(int i = 0; i < leftFactor.length; i++) {
for(int j = 0; j < rightFactor.length; j++) {
multiplyDigit(result, resultIndex - (i + j),
leftFactor[leftFactor.length-i-1],
rightFactor[rightFactor.length-j-1]);
}
}
}
Espero tener los cálculos del índice correctos. Con una representación little-endian, habría sido multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j]) - bastante claro, ¿no?
Nuestro método de times ahora solo tiene que asignar la matriz de resultados, invocar multiplyDigits y ajustar el resultado.
/**
* returns the product {@code this × that}.
*/
public DecimalBigInt times(DecimalBigInt that) {
int[] result = new int[this.digits.length + that.digits.length];
multiplyDigits(result, result.length-1,
this.digits, that.digits);
// cut off leading zero, if any
if(result[0] == 0) {
result = Arrays.copyOfRange(result, 1, result.length);
}
return new DecimalBigInt(result);
}
Para las pruebas, d2.times(d2) da Big[152, 415787532, 388367501, 905199875, 19052100] , que es lo mismo que calcula mi Emacs calc aquí.
Comparación
Queremos poder comparar dos de nuestros objetos. Entonces, implementamos Comparable<DecimalBigInt> y su método compareTo.
public int compareTo(DecimalBigInt that) {
¿Cómo saber si uno de nuestros números es más grande que otro? Primero, comparamos la longitud de las matrices. Como nos cuidamos de no inducir ninguno de los ceros a la izquierda (¿verdad?), La matriz más larga debería tener el número más grande.
if(this.digits.length < that.digits.length) {
return -1;
}
if (that.digits.length < this.digits.length) {
return 1;
}
Si la longitud es la misma, podemos comparar elementos. Como utilizamos big endian (es decir, el gran extremo es lo primero ), comenzamos por el principio.
for(int i = 0; i < this.digits.length; i++) {
if(this.digits[i] < that.digits[i]) {
return -1;
}
if(that.digits[i] < this.digits[i]) {
return 1;
}
}
Si todo fue lo mismo, obviamente nuestros números son idénticos, y podemos devolver 0 .
return 0;
}
equals + hashCode()
Toda buena clase inmutable debería implementar equals() y hashCode() de una manera adecuada (y compatible).
Para nuestro hashCode() , simplemente hashCode() los dígitos, multiplicándolos con un primo pequeño para asegurarnos de que la conmutación de dígitos no dé como resultado el mismo código hash:
/**
* calculates a hashCode for this object.
*/
public int hashCode() {
int hash = 0;
for(int digit : digits) {
hash = hash * 13 + digit;
}
return hash;
}
En el método equals() simplemente podemos delegar en el método compareTo, en lugar de implementar el mismo algoritmo de nuevo:
/**
* compares this object with another object for equality.
* A DecimalBigInt is equal to another object only if this other
* object is also a DecimalBigInt and both represent the same
* natural number.
*/
public boolean equals(Object o) {
return o instanceof DecimalBigInt &&
this.compareTo((DecimalBigInt)o) == 0;
}
Entonces, suficiente para hoy. La resta (y tal vez los números negativos) y la división son más complicados, así que los estoy omitiendo por ahora. Para calcular el factorial de 90 esto debería ser suficiente.
Cálculo de grandes factoriales:
Aquí la función factorial:
/**
* calculates the factorial of an int number.
* This uses a simple iterative loop.
*/
public static DecimalBigInt factorial(int n) {
DecimalBigInt fac = new DecimalBigInt(1);
for(int i = 2; i <= n; i++) {
fac = fac.times(new DecimalBigInt(i));
}
return fac;
}
Esto nos da
fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000
Conversión de representaciones de raíz arbitraria
Impulsado por la siguiente pregunta de frodosamoa, escribí mi respuesta sobre cómo convertir sistemas de números arbitrarios (posicionales) en uno en el que podemos (o queremos) calcular . (En el ejemplo de allí, convertí de trinario a decimal, mientras que la pregunta era de decimal a binario).
Aquí queremos convertir desde un sistema numérico arbitrario (de acuerdo, con radix entre 2 y 36, así que podemos usar Character.digit() para convertir dígitos únicos en ints) en nuestro sistema con radix BASE (= 1.000.000.000, pero esto no es realmente importante aquí).
Básicamente, utilizamos el esquema de Horner para calcular el valor del polinomio con los dígitos como coeficientes en el punto dado por el radix.
sum[i=0..n] digit[i] * radix^i
se puede calcular con este ciclo:
value = 0;
for i = n .. 0
value = value * radix + digit[i]
return value
Dado que nuestras cadenas de entrada son big-endian, no tenemos que contar hacia atrás, pero podemos usar un simple loop forzado. (Parece más feo en Java, ya que no tenemos sobrecarga del operador, y no hay autoboxing de int a nuestro tipo DecimalBigInt).
public static DecimalBigInt valueOf(String text, int radix) {
DecimalBigInt bigRadix = new DecimalBigInt(radix);
DecimalBigInt value = new DecimalBigInt(); // 0
for(char digit : text.toCharArray()) {
DecimalBigInt bigDigit =
new DecimalBigInt(Character.digit(digit, radix));
value = value.times(bigRadix).plus(bigDigit);
}
return value;
}
En mi implementación real , agregué algunas comprobaciones de errores (y lanzamiento de excepciones) para asegurarme de que realmente tenemos un número válido y, por supuesto, un comentario de documentación.
La conversión a un sistema posicional arbitrario es más complicado, ya que involucra el resto y la división (por la base arbitraria), que no hemos implementado todavía, por lo que no es por ahora. Se hará cuando tenga una buena idea sobre cómo hacer la división. (Necesitamos solo división por números pequeños (de un dígito) aquí, que puede ser más fácil que una división general.)
División por pequeños números
En la escuela, aprendí la división larga . Aquí hay un ejemplo para un divisor pequeño (de un dígito), en la notación que usamos aquí en Alemania (con anotaciones sobre los cálculos de fondo, que normalmente no escribiríamos), en sistema decimal:
12345 : 6 = 02057 1 / 6 = 0
-0┊┊┊┊ 0 * 6 = 0
──┊┊┊┊
12┊┊┊ 12 / 6 = 2
-12┊┊┊ 2 * 6 = 12
──┊┊┊
03┊┊ 3 / 6 = 0
- 0┊┊ 0 * 6 = 0
──┊┊
34┊ 34 / 6 = 5
-30┊ 5 * 6 = 30
──┊
45 45 / 6 = 7
-42 7 * 6 = 42
──
3 ==> quotient 2057, remainder 3.
Por supuesto, no necesitamos calcular estos productos (0, 12, 0, 30, 42) y restarlos si tenemos una operación de residuo nativo. Entonces se ve así (por supuesto, aquí no necesitaríamos escribir las operaciones):
12345 : 6 = 02057 1 / 6 = 0, 1 % 6 = 1
12┊┊┊ 12 / 6 = 2, 12 % 6 = 0
03┊┊ 3 / 6 = 0, 3 % 6 = 3
34┊ 34 / 6 = 5, 34 % 6 = 4
45 45 / 6 = 7, 45 % 6 = 3
3
==> quotient 2057, remainder 3.
Esto ya se parece bastante a una división corta , si la escribimos en otro formato.
Podemos observar (y probar) lo siguiente:
Si tenemos un número de dos dígitos x con el primer dígito más pequeño que nuestro divisor d, entonces x / d es un número de un dígito, y x % d también es un número de un dígito, más pequeño que d. Esto, junto con la inducción, muestra que solo necesitamos dividir (con el resto) números de dos dígitos por nuestro divisor.
Volviendo a nuestros grandes números con radix BASE: todos los números de dos dígitos son representables como Java long , y allí tenemos native / y % .
/**
* does one step in the short division algorithm, i.e. divides
* a two-digit number by a one-digit one.
*
* @param result the array to put the quotient digit in.
* @param resultIndex the index in the result array where
* the quotient digit should be put.
* @param divident the last digit of the divident.
* @param lastRemainder the first digit of the divident (being the
* remainder of the operation one digit to the left).
* This must be < divisor.
* @param divisor the divisor.
* @returns the remainder of the division operation.
*/
private int divideDigit(int[] result, int resultIndex,
int divident, int lastRemainder,
int divisor) {
assert divisor < BASE;
assert lastRemainder < divisor;
long ent = divident + (long)BASE * lastRemainder;
long quot = ent / divisor;
long rem = ent % divisor;
assert quot < BASE;
assert rem < divisor;
result[resultIndex] = (int)quot;
return (int)rem;
}
Ahora llamaremos a este método en un bucle, siempre alimentando el resultado de la llamada anterior como lastRemainder .
/**
* The short division algorithm, like described in
* <a href="http://en.wikipedia.org/wiki/Short_division">Wikipedia''s
* article <em>Short division</em></a>.
* @param result an array where we should put the quotient digits in.
* @param resultIndex the index in the array where the highest order digit
* should be put, the next digits will follow.
* @param divident the array with the divident''s digits. (These will only
* be read, not written to.)
* @param dividentIndex the index in the divident array where we should
* start dividing. We will continue until the end of the array.
* @param divisor the divisor. This must be a number smaller than
* {@link #BASE}.
* @return the remainder, which will be a number smaller than
* {@code divisor}.
*/
private int divideDigits(int[] result, int resultIndex,
int[] divident, int dividentIndex,
int divisor) {
int remainder = 0;
for(; dividentIndex < divident.length; dividentIndex++, resultIndex++) {
remainder = divideDigit(result, resultIndex,
divident[dividentIndex],
remainder, divisor);
}
return remainder;
}
Este método aún devuelve un int, el resto.
Ahora queremos que un método público devuelva un DecimalBigInt, por lo que creamos uno. Tiene la tarea de verificar los argumentos, crear una matriz para el método de trabajo, descartar el resto y crear un DecimalBigInt a partir del resultado. (El constructor elimina un cero que puede estar allí).
/**
* Divides this number by a small number.
* @param divisor an integer with {@code 0 < divisor < BASE}.
* @return the integer part of the quotient, ignoring the remainder.
* @throws IllegalArgumentException if the divisor is <= 0 or >= BASE.
*/
public DecimalBigInt divideBy(int divisor)
{
if(divisor <= 0 || BASE <= divisor) {
throw new IllegalArgumentException("divisor " + divisor +
" out of range!");
}
int[] result = new int[digits.length];
divideDigits(result, 0,
digits, 0,
divisor);
return new DecimalBigInt(result);
}
También tenemos un método similar, que devuelve el resto en su lugar:
/**
* Divides this number by a small number, returning the remainder.
* @param divisor an integer with {@code 0 < divisor < BASE}.
* @return the remainder from the division {@code this / divisor}.
* @throws IllegalArgumentException if the divisor is <= 0 or >= BASE.
*/
public int modulo(int divisor) {
if(divisor <= 0 || BASE <= divisor) {
throw new IllegalArgumentException("divisor " + divisor +
" out of range!");
}
int[] result = new int[digits.length];
return divideDigits(result, 0,
digits, 0,
divisor);
}
Estos métodos se pueden invocar así:
DecimalBigInt d3_by_100 = d3.divideBy(100);
System.out.println("d3/100 = " + d3_by_100);
System.out.println("d3%100 = " + d3.modulo(100));
Conversión a raíz arbitraria
Ahora tenemos lo básico para convertir a una base arbitraria. Por supuesto, no es realmente arbitrario, solo se permiten radix más pequeñas que BASE , pero este no debería ser un problema demasiado grande.
Como ya se respondió en otra respuesta sobre la conversión de números, tenemos que hacer "división, resto, multiplicar, agregar. La parte de" multiplicar-agregar "es, de hecho, solo armar los dígitos individuales, por lo que podemos reemplazarlo por una simple matriz- acceso.
Como siempre necesitamos tanto el cociente como el resto, no usaremos los métodos públicos modulo y divideBy , sino que repetidamente llamaremos al método divideDigits .
/**
* converts this number to an arbitrary radix.
* @param radix the target radix, {@code 1 < radix < BASE}.
* @return the digits of this number in the base-radix system,
* in big-endian order.
*/
public int[] convertTo(int radix)
{
if(radix <= 1 || BASE <= radix) {
throw new IllegalArgumentException("radix " + radix +
" out of range!");
}
Primero, un manejo de caso especial para 0.
// zero has no digits.
if(digits.length == 0)
return new int[0];
Luego, creamos una matriz para los dígitos de resultado (el tiempo suficiente) y algunas otras variables.
// raw estimation how many output digits we will need.
// This is just enough in cases like BASE-1, and up to
// 30 digits (for base 2) too much for something like (1,0,0).
int len = (int) (Math.log(BASE) / Math.log(radix) * digits.length)+1;
int[] rDigits = new int[len];
int rIndex = len-1;
int[] current = digits;
int quotLen = digits.length;
quotLen es la cantidad de dígitos (excluyendo los ceros a la izquierda) en el último cociente. Si esto es 0, hemos terminado.
while(quotLen > 0) {
Una nueva matriz para el próximo cociente.
int[] quot = new int[quotLen];
La operación cociente-y-resto. El cociente ahora está en quot , el resto en rem .
int rem = divideDigits(quot, 0,
current, current.length - quotLen,
radix);
Ponemos el resto en la matriz de salida (llenándolo desde el último dígito).
rDigits[rIndex] = rem;
rIndex --;
Luego intercambiamos las matrices para la próxima ronda.
current = quot;
Si hay ceros a la izquierda en el cociente (habrá como máximo uno, ya que radix es más pequeño que BASE), reducimos el tamaño del cociente en uno. La próxima matriz será más pequeña.
if(current[0] == 0) {
// omit leading zeros in next round.
quotLen--;
}
}
Después del ciclo, puede haber ceros a la izquierda en la matriz rDigits, y los cortamos.
// cut of leading zeros in rDigits:
while(rIndex < 0 || rDigits[rIndex] == 0) {
rIndex++;
}
return Arrays.copyOfRange(rDigits, rIndex, rDigits.length);
}
Eso es. Aunque parece un poco complicado. Aquí hay un ejemplo de cómo usarlo:
System.out.println("d4 in base 11: " +
Arrays.toString(d4.convertTo(11)));
System.out.println("d5 in base 7: " +
Arrays.toString(d5.convertTo(7)));
Estas impresiones [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0] y [1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0] , exactamente los mismos números que analizamos antes (de una Cadena, sin embargo).
En base a esto también podemos formatear como una cadena:
/**
* Converts the number to a String in a given radix.
* This uses {@link Character.digit} to convert each digit
* to one character.
* @param radix the radix to use, between {@link Character.MIN_RADIX}
* and {@link Character.MAX_RADIX}.
* @return a String containing the digits of this number in the
* specified radix, using ''0'' .. ''9'' and ''a'' .. ''z'' (as much as needed).
*/
public String toString(int radix) {
if(radix < Character.MIN_RADIX || Character.MAX_RADIX < radix) {
throw new IllegalArgumentException("radix out of range: " + radix);
}
if(digits.length == 0)
return "0";
int[] rdigits = convertTo(radix);
StringBuilder b = new StringBuilder(rdigits.length);
for(int dig : rdigits) {
b.append(Character.forDigit(dig, radix));
}
return b.toString();
}
Es posible que desee implementar o buscar una biblioteca de decimal codificado en binario si está intentando evitar BigInteger . Sin embargo, puedes obtener un factorial de 90 con BigInteger si quieres usarlo:
public static BigInteger factorial(BigInteger value) {
BigInteger total = BigInteger.ONE;
for (int i = 0; value.compareTo(BigInteger.ONE) == 1; i++) {
total = total.multiply(value);
value = value.subtract(BigInteger.ONE);
}
return total;
}
Las operaciones aritméticas en Java que usan los operadores + , - , * , / y % están vinculadas por las restricciones de los tipos de datos primitivos de Java .
Esto significa que si no puede ajustar sus números deseados en el rango de, por ejemplo, double o long , tendrá que usar una biblioteca de "gran número", como la que está incorporada en Java ( BigDecimal , BigInteger ) , o una biblioteca de terceros, o escribe la tuya. Esto también significa que no puede usar los operadores aritméticos ya que Java no admite la sobrecarga del operador.
Usa el siguiente código para multiplicar números de cualquier longitud: -
public class BigNumberMultiplication {
private static int[] firstBigNumber = null;
private static int[] secondBigNumber = null;
public static int[] baseMul(int[] baseMultiple, int base) {
System.out.println("baseMultiple" + Arrays.toString(baseMultiple) + base);
for (int i = 0; i < baseMultiple.length; i++) {
baseMultiple[i] *= base;
}
System.out.println("basemultipleresultwithoutcarryforward" + baseMultiple);
return carryForward(baseMultiple);
}
public static int[] basePowerMul(int[] basePowerMultiple, int base, int power) {
int basePowerMultipleTemp[] = baseMul(basePowerMultiple, base);
System.out.println("basePowerMultipleTemp" + Arrays.toString(basePowerMultipleTemp) + "power" + power);
int basePowerMultipleResult[] = new int[basePowerMultipleTemp.length + (power - 1)];
for(int i = 0; i < basePowerMultipleTemp.length; i++)
basePowerMultipleResult[i] = basePowerMultipleTemp[i];
if(power > 1){
for(int i = 0; i < (power - 1); i++)
basePowerMultipleResult[basePowerMultipleTemp.length + i] = 0;
}
System.out.println("basepowermulresult" + Arrays.toString(basePowerMultipleResult));
return basePowerMultipleResult;
}
public static int[] addBigNumber(int[] finalNumberInArray, int[] finalNumberInArrayTemp){
System.out.println("final number in array" + Arrays.toString(finalNumberInArray) + "finalNumberInTemp" + Arrays.toString(finalNumberInArrayTemp));
int n = finalNumberInArray.length;
for(int i = (finalNumberInArrayTemp.length - 1); i >= 0; i--){
finalNumberInArray[n - 1] += finalNumberInArrayTemp[i];
n--;
}
return carryForward(finalNumberInArray);
}
public static int[] carryForward(int[] arrayWithoutCarryForward){
int[] arrayWithCarryForward = null;
System.out.println("array without carry forward" + Arrays.toString(arrayWithoutCarryForward));
for (int i = arrayWithoutCarryForward.length - 1; i > 0; i--) {
if (arrayWithoutCarryForward[i] >= 10) {
int firstDigit = arrayWithoutCarryForward[i] % 10;
int secondDigit = arrayWithoutCarryForward[i] / 10;
arrayWithoutCarryForward[i] = firstDigit;
arrayWithoutCarryForward[i - 1] += secondDigit;
}
}
if(arrayWithoutCarryForward[0] >= 10){
arrayWithCarryForward = new int[arrayWithoutCarryForward.length + 1];
arrayWithCarryForward[0] = arrayWithoutCarryForward[0] / 10;
arrayWithCarryForward[1] = arrayWithoutCarryForward[0] % 10;
for(int i = 1; i < arrayWithoutCarryForward.length; i++)
arrayWithCarryForward[i + 1] = arrayWithoutCarryForward[i];
}
else{
arrayWithCarryForward = arrayWithoutCarryForward;
}
System.out.println("array with carry forward" + Arrays.toString(arrayWithCarryForward));
return arrayWithCarryForward;
}
public static int[] twoMuscularNumberMul(){
int finalNumberInArray[] = null;
for(int i = 0; i < secondBigNumber.length; i++){
if(secondBigNumber[i] == 0){}
else {
int[] finalNumberInArrayTemp = basePowerMul(Arrays.copyOf(firstBigNumber, firstBigNumber.length), secondBigNumber[i], secondBigNumber.length - i);
if(finalNumberInArray == null){
finalNumberInArray = finalNumberInArrayTemp;
System.out.println("finalNumberInArray" + Arrays.toString(finalNumberInArray));
}
else{
finalNumberInArray = addBigNumber(finalNumberInArray, finalNumberInArrayTemp);
System.out.println("finalNumberInArray" + Arrays.toString(finalNumberInArray));
}
}
}
return finalNumberInArray;
}
public static int [] readNumsFromCommandLine() {
Scanner s = new Scanner(System.in);
System.out.println("Please enter the number of digit");
int count = s.nextInt();
System.out.println("please enter the nuumber separated by space");
s.nextLine();
int [] numbers = new int[count];
Scanner numScanner = new Scanner(s.nextLine());
for (int i = 0; i < count; i++) {
if (numScanner.hasNextInt()) {
numbers[i] = numScanner.nextInt();
} else {
System.out.println("You didn''t provide enough numbers");
break;
}
}
return numbers;
}
public static void main(String[] args) {
firstBigNumber = readNumsFromCommandLine();
secondBigNumber = readNumsFromCommandLine();
System.out.println("1st number" + Arrays.toString(firstBigNumber) + "2nd number" + Arrays.toString(secondBigNumber));
int[] finalArray = twoMuscularNumberMul();
System.out.println(Arrays.toString(finalArray));
}
}
texto fuerte de la clase pública BigInteger {
public static String checkSignWithRelational(int bigInt1, int bigInt2){
if( bigInt1 < 0){
return "negative";
}else {
return "positive";
}
}
BigInteger( long init)
{
Long.parseLong(bigInt1);
}
BigInteger String (String init){
return null;
}
private static int intLenght(int bigInt) {
return Integer.toString(bigInt).length();
}
private static int[] intToArray(int bigInt, int bigIntLength, int arrayLength) {
int array[] = new int[arrayLength ];
for (int i = 0; i < arrayLength ; i++) {
array[i] = ( i<bigIntLength ?
getDigitAtIndex(bigInt, bigIntLength - i -1) :0 );
}
return array;
}
static String add(int bigInt1, int bigInt2) {
//Find array length
int length1 = intLenght(bigInt1);
int length2 = intLenght(bigInt2);
int arrayLength = Math.max(length1, length2);
int array1[] = intToArray(bigInt1, length1, arrayLength);
int array2[] = intToArray(bigInt2, length2, arrayLength);
return add(array1, array2);
}
private static String add(int[] array1, int[] array2) {
int carry=0;
int addArray[] = new int[array1.length + 1];
for (int i = 0; i < array1.length; i++) {
addArray[i] = (array1[i] + array2[i] + carry) % 10 ;
carry = (array1[i] + array2[i] + carry) / 10;
}
addArray[array1.length] = carry;
return arrayToString(addArray);
}
private static int getDigitAtIndex(int longint,int index){
return Integer.parseInt(Integer.toString(longint).substring(index, index+1));
}
private static String arrayToString(int[] addArray) {
String add = "";
boolean firstNonZero = false;
for (int i = addArray.length-1; i >= 0 ; i--) {
if(!firstNonZero && (addArray[i]==0)){
continue;
} else{
firstNonZero=true;
}
add += addArray[i];
if((i%3 ==0)&&i!=0){ add +=",";} //formatting
}
String sumStr = add.length()==0?"0":add;
return sumStr;
}
public static String sub(int bigInt1, int bigInt2) {
int length1 = intLenght(bigInt1);
int length2 = intLenght(bigInt2);
int arrayLength = Math.max(length1, length2);
int array1[] = intToArray(bigInt1, length1, arrayLength);
int array2[] = intToArray(bigInt2, length2, arrayLength);
return sub(array1, array2);
}
private static String sub(int[] array1, int[] array2) {
int carry=0;
int sub[] = new int[array1.length + 1];
for (int i = 0; i < array1.length; i++) {
sub[i] = (array1[i] - array2[i] + carry) % 10 ; //sum digits + carry; then extract last digit
carry = (array1[i] - array2[i] + carry) / 10; //Compute carry
}
sub[array1.length] = carry;
return arrayToString(sub);
}
public static String mul(int bigInt1, int bigInt2) {
int length1 = intLenght(bigInt1), length2 = intLenght(bigInt2), length = Math.max(length1, length2);
int array1[] = intToArray(bigInt1, length1, length); int array2[] = intToArray(bigInt2, length2, length);
return mul(array1, array2);
}
private static String mul(int[] array1, int[] array2) {
int product[] = new int[array1.length + array2.length];
for(int i=0; i<array1.length; i++){
for(int j=0; j<array2.length; j++){
int prod = array1[i] * array2[j];
int prodLength = intLenght(prod);
int prodAsArray[] = intToArray(prod, prodLength, prodLength);
for (int k =0; k < prodAsArray.length; k++) {
product[i+j+k] += prodAsArray[k];
int currentValue = product[i+j+k];
if(currentValue>9){
product[i+j+k] = 0;
int curValueLength = intLenght(currentValue);
int curValueAsArray[] = intToArray(currentValue, curValueLength, curValueLength);
for (int l = 0; l < curValueAsArray.length; l++) {
product[i+j+k+l] += curValueAsArray[l];
}
}
}
}
}
return arrayToString(product);
}
public static int div(int bigInt1, int bigInt2) {
if ( bigInt2 == 0){
throw new ArithmeticException("Division by 0 is undefined:" + bigInt1+ "/" + bigInt2);
}
int sign = 1;
if(bigInt1 < 0) {
bigInt1 = -bigInt1;
sign = -sign;
}
if (bigInt2 < 0){
bigInt2 = -bigInt2;
sign = -sign;
}
int result =0;
while (bigInt1 >= 0){
bigInt1 -= bigInt2;
result++;
}
return (result - 1) * sign;
}
public static String check(String bigInt1, String bigInt2){
int difference;
StringBuilder first = new StringBuilder(bigInt1);
StringBuilder second = new StringBuilder(bigInt2);
if(bigInt1.length()> bigInt2.length()){
difference = bigInt1.length() - bigInt2.length();
for(int x = difference; x > 0; x--){
second.insert(0,"0");
}
bigInt2 = second.toString();
return bigInt2;
}else {
difference = bigInt2.length() - bigInt1.length();
for (int x = difference; x> 0; x--)
{
first.insert(0, "0");
}
bigInt1 = first.toString();
return bigInt1;
}
}
public static int mod(int bigInt1, int bigInt2){
int res = bigInt1 % bigInt2;
return (res);
}
public static void main(String[] args) {
int bigInt1 = Integer.parseInt("987888787");
int bigInt2 = Integer.parseInt("444234343");
System.out.println(bigInt1+" + "+bigInt2+" = "+add(bigInt1, bigInt2));
System.out.println(bigInt1+" - "+bigInt2+" = "+sub(bigInt1, bigInt2));
System.out.println(bigInt1+" * "+bigInt2+" = "+mul(bigInt1, bigInt2));
System.out.println(bigInt1+" / "+bigInt2+" = "+div(bigInt1, bigInt2));
System.out.println(bigInt1+" % "+bigInt2+" = "+mod(bigInt1, bigInt2));
}
}
If we have really big numbers on which we want to perform arithmetic operations than they must be in some object form such as Strings.
Let their be strings with the character length greater than the range of BigInteger.
In this case I''ll perform arithmetic operation the way we do it on a notebook. For Example - Let''s assume we have to do the addition. Start with comparing the two strings for length. Make three new Strings. The First String is the smaller one. The Second String is the rightmost substring of the longer string with length equal to the smaller string. The third string is the leftover long string from the left side. Now add the first and second string from the end converting characters to integers, one character at a time and keeping the carry in an int variable. Immediately after each addition, append the sum in a StringBuffer. After the two strings are added, do the same operation for the third string and keep on adding the carry. In the end reverse the StringBuffer and return the String.
Here is the code I used for Addition
public String addNumber(String input1,String input2){
int n=0;String tempStr;
String one="";
String two="";
if(input1.length()>input2.length()){
n=input1.length()-input2.length();
tempStr=new String(input1);
one=new String(input1.substring(n,input1.length()));
two=new String(input2);
}else{
n=input2.length()-input1.length();
tempStr=new String(input2);
one=new String(input2.substring(n,input2.length()));
two=new String(input1);
}
StringBuffer temp=new StringBuffer();
for(int i=0;i<n;i++){
temp.append(tempStr.charAt(i));
}
StringBuffer newBuf=new StringBuffer();
int carry=0;
int c;
for(int i=one.length()-1;i>=0;i--){
int a=Character.getNumericValue(one.charAt(i));
int b=Character.getNumericValue(two.charAt(i));
c=a+b+carry;
newBuf.append(""+(c%10));
c=c/10;
carry=c%10;
}
String news=new String(temp);
for(int i=news.length()-1;i>=0;i--){
c=(Character.getNumericValue(news.charAt(i)))+carry;
newBuf.append(""+(c%10));
c=c/10;
carry=c%10;
}
if(carry==1){
newBuf.append(""+carry);
}
String newisis=new String(newBuf.reverse());
return newisis;
}
When I want to do 90! or some other massive calculation, I try and use an int[] array, each element holding one of the digits. Then I apply the traditional multiplication we using pen and paper to get the answer in another int[] array.
This is the code I wrote in Java which calculates 100! rather quickly. Feel free to use this however you like.
public int factoial(int num) {
int sum = 0;
int[][] dig = new int[3][160];
dig[0][0] = 0;
dig[0][1] = 0;
dig[0][2] = 1;
for (int i = 99; i > 1; i--) {
int len = length(i);
for (int k = 1; k <= len; k++) { // Sets up multiplication
int pos = len - k;
dig[1][pos] = ((i / (int) (Math.pow(10, pos))) % 10);
}
int temp;
for (int k = 0; k < len; k++) { // multiplication
for (int j = 0; j < 159; j++) {
dig[2][k + j] += (dig[1][k] * dig[0][j]);
if (dig[2][k + j] >= 10) {
dig[2][k + j + 1] += dig[2][k + j] / 10;
dig[2][k + j] = dig[2][k + j] % 10;
}
}
}
sum = 0;
for (int k = 159; k >= 0; k--) {
System.out.print(dig[2][k]);
dig[0][k] = dig[2][k];
dig[1][k] = 0;
sum += dig[2][k];
dig[2][k] = 0;
}
System.out.println();
}
return sum;
}