Luego de tanto luchar pudimos dar con la contestación de esta incógnita que algunos lectores de nuestra web tienen. Si deseas compartir algo puedes aportar tu conocimiento.
Solución:
Creo que un programador debería haber implementado su propia biblioteca bignum una vez, así que bienvenido aquí.
(Por supuesto, más adelante entenderá que BigInteger es mejor y usará esto, pero es una experiencia de aprendizaje valiosa).
(Puede seguir el código fuente de la vida de este curso en github. Además, lo rehice (un poco pulido) en una serie de blogs de 14 partes).
Crear 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 nos da Java.
Como cree que la conversión decimal es la parte más complicada, permanezcamos en un modo basado en decimal. Para mayor eficiencia, no almacenaremos dígitos decimales reales, sino que trabajaremos en base 1 000 000 000 = 10^9 < 2^30. Esto encaja en un Java int (hasta 2^31 o 2^32), y el producto de dos de estos digitos encaja muy bien en un Java long.
final static int BASE = 1000000000;
final static int BASE_DECIMAL_DIGITS = 9;
Entonces la matriz de dígitos:
private int[] digits;
¿Almacenamos los dígitos en little- o big endian, es decir, las partes más grandes al principio o al final? Realmente no importa, así que decidimos por big-endian, ya que así es como los humanos quieren leerlo. (Por ahora, nos concentramos en los valores no negativos; luego agregaremos un bit de signo para los números negativos).
Para propósitos de prueba, agregamos un constructor que permite inicializar desde un 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)
this.digits = digits.clone();
Como beneficio adicional, este constructor también se puede usar para un solo int (si es menor que BASE), e incluso sin 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 [email protected], no tan útil. Entonces, agregamos un toString() método:
/**
* 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 es ahora Big[7, 5, 2, 12345], que es más útil para realizar pruebas, ¿no?
En segundo lugar, conversión de formato decimal.
Tenemos suerte aquí: nuestra base (10 ^ 9) es una potencia de la base que queremos convertir de (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 de escritura Java int 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];
Recorriendo los dígitos que se crearán:
for(int i = 0; i < bigLen; i++)
Cada uno de nuestro 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);
(Los Math.max se necesita aquí para el primer bloque más corto). Ahora usamos la función de análisis de enteros habitual y colocamos el resultado en la matriz:
digits[i] = Integer.parseInt(block);
A partir de 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);
Producción:
Big[12, 345678901, 234567890]
Parece correcto 🙂 Deberíamos probarlo con algunos otros números (de diferente longitud) también.
La siguiente parte será el formato decimal, esto debería ser aún más fácil.
En tercer lugar, conversión a formato decimal.
Necesitamos generar nuestros dígitos individuales como 9 dígitos decimales cada uno. Para esto podemos usar el Formatter class, que admite cadenas de formato tipo 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 vuelve 000000007000000005000000002000012345 y 000000012345678901234567890 para nuestros dos números. Esto funciona para un viaje de ida y vuelta (es decir, alimentarlo al valueOf da un objeto equivalente), pero los ceros iniciales no son realmente agradables a la vista (y podrían crear confusión con los números octales). Así que necesitamos separar nuestro hermoso bucle for-each y usar una cadena de formato diferente para el primer y los siguientes dígitos.
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 más adelante).
/**
* 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, por lo tanto plus, minus, times en lugar de add, subtract, multiply.
Entonces, ¿cómo funciona la suma? 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 mayor 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 miramos el caso simple de que ambos números tienen el mismo número de dígitos. Entonces se ve simplemente 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, por lo 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 el mismo número de dígitos, se complica un poco.
Para que sea lo más simple posible, lo dividimos en varios métodos:
Este método agrega un dígito a un elemento en la matriz (que ya puede contener algún valor distinto de cero) y almacena el resultado en la matriz. Si hubo desbordamiento, lo llevamos al siguiente dígito (que tiene índice uno menos, no uno más) mediante 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 con toda una serie 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)
int addendIndex = addend.length - 1;
while(addendIndex >= 0)
addDigit(result, resultIndex,
addend[addendIndex]);
addendIndex--;
resultIndex--;
Ahora podemos implementar nuestro plus método:
/**
* 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 hacerlo un poco mejor aquí si miráramos antes si el desbordamiento es posible y solo entonces creamos la matriz una más grande de lo necesario.
Ah, una prueba: d2.plus(d2) da 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 sume el producto en dígitos[i+j] del resultado (y preste atención a llevar). Por supuesto, aquí los índices se cuentan desde la derecha, no desde la izquierda. (Ahora realmente desearía haber usado números little-endian).
Dado que el producto de dos de nuestros dígitos puede estar fuera 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é declaré mi addDigits método para tomar un resultIndex parámetro. (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 de índice correctos. Con una representación little-endian, habría sido multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j]) - bastante más claro, ¿no?
Nuestro times El método ahora solo tiene que asignar la matriz de resultados, invocar multiplyDigits y envolver 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 cálculo de Emacs aquí.
Comparación
Queremos poder comparar dos de nuestros objetos. Entonces, implementamos Comparable y su método compareTo.
public int compareTo(DecimalBigInt that)
¿Cómo saber si uno de nuestros números es mayor que otro? Primero, comparamos la longitud de las matrices. Como nos cuidamos de no inducir 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. Dado que usamos big endian (es decir, el gran final 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 igual, 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 forma adecuada (y compatible).
Para nuestro hashCode(), simplemente sumamos los dígitos, multiplicándolos con un pequeño número primo para asegurarnos de que el cambio 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 equals() método simplemente podemos delegar en el método compareTo, en lugar de implementar el mismo algoritmo nuevamente:
/**
* 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 por hoy. La resta (y tal vez los números negativos) y la división son más complicadas, así que las omitiré 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 radix arbitrarias
Impulsado por la siguiente pregunta de frodosamoa, escribí mi respuesta sobre cómo convertir de sistemas numéricos arbitrarios (posicionales) en uno en el que podemos (o queremos) calcular. (En el ejemplo, convertí de trinario a decimal, mientras que la pregunta era de decimal a binario).
Aquí queremos convertir de un sistema numérico arbitrario (está bien, con base entre 2 y 36, entonces podemos usar Character.digit() para convertir dígitos de un solo dígito a ints) a nuestro sistema con radix BASE (= 1.000.000.000, pero esto no es realmente importante aquí).
Básicamente usamos el esquema de Horner para calcular el valor del polinomio con los dígitos como coeficientes en el punto dado por la base.
sum[i=0..n] digit[i] * radix^i
se puede calcular con este bucle:
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 hacer una cuenta regresiva, pero podemos usar un bucle for simple mejorado. (Se ve más feo en Java, ya que no tenemos operadores sobrecargados ni 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 asegurarnos de que realmente tenemos un número válido y, por supuesto, un comentario de documentación.
Mudado para un sistema posicional arbitrario es más complicado, ya que implica el resto y la división (por la base arbitraria), que aún no implementamos, por lo que no por ahora. Lo haré cuando tenga una buena idea de cómo hacer la división. (Aquí solo necesitamos la división por números pequeños (de un dígito), lo que puede ser más fácil que una división general).
División por números pequeños
En la escuela, aprendí división larga. Aquí hay un ejemplo de 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 resto nativa. 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 parece una división corta, si lo escribimos en otro formato.
Podemos observar (y probar) lo siguiente:
Si tenemos un número x de dos dígitos 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, menor que d. Esto, junto con la inducción, muestra que solo necesitamos dividir (con resto) números de dos dígitos por nuestro divisor.
Volviendo a nuestros números grandes con base BASE: todos los números de dos dígitos se pueden representar como Java long, y ahi tenemos nativos / 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
* Wikipedia's
* article Short division.
* @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 todavía devuelve un int, el resto.
Ahora queremos tener un método público que devuelva un DecimalBigInt, así 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 a la izquierda 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)
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) 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 base arbitraria
Ahora tenemos los conceptos básicos para convertir a una base arbitraria. Por supuesto, no es realmente arbitrario, solo radixes menores que BASE están permitidos, pero esto 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, sumar. La parte" multiplicar-sumar "es, de hecho, solo juntar los dígitos individuales, por lo que podemos reemplazarlo por una matriz simple- acceso.
Como siempre necesitamos tanto el cociente como el resto, no usaremos los métodos públicos modulo y divideBy, sino que llame repetidamente al divideDigits método.
/**
* 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
Eso es todo. Sin embargo, parece un poco complicado. A continuación, se muestra un ejemplo de cómo utilizarlo:
System.out.println("d4 in base 11: " +
Arrays.toString(d4.convertTo(11)));
System.out.println("d5 in base 7: " +
Arrays.toString(d5.convertTo(7)));
Estos imprimen [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], solo los mismos números que analizamos antes (aunque de una cadena).
Basándonos en 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) 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 investigar una biblioteca para decimal codificado en binario si está tratando de evitar BigInteger. Puedes lograr un factorial de 90 con BigInteger aunque 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;
Te mostramos comentarios y calificaciones
Nos puedes apoyar nuestra investigación exponiendo un comentario o dejando una puntuación te damos las gracias.