Привет.

Из курса численных методов и архитектуры FPU, я помню что железо имеет встроенный расчет
натурального логарифма.

1) Кто знает какой метод реализован под капотом? Сходу я замечу что "лобовые" методы такие как ряды Тейлора-Лорана
я обдумывал. Но возможно они не подойдут из-за наличия высоких степеней в которые нужно возводить x (см. дальше почему)

Нужна хитрость. Возможно методы основанные на последовательных приближениях.

Вот про эту хитрость я и спрашиваю.

2) В топиках простых чисел я неоднократно сталкивался с расчетом натруального логарифма для числе разрядностью
в 512 и более бит. И возникла необходимость считать с точностью выше чем double(64bit) т.к. в противном случае
мы теряем младшие разряды.

Тоесть если я к примеру беру натруальный логарим от рандомного числа с разрядностью 512 бит то я и ожидаю
что следующая проверка будет близка к точности длинных целых чисел. Например:

Можем-ли мы применить Метод Ньютона? В этом случае мы переворачиваем график относительно диагонали
и ищем решение пересечения экспоненты с осью OX.

Соколинский Борисmayton,
Хитрость тут, по-моему лежит на поверхности.

Нужно привести к виду
,
где A-"удобное" число, из которого извлекается целый логарифм, B<1. Второе слагаемое считаем в лоб, сходится будет очень быстро.
С натуральным вычислить A неудобно, проще перевести в двоичный, и тогда это ближайшая степень двойки.
Какое удобное число А вы предложите?

Aklinmayton1) Кто знает какой метод реализован под капотом?

Есть же стандарт IEEE-754 для таких вопросов, там емнип должно быть описано какой метод в итоге реализован.
Пока не нашел. Стандарт описывает только формат представления числа.
То что я спрашиваю - скорее всего архитектура со-процессора или численные методы мат-библиотек.

Но если вы знаете линк - прошу скинуть.

Скачал один док The Computation of Transcendental Functions on the IA-64 Architecture. Почитаю.

Dima Tmayton, ИМХО в железе нет супералгоритмов, подозреваю что там решено по принципу "лишь бы было", это не та задача куда надо кучу бабла вложить
Ты ошибаешься. Это очень дорогая задача.

В свое время Intel бесплатно менял процессоры на новые тем клиентам которые пострадали от ошибки в FPU. Даже при том что эту ошибку долго не замечали в расчетах.

exp98,

Дорогой друг. Была пятница. Я хоть и активный мамбер но тоже могу завтыкать. Надеюсь мне простят эту слабость.

exp98Так ли нужны сами логарифмы?
2 контрольных вопроса:
а) правильно понял, что нужно выражение b/ln(b) - a/ln(a) ?
Да. Логарифм это не главное. Главное - получить численную оценку.

Стоп. Пока я не кинулся очертя голову считать толстые логарифмы.

Я не исчерпал возможности double. По экспоненциальной сетке он доходит лишь до 1.7*10^308.
Мы ищем Хи-криптографическое (о котором я писал в другом тематическом топике) до 2^2048.
Для сравнения прологарифмирую оба числа.




Хи-крипотграфическое - больше.

Помимо стандартного double имеет под-виды.
- long double (extended) 80bit
- binary128 (Quadruple precision) 128 bit
- binary256 (Octuple precision) 256 bit

extended теоретически поддерживается GCC/Clang компилляторами поэтому играя настройками
и типами данных я думаю что этот злосчастный логарифм я смогу посчитать приближенно
без дополнительных делений.

На long double. Эффективно мне удасться посчитать только на числах менее 64бит по мантиссе. Если подставлять
более длинные числа то мантисса режет младшие разряды и сложение с 50 000 000 может быть грубее и грубее
соотв. с ростом выхода за пределы мантиссы.

Wiki пишет разную информацию по разрядности. Она может плавать. Visual C++ может вообще long double
проигнорировать и считать его синонимом double.

Мой GCC gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1) показывает 16 байт == 128 бит. Это неожиданно.
Я предполагал что будет 80. Это странно надо поразбираться.
На других компиллерах возможно будет другой эффект.

В таком случае __float128 должен быть бинарно совместим с long double однако мне пока его не удается распечатать
на экране с корректным форматированием.

Вот этот дефект. После возведения 2 в 128 степень результат уже не отличается от сложения с 50 лимонами.

