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

[vicvolf]

Cash в сообщении #666607 писал(а):

anwior,
Стоит также отметить, что современное ПО работает с 64-битовой арифметикой, то бишь в системе счисления по основанию $2^{64}$, где ваше страшное $10^{650}$ имеет всего 34 знака. И проблем с извлечением корня у чисел порядка $10^{1000000}$ нет никаких.

После этого тема давно перешла в разговорный жанр, никого отношения к делу не имеющий. Попытки автора тема расширить ее усовершенствованием алгоритма извлечения корня n-й степени не имеют смысла, т.к. метод Ньютона успешно решает уравнение $x^n-a=0$ для достаточно больших n.

[anwior]

Полная цитата предыдущего сообщения удалена!

После этого тема давно перешла в разговорный жанр, никого отношения к делу не имеющий. Попытки автора тема расширить ее усовершенствованием алгоритма извлечения корня n-й степени не имеют смысла, т.к. метод Ньютона успешно решает уравнение $x^n-a=0$ для достаточно больших n.[/quote]
Ваше мнение базируется на старых известных укрепившихся знаниях о предмете. Однако, Вы даже не узнали от меня про новое знание про предмет, но заранее выдаёте категоричное -- не имеет смысла. Конфуз вышел. Крапка.

(Оффтоп)

Уважаемый vicvolf! Не бросайте, пожалуйста, окурки в унитаз!
Мне их расскуривать потом тяжело.
И все-таки, с уважением.

[anwior]

Ich fange an!
Хотя подготовка не доведена до желаемого, один момент кортит прояснить.

Тезис первый: все известные на сей день программы извлечения кв. корней из больших чисел
используют чересчур большую избыточную базу даных.
Подкреплю тезис примерами.
Пример 1. Пусть дано: N=1835151550729421589488969779578
777120720763266776645531725557755441596097921663776849 --85 дес. знаков.
Требуется найти: [\sqrt N].
Вот описание фактически исполненых решений двумя алгоритмами в общих чертах.

а) для получения 43-значного [\sqrt N], равного
1354677655654444456773988876555499000087543, в прогр. WolframAlpha необходимо было ввести 85 дес. знаков, то есть, число N ввести целиком.

б) для получения 43-значного [\sqrt N], равного
1354677655654444456773988876555499000087543, в Excel'е достаточно было воспользоваться лишь (вы верно подумали!) лишь 47 -ю дес. знаками старших разрядов в N. Остальные 38 знаков младших разрядов в N участия в "основной игре"
не принимают! Более того, их нет даже "на скамье запасных".

Вот второй пример, аналогичный пункту б) (теперь N приравнено к RSA-2048 с 617-ью дес. знаками):

в) для получения 309-значного [\sqrt N], равного
158732191050391204174482508661063007579358463444809715795726627753579970080

74994840427864325956810113267140205619002146475341948047281684064616857522262893467

1405739213477439533870489791038973166834068736234020361664820266987726919453356824

138007381985796493621233035112849373047484148399095287142097834807844, в Excel'е достаточно было воспользоваться лишь (вы вновь верно подумали!) лишь 317 -ю дес. знаками старших разрядов в N. Остальные 300 знаков младших разрядов в N участия в "основной игре" не принимают! Более того, их нет даже "на скамье запасных".

Судите, решайте, проверяйте! Опровергайте: говорите, что это вам давно известно; что это вы проходили; что приведенное не имеет смысла. Притом, приводите ссылки. Успехов Вам.
P. S. О других деталях расскажу позже.

[Cash]

anwior, скажите, пожалуйста, как вы думаете, а зачем этому WolframAlpha вообще нужно извлекать корни? А ведь этот гад еще из миллионзначного числа нам предлагает это делать. Я тут немного прикинул: если в него вводить по 3 знака в секунду (у меня быстрее не получается), то чтобы вбить туда это число потребуется четверо суток(!). Без перерыва на сон, обед и прочие радости жизни. А если на середине ошибешься и циферку пропустишь? Это ж вся работа насмарку. Ну и какой дурак согласится?

[tolstopuz]

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

а) для получения 43-значного [\sqrt N], равного
1354677655654444456773988876555499000087543, в прогр. WolframAlpha необходимо было ввести 85 дес. знаков, то есть, число N ввести целиком.

Это утверждение неверно.

В WolframAlpha достаточно ввести лишь 47 десятичных знаков старших разрядов этого числа и количество пропущенных разрядов - число 38.

IntegerPart(sqrt((18351515507294215894889697795787771207207632667+1)*10^38))

Result:
1354677655654444456773988876555499000087543

http://www.wolframalpha.com/input/?i=In ... 5E38%29%29

Остальные 38 знаков младших разрядов в N участия в "основной игре" не принимают! Более того, их нет даже "на скамье запасных".

[anwior]

Полная цитата предыдущего сообщения удалена!!

