Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
 Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Привет.

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

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

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

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

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


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

exp(ln(x)) = x


Сообщение было отредактировано: 20 сен 19, 12:28
20 сен 19, 11:44    [21975074]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы.  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10988
mayton,
Хитрость тут, по-моему лежит на поверхности.

Нужно привести к виду
,
где A-"удобное" число, из которого извлекается целый логарифм, B<1. Второе слагаемое считаем в лоб, сходится будет очень быстро.
С натуральным вычислить A неудобно, проще перевести в двоичный, и тогда это ближайшая степень двойки.
20 сен 19, 11:56    [21975093]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы.  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Можем-ли мы применить Метод Ньютона? В этом случае мы переворачиваем график относительно диагонали
и ищем решение пересечения экспоненты с осью OX.
20 сен 19, 12:10    [21975119]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы.  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Соколинский Борис
mayton,
Хитрость тут, по-моему лежит на поверхности.

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

Какое удобное число А вы предложите?
20 сен 19, 12:12    [21975123]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы.  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59122
mayton
1) Кто знает какой метод реализован под капотом?


Есть же стандарт IEEE-754 для таких вопросов, там емнип должно быть описано какой метод в итоге реализован.

В целом я бы сказал что там табличные функции (основная таблица плюс приближения).

Есть софт-реализации (типа теста softfloat), которые сходятся со стандартом до бита.

Но это все в рамках ieee-754 разрядностей. Все что больше - на усмотрение разработчиков железа, насколько я думаю.
20 сен 19, 12:37    [21975178]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10988
mayton
Какое удобное число А вы предложите?
Я бы сначала перевел в двоичный, нашел ближайшую степень двойки, вычислил первое слагаемое, потом перевел обратно в натуральный и досчитал второе.
20 сен 19, 12:49    [21975200]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Aklin
mayton
1) Кто знает какой метод реализован под капотом?


Есть же стандарт IEEE-754 для таких вопросов, там емнип должно быть описано какой метод в итоге реализован.

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

Но если вы знаете линк - прошу скинуть.
20 сен 19, 13:32    [21975251]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48641
mayton
Кто знает какой метод реализован под капотом?

https://math.stackexchange.com/questions/61209/what-algorithm-is-used-by-computers-to-calculate-logarithms
20 сен 19, 13:36    [21975255]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Скачал один док The Computation of Transcendental Functions on the IA-64 Architecture. Почитаю.
20 сен 19, 17:34    [21975627]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1846
Так ли нужны сами логарифмы?
2 контрольных вопроса:
а) правильно понял, что нужно выражение b/ln(b) - a/ln(a) ?
б) разумна ли оценка этого выражения в 275 ? при а= 2^500, b= a+ 2*10^5 ?
20 сен 19, 20:37    [21975725]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1846
блин , на ln(2) надо было не умножать, а делить
Поправка в вопросе п.(б) :
оценка 577 + o((1/ln(a))^2) для b= 2^500 + 2*10^5

для b= 2^200 + 10^6 оценка разности = 7213,4752....

Годится?
20 сен 19, 21:03    [21975734]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Dima T
Member

Откуда:
Сообщений: 14096
mayton, ИМХО в железе нет супералгоритмов, подозреваю что там решено по принципу "лишь бы было", это не та задача куда надо кучу бабла вложить
20 сен 19, 21:10    [21975740]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1846
реакции 0,
а я ваш последний диапазон нашёл. Оценка разности
для b= 2^1024 + 200 000 равна 281,50147

Вообще, это нижние оценки и их можно улучшать.
Но я ещё погрешность не ту сказал, она для производной, её надо умножать на те самые маленькие диапазончики 200 000 и 10^6.
20 сен 19, 21:40    [21975759]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Dima T
mayton, ИМХО в железе нет супералгоритмов, подозреваю что там решено по принципу "лишь бы было", это не та задача куда надо кучу бабла вложить

Ты ошибаешься. Это очень дорогая задача.

В свое время Intel бесплатно менял процессоры на новые тем клиентам которые пострадали от ошибки в FPU. Даже при том что эту ошибку долго не замечали в расчетах.
21 сен 19, 08:35    [21975853]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
exp98,

Дорогой друг. Была пятница. Я хоть и активный мамбер но тоже могу завтыкать. Надеюсь мне простят эту слабость.
21 сен 19, 08:42    [21975855]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
exp98
Так ли нужны сами логарифмы?
2 контрольных вопроса:
а) правильно понял, что нужно выражение b/ln(b) - a/ln(a) ?

Да. Логарифм это не главное. Главное - получить численную оценку.
21 сен 19, 17:04    [21976013]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Стоп. Пока я не кинулся очертя голову считать толстые логарифмы.

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

2^2048 => 
  2048 * Ln(2) = 1419.565425786768

1.7976931348623157 * 10^308 => 
  Ln(1.7976931348623157 * 10^308) = Ln(1.7976931348623157) + 308 * Ln(10) = 709.782712893384


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

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

extended теоретически поддерживается GCC/Clang компилляторами поэтому играя настройками
и типами данных я думаю что этот злосчастный логарифм я смогу посчитать приближенно
без дополнительных делений.
21 сен 19, 21:12    [21976064]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1846
80bit декларировалось даже в старом ВС (я не проверял). Не помню, есть ли 128bit в 11g оракла. Но дело не в этом.
Пока ты в самом деле не кинулся их считать: В каких случаях это не нужно.
Это не нужно если диапазон вподне сносный для обычного подсчёта. 50 млн вполне себе.

Просто скажу, что усов-то уже сделал до меня оценку, а я зря трудился. Что там где-то расхождения в 1-50-10тыс - это ерунда. Важнее подсчитать точность оценочной формулы и контролировать именно этот +-.
21 сен 19, 22:07    [21976084]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1846
Оценки разности ,данные в таблице Усовым вполне можно использовать.
Поясню школьными рассуждениями. Скорее всего мы оба считали примерно одно.
Имеем ф-цию F=X/LnX в точках a,b, где dx= b-a (50млн, 1млн, 200тыс ...)
Т.е. доля dx/a пренебрежительно мала.

Производная F'= (Ln X - 1)/Ln^2 X
График F ассимптотически приближается к Х снизу, зачит F ещё и выпукла вверх.
Значит линейное приближение
dy= F(b)-F(a)= F'(a) dx + О(dx ^2)
будет верхней оценкой искомой разности (у меня была описка, что нижней оц.)
Кто забыл F'(a) = тангенсу наклона прямой.
Вот F'(a) dx я и подсчитал (правда на калькуляторе, поэтому и саму F'(a) без второго слагаемого, но даже это даёт ничтожное различие).

Согласно Тейлору коэфф-т при степени будет F''(a).
F''(x)= 1/X/Ln^2 X *(2/Ln X - 1)

Так что остаточный член в разложении = F''(a)/2 * dx ^2
dx ^2 / X пренебрежимо мал для ваших X= 2^200 и т.д. по сравнению с первой степенью разложения. Так что, пока это выполняется, тут всё хорошо. Надо смотреть точностные границы самой формулы для интереса.
21 сен 19, 22:36    [21976093]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
На 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 однако мне пока его не удается распечатать
на экране с корректным форматированием.
22 сен 19, 00:28    [21976116]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
+
long double primesIntervalLongDouble(long double a, long double b) {
    return b / log(b) - a / log(a);
}

double primesIntervalDouble(double a, double b) {
    return b / log(b) - a / log(a);
}

__float128 primeIntFloat128(__float128 a, __float128 b) {
    return 0.0; //b / log(b) - a / log(a);
}


int main(int argc, char* argv[], char* env[]) {

	__float128 f128=0.0;

	long double a = pow(2.0, 64.0);
	long double b = pow(2.0, 64.0) + 50000000.0;
	long double c = primesIntervalLongDouble(a,b);

	printf("\n");

	printf("a   = %Lf,    sizeof(a) = %li\n", a, sizeof(a));
	printf("b   = %Lf,    sizeof(b) = %li\n", b, sizeof(b));
	printf("res = %Lf\n", c);



	double aa = 1500000000.0;
	double bb = 1550000000.0;
	double cc = primesIntervalLongDouble(aa,bb);

	printf("\n");

	printf("a = %f,    sizeof(a) = %li\n", aa, sizeof(aa));
	printf("b = %f,    sizeof(b) = %li\n", bb, sizeof(bb));
	printf("res = %f\n", cc);



	return 0;
}


a   = 18446744073709551616.000000,    sizeof(a) = 16
b   = 18446744073759551488.000000,    sizeof(b) = 16
res = 1101695.343750

a = 1500000000.000000,    sizeof(a) = 8
b = 1550000000.000000,    sizeof(b) = 8
res = 2252774.751388
22 сен 19, 00:30    [21976118]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Вот этот дефект. После возведения 2 в 128 степень результат уже не отличается от сложения с 50 лимонами.

a   = 340282366920938463463374607431768211456.000000,    sizeof(a) = 16
b   = 340282366920938463463374607431768211456.000000,    sizeof(b) = 16
res = 0.000000
22 сен 19, 00:32    [21976119]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
size(16) - скорее всего фейк. Там по идее должно быть 80 бит или 10 байт. А 16 это возможно результат
такого себе padding.
22 сен 19, 00:38    [21976121]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
для __float128 функция логарифма скорее всего не определена в стандартных либах. Надо искать нестандартные.
22 сен 19, 00:41    [21976122]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Barlone
Member

Откуда:
Сообщений: 1348
https://www.mpfr.org/
22 сен 19, 08:47    [21976158]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
Все форумы / Программирование Ответить