Форум программистов, компьютерный форум, киберфорум
Люк Кио
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Быстрый алгоритм корня

Запись от Люк Кио размещена 14.05.2020 в 17:56

Если находить арифметический корень с помощью степенного ряда Урала в области бэтта-1, можно использовать величину «p» для ускорения сходимости.
Нажмите на изображение для увеличения
Название: sqrN01.jpg
Просмотров: 788
Размер:	115.5 Кб
ID:	6235
Если рассматривать любой частный случай, всегда можно подобрать «p» таким, чтобы ряд сходился значительно быстрее, чем даже самый быстросходящийся, из всех известных сегодня алгоритмов нахождения корня, частным случаем которого является итерационная формула Герона.
Этот метод до сих пор оставался лидером по скорости сходимости. Но у этого метода, как, впрочем, практически у всех методов тыка есть один недостаток – необходимость повторять ресурсоёмкие операции над каждым следующим членом. В данном случае, брать в степень большое число - каждый предыдущий член. Кроме гибкости, позволяющей снизить количество шагов, т.е. обогнать всех по скорости сходимости, дополнительное преимущество Урала бэтта-1 заключается в том, что ему не нужно на каждом шаге вычислять факториал, или возводить большое число в степень. Каждый следующий член вычисляется умножением предыдущего на большое число и делением на маленькое. Т. е. фактически для любой степени над числом любой длины гибкость Урала позволяет получать результат за более короткое время, чем любым другим известным сегодня методом. С меньшим числом членов и с меньшим числом ресурсоёмких операций над ними.
Но чтобы сделать универсальный алгоритм для любой степени над любым числом, нужно учитывать различные нюансы и делать перепроверки. Все эти подготовительные работы делаются маленькими числами. Поэтому в целом весь метод можно сделать самым быстрым для применения в работе с большими числами. Возможно, когда-нибудь и найдётся программист, который так и сделает. Пока что мы можем показать лишь самые простые ухищрения, до которых нам удалось додуматься.
Нажмите на изображение для увеличения
Название: sqrN01.jpg
Просмотров: 788
Размер:	115.5 Кб
ID:	6235
Чтобы ряд сходился, нужно, чтобы q/mp<1, чем ближе к нулю, тем быстрее сходимость. Для любого «t» можно подобрать такое «p», чтобы эта дробь была менее 0,1. Но при этом нам нужно будет извлечь корень этой же степени из числа «p». Определяем наиболее ускоряющее сходимость число «p» маленькими числами, округляем до 3-4 цифр, и уже это короткое число возводим в степень.
В теории всё просто, но на практике сложнее. Этот ряд подходит и для степени, и для корня, и для t>1 и для t<1, и для целых, и для дробных степеней. В каждом случае, чтобы находить наиболее подходящее «p», нужен свой подход. Рассмотрим только целые степени корней, при t>1.
если t<1, t=1/f(1/t)
если t>2^53, сперва уменьшить степень на km, в конце увеличить на k
или сперва разделить на K^m, в конце умножить на K
e=B.length+E;if(e>15){k=(e/m).int;if(k){E-=km;t=f(t);E+=k}else{K=2^(m);t =2f(t/K)}return t}
Нажмите на изображение для увеличения
Название: sqrN02.jpg
Просмотров: 797
Размер:	14.6 Кб
ID:	6236
Оставляем z цифр, но не менее двух. Чем меньше цифр, тем быстрее возведение в большую степень. Но на некоторых участках двух цифр может быть недостаточно, чтобы q<p. В целом можно использовать такой простой алгоритм. Начальное z=3. Не считая первой цифры, оставляем z цифр после первой ненулевой. Например, 1.001001023 = 1.001, 0.0907123=0.0907. Красным отмечены операции с маленькими числами. Синим – с большими.
Нажмите на изображение для увеличения
Название: sqrN03.jpg
Просмотров: 786
Размер:	14.3 Кб
ID:	6237
G – это требования к чистоте на участках. Можно сделать его и равным одному, но тогда будут такие зоны, в которых q/p близки к единице, т. е. сходимость будет медленная. В единичных вычислениях скорость вообще неважна, а в среднестатистических эти зоны занимают немного места. Для чистоты быстросходимости лучше делать G=2, ещё лучше G=10. Но в других зонах, где и без того чисто придётся лишний раз увеличивать z, и неизвестно, будет ли игра стоить свеч. Здесь тоже нужен дополнительный алгоритм, решающий в каждом конкретном случае, что лучше. Мы пока оставили G=1 для всех случаев, и не жалуемся.
Нажмите на изображение для увеличения
Название: sqrN04.jpg
Просмотров: 787
Размер:	47.9 Кб
ID:	6238
Этот алгоритм проверен до степени корня = 100, над числами от 1e-40 до 1e+40 при длине чисел = 150 цифр.
Наша экспедиция держит курс на полиномы, а не на арифметические корни. Поэтому дальнейшим развитием этого метода мы пока заниматься не можем. Инструменты лаборатории (программного обеспечения) нашей экспедиции больше похожи на хакерство, чем на математику. С той точностью, которую даёт js, мы выжали из Урала и из западного фронта (методы фомки), всё что могли. Сейчас лабораторию переоборудуем на большие числа. Так как многие инструменты работают медленно даже с маленькими числами, требования к скорости алгоритмов больших чисел для нас очень актуальны. Если кто-то доведёт этот метод до совершенства, мы будем рады сотрудничеству.
Просмотров 146 Комментарии 2
Всего комментариев 2
Комментарии
  1. Старый комментарий

    Чем проще уравнение, тем проще ваша жизнь

    Уважаемый Люк Кио,
    мне всё-таки непонятно рассмотрение вами общего уравнения https://www.cyberforum.ru/cgi-bin/latex.cgi?sx^m+px^n+q=0
    В математике принято уменьшать число параметров. В данном случае вместо пяти параметров легко обойтись тремя.
    В самом деле, пусть x = kz, тогда получим уравнение https://www.cyberforum.ru/cgi-bin/latex.cgi?(sk^m)z^m+(pk^n)z^n+q=0
    И полагая, что https://www.cyberforum.ru/cgi-bin/latex.cgi?s=k^{-m} и https://www.cyberforum.ru/cgi-bin/latex.cgi?p=k^{-n} получим следующее уравнение https://www.cyberforum.ru/cgi-bin/latex.cgi?z^m+z^n+q=0
    Согласитесь, последнее уравнение (имеет три параметра) гораздо проще того, что вы изучаете...
    Запись от wer1 размещена 15.05.2020 в 17:03 wer1 вне форума
  2. Старый комментарий
    Аватар для Люк Кио

    Чем проще уравнение, тем проще ваша жизнь

    Цитата:
    Сообщение от wer1 Просмотреть комментарий
    Уважаемый Люк Кио,
    мне всё-таки непонятно рассмотрение вами общего уравнения https://www.cyberforum.ru/cgi-bin/latex.cgi?sx^m+px^n+q=0
    В математике принято уменьшать число параметров. В данном случае вместо пяти параметров легко обойтись тремя.
    В самом деле, пусть x = kz, тогда получим уравнение https://www.cyberforum.ru/cgi-bin/latex.cgi?(sk^m)z^m+(pk^n)z^n+q=0
    И полагая, что https://www.cyberforum.ru/cgi-bin/latex.cgi?s=k^{-m} и https://www.cyberforum.ru/cgi-bin/latex.cgi?p=k^{-n} получим следующее уравнение https://www.cyberforum.ru/cgi-bin/latex.cgi?z^m+z^n+q=0
    Согласитесь, последнее уравнение (имеет три параметра) гораздо проще того, что вы изучаете...
    Уменьшать число параметров принято не во всей математике, а в лишь в редких конкретных ситуациях. После предложенных вами упрощений (вертикального и объёмного сжатия, которые, жаль что вы не заметили, описаны в свойствах этого ряда) вы теряете возможность использовать удалённые вами параметры для других целей. Одна из которых, тоже жаль что вы не заметили, как раз и описана в этом блоге. После вашего упрощения, из такой формулы можно получить только обычный ряд корня, выведенный Ньютоном несколько столетий назад.
    Законный вопрос кому нужна такая кастрация? Она уже давно всем известна и не применяется из-за низкой производительности. Вероятно вы не читаете тему в которой ставите свои комментарии. Это считается дурным тоном.
    Посмотрите как это выглядит со стороны.
    Люди говорят об одном. Вы подходите и вставляете что-то совсем несусветное. Только потому что в нём есть такое же слово, которое вы услышали из их разговора. Возьмите себя в руки. Вы же джентльмен.
    Никто не спорит с вами, что тяга к простоте - это прекрасно. Но если вы всё таки прочитаете эту тему, вы сами увидите, до какой степени абсурдное предложение вы сделали.
    После того, как всё поймёте, дайте мне знать, чтобы я удалил эту тупость со своего блога.
    Весь смысл этой темы именно в той величине, которую вы советуете сократить. Я мог бы понять любую глупость, но это уже просто идиотизм какой-то.
    Запись от Люк Кио размещена 15.05.2020 в 18:36 Люк Кио вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.