У Вас тоже верно! А вот что подтолкнуло tolstopuz'а к такому эксперименту (а был бы он вообще когда-нибудь проделан, он скромно не упомянул! Так держать!

[venco]

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

Всё правильно! А вот что подтолкнуло tolstopuz'а к такому эксперименту, он не упомянул! Так держать!

Это утверждение неверно. Упомянул:

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

Это утверждение неверно.

[anwior]

Полная цитата предыдущего сообщения удалена!!!

А может он за себя, а не Вы за него ответит?

[vicvolf]

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

А вот что подтолкнуло tolstopuz'а к такому эксперименту (а был бы он вообще когда-нибудь проделан, он скромно не упомянул! Так держать![/

Для того, чтобы никто не сомневался, в том числе и Вы, в сообщении дана ссылка.

-- 18.01.2013, 16:48 --

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

http://www.wolframalpha.com/input/?i=In ... 5E38%29%29

[anwior]

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

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

а) для получения 43-значного [\sqrt N], равного
1354677655654444456773988876555499000087543, в прогр. WolframAlpha необходимо было ввести 85 дес. знаков, то есть, число N ввести целиком.

Это утверждение неверно.

В WolframAlpha достаточно ввести лишь 47 десятичных знаков старших разрядов этого числа и количество пропущенных разрядов - число 38.

IntegerPart(sqrt((18351515507294215894889697795787771207207632667+1)*10^38))

Result:
1354677655654444456773988876555499000087543

http://www.wolframalpha.com/input/?i=In ... 5E38%29%29

Остальные 38 знаков младших разрядов в N участия в "основной игре" не принимают! Более того, их нет даже "на скамье запасных".

Cash
Разве tolstopuz не подтвердил улучшение? Ведь вместо 38 знаков, добавил несколько скобок, 4 цифры.

IntegerPart(sqrt((18351515507294215894889697795787771207207632667+1)*10^38))
Правда, смахлевал "со скамейкой запасных".
(домножил ведь на 10^{38}).
tolstopuz
Чего же не защищаетесь?

[Xaositect]

Проблема в том, что мы заранее не знаем, сколько знаков потребуется. Вот, скажем, для 78-значного числа 216424204356987207148983557079981380637369948278232037754581733673992251175059 потребуются все знаки.

[anwior]

Cash в сообщении #672993 писал(а):

anwior, скажите, пожалуйста, как вы думаете, а зачем этому WolframAlpha вообще нужно извлекать корни? А ведь этот гад еще из миллионзначного числа нам предлагает это делать. Я тут немного прикинул: если в него вводить по 3 знака в секунду (у меня быстрее не получается), то чтобы вбить туда это число потребуется четверо суток(!). Без перерыва на сон, обед и прочие радости жизни. А если на середине ошибешься и циферку пропустишь? Это ж вся работа насмарку. Ну и какой дурак согласится?

Какой дурак? Обьявите заоблачный стимул -- и я полмиллиона знаков согласен вводить. Только не в
WolframAlpha, а в что-то покруче и, главное, доступное.

-- Пт янв 18, 2013 16:29:46 --

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

Проблема в том, что мы заранее не знаем, сколько знаков потребуется. Вот, скажем, для 78-значного числа 216424204356987207148983557079981380637369948278232037754581733673992251175059 потребуются все знаки.

Первый предметный отклик! Спасибо!
Сейчас же проверю на своем алгоритме. Махлеж исключен. Отвечу правдиво.

[Xaositect]

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

Только не в
WolframAlpha, а в что-то покруче и, главное, доступное.

Насчет покруче не уверен, но вот Вам доступное: http://yadi.sk/d/_ZL7VKjN1xQpm
Для выхода из программы наберите quit.

[anwior]

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

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

Только не в
WolframAlpha, а в что-то покруче и, главное, доступное.

Насчет покруче не уверен, но вот Вам доступное: http://yadi.sk/d/_ZL7VKjN1xQpm
Для выхода из программы наберите quit.

Благодарю! При удобном случае поработаю с прогой.

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

Проблема в том, что мы заранее не знаем, сколько знаков потребуется. Вот, скажем, для 78-значного числа 216424204356987207148983557079981380637369948278232037754581733673992251175059 потребуются все знаки.

Пока- что умножением не проверил верность, но при 44 знаках получилось это:
465 214 148 921 748 947 217 489 218 947 218 748 916.
Я думаю, что всех знаках надобности нет и даже думаю, что 9, 10 дополнительных к искомому кол-ву знаков всегда приведут к успеху. Интуиция.

[Xaositect]

Я имел в виду, что корень из
216424204356987207148983557079981380637369948278232037754581733673992251175059 равен 465214148921748947217489218947218748916, а из
216424204356987207148983557079981380637369948278232037754581733673992251175053, например, - 465214148921748947217489218947218748915.
Мне интересно, как Вы эти числа отличаете.