Новые форумы для: пользователей, администраторов, математиков и филологов.
2

Что-то sqrt у него не заметил.

задан 21 Фев 5:06

hitman249's gravatar image

hitman249
276
100% принятых

изменен 22 Фев 19:37

Angry%20Bird's gravatar image

Angry Bird
609310

Вообще пишу сканер для поиска корней в числах длинной от 9 - 100 цифр. Берётся число от 9 знаков и циклом проверяется на корни от 2 - 100 скорость критична.

(22 Фев 7:03) hitman249
3

Вот попытка найти решение в лоб (методом деления отрезка пополам)

import java.lang.Math;
import java.math.BigInteger;
public class BigRoot {
    public static BigInteger roots(BigInteger number, int power) throws Exception
    {
        Double d = number.doubleValue();
        BigInteger x1;
        if(Double.isInfinite(d)) {
            String strapprox = number.toString();
            x1 = new BigInteger(strapprox.substring(0, strapprox.length()/7));
        } else {
            String strapprox = String.valueOf(Math.exp(Math.log(number.doubleValue())/power));
            x1 = new BigInteger(strapprox.substring(0, strapprox.indexOf('.')));
        }
        BigInteger x2 = number.divide(x1.pow(power-1));
        switch (x1.compareTo(x2)) {
        case 0: return x1;
        case 1: {BigInteger w = x1;
            x2 = x1;
            x1 = w;
            break;
            }
        default: break;
        }
        while(x2.subtract(x1).compareTo(BigInteger.ONE) > 0) {
            BigInteger w = x1.add(x2).divide(BigInteger.valueOf(2));
            switch(w.pow(power).compareTo(number)) {
            case -1: x1 = w;
                break;
            case 0:  return w;
            case 1:  x2 = w;
                break;
            }
        }
        throw new IllegalAccessException(number.toString());
    }
}
ссылка

отвечен 1 Мар 16:09

alexlz's gravatar image

alexlz
3.4k15

3

Еще один вариант решения, покороче и несколько скоростнее. Выдает число b, для которого b*b = N. Используется итерационный алгоритм Ньютона: b=(b+N/b)/2.

    final BigInteger TWO = new BigInteger("2");

public BigInteger sqrt(BigInteger N)
{
    BigInteger result=N.divide(TWO);
    while(result.multiply(result).subtract(N).compareTo(BigInteger.ONE.divide(new BigInteger("100000000")))>0)
        result=result.add(N.divide(result)).divide(TWO);
    return result;
}
ссылка

отвечен 7 Мар 16:35

Selden's gravatar image

Selden
1164

compareTo(BigInteger.ONE.divide(new BigInteger("100000000"))

  • это настройка точности приближения. Если ее уменьшить, можно ускорить процесс вычисления, уменьшив количество итераций. Поэкспериментируйте. Главное - лишних объектов внутри корневычисляющего метода не создавайте, иначе засорите память.
(7 Мар 16:40) Selden
2

Вы можете написать код для вычисления квадратного корня самостоятельно. Например, используя простейший алгоритм. Если нужна большая скорость, есть и более оптимальные алгоритмы.

Образец:

public static BigInteger sqrt(BigInteger number, BigInteger trial)
{
    BigInteger result = BigInteger.ZERO;
    BigInteger a = result;
    BigInteger b = result;

    boolean first = true;

    while (result.compareTo(trial) != 0) {

        if (!first)
            trial = result;
        else
            first = false;

        result = number.divide(trial).add(trial).divide(BigInteger.valueOf(2));

        if (result.equals(b)) {
            return a;
        }

        b = a;
        a = result;
    }
    return result;

}
ссылка

отвечен 21 Фев 10:07

%D0%9F%D1%80%D0%B8%D0%B2%D0%B5%D1%82's gravatar image

Привет
7376

изменен 21 Фев 11:51

result = number.divide(trial).add(trial).divide(BigIntegerTWO);

Непонятно :( откуда поле BigIntegerTWO?) Что за метод divide?

И надо в такой последовательности читать: берем поле number, применяем метод divide, потом применяем метод add, потом применяем метод divide?

(21 Фев 11:44) spbsmile
1

Поправил, вместо BigIntegerTWO - BigInteger.valueOf(2). Читать слева направо.

(21 Фев 11:52) Привет

что делает trial ? какое значение не подаю, результат не меняет.
как сделать чтобы вычислялся разный корень вместо trial?

(27 Фев 12:14) hitman249

trial -- пробное значение. Чем ближе к значению корня, тем меньше итераций. Если уж очень хочется, то можно взять что нибудь типа

    String strapprox = String.valueOf(Math.sqrt(number.doubleValue()));
    BigInteger trial = new BigInteger(strapprox.substring(0, strapprox.indexOf('.')));

Но BigInteger.ONE -- тоже вполне себе приближение.

(28 Фев 8:43) alexlz

а что насчёт вычисления произвольных целочисленных корней?

(28 Фев 11:51) hitman249

@hitma249 Непонятен вопрос. Что значит "произвольные целочисленные корни" и чем не подходить функция от @Привет?

(28 Фев 11:57) alexlz

to alexlz тем, что кроме расчета квадратного корня он больше ничего не умеет.
поэтому особой ценности в коде нет, так как требуется подставлять разные корни для вычислений(кроме квадратных и кубических)

(28 Фев 13:01) hitman249

@hitman249 так что надо-то? Какие корни, какие числа (только положительные или нет), какой результат должен быть в случае, если целого корня n степени у числа нет? А то претензия к sqrt насчёт корней разных степеней весьма странная

(28 Фев 13:13) alexlz

to alexlz,
- если целого корня n степени у числа нет?
то ничего не выводить, или если нельзя так, выводить чтото вроде эксепшен
- только положительные или нет
и то и то(по сути не важно), главное чтобы это был целочисленный корень из целочисленного числа (если число НЕ целочисленное см. пукт первый).

(28 Фев 14:02) hitman249
показано 5 из 9 показать еще 4
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

ХэшКод - это совместно редактируемый форум вопросов и ответов для начинающих и опытных программистов.

Присоединяйтесь!

отмечен:

×1,473

задан
21 Фев 5:06

показан
224 раза

обновлен
7 Мар 16:40

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии