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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

Откуда:
Сообщений: 1831
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
Сообщений: 42852
Какое свое?
24 сен 19, 08:33    [21977486]     Ответить | Цитировать Сообщить модератору
 Re: Толстые натуральные логарифмы  [new]
Gennadiy Usov
Member

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-простое- 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596231637
-простое- 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596232273
24 сен 19, 12:52    [21977793]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4   вперед  Ctrl      все
Все форумы / Программирование Ответить