Есть ли библиотека, которая найдет квадратный корень BigInteger? Я хочу, чтобы он вычислялся в автономном режиме - только один раз, а не внутри любого цикла. Таким образом, даже дорогостоящее решение с калькуляцией в порядке.
Я не хочу найти какой-то алгоритм и реализовать. Легко доступное решение будет идеальным.
Я не знаю библиотечного решения для вашего вопроса. Вам придется импортировать решение для внешней библиотеки откуда-то. То, что я даю вам ниже, менее сложно, чем получение внешней библиотеки.
Вы можете создать собственное решение внешней библиотеки в классе с двумя статическими методами, как показано ниже, и добавить это в свою коллекцию внешних библиотек. Эти методы не обязательно должны быть методами экземпляра, поэтому они являются статическими и, как правило, вам не нужно указывать класс для их использования. Нормой для целых квадратных корней является значение пола (т.е. Наибольшее целое число, меньшее или равное квадратному корню), поэтому вам может понадобиться только один статический метод, метод пола, в классе ниже для значения пола и может выбрать чтобы игнорировать версию метода потолка (т.е. наименьшее целое число, большее или равное квадратному корню). Прямо сейчас они находятся в пакете по умолчанию, но вы можете добавить оператор пакета, чтобы поместить их в любой пакет, который вам удобнее.
Методы просты, и итерации сходятся к ближайшему целочисленному ответу очень, очень быстро. Они бросают исключение IllegalArgumentException, если вы попытаетесь дать им отрицательный аргумент. Вы можете изменить исключение на другое, но вы должны убедиться, что аргумент negatve вызывает какое-то исключение или, по крайней мере, не пытается выполнить вычисление. Целочисленные квадратные корни отрицательных чисел не существуют, так как мы не находимся в сфере мнимых чисел.
Они исходят из очень известных простых итеративных алгоритмов с квадратным корнем, которые использовались в ручных вычислениях на протяжении веков. Он работает путем усреднения завышения и недооценки для сближения с лучшей оценкой. Это может повторяться до тех пор, пока оценка не будет столь же близка, как желательно.
Они основаны на y1 = ((x/y0) + y0)/2, сходящихся к наибольшему целому числу yn, где yn * yn <= x.
Это даст вам значение пола для квадратного корня BigInteger, y, of x, где y * y <= x и (y + 1) * (y + 1) > x.
Адаптация может дать вам значение потолка для квадратного корня BigInteger, y, x, где y * y >= x и (y - 1) * (y - 1) х
Оба метода были протестированы и работают. Они здесь:
import java.math.BigInteger;
public class BigIntSqRoot {
public static BigInteger bigIntSqRootFloor(BigInteger x)
throws IllegalArgumentException {
if (x.compareTo(BigInteger.ZERO) < 0) {
throw new IllegalArgumentException("Negative argument.");
}
// square roots of 0 and 1 are trivial and
// y == 0 will cause a divide-by-zero exception
if (x .equals(BigInteger.ZERO) || x.equals(BigInteger.ONE)) {
return x;
} // end if
BigInteger two = BigInteger.valueOf(2L);
BigInteger y;
// starting with y = x / 2 avoids magnitude issues with x squared
for (y = x.divide(two);
y.compareTo(x.divide(y)) > 0;
y = ((x.divide(y)).add(y)).divide(two));
return y;
} // end bigIntSqRootFloor
public static BigInteger bigIntSqRootCeil(BigInteger x)
throws IllegalArgumentException {
if (x.compareTo(BigInteger.ZERO) < 0) {
throw new IllegalArgumentException("Negative argument.");
}
// square roots of 0 and 1 are trivial and
// y == 0 will cause a divide-by-zero exception
if (x == BigInteger.ZERO || x == BigInteger.ONE) {
return x;
} // end if
BigInteger two = BigInteger.valueOf(2L);
BigInteger y;
// starting with y = x / 2 avoids magnitude issues with x squared
for (y = x.divide(two);
y.compareTo(x.divide(y)) > 0;
y = ((x.divide(y)).add(y)).divide(two));
if (x.compareTo(y.multiply(y)) == 0) {
return y;
} else {
return y.add(BigInteger.ONE);
}
} // end bigIntSqRootCeil
} // end class bigIntSqRoot
Просто для удовольствия:
public static BigInteger sqrt(BigInteger x) {
BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2);
BigInteger div2 = div;
// Loop until we hit the same value twice in a row, or wind
// up alternating.
for(;;) {
BigInteger y = div.add(x.divide(div)).shiftRight(1);
if (y.equals(div) || y.equals(div2))
return y;
div2 = div;
div = y;
}
}
Я не могу проверить точность их, но есть несколько домашних решений, когда вы отправляетесь в поисковую систему. Лучшие из них, казалось, были такими: http://www.merriampark.com/bigsqrt.htm
Также попробуйте проект Apath commons Math (после того, как Apache восстановится после бомбардировки после сообщения в блоге JCP).
Мне нужно было иметь квадратный корень для BigIntegers для реализации квадратного сита. Я использовал некоторые из решений здесь, но самое быстрое и лучшее решение пока доступно из библиотеки Google Guava BigInteger.
Документацию можно найти здесь.
Как Jigar утверждает, Newton iteration является оба достаточно простые для понимания и реализации. Я оставлю его другим, решите, является ли он наиболее эффективным алгоритмом или нет для нахождения квадратного корня из числа.
С рекурсией это можно сделать примерно в двух строках.
private static BigInteger newtonIteration(BigInteger n, BigInteger x0)
{
final BigInteger x1 = n.divide(x0).add(x0).shiftRight(1);
return x0.equals(x1)||x0.equals(x1.subtract(BigInteger.ONE)) ? x0 : newtonIteration(n, x1);
}
Где n - это число, в котором мы хотим найти квадратный корень, а x0 - номер предыдущего вызова, который всегда будет равен 1 при первом вызове другого метода. Поэтому желательно, чтобы вы дополняли его чем-то вроде этого;
public static BigInteger sqrt(final BigInteger number)
{
if(number.signum() == -1)
throw new ArithmeticException("We can only calculate the square root of positive numbers.");
return newtonIteration(number, BigInteger.ONE);
}
Для первоначального предположения я бы использовал Math.sqrt(bi.doubleValue()), и вы можете использовать уже предложенные ссылки, чтобы сделать ответ более точным.
Это лучшее (и самое короткое) рабочее решение, которое я нашел
http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/
Вот код:
public static BigInteger sqrt(BigInteger n) {
BigInteger a = BigInteger.ONE;
BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
while(b.compareTo(a) >= 0) {
BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(BigInteger.ONE);
else a = mid.add(BigInteger.ONE);
}
return a.subtract(BigInteger.ONE);
}
Я тестировал его, и он работает правильно (и кажется быстрым)
BigDecimal BDtwo = new BigDecimal("2");
BigDecimal BDtol = new BigDecimal(".000000001");
private BigDecimal bigIntSQRT(BigDecimal lNew, BigDecimal lOld, BigDecimal n) {
lNew = lOld.add(n.divide(lOld, 9, BigDecimal.ROUND_FLOOR)).divide(BDtwo, 9, BigDecimal.ROUND_FLOOR);
if (lOld.subtract(lNew).abs().compareTo(BDtol) == 1) {
lNew = bigIntSQRT(lNew, lNew, n);
}
return lNew;
}
Я просто работал над этой проблемой и успешно написал рекурсивный квадратный корневой искатель в Java. Вы можете изменить BDtol так, как хотите, но это выполняется довольно быстро и в результате получило следующий результат:
Исходный номер 146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025
SQRT → 383123885216472214589586756787577295328224028242477055.000000000
Затем для подтверждения 146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025,000000000000000000
Альтернативный подход, который довольно лёгкий. Скорее всего, ответ Мэнтоно, который использует метод Ньютона, может быть предпочтительным для некоторых случаев.
Здесь мой подход...
public static BigInteger sqrt(BigInteger n) {
BigInteger a = BigInteger.ONE;
BigInteger b = n.shiftRight(1).add(new BigInteger("2")); // (n >> 1) + 2 (ensure 0 doesn't show up)
while (b.compareTo(a) >= 0) {
BigInteger mid = a.add(b).shiftRight(1); // (a+b) >> 1
if (mid.multiply(mid).compareTo(n) > 0)
b = mid.subtract(BigInteger.ONE);
else
a = mid.add(BigInteger.ONE);
}
return a.subtract(BigInteger.ONE);
}
Я только добираюсь до целочисленной части квадратного корня, но вы можете изменить этот грубый алгоритм, чтобы добиться гораздо большей точности, чем вы хотите:
public static void main(String args[]) {
BigInteger N = new BigInteger(
"17976931348623159077293051907890247336179769789423065727343008115"
+ "77326758055056206869853794492129829595855013875371640157101398586"
+ "47833778606925583497541085196591615128057575940752635007475935288"
+ "71082364994994077189561705436114947486504671101510156394068052754"
+ "0071584560878577663743040086340742855278549092581");
System.out.println(N.toString(10).length());
String sqrt = "";
BigInteger divisor = BigInteger.ZERO;
BigInteger toDivide = BigInteger.ZERO;
String Nstr = N.toString(10);
if (Nstr.length() % 2 == 1)
Nstr = "0" + Nstr;
for (int digitCount = 0; digitCount < Nstr.length(); digitCount += 2) {
toDivide = toDivide.multiply(BigInteger.TEN).multiply(
BigInteger.TEN);
toDivide = toDivide.add(new BigInteger(Nstr.substring(digitCount,
digitCount + 2)));
String div = divisor.toString(10);
divisor = divisor.add(new BigInteger(
div.substring(div.length() - 1)));
int into = tryMax(divisor, toDivide);
divisor = divisor.multiply(BigInteger.TEN).add(
BigInteger.valueOf(into));
toDivide = toDivide.subtract(divisor.multiply(BigInteger
.valueOf(into)));
sqrt = sqrt + into;
}
System.out.println(String.format("Sqrt(%s) = %s", N, sqrt));
}
private static int tryMax(final BigInteger divisor,
final BigInteger toDivide) {
for (int i = 9; i > 0; i--) {
BigInteger div = divisor.multiply(BigInteger.TEN).add(
BigInteger.valueOf(i));
if (div.multiply(BigInteger.valueOf(i)).compareTo(toDivide) <= 0)
return i;
}
return 0;
}
Язык С# имеет аналогичный синтаксис для Java. Я написал это рекурсивное решение.
static BigInteger fsqrt(BigInteger n)
{
string sn = n.ToString();
return guess(n, BigInteger.Parse(sn.Substring(0, sn.Length >> 1)), 0);
}
static BigInteger guess(BigInteger n, BigInteger g, BigInteger last)
{
if (last >= g - 1 && last <= g + 1) return g;
else return guess(n, (g + (n / g)) >> 1, g);
}
Назовите этот код следующим образом (в Java я предполагаю, что это будет "System.out.print" ).
Console.WriteLine(fsqrt(BigInteger.Parse("783648276815623658365871365876257862874628734627835648726")));
И ответ: +27993718524262253829858552106
Отказ от ответственности: я понимаю, что этот метод не работает для чисел менее 10; это метод квадратного корня BigInteger.
Это легко исправить. Измените первый метод следующим образом, чтобы дать рекурсивной части возможность дышать.
static BigInteger fsqrt(BigInteger n)
{
if (n > 999)
{
string sn = n.ToString();
return guess(n, BigInteger.Parse(sn.Substring(0, sn.Length >> 1)), 0);
}
else return guess(n, n >> 1, 0);
}
Упрощенный Джим ответил и улучшил производительность.
public class BigIntSqRoot {
private static BigInteger two = BigInteger.valueOf(2L);
public static BigInteger bigIntSqRootFloor(BigInteger x)
throws IllegalArgumentException {
if (checkTrivial(x)) {
return x;
}
if (x.bitLength() < 64) { // Can be cast to long
double sqrt = Math.sqrt(x.longValue());
return BigInteger.valueOf(Math.round(sqrt));
}
// starting with y = x / 2 avoids magnitude issues with x squared
BigInteger y = x.divide(two);
BigInteger value = x.divide(y);
while (y.compareTo(value) > 0) {
y = value.add(y).divide(two);
value = x.divide(y);
}
return y;
}
public static BigInteger bigIntSqRootCeil(BigInteger x)
throws IllegalArgumentException {
BigInteger y = bigIntSqRootFloor(x);
if (x.compareTo(y.multiply(y)) == 0) {
return y;
}
return y.add(BigInteger.ONE);
}
private static boolean checkTrivial(BigInteger x) {
if (x == null) {
throw new NullPointerException("x can't be null");
}
if (x.compareTo(BigInteger.ZERO) < 0) {
throw new IllegalArgumentException("Negative argument.");
}
// square roots of 0 and 1 are trivial and
// y == 0 will cause a divide-by-zero exception
if (x.equals(BigInteger.ZERO) || x.equals(BigInteger.ONE)) {
return true;
} // end if
return false;
}
}
вы также можете использовать бинарный поиск, чтобы найти квадратный корень из x также вы можете умножить его на, например, 10 ^ 10 и найти целое число, подобное m бинарным поиском, так как m ^ 2
System.out.println(m.divide(10^5)+"."+m.mod(10^5));Я изучал факторизацию и в итоге написал это.
package com.example.so.math;
import java.math.BigInteger;
/**
*
* <p>https://stackoverflow.com/questions/4407839/how-can-i-find-the-square-root-of-a-java-biginteger</p>
* @author Ravindra
* @since 06August2017
*
*/
public class BigIntegerSquareRoot {
public static void main(String[] args) {
int[] values = {5,11,25,31,36,42,49,64,100,121};
for (int i : values) {
BigInteger result = handleSquareRoot(BigInteger.valueOf(i));
System.out.println(i+":"+result);
}
}
private static BigInteger handleSquareRoot(BigInteger modulus) {
int MAX_LOOP_COUNT = 100; // arbitrary for now.. but needs to be proportional to sqrt(modulus)
BigInteger result = null;
if( modulus.equals(BigInteger.ONE) ) {
result = BigInteger.ONE;
return result;
}
for(int i=2;i<MAX_LOOP_COUNT && i<modulus.intValue();i++) { // base-values can be list of primes...
//System.out.println("i"+i);
BigInteger bigIntegerBaseTemp = BigInteger.valueOf(i);
BigInteger bigIntegerRemainderTemp = bigIntegerBaseTemp.modPow(modulus, modulus);
BigInteger bigIntegerRemainderSubtractedByBase = bigIntegerRemainderTemp.subtract(bigIntegerBaseTemp);
BigInteger bigIntegerRemainderSubtractedByBaseFinal = bigIntegerRemainderSubtractedByBase;
BigInteger resultTemp = null;
if(bigIntegerRemainderSubtractedByBase.signum() == -1 || bigIntegerRemainderSubtractedByBase.signum() == 1) {
bigIntegerRemainderSubtractedByBaseFinal = bigIntegerRemainderSubtractedByBase.add(modulus);
resultTemp = bigIntegerRemainderSubtractedByBaseFinal.gcd(modulus);
} else if(bigIntegerRemainderSubtractedByBase.signum() == 0) {
resultTemp = bigIntegerBaseTemp.gcd(modulus);
}
if( resultTemp.multiply(resultTemp).equals(modulus) ) {
System.out.println("Found square root for modulus :"+modulus);
result = resultTemp;
break;
}
}
return result;
}
}
Подход можно визуализировать следующим образом:
Надеюсь, это поможет!
Одна строка может выполнять работу, я думаю.
Math.pow(bigInt.doubleValue(), (1/n));