Улучшение способа извлечения кв. корня из больших чисел

[anwior]

Не хочу далее донимать своими вопросами в чужой теме: Поиск простых чисел.
Отвечайте мне здесь, пожалуйста!

tolstopuz в сообщении #666252 писал(а):

да какая там секунда...

http://code.activestate.com/recipes/577 ... -function/

def isqrt(x):
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return 0
    a, b = divmod(n.bit_length(), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

print(isqrt(int('1234567890'*30) ** 2))

Уважаемые nnosipov, tolstopuz
И первый, и второй коды мне ничего проясняют (смотрю на них как Баран на калитку).
Прошу ответить: какой диапазон вводимых знаков и необрезаются ли младшие разряды при завершении вычисления?

[nnosipov]

anwior в сообщении #666520 писал(а):

какой диапазон вводимых знаков и необрезаются ли младшие разряды при завершении вычислиния?

С диапазоном поэкспериментируйте сами. Вычисления точные, т.е. находится именно $[\sqrt{N}]$.

[Cash]

anwior,
предъявленные алгоритмы основаны на итерационном способе нахождения квадратного корня, известном еще древним грекам. А именно: последовательность $x_0=a$, $x_{n+1}=\frac 12(x_n+\frac{a}{x_n})$ очень быстро сходится к величине $\sqrt a$. Для обоснования этого метода можно заметить, что это есть не что иное, как метод Ньютона нахождения корня уравнения $x^2-a=0$.
Метод Ньютона имеет квадратичную скорость сходимости, или же, грубо говоря, порядок расхождения с искомым результатом каждого следующего значения уменьшается примерно в два раза. Т.е. для числа порядка $10^{600}$ потребуется около ... 10-15 итераций (начальное приближение требуется, правда, поточнее). В общем случае, если нам дано $N$-значное число, то число итераций будет порядка $O(\log N)$.
Далее рассмотрим насколько трудоемка одна итерация. У нас используется одна операция сложения, одна операция деления и одна операция деления пополам. Операции сложения и деления пополам (сдвиг на 1 бит) практически бесплатны, а вот операция деления достаточно трудоемка. Например, классический алгоритм деление уголком требует порядка $N^2$ операций. Но и здесь придумано множество быстрых алгоритмов со сложностью порядка $N\log N$. Любопытно, что одним из способов вычисления $a/b$ является поиск всё тем же методом Ньютона корня уравнения $\frac 1x= b$ с последующим "быстрым" умножением на $a$. Исследование показывает, что данный алгоритм требует всего лишь в 3 раза больше времени, затрачиваемого на умножение.
Итого на поиск квадратного корня из $N$-значного числа требуется порядка $O(N \log^2 N)$ элементарных операций (сложение, умножение однозначных чисел).
Стоит также отметить, что современное ПО работает с 64-битовой арифметикой, то бишь в системе счисления по основанию $2^{64}$, где ваше страшное $10^{650}$ имеет всего 34 знака. И проблем с извлечением корня у чисел порядка $10^{1000000}$ нет никаких.

[anwior]

Cash
Огромное СПАСИБО!
Ваша информация самодостаточна, исчерпывающа. Не смог сегодня пополнить сим-карту.
Завтра, (надеюсь) удастся предложить информацию достойную внимания для Вас и коллег.

[anwior]

Я не спасовал. Задержка связана с тщательной подготовкой набора аргументов.
Хочу прозондировать следующее:
Можно ли назвать ту или иную программу хорошей (эфектной), если в неё вводится
очень много (чересчур много и еще раз много) избыточных данных, но результат точен?
Отдаётся ли в этом случае предпочтение точности в ущерб увеличению используемой опер. памяти?

[Xaositect]

anwior
Поясните, пожалуйста. Мы хотим вычислить какую то функцию $F$ от параметра $x$, но алгоритм кроме $x$ принимает на вход какие-то еще значения? То есть на самом деле мы вычисляем какую-то другую функцию $G(x, y)$, которая равна $F(x)$, если мы правильно подберем $y$?

[arseniiv]

(Оффтоп)

anwior в сообщении #671166 писал(а):

эфектной

Скорее, эффективной.

[anwior]

Xaositect в сообщении #671201 писал(а):

anwior
Поясните, пожалуйста. Мы хотим вычислить какую то функцию $F$ от параметра $x$, но алгоритм кроме $x$ принимает на вход какие-то еще значения? То есть на самом деле мы вычисляем какую-то другую функцию $G(x, y)$, которая равна $F(x)$, если мы правильно подберем $y$?

Нет, алгоритм иных значений не принимает!
Мои вопросы исключительно в контексте данной темы.

arseniiv в сообщении #671201 писал(а):

Скорее, эффективной.

Я спрашивал об эфекте; и только. Я в Excel тоже эффективно вычисляю кв. корни.

[Xaositect]

Тогда что Вы имели в виду, когда говорили, что "в программу вводится много избыточных данных"? Приведите пример, пожалуйста.

[anwior]

(Оффтоп)

Xaositect в сообщении #671270 писал(а):

Приведите пример, пожалуйста.

Нет проблем.
Уявите, что эта тема есть наша алгоритм-машина. Машина запущена!
Изобрёвший её вводит "очень много избыточных данных", а именно:

anwior в сообщении #671166 писал(а):

Хочу прозондировать следующее:
Можно ли назвать ту или иную программу хорошей (эфектной), если в неё вводится
очень много (чересчур много и еще раз много) избыточных данных, но результат точен?
Отдаётся ли в этом случае предпочтение точности в ущерб увеличению используемой опер. памяти?

Состояние: машина ожидает ввода ответов--да, нет; --да, да; --нет, нет; --нет, да.
В зависимости от ввода 1 - ой из 4-ех пар, по соответствующему ветвлению начнёт что-то там делать. По окончании работы мы получим: полное описание анонсированного изобретения.

До нашей машины к пульту ввода добрался мистер К и ввёл чересчур много избыточных данных, а именно:

Xaositect в сообщении #671201 писал(а):

anwior
Поясните, пожалуйста. Мы хотим вычислить какую то функцию $F$ от параметра $x$, но алгоритм кроме $x$ принимает на вход какие-то еще значения? То есть на самом деле мы вычисляем какую-то другую функцию $G(x, y)$, которая равна $F(x)$, если мы правильно подберем $y$?

Машина поскрипела, позвенела, позеленела, .. но выдала ответ!

anwior в сообщении #671251 писал(а):

Нет, алгоритм иных значений не принимает!
Мои вопросы исключительно в контексте данной темы.

Состояние машины: ждущий режим! никто не знает какую из 4-ех пар (да, нет) выбрать для ввода.
Меж тем, мистер К опять у пульта ввода данных и на сей раз ввёл чересчур много и ещё раз много избыточных данных, а именно:

Xaositect в сообщении #671270 писал(а):

Тогда что Вы имели в виду, когда говорили, что "в программу вводится много избыточных данных"? Приведите пример, пожалуйста.

Похоже машина за-вис-ла!
А я говорил мистеру К, что все четыре ответа на его вопросы он увидел бы в:
полном описании анонсированного изобретения.

[arseniiv]

anwior в сообщении #671688 писал(а):

Состояние машины: ждущий режим! никто не знает какую из 4-ех пар (да, нет) выбрать для ввода.

Пусть она тогда по очереди выбирает каждую и отрабатывает, раз уж она их так ждала. 4 пары — не 10000 пар. (А если ей лень, пусть выберет всего одну пару случайным образом.)

[anwior]

arseniiv в сообщении #671716 писал(а):

anwior в сообщении #671688 писал(а):

Состояние машины: ждущий режим! никто не знает какую из 4-ех пар (да, нет) выбрать для ввода.

Пусть она тогда по очереди выбирает каждую и отрабатывает, раз уж она их так ждала. 4 пары — не 10000 пар. (А если ей лень, пусть выберет всего одну пару случайным образом.)

С таким советом надо стоять рядом с сапёром (опытный Вас пошлет, неопытный, возможно, клюнет), который обезвреживает ядерную бомбу.
Я могу ошибиться, но в первом случае думаю результат будет эффективный, в другом -- эфектен!
А ежели серьезно-- дайте ответы на мои два вопроса.

[arseniiv]

Мне-то вообще всё равно, но пусть будет (нет, да). Подходит, или другой ответ сгенерировать?

[anwior]

arseniiv в сообщении #671936 писал(а):

Мне-то вообще всё равно, но пусть будет (нет, да). Подходит, ...?

Подходит! Вариант очень приемлем для меня.

arseniiv в сообщении #671936 писал(а):

... или другой ответ сгенерировать?

Спасибо! Больше не утруждайте себя.
Одно неказистое "но". Я ранее "забыл" озвучить:
Вы имеете право молчать. Всё сказанное Вами может быть использовано против Вас.
Сейчас ухожу на перерыв (1-2 часа), а вернувшись -- выполню обещанное.
Сим-карту даже заранее пополнил.

[anwior]

"anwior'' ранее писал:
Сейчас ухожу на перерыв (1-2 часа), а вернувшись -- выполню обещанное.
Сим-карту даже заранее пополнил.
Не вкладываюсь в сроки. Приношу извинения. Вчера вдруг вспомнил, что не рассмотрел такой важный аспект, как приложение способа к извлечению корней кубических и выше. Стараюсь оперативно наверстать упущенное.

-- Ср янв 16, 2013 10:11:41 --

(Оффтоп)

Какая падлюка колдует здесь одновременно при редактировании?
Обьявись и згинь навеки.