size(16) - скорее всего фейк. Там по идее должно быть 80 бит или 10 байт. А 16 это возможно результат
такого себе padding.

для __float128 функция логарифма скорее всего не определена в стандартных либах. Надо искать нестандартные.

О. Крутяк. Я уже из буста на нее по линкам вышел.

Надо Усова протестировать. Он насчитал 7134 простых чисел на интервале от 2^200 +1 до 2^200 + 1 + 1 000 000.
Есть у меня сомнения что там все корректно. Эта арифметика длинных чисел... Вобщем нужен какой-то общий тест.



Единичкой можно пренебрегать. Но этот лимон учесть надо. Он определяет количество простых. Функция - приближенная
ясен пень. Но другого нет.

Если неосилим - попробуем Монте-Карло.

И как они прогарантировали точность результата? 128 десятичных это грубо 2048 бит.
Перебор делителей уже нелетает. Снова пробабаблистик? И кого мы проверяем? Их или себя?

Gennadiy UsovКак у Высоцкого:
"Возьмите мне один билет до Монте-Карло".
Да вы - романтик. А я думал - законченный учёный сухарь

Хм... да возможно. Но суть не меняет.

Хм... Может свести его к основанию 2?
Будет точный расчет в некоторых точках.
А интервалы - интерпольнем через кубические полиномы.

Какое свое?

Он уже назвал. Его число больше.
Значит ты пропустил числа.

Смотри. В программировании принято покрывать разработки тестами.
Если ты написал код но нет никаких asserts которые доказывают что твой код
корректен - то такой код не считается надёжным или достоверным.

Просмотр кода глазами не является доказательством правоты. Поэтому я апелирую к общим
числовым метрикам которые удалось найти. А именно к количеству простых на интервале
которое мы (приближенно можем посчитать по формуле).

Тот факт что на малых простых твой алгоритм совпал с моим PBFA (полный перебор делителей с кешом простых)
- это просто совпадение. Это ... как сломанные часы которые 2 раза в сутки могут показать точное время.
Это я не принимаю в качестве доказательства правоты. Предметная область с которой мы работаем
интересна в области сверх-больших чисел (хи-криптографическое) и там-же эта предметная область
имеет пробелы в части алгоритмов и извесных данных. Таблиц простых чисел в этой области нету.

Мой PBFA не работает в области хи. Он - только до 64-битных целых.

Я не хочу говорить что ты 100% неправ. Просто у меня есть сомнения.

И я хочу чтобы мои сомнения были развеяны участниками топика и тобой.

Gennadiy Usov,

ты как почтальон Печкин. Типа у меня есть посылка - только я вам ее не отдам.

Давай предположим что я взял 2 больших простых числа в районе от 1023 до 1024 бит. И перемножил их.
Получил составное число длиной 2048 бит. И опубликовал его здесь. И заявляю что оно - простое.

Как вы можете меня опровергнуть?

А если я действительно подставлю 1 большое 2048 битное простое?

exp98maytonОн уже назвал. Его число больше. Не, рмужики, я полагал, что усовское число оценочное, примерно способом как у меня , а выходит, что если и оценочное, то совсем другим способом. Но он же не раскрывает свой секрет.
Внимание! я писал, что ОЦЕНИВАЛ разность (b/Ln b-a/Ln a). Кроме того, они заведомо выше истинного значения в силу линейности приближения (но незначительно). Мои значения не служат основанием для обвинений. Можно только прикинуть интервал погрешности самой формулы и увидеть, что на больших числах теоретическая погрешность даже если она в 0,5% - это гигантская погрешность.
Только если программно вычисленное кол-во БОЛЬШЕ верхней границы погрешности, тогда можно говорить, что прога с ошибкой. И только тогда.

Специально для Усова: я всё писал по памяти, поэтому мог наврать. Сначала у меня было 7213". Только поэтому я подумал, что усовское значение кривое - слишком большое расхождение. Потом оформил всё регулярно в эксэлке, привлёк квадратичное слагаемое в производной, получилась оценка 7161,4. Но, повторю, моё число остаётся ЛИНЕЙНОЙ оценкой разности.

Так что,давайте жить дружно! (цэ)
Ты считал на калькуляторе. Давай я подключу Arbitrary-precsission типы данных с плавающей точкой. И посчитаем
пропорцию более точно. Ты по сути должен был считать один из катетов прямоугольного треугольника который лежит
гипотенузой на линейной апроксимации логарифмы. А второй катет == 1 000 000.