Как я буду делать арифметику, + -/*%!, с произвольно большими целыми числами без использования java.math.BigInteger?
Например, факториал 90 возвращает 0 в Java. Я хотел бы иметь возможность решить эту проблему.
Как обрабатывать очень большие числа в Java без использования java.math.BigInteger
Ответ 1
Я думаю, что программист должен был однажды реализовать свою собственную библиотеку бигмуна, поэтому приветствую вас здесь.
(Конечно, позже вы получите, что BigInteger лучше, и используйте это, но это ценный опыт обучения.)
(Вы можете следить за исходным кодом этого курса в github. Кроме того, я переделал это (немного полированное) в 14-секционная серия блога.)
Создание простого класса больших чисел в Java
Итак, что нам нужно?
Во-первых, представление числа,
на основе типов данных, которые дает нам Java.
Как вы считаете, десятичное преобразование является самой сложной частью, давайте оставаться в десятичном режиме. Для эффективности мы будем хранить не реальные десятичные цифры, а работать в базе 1 000 000 000 = 10^9 < 2^30. Это соответствует Java int (до 2^31 или 2^32), а произведение двух таких цифр прекрасно вписывается в Java long.
final static int BASE = 1000000000;
final static int BASE_DECIMAL_DIGITS = 9;
Затем набор цифр:
private int[] digits;
Сохраняем ли цифры в маленьком или большом конце, т.е. более крупные части сначала или в последний раз? Это не имеет большого значения, поэтому мы принимаем решение по поводу того, как люди хотят его прочитать. (На данный момент мы концентрируемся на неотрицательных значениях - позже мы добавим знаковый бит для отрицательных чисел.)
В целях тестирования мы добавляем конструктор, который позволяет инициализировать такой 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();
}
В качестве дополнительного бонуса этот конструктор также можно использовать для одного int (если меньше, чем BASE) и даже для no int (который мы будем интерпретировать как 0). Итак, теперь мы можем сделать это:
DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345);
System.out.println(d);
Это дает нам [email protected], что не так полезно. Итак, мы добавляем метод 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);
}
Теперь результат Big[7, 5, 2, 12345], что более полезно для тестирования, не так ли?
Во-вторых, преобразование из десятичного формата.
Нам повезло: наша база (10 ^ 9) - это сила базы, которую мы хотим преобразовать из (10). Таким образом, мы всегда имеем одинаковое число (9) десятичных цифр, представляющих цифру "наш формат". (Конечно, в начале могут быть некоторые цифры меньше.) В следующем коде decimal является строкой десятичных цифр.
int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;
Эта странная формула - это Java-способ записи bigLen = ceil(decLen/BASE_DECIMAL_DIGITS). (Я надеюсь, что это правильно, мы позже проверим его.)
int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;
Это длина первого блока десятичных цифр, должна быть между 1 и 9 (включительно).
Мы создаем наш массив:
int[] digits = new int[bigLen];
Цитирование через цифры, которые нужно создать:
for(int i = 0; i < bigLen ; i++) {
Каждая из наших цифр представлена блоком цифр в исходном номере:
String block =
decimal.substring(Math.max(firstSome + (i-1)*BASE_DECIMAL_DIGITS, 0),
firstSome + i *BASE_DECIMAL_DIGITS);
(Math.max нужен здесь для первого более короткого блока.)
Теперь мы используем обычную функцию разбора целых чисел и помещаем результат в массив:
digits[i] = Integer.parseInt(block);
}
Из созданного массива мы создаем наш объект DecimalBigInt:
return new DecimalBigInt(digits);
Посмотрим, работает ли это:
DecimalBigInt d2 = DecimalBigInt.valueOf("12345678901234567890");
System.out.println(d2);
Вывод:
Big[12, 345678901, 234567890]
Выглядит правильно:-) Мы должны проверить его с некоторыми другими номерами (разной длины) тоже.
Следующая часть будет десятичным форматированием, это должно быть еще проще.
В-третьих, преобразование в десятичный формат.
Нам нужно выводить наши отдельные цифры как 9 десятичных цифр каждый. Для этого мы можем использовать класс Formatter, который поддерживает строки формата printf.
Простым вариантом будет следующее:
public String toDecimalString() {
Formatter f = new Formatter();
for(int digit : digits) {
f.format("%09d", digit);
}
return f.toString();
}
Это возвращает 000000007000000005000000002000012345 и 000000012345678901234567890 для наших двух чисел. Это работает для туда-обратно (т.е. Подача его методу valueOf дает эквивалентный объект), но ведущие нули не очень приятно смотреть (и могут создавать путаницу с восьмеричными числами). Поэтому нам нужно разбить наш красивый для каждого цикла и использовать другую строку форматирования для первой и следующих цифр.
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();
}
Добавление.
Начнем с добавления, поскольку это просто (и мы можем использовать его части для последующего умножения).
/**
* calculates the sum of this and that.
*/
public DecimalBigInt plus(DecimalBigInt that) {
...
}
Мне нужны имена методов, которые вы можете прочитать, как будто бы вы читали формулу, поэтому plus, minus, times вместо add, subtract, multiply.
Итак, как работает дополнение? Он работает так же, как мы узнали его в школе, для десятичных чисел, превышающих 9: добавьте соответствующие цифры, и если в течение некоторого времени результат будет больше 10 (или BASE в нашем случае), переведите его на следующую цифру, Это может привести к тому, что результирующее число будет иметь одну цифру больше, чем исходные.
Сначала мы рассмотрим простой случай, когда оба числа имеют одинаковое количество цифр. Тогда это выглядит просто так:
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);
(Мы переходим справа налево, поэтому мы можем переносить любые переполнения на следующую цифру. Это было бы немного красивее, если бы мы решили использовать формат Little Endian.)
Если оба номера не имеют одинакового количества цифр, это немного усложняется.
Чтобы сделать это максимально простым, мы разделим его на несколько методов:
Этот метод добавляет одну цифру к элементу массива (который может уже содержать некоторое ненулевое значение) и сохраняет результат в массиве. Если было переполнение, мы переносим его на следующую цифру (которая имеет индекс один меньше, а не один) с помощью рекурсивного вызова. Таким образом, мы гарантируем, что наши цифры всегда будут в допустимом диапазоне.
/**
* 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);
}
}
Следующее делает то же самое для целого массива цифр:
/**
* 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--;
}
}
Теперь мы можем реализовать наш метод 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);
}
Мы могли бы сделать немного лучше, если бы посмотрели раньше, если переполнение вообще возможно, и только затем создайте массив, который больше, чем необходимо.
Ah, одно испытание: d2.plus(d2) дает Big[24, 691357802, 469135780], который выглядит правильно.
Умножение.
Вспомните в школу, как мы умножали большие числа на бумаге?
123 * 123
----------
369 <== 123 * 3
246 <== 123 * 2
123 <== 123 * 1
--------
15129
Итак, мы должны умножить каждую цифру [i] первого числа на каждую цифру [j] второго номера и добавить произведение в цифру [i + j] результата (и обратить внимание на перенос), Конечно, здесь индексы подсчитываются справа, а не слева. (Теперь мне действительно жаль, что я не использовал малозначные числа.)
Так как произведение двух наших цифр может выйти за пределы диапазона int, мы используем long для умножения.
/**
* 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);
}
Теперь мы можем понять, почему я объявил, что мой метод addDigits принимает параметр resultIndex. (И я просто изменил последний аргумент на параметр varargs, чтобы лучше было писать это здесь.)
Итак, здесь метод кросс-умножения:
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]);
}
}
}
Надеюсь, что у меня есть индексные вычисления. С представлением мало-endian это было бы multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j]) - довольно ясным, не так ли?
Наш метод times теперь должен только выделить массив результатов, вызвать multiplyDigits и обернуть результат.
/**
* 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);
}
Для тестирования d2.times(d2) дает Big[152, 415787532, 388367501, 905199875, 19052100], что то же, что и вычисляет мой Emacs calc.
Сравнение
Мы хотим иметь возможность сравнивать два наших объекта. Итак, мы реализуем Comparable<DecimalBigInt> и метод compareTo.
public int compareTo(DecimalBigInt that) {
Как узнать, больше ли один из наших чисел? Во-первых, мы сравниваем длину массивов. Поскольку мы позаботились о том, чтобы не приводить к каким-либо ведущим нулям (мы?), Более длинный массив должен иметь большее число.
if(this.digits.length < that.digits.length) {
return -1;
}
if (that.digits.length < this.digits.length) {
return 1;
}
Если длина такая же, мы можем сравнить элемент. Поскольку мы используем большой endian (то есть большой конец на первом месте), мы начинаем с самого начала.
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;
}
}
Если все было одинаково, очевидно, что наши числа идентичны, и мы можем вернуть 0.
return 0;
}
equals + hashCode()
Каждый хороший неизменяемый класс должен реализовывать equals() и hashCode() подходящим (и совместимым) способом.
Для нашего hashCode() мы просто суммируем цифры, умножая их на небольшое простое, чтобы убедиться, что переключение цифр не приводит к тому же хэш-коду:
/**
* calculates a hashCode for this object.
*/
public int hashCode() {
int hash = 0;
for(int digit : digits) {
hash = hash * 13 + digit;
}
return hash;
}
В методе equals() мы просто можем делегировать метод compareTo, а не повторять тот же алгоритм:
/**
* 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;
}
Итак, хватит на сегодня. Вычитание (и, может быть, отрицательные числа) и деление более сложны, поэтому я сейчас их опускаю. Для вычисления факториала 90 это должно быть достаточно.
Вычисление больших факториалов:
Здесь факториальная функция:
/**
* 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;
}
Это дает нам
fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000
Преобразование из произвольно-радиальных представлений
В ответ на следующий вопрос frodosamoa я написал мой ответ о том, как преобразовать из произвольных (позиционных) систем с номерами в тот, в котором мы можем (или хотим) вычислить. (В примере там я преобразовал из трехмерного в десятичный, тогда как вопрос был о десятичном значении для двоичного.)
Здесь мы хотим конвертировать из произвольной системы чисел (хорошо, с радиусом между 2 и 36, поэтому мы можем использовать Character.digit() для конвертировать отдельные цифры в ints) в нашу систему с помощью radix BASE (= 1.000.000.000, но здесь это не очень важно).
В основном мы используем схему Хорнера для вычисления значения полинома с цифрами в качестве коэффициентов в точке, заданной основанием.
sum[i=0..n] digit[i] * radix^i
можно вычислить с помощью этого цикла:
value = 0;
for i = n .. 0
value = value * radix + digit[i]
return value
Поскольку наши входные строки являются большими, нам не нужно обращать внимание, но они могут использовать простой расширенный цикл. (Это выглядит более уродливым на Java, поскольку у нас нет перегрузки оператора, и нет autoboxing от int до нашего Тип 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;
}
В моя фактическая реализация Я добавил некоторую проверку ошибок (и исключение бросания), чтобы убедиться, что у нас действительно есть действительное число, и, конечно, комментарий к документации.
Преобразование в произвольной позиционной системы сложнее, поскольку она включает в себя остаток и деление (на произвольный радикс), которые мы еще не реализовали - так что пока. Это будет сделано, когда у меня будет хорошая идея о том, как сделать разделение. (Нам нужно только деление на маленькие (однозначные) числа, что может быть проще, чем общее деление.)
Разделение на небольшие числа
В школе я узнал длинное разделение. Вот пример небольшого (одноразрядного) делителя в обозначениях, которые мы используем здесь в Германии (с аннотациями о фоновых вычислениях, которые мы обычно не будем писать), в десятичной системе:
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.
Мы не должны вычислять эти продукты (0, 12, 0, 30, 42) и вычесть их, если у нас есть нативная операция остатка. Тогда это выглядит (конечно, нам здесь не нужно будет писать операции):
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.
Это уже выглядит как короткое разделение, если мы напишем его в другом формате.
Мы можем наблюдать (и доказывать) следующее:
Если у нас есть двузначное число x с первой цифрой меньше нашего дивизора d, чем x / d является одноразрядным числом, а x % d также является одноразрядным числом, меньшим, чем d. Это, вместе с индукцией, показывает, что нам нужно когда-либо делить (с остатком) двузначные числа на наш делитель.
Возвращаясь к нашим большим числам с основанием BASE: все двузначные числа представляются как Java long, и там у нас есть родные / и %.
/**
* 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;
}
Теперь мы будем вызывать этот метод в цикле, всегда подавая результат из предыдущего обратного вызова как 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 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;
}
Этот метод все еще возвращает int, остаток.
Теперь мы хотим, чтобы публичный метод возвращал DecimalBigInt, поэтому мы его создаем. У него есть задача проверить аргументы, создать массив для рабочего метода, отбросить остаток и создать DecimalBigInt из результата. (Конструктор удаляет начальный ноль, который может быть там.)
/**
* 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);
}
У нас также есть аналогичный метод, который вместо этого возвращает остаток:
/**
* 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);
}
Эти методы можно вызвать следующим образом:
DecimalBigInt d3_by_100 = d3.divideBy(100);
System.out.println("d3/100 = " + d3_by_100);
System.out.println("d3%100 = " + d3.modulo(100));
Преобразование в произвольный радиус
Теперь у нас есть основы для преобразования в произвольный радиус. Конечно, не очень произвольно, допустимы только радионы меньше BASE, но это не должно быть слишком большой проблемой.
Как уже было сказано в другом ответе о преобразовании чисел, мы должны делать "деление, остаток, умножить, добавить". Часть "умножить-добавить" на самом деле составляет только отдельные цифры, поэтому мы можем заменить ее на простой доступ к массиву.
Поскольку нам всегда нужны как частное, так и остальное, мы не будем использовать общедоступные методы modulo и divideBy, но вместо этого повторно вызываем метод 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!");
}
Во-первых, обработка специального случая для 0.
// zero has no digits.
if(digits.length == 0)
return new int[0];
Затем мы создаем массив для цифр результата (достаточно долго), и некоторые другие переменные.
// 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 - это число цифр (исключая начальные нули) в последнем частном. Если это 0, мы закончили.
while(quotLen > 0) {
Новый массив для следующего частного.
int[] quot = new int[quotLen];
Операция quotient-and-else. Фактор теперь находится в quot,
остаток в rem.
int rem = divideDigits(quot, 0,
current, current.length - quotLen,
radix);
Мы помещаем остаток в выходной массив (заполняя его с последней цифры).
rDigits[rIndex] = rem;
rIndex --;
Затем мы заменяем массивы для следующего раунда.
current = quot;
Если в факторе есть ведущие нули (будет не более одного, так как radix меньше, чем BASE), мы уменьшаем размер фактора на единицу. Следующий массив будет меньше.
if(current[0] == 0) {
// omit leading zeros in next round.
quotLen--;
}
}
После цикла в массиве rDigits могут быть ведущие нули, и мы отключим их.
// cut of leading zeros in rDigits:
while(rIndex < 0 || rDigits[rIndex] == 0) {
rIndex++;
}
return Arrays.copyOfRange(rDigits, rIndex, rDigits.length);
}
Что это. Однако это выглядит немного сложнее. Вот пример того, как его использовать:
System.out.println("d4 in base 11: " +
Arrays.toString(d4.convertTo(11)));
System.out.println("d5 in base 7: " +
Arrays.toString(d5.convertTo(7)));
Эти печатные [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0] и [1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0], те же номера, что и раньше (начиная с String).
На основании этого мы также можем форматировать как строку:
/**
* 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();
}
Ответ 2
Возможно, вы захотите реализовать или исследовать библиотеку для двоично-десятичного десятичного кода, если вы пытаетесь избежать BigInteger. Вы можете выполнить факториал 90 с BigInteger, если вы хотите использовать его, хотя:
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;
}
Ответ 3
Арифметические операции в Java с использованием операторов +, -, *, / и % связаны ограничениями Примитивные типы данных Java.
Это означает, что если вы не можете поместить свои нужные номера в диапазон, скажем, double или long, тогда вам придется использовать библиотеку "большого числа", такую как один встроенный к Java (BigDecimal, BigInteger), или стороннюю библиотеку, или написать свой собственный. Это также означает, что вы не можете использовать арифметические операторы, поскольку Java не поддерживает перегрузку оператора.
Ответ 4
Используйте следующий код для умножения чисел любой длины: -
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));
}
}
Ответ 5
сильный текст открытый класс 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));
}
}
Ответ 6
Когда я хочу сделать 90! или некоторые другие массовые вычисления, я пытаюсь использовать массив int [], каждый элемент содержит одну из цифр. Затем я применяю традиционное умножение, используя ручку и бумагу, чтобы получить ответ в другом массиве int [].
Это код, который я написал на Java, который вычисляет 100! довольно быстро. Не стесняйтесь использовать это, как вам нравится.
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;
}
Ответ 7
Если у нас действительно большие числа, на которых мы хотим выполнить арифметические операции, то они должны быть в какой-то объектной форме, такой как строки.
Пусть они являются строками с длиной символа, большей, чем диапазон BigInteger.
В этом случае я буду выполнять арифметическую операцию так, как мы это делаем на ноутбуке. Например, предположим, что мы должны сделать дополнение. Начните с сравнения двух строк для длины. Сделайте три новые строки. Первая строка меньше. Вторая строка является самой правой подстрокой длинной строки с длиной, равной меньшей строкой. Третья строка - оставшаяся длинная строка с левой стороны. Теперь добавьте первую и вторую строки из конца, преобразуя символы в целые числа, по одному символу за раз и сохраняя перенос в переменной int. Сразу же после каждого добавления добавьте сумму в StringBuffer. После добавления двух строк выполните ту же операцию для третьей строки и продолжайте добавлять перенос. В конце отмените StringBuffer и верните String.
Вот код, который я использовал для добавления
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;
}