В настоящее время я пишу функцию для нахождения квадратного корня из заданного BigInteger. Текущее число в моем тестовом файле — 250074134890485729738. Однако программа всегда останавливается, находя sqrt на 15813732488, что в квадрате равно 250074135202026670144. Я скопировал этот код из другой задачи StackOverflow, и он перестает сходиться с тем же номером. Он использует метод Ньютона, а я использую метод Вавилона/Герона.
Их код:
public static BigInteger sqrtN(BigInteger in) {
final BigInteger TWO = BigInteger.valueOf(2);
int c;
// Significantly speed-up algorithm by proper select of initial approximation
// As square root has 2 times less digits as original value
// we can start with 2^(length of N1 / 2)
BigInteger n0 = TWO.pow(in.bitLength() / 2);
// Value of approximate value on previous step
BigInteger np = in;
do {
// next approximation step: n0 = (n0 + in/n0) / 2
n0 = n0.add(in.divide(n0)).divide(TWO);
// compare current approximation with previous step
c = np.compareTo(n0);
// save value as previous approximation
np = n0;
// finish when previous step is equal to current
} while (c != 0);
return n0;}
Мой код:
static BigInteger number;
static BigInteger sqrt;
public static void main(String[] args) throws Exception {
number = new BigInteger(getFile());
System.out.println("Factoring: \n\n" + number);
sqrt = sqrt();
System.out.println("The root is: " + sqrt.toString());
System.out.println("Test, should equal nearest square at or above original number: " + sqrt.multiply(sqrt).toString() + "\nOriginal number: " + number.toString());
}
public static BigInteger sqrt() {
BigInteger guess = number.divide(new BigInteger("500"));
BigInteger TWO = new BigInteger("2");
BigInteger HUNDRED = new BigInteger("100");
boolean go = true;
while (number.subtract((guess.multiply(guess))).abs().compareTo(HUNDRED) == 1 && go){
BigInteger numOne = guess.divide(TWO);
BigInteger numTwo = number.divide(guess.multiply(TWO));
guess = numOne.add(numTwo);
if (numOne.equals(numTwo))
go = false;
System.out.println(guess.toString());
}
return guess.add(BigInteger.ONE);
Мой вывод:
Факторинг:
250074134890485729738
250074134890485979
125037067445243488
62518533722622743
31259266861313370
15629633430660684
7814816715338341
3907408357685169
1953704178874583
976852089501290
488426044878644
244213022695321
122106511859659
61053256953828
30526630524913
15263319358455
7631667871224
3815850319588
1907957927606
954044498302
477153309146
238838702566
119942872245
61013907968
32556274730
20118781556
16274333124
15820250501
15813733820
15813732478
15813732478
The root is: 15813732479
Test, should equal nearest square at or above original number: 250074134917379485441
Original number: 250074134890485729738
Пара замечаний:
- Когда я писал это, у меня было несколько идей, и я их опробовал. Если что-то не совпадает, это моя вина. Я проверил, но я не идеален.
- Хотя я ценю, что люди достаточно щедры, чтобы указать мне на другой кусок заранее написанного кода / опубликовать свой собственный, это (хотя и не школьная работа) является для меня опытом обучения. ПОЖАЛУЙСТА, опубликуйте, как этот код можно исправить, ПОЖАЛУЙСТА, НЕ публикуйте просто другой фрагмент кода, который делает то же самое.
ОТВЕТ: Это на самом деле работает как есть, исходный ввод просто не является идеальным квадратом. Таким образом, это прекрасно работает для моих целей. Спасибо всем, кто потратил свое время из-за моей некомпетентности. Я изменил код, чтобы он возвращал значение, эквивалентное (если Math.sqrt/ceil работал с BigInts):
sqrt = Math.Ceil(Math.Sqrt(A_RANDOM_BIGINTEGER_HERE));
Я также удалил ненужные переменные и обновил вывод, чтобы он соответствовал. Оба эти метода работают нормально, хотя для первого требуется некоторый код, чтобы поймать цикл неконвергенции, на случай, если какие-либо будущие посетители этого вопроса захотят их использовать.
BigInteger.ONE, TWO
и т. д. вместо создания новых каждый раз в цикле. - person user207421   schedule 08.01.2014