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

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

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

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

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

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

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


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

exp(ln(x)) = x


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

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

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

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

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

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

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

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


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

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

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

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

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

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


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

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

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

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

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

Откуда:
Сообщений: 1843
блин , на 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

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

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

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

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

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

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

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

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

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

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

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

Я не исчерпал возможности 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

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

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

Откуда:
Сообщений: 1843
Оценки разности ,данные в таблице Усовым вполне можно использовать.
Поясню школьными рассуждениями. Скорее всего мы оба считали примерно одно.
Имеем ф-цию 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
Сообщений: 42891
На 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
Сообщений: 42891
+
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
Сообщений: 42891
Вот этот дефект. После возведения 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
Сообщений: 42891
size(16) - скорее всего фейк. Там по идее должно быть 80 бит или 10 байт. А 16 это возможно результат
такого себе padding.
22 сен 19, 00:38    [21976121]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

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

Откуда:
Сообщений: 1347
https://www.mpfr.org/
22 сен 19, 08:47    [21976158]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
О. Крутяк. Я уже из буста на нее по линкам вышел.
22 сен 19, 11:00    [21976179]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Aklin
Member

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

Но если вы знаете линк - прошу скинуть.
КСТАТИ!

я тут вспомнил.
Я ошибался выше.

Стандарт ничего не описывает по функциям.
Между разными ОС, даже на одной машине я ловил разные результаты, в зависимости от разрядности ОС.
А между разными машинами тем более.

Доходило до маразма, что пришлось заменять функции-константы на просто константы (например замерять log(2) на его бинарное представление).

А вообще почитай что-то вроде этого
http://www.jhauser.us/arithmetic/SoftFloat.html
23 сен 19, 13:11    [21976775]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
mayton
Вот этот дефект. После возведения 2 в 128 степень результат уже не отличается от сложения с 50 лимонами.
Ну мы же и говорили, что длина диапазона пренебрежимо мала, и прибавка в 1 или неск. единиц не существенна. Только на этих , больших, дальостях.
Насчёт оценки ассимптоотики x/log x особо не искал, есть точные неравенства 80-х годов
]x/(lnX + 2); x/(lnX -4)[ для x от 55 и т.п.
или
]а*x/lnX; А*x/lnX[ где а=0,92.... А= 0,05...
23 сен 19, 13:24    [21976795]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
А= 1.05...
23 сен 19, 13:25    [21976798]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

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



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

Если неосилим - попробуем Монте-Карло.
23 сен 19, 16:14    [21977058]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
Надо Усова протестировать. Он насчитал 7134 простых чисел на интервале от 2^200 +1 до 2^200 + 1 + 1 000 000.
Есть у меня сомнения что там все корректно. Эта арифметика длинных чисел... Вобщем нужен какой-то общий тест.
Если неосилим - попробуем Монте-Карло.
Есть калькулятор,
"Империя чисел",
который проверяет на простоту до 128 цифр, а на факторизацию, до 60 цифр.

Как у Высоцкого:
"Возьмите мне один билет до Монте-Карло".
23 сен 19, 16:28    [21977068]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
И как они прогарантировали точность результата? 128 десятичных это грубо 2048 бит.
Перебор делителей уже нелетает. Снова пробабаблистик? И кого мы проверяем? Их или себя?
23 сен 19, 17:39    [21977142]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Gennadiy Usov
Как у Высоцкого:
"Возьмите мне один билет до Монте-Карло".

Да вы - романтик. А я думал - законченный учёный сухарь
23 сен 19, 17:44    [21977147]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
И как они прогарантировали точность результата? 128 десятичных это грубо 2048 бит.
А не 2^426?
23 сен 19, 18:13    [21977180]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Хм... да возможно. Но суть не меняет.
23 сен 19, 18:17    [21977187]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
mayton
Надо Усова протестировать. Он насчитал 7134 простых чисел на интервале от 2^200 +1 до 2^200 + 1 + 1 000 000.
Когда это он успел? Потому что не вту колонку написал? Тогда он и 2^500 b 2^1024 "успел".

Просто "7134" - кривая оценка. Даже я на калькуляторе точнее оценил. Вообще-то я их потом пересчитал в эксэлке с точной производной, именно 7134 кривая оценка. Только у меня это на другой машине, там что-то типа 72*** (но оценка сверху, как я уже выше рассказывал) . Ну да, "+1" игнорировали для простоты,но 1 млн уж был учтён.
23 сен 19, 19:47    [21977248]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
Продолжу.
1 млн для 2^200 достаточно приличная величина, поэтому погрешность повыше, чем дальше.
Я ещё для 7,5 млн оценил таким же способом, но погрешность уж очень большая, там в многие тысячи расхождения.

А вот проверить, выходит ли для 7,5 млн НАЙДЕННОЕ значение из неравенства, может теперь любой (погрешность формулы ~1-3 % для 2^500). Для для 2^1024 соответственно вдвое ниже,для 2^200 вдвое выше.

Но есть ещё лучше формула из тех же 80-х
]x/Ln x; x/(Ln x -2)[ при x от e^200 и при x [17; e^100].
Это даёт погрешность формулы в 0,5% для 2^500.

Я в уме прикинул, мог и наврать везде.
23 сен 19, 20:01    [21977252]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Хм... Может свести его к основанию 2?
Будет точный расчет в некоторых точках.
А интервалы - интерпольнем через кубические полиномы.
23 сен 19, 22:36    [21977358]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
exp98
mayton
Надо Усова протестировать. Он насчитал 7134 простых чисел на интервале от 2^200 +1 до 2^200 + 1 + 1 000 000.
Когда это он успел? Потому что не вту колонку написал? Тогда он и 2^500 b 2^1024 "успел".
Просто "7134" - кривая оценка. Даже я на калькуляторе точнее оценил.
Вообще-то я их потом пересчитал в эксэлке с точной производной, именно 7134 кривая оценка.
Только у меня это на другой машине, там что-то типа 72*** (но оценка сверху, как я уже выше рассказывал) .
Ну да, "+1" игнорировали для простоты,но 1 млн уж был учтён.
Самое интересное: число 7134 не то, а своё число не называет.

Я считал не по всем известным формулам, а по эвристическому алгоритму 21969065
(без учёта проверки на делители. Делители работают только до 2^67).
24 сен 19, 05:02    [21977447]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Какое свое?
24 сен 19, 08:33    [21977486]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
Какое свое?
Ведь было сообщение
exp98
Просто "7134" - кривая оценка. Даже я на калькуляторе точнее оценил. Вообще-то я их потом пересчитал в эксэлке с точной производной, именно 7134 кривая оценка. Только у меня это на другой машине, там что-то типа 72*** (но оценка сверху, как я уже выше рассказывал) . Ну да, "+1" игнорировали для простоты,но 1 млн уж был учтён.
И где число точнее?
24 сен 19, 09:18    [21977513]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Он уже назвал. Его число больше.
Значит ты пропустил числа.
24 сен 19, 09:58    [21977559]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
Он уже назвал. Его число больше.
Значит ты пропустил числа.
И сколько чисел пропустил?
24 сен 19, 11:10    [21977635]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

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

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

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

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

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

И я хочу чтобы мои сомнения были развеяны участниками топика и тобой.
24 сен 19, 11:28    [21977656]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
Я не хочу говорить что ты 100% неправ. Просто у меня есть сомнения.
И я хочу чтобы мои сомнения были развеяны участниками топика и тобой.
Как я уже ранее говорил, простоту числа, определяемую каким-нибудь тестом простоты,
может подтвердить только деление на множители!

Либо надёжность алгоритма теста простоты, в том числе эвристического алгоритма.

Вы можете оставаться в сомнениях ещё очень долго,
а тем временем получаемые простые (или псевдопростые) числа будут применяться.
24 сен 19, 11:38    [21977669]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Gennadiy Usov,

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

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

Как вы можете меня опровергнуть?
24 сен 19, 11:50    [21977694]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
Gennadiy Usov,
Давай предположим что я взял 2 больших простых числа в районе от 1023 до 1024 бит. И перемножил их.
Получил составное число длиной 2048 бит. И опубликовал его здесь. И заявляю что оно - простое.
Как вы можете меня опровергнуть?
Очень просто!

Подставляю это число длиной 2048 бит в эвристический алгоритм и получаю ответ:
число составное (т.е. программа скажет - нет простых чисел)

Кстати, а где число?
24 сен 19, 12:15    [21977731]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
А если я действительно подставлю 1 большое 2048 битное простое?
24 сен 19, 12:28    [21977749]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

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

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

Так что,давайте жить дружно! (цэ)
24 сен 19, 12:47    [21977782]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
А если я действительно подставлю 1 большое 2048 битное простое?
Испугал...

После числа 2**2048 - 1 на диапазоне 5000 чисел я нашёл 5 простых чисел.
Вот два из них
+

-простое- 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596231637
-простое- 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596232273
24 сен 19, 12:52    [21977793]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

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

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

Так что,давайте жить дружно! (цэ)

Ты считал на калькуляторе. Давай я подключу Arbitrary-precsission типы данных с плавающей точкой. И посчитаем
пропорцию более точно. Ты по сути должен был считать один из катетов прямоугольного треугольника который лежит
гипотенузой на линейной апроксимации логарифмы. А второй катет == 1 000 000.
24 сен 19, 13:00    [21977804]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
exp98
mayton
Он уже назвал. Его число больше.
Не, рмужики, я полагал, что усовское число оценочное, примерно способом как у меня, а выходит, что если и оценочное, то совсем другим способом. Но он же не раскрывает свой секрет.
Вы ещё и читаете плохо.

В сообщении 21977447 я Вам ответил, что считал по программе, указанной в ссылке.
Так что я скрываю?

А число простых чисел у меня не оценочное. а посчитанное согласно алгоритму21968895
(опубликовал согласно просьбе mayton)
24 сен 19, 13:01    [21977806]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
Выскажу со своей стороны, что имхо изучение кода экспертами является составной частью проверки программы на правильность.
Примерно так было с первым окончанием доказательства Большой Т.Ферма в 90-х (с привличением компа). С помощью эксперта нашлась ошибка (правда не помню в коде или в рассуждениях). Вторая попытка уже не вызвала возражений. Считается, что Т.Ф. доказана полностью.

Свою оценку для 2^200 я привёл выше, для больших можно оставить усовские - уменя почти один в один:
575,4
281,38,
для 1,5 млрд 2326984,54 (но здесь уже возрастает погрешность линейной оценки разности),
для 750 млн 2326984,54,
для 350 млн 2412313,
до 50млн линейная оценка совсем кривая 4085189.
24 сен 19, 13:03    [21977808]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
mayton
Ты по сути должен был считать один из катетов прямоугольного треугольника который лежит гипотенузой на линейной апроксимации логарифмы. А второй катет == 1 000 000.
Именно так.
24 сен 19, 13:06    [21977812]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
Gennadiy Usov
Вы ещё и читаете плохо. В сообщении 21977447 я Вам ответил, ...
Ошибаетесь, я не читаю плохо. Кое-какие посты я видел. Я, можно сказать почти не читаю (а эту тему ваще только в конце открыл), поскольку видел достаточное кол-во раз ваши многочисленные посты с ссылками, потом их опровержения с сыллками, потом опровержения на опрровержения и т.д. И не в одной только теме.
Поспешность нужна только при ловле блох (цэ), не только для хождения по ссылкам, но и для просто внимательного чтения.
24 сен 19, 13:13    [21977823]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Gennadiy Usov
После числа 2**2048 - 1 на диапазоне 5000 чисел я нашёл 5 простых чисел.
Ещё раз запустил программу для дополнительной оценки:

1. После числа 2**2048 - 1 простые числа расположены на расстоянии
982, 1618, 3064, 3212, 4144

2. Максимальное значение числа а1 равно 2 (запас - 15)

3. Программа считала на моём стареньком ПК 3 мин. 51сек.
24 сен 19, 13:15    [21977829]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
exp98
mayton
Ты по сути должен был считать один из катетов прямоугольного треугольника который лежит гипотенузой на линейной апроксимации логарифмы. А второй катет == 1 000 000.
Именно так.


Только не логарифм оценивался, а разность дробей, т.е. касательная проводилась к дроби
A/Ln A.
24 сен 19, 13:16    [21977832]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Да разность это пустяк.
24 сен 19, 13:17    [21977836]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
exp98
Gennadiy Usov
Вы ещё и читаете плохо. В сообщении 21977447 я Вам ответил, ...
Ошибаетесь, я не читаю плохо. Кое-какие посты я видел. Я, можно сказать почти не читаю (а эту тему ваще только в конце открыл), поскольку видел достаточное кол-во раз ваши многочисленные посты с ссылками, потом их опровержения с сыллками, потом опровержения на опрровержения и т.д. И не в одной только теме.
Поспешность нужна только при ловле блох (цэ), не только для хождения по ссылкам, но и для просто внимательного чтения.
Кстати, насчет торопливости...

Сначала спросите, если не понятно, а уже потом говорите, что что-то от Вас скрывают.
24 сен 19, 13:18    [21977842]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
exp98
Только не логарифм оценивался, а разность дробей, т.е. касательная проводилась к дроби
A/Ln A.
И число е было по памяти 2,718281828.
24 сен 19, 13:22    [21977850]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
Gennadiy Usov
Сначала спросите, если не понятно, а уже потом говорите, что что-то от Вас скрывают.
Опровержения контента по ссылке точно не будет? Зуб даёте на отсечение?
24 сен 19, 13:24    [21977853]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
mayton
Да разность это пустяк.
Зато именно она даже для больших чисел считается на калькуляторе достаточно точно в даблах. Беда только, что погрешность для разности ассимптотическиой формулы удваивается для разности.
24 сен 19, 13:28    [21977863]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
exp98
Gennadiy Usov
Сначала спросите, если не понятно, а уже потом говорите, что что-то от Вас скрывают.
Опровержения контента по ссылке точно не будет? Зуб даёте на отсечение?
Программа считает до и после 2**2048-1, и находит простые числа.
24 сен 19, 13:30    [21977866]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
Спешу слишком ... И как раз благодяря разности без потерь учитываются те самые небольшие диапазоны 50 тыс и 1 млн.
24 сен 19, 13:31    [21977868]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
Gennadiy Usov
exp98
пропущено...
Опровержения контента по ссылке точно не будет? Зуб даёте на отсечение?
Программа считает до и после 2**2048-1, и находит простые числа.
Жду зуб в банковской ячейке ...
24 сен 19, 13:34    [21977878]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
exp98
Gennadiy Usov
Сначала спросите, если не понятно, а уже потом говорите, что что-то от Вас скрывают.
Опровержения контента по ссылке точно не будет? Зуб даёте на отсечение?
Тороплюсь, забыл...

Я уже на форуме говорил, что на диапазоне с 5 до 1 000 000 000
все найденные эвристическим алгоритмом простые числа проверены на множители.

Кроме того, все "отброженные" (составные) числа проверены на отсутствие множителей.

Так что есть доказательства достаточности алгоритма на отдельно взятом диапазоне,
и этот алгоритм в виде эвристического можно распространить на все числа (нечётные).
24 сен 19, 13:40    [21977888]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
exp98
exp98
Только не логарифм оценивался, а разность дробей, т.е. касательная проводилась к дроби
A/Ln A.
И число е было по памяти 2,718281828.

Вот более точно https://ru.wikipedia.org/wiki/E_(число) до 1000 знаков.
24 сен 19, 14:20    [21977949]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
exp98
Gennadiy Usov
пропущено...
Программа считает до и после 2**2048-1, и находит простые числа.
Жду зуб в банковской ячейке ...

Поднимем ставки?

Могу поставить бутылку чего-то крепкого что Усов ошибается.
24 сен 19, 14:33    [21977964]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
exp98
Жду зуб в банковской ячейке ...
Поднимем ставки?
Могу поставить бутылку чего-то крепкого что Усов ошибается.
Это конечно хорошо, что ставки повышаются...

А кто рассудит?
24 сен 19, 14:38    [21977970]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Мы найдем хотя-бы 1 простое которое ты проеб.... пропустил. И будешь должен мне бутылку Jameson.
24 сен 19, 14:41    [21977973]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Или составное которое было учтено как простое. Это как раз вариант двух длинных множителей как я писал выше.
24 сен 19, 14:42    [21977974]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
Исходник программы со всеми библиотеками рассудит.
Или полное описание алгоритма + своя прога по нему.
24 сен 19, 14:44    [21977977]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
Gennadiy Usov
Так что есть доказательства достаточности алгоритма на отдельно взятом диапазоне, и этот алгоритм в виде эвристического можно распространить на все числа (нечётные).
Надеюсь, вы не собираетесь таким же способом решать проблему Гольдбаха.
24 сен 19, 14:47    [21977986]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
exp98
Исходник программы со всеми библиотеками рассудит.

А толку. Голый исходник еще ничего не значит. Это тоже самое
что решать "проблему останова" Алана Тьюринга.
24 сен 19, 14:48    [21977987]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Стороны высказали пожелания на тему: как отдать бутылку Jameson.

И что дальше?
Пш...
24 сен 19, 14:52    [21978000]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
mayton, ну понятно же, что + отладка, проверки, "метод аддитивности интервалов", тудемо-сюдемо ...
Кста, уж полночь близится, а зуба-то всё нет.
24 сен 19, 14:54    [21978007]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Gennadiy Usov, я на самом деле щас на работе. И кроме толстых логарифмов у меня еще есть актуальные задачи
которые приносят прибыль.

Поэтому будь терпелив. На серъезный investigation я щас не буду тратиться. Может ближе к вечеру. Или завтра.
24 сен 19, 14:54    [21978008]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
exp98
Gennadiy Usov
Так что есть доказательства достаточности алгоритма на отдельно взятом диапазоне, и этот алгоритм в виде эвристического можно распространить на все числа (нечётные).
Надеюсь, вы не собираетесь таким же способом решать проблему Гольдбаха.
Для меня не представляет интереса.

Это как недавно рассуждали о задаче 3-х кубах.

Нашли и что?

Тупой перебор, может быть ограничения какие-то есть, может быть и математика...
24 сен 19, 14:56    [21978013]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
exp98
mayton, ну понятно же, что + отладка, проверки, "метод аддитивности интервалов", тудемо-сюдемо ...
Кста, уж полночь близится, а зуба-то всё нет.

Зачем вам зуб? Нужна бутылка 40-градусного напитка.
24 сен 19, 14:56    [21978016]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
mayton, это аллегория, не Шейлок же я, в самом деле ...
24 сен 19, 14:59    [21978022]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
А-а-а, я понял! Нужен стимул в виде официального запроса на проверку от некого "авторитетного" лица. Тщеславие, оно всё такое тщеславительное ...
Или уже есть такой запрос))

Есть простейший тест - аддитивность по интервалам.
24 сен 19, 15:07    [21978047]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Или обратная связь по научным статьям в журналах.
24 сен 19, 15:08    [21978051]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
exp98
Member

Откуда:
Сообщений: 1843
вспомнилось, оффф
+
Но одна маленькая, но очень гордая птичка сказала: "Я полечу на Солнце!". И она поднималась фсё више и више ...
24 сен 19, 17:26    [21978271]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4      [все]
Все форумы / Программирование Ответить