Только надо быть осторожным, потому что даже безобидные вещи вроде "double y=f(x); ... if (y==f(x))" могут работать неправильно (из-за промежуточных вычислений в 80-битных регистрах, насколько я понимаю).
Но согласен, что в некоторых случаях, например, бинарном или тернарном поиске, сравнение через эпсилон только навредит.
Во всех старых книгах для хранения размеров массивов и для организации циклов использовались переменные типа int. Так и делай. Не стоит нарушать традиции.
Если эта рекомендация предлагает использовать беззнаковый size_t, то тоже можно поспорить... Бесчисленное число багов связано с тем, что когда от нулевого значения size_t отнимают единицу, то получают число "бесконечность". Если мы говорим о среднестатистической программе, не собирающейся ворочать гигабайты памяти, и при этом слишком "ленивы", чтобы использовать честный ptrdiff_t или итераторы, то не лучше ли старый добрый int?
Google Style Guide тоже даёт рекомендацию в этом ключе, и даже ссылается на (правда, неназванных) членов комитета, считающих, что использование беззнаковых типов в стандартной библиотеке - это ошибка:
Because of historical accident, the C++ standard also uses unsigned integers to represent the size of containers - many members of the standards body believe this to be a mistake, but it is effectively impossible to fix at this point. <...>
The best advice we can provide: try to use iterators and containers rather than pointers and sizes, try not to mix signedness, and try to avoid unsigned types (except for representing bitfields or modular arithmetic).
Нет смысла проверять, удалось ли выделить память. На современных компьютерах её много. А если не хватило, то и незачем дальше работать. Пусть программа упадёт. Все равно уже больше ничего сделать нельзя.
На самом деле, даже если без шуток, это нормальный совет для большинства программ. Если мы не можем больше выделить нисколько памяти, то сделать что-то осмысленное - очень сложно, а выхлопа - мало, потому что, скорее всего, нам в любом случае надо завершиться. ОК, может быть, в каких-то редких случаях, например, если мы пишем какой-то системно-важный демон или пишем embedded софт, дополнительные усилия могут быть оправданы. Но в среднестатистической программе падать на OOM - это стандартная рекомендация.
Кстати, насколько я знаю, в Rust это стандартное поведение библиотеки - немедленное завершение при OOM. То же делает аллокатор в реализации Chrome.
For about a month everyone at Yale worked on it, with no result. A similar phenomenon happened when I mentioned it at the University of Chicago. A joke was made that this problem was part of a conspiracy to slow down mathematical research in the U.S.
(Примерный перевод: "Каждый в Йельском университете проработал над этой проблемой в течение месяца. Похожий фенонен наблюдался в Чикагском университете после того, как я упомянул о ней. Ходила шутка, что эта задача была частью заговора, имевшего целью затормозить математические исследования в США.".)
Нет, это совсем другое. В гипотезе Коллатца, например, из 11 переходим в 34, и оттуда в 17. Это гораздо более "рандомная" последовательность, чем +1 и /2. Полная последовательность, начиная с 11, будет выглядеть 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Преувеличивать надёжность Tor тоже не следует. От Sybil attack, насколько я знаю, полностью защититься не смогли. А совсем недавний пример - так называемый "KAX17":
KAX17 threat actor is attempting to deanonymize Tor users running thousands of rogue relays.
Since 2017, an unknown threat actor has run thousands of malicious Tor relay servers in the attempt to unmask Tor users.
<...> In May 2020, the threat actor managed to control over 380 Tor exit nodes, with a peak on May 22, when he controlled the 23.95% of Tor exit relay.
А в 2016 г. сооснователь сети приводил оценку вероятности в 2*10^-6 для атакующего, у которого всего лишь два узла под контролем. Я не знаю, повысили ли защиту от такой атаки с тех пор, но вот цитата:
At the most basic level, an attacker who runs two poisoned Tor nodes—one entry, one exit—is able to analyse traffic and thereby identify the tiny, unlucky percentage of users whose circuit happened to cross both of those nodes. At present (2016) the Tor network offers, out of a total of around 7,000 relays, around 2,000 guard (entry) nodes and around 1,000 exit nodes. So the odds of such an event happening are one in two million (1/2000 x 1/1000), give or take.
Спасибо за перевод, но насчёт "крутости" алгоритма - представленные данные не слишком убедительны...
БОльшая часть графиков - про сортировку рандомных данных, но ведь это и так общеизвестный факт, что существуют алгоритмы, которые отлично справляются именно с рандомными входными наборами. Например (первый же результат в гугле) - статья 2013 г. "Unisort: an Algorithm to Sort Uniformly Distributed Numbers in O(n) Time". Сравнения с этим и подобными специализированными алгоритмами нет.
В остатке - честный график, что на нерандомных входах предложенный "ska sort" проигрывает std::sort; в некоторых диапазонах - проигрывает с треском. А также нестадартный интерфейс ("ska sort" нельзя подключить как drop-in replacement, потому что она не умеет работать с компараторами) и отсутствие поддержки некоторых видов элементов.
Также вашему переводу противоречит статья с ADAC (это немецкий автоклуб):
Unbeschränkt ist die neue Freiheit freilich nicht. Sondern weil Mercedes hier die Verantwortung übernimmt, sind die Schwaben ziemlich vorsichtig: Bei Nacht und Nebel, ja sogar bei Nieselregen quittiert der Drive Pilot deshalb genauso den Dienst wie bei Temperaturen nahe des Gefrierpunktes, in Baustellen oder Tunnels. Und weil der Fahrer im Zweifelsfall mit einer Vorlaufzeit von maximal zehn Sekunden Vorwarnung wieder übernehmen muss, kontrolliert eine Infrarot-Stereo-Kamera im Fahrerdisplay ständig seine Einsatzbereitschaft.
Переводить я всё вручную здесь не буду, но можно обратить внимание на это: "weil Mercedes hier die Verantwortung übernimmt", что переводится как "поскольку "Мерседес" берёт здесь ответственность на себя".
Ваш перевод автоматизированный? Мои (конечно, ограниченные) познания немецкого говорят о том, что он неверен. Но вообще забавно, конечно - "казнить нельзя помиловать", получается, в статье написано.
Т. е., фактически, только в пробках? В нормальной ситуации (не пробка и не зона ремонта) такой маленькой скорости на автобане не может быть: рекомендуемая скорость по умолчанию 130, и даже если стоит типичное ограничение 120 - ехать там со скоростью 60 просто нельзя.
После перечитывания FIPS 186-4 (секция C.6) и поиска доп. информации по алгоритму Shawe-Taylor получилось выйти на упоминания алгоритма Maurer, который уже очень похож на то, что описано в статье ("Fast Generation of Secure RSA-Moduli with Almost Maximal Diversity", Maurer, 1989):
Lemma 1 suggests a method for constructing large primes. One can form the product F = product q_j^beta_j of some known primes q_j, raised to some powers beta_j, and repeatedly choose an integer R < F at random until n = 2RF + 1 can be proved to be prime by an appropriate choice of the base a. Lemma 3 shows that if n is indeed prime and if all q_j's are large, then virtually every base a can be used for certifying the primality of n. On the other hand, if n is composite but does not contain a small prime factor that allows to detect this by trial division, then virtually every base a will satisfy a^{n-1} \ne 1 (mod n) and hence reveal the compositeness of n, unless n is of a very special form.
Кроме того, там дальше в статье, по-видимому, делаются дополнительные ухищрения, чтобы добиться более равномерной генерации случайных простых.
Поглядев ещё в статьях, нашёл ещё один близкий аналог - "Generating Provable Primes Efficiently on Embedded Devices" (Clavier, 2012). "Ядро" алгоритма там выглядит ещё ближе к вашему алгоритму:
We generate a provable prime by doubling at each iteration the size of the current prime p to derive the new prime n = 2rp + 1.
и псевдокод алгоритма очень похож. Но есть и отличия - например, они стартуют не с решета Эратосфена, а с генерации числа до 2^32 с помощью тестов Миллера-Рабина. У них там много и других интересных соображений - про энтропию, про ускорение подбора случайных параметров путём поиска их в специальной форме, и т. п.
Думаю, сравнение с другими алгоритмами по эффективности было бы очень наглядным!
Но всё-таки по-прежнему интересен вопрос с асимптотикой в "плохом" случае (я предполагаю, что говорить о "худшем" случае тут неинтересно, поскольку, видимо, алгоритм сильно завязан на рандоме). Сколько разных a нам может понадобиться для проверки одного (положим, "неудачно" выбранного) r? Или сколько, в среднем, r нам понадобится просмотреть?
Вы же сами даёте ссылки на статьи с другими алгоритмами. Но, для определённости, пример - запуск серии тестов Миллера-Рабина (что, например, используется OpenSSL на практике).
Только надо быть осторожным, потому что даже безобидные вещи вроде "double y=f(x); ... if (y==f(x))" могут работать неправильно (из-за промежуточных вычислений в 80-битных регистрах, насколько я понимаю).
Но согласен, что в некоторых случаях, например, бинарном или тернарном поиске, сравнение через эпсилон только навредит.
Если эта рекомендация предлагает использовать беззнаковый size_t, то тоже можно поспорить... Бесчисленное число багов связано с тем, что когда от нулевого значения size_t отнимают единицу, то получают число "бесконечность". Если мы говорим о среднестатистической программе, не собирающейся ворочать гигабайты памяти, и при этом слишком "ленивы", чтобы использовать честный ptrdiff_t или итераторы, то не лучше ли старый добрый int?
Google Style Guide тоже даёт рекомендацию в этом ключе, и даже ссылается на (правда, неназванных) членов комитета, считающих, что использование беззнаковых типов в стандартной библиотеке - это ошибка:
На самом деле, даже если без шуток, это нормальный совет для большинства программ. Если мы не можем больше выделить нисколько памяти, то сделать что-то осмысленное - очень сложно, а выхлопа - мало, потому что, скорее всего, нам в любом случае надо завершиться. ОК, может быть, в каких-то редких случаях, например, если мы пишем какой-то системно-важный демон или пишем embedded софт, дополнительные усилия могут быть оправданы. Но в среднестатистической программе падать на OOM - это стандартная рекомендация.
Кстати, насколько я знаю, в Rust это стандартное поведение библиотеки - немедленное завершение при OOM. То же делает аллокатор в реализации Chrome.
Как в 1960 г. писал математик Сидзуо Какутани:
(Примерный перевод: "Каждый в Йельском университете проработал над этой проблемой в течение месяца. Похожий фенонен наблюдался в Чикагском университете после того, как я упомянул о ней. Ходила шутка, что эта задача была частью заговора, имевшего целью затормозить математические исследования в США.".)
Нет, это совсем другое. В гипотезе Коллатца, например, из 11 переходим в 34, и оттуда в 17. Это гораздо более "рандомная" последовательность, чем +1 и /2. Полная последовательность, начиная с 11, будет выглядеть 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Преувеличивать надёжность Tor тоже не следует. От Sybil attack, насколько я знаю, полностью защититься не смогли. А совсем недавний пример - так называемый "KAX17":
(https://cybersecurityworldconference.com/2021/12/03/kax17-threat-actor-is-attempting-to-deanonymize-tor-users-running-thousands-of-rogue-relays/)
А в 2016 г. сооснователь сети приводил оценку вероятности в 2*10^-6 для атакующего, у которого всего лишь два узла под контролем. Я не знаю, повысили ли защиту от такой атаки с тех пор, но вот цитата:
(https://arstechnica.com/information-technology/2016/08/building-a-new-tor-that-withstands-next-generation-state-surveillance/)
Можно ли где-то послушать "направление А"? (youtube? беглый поиск не дал результатов...)
Спасибо за перевод, но насчёт "крутости" алгоритма - представленные данные не слишком убедительны...
БОльшая часть графиков - про сортировку рандомных данных, но ведь это и так общеизвестный факт, что существуют алгоритмы, которые отлично справляются именно с рандомными входными наборами. Например (первый же результат в гугле) - статья 2013 г. "Unisort: an Algorithm to Sort Uniformly Distributed Numbers in O(n) Time". Сравнения с этим и подобными специализированными алгоритмами нет.
В остатке - честный график, что на нерандомных входах предложенный "ska sort" проигрывает std::sort; в некоторых диапазонах - проигрывает с треском. А также нестадартный интерфейс ("ska sort" нельзя подключить как drop-in replacement, потому что она не умеет работать с компараторами) и отсутствие поддержки некоторых видов элементов.
Неубедительно...
Я такого произношения не встречал. Merriam-webster тоже указывает другую форму как более распространённую: ˈfȯr-ˌtā , ˈfȯr-tē.
Неужели проект Log4j не использует фаззинг? Кажется, такой баг нормальным фаззером был бы отловлен давным-давно.
Также вашему переводу противоречит статья с ADAC (это немецкий автоклуб):
https://www.adac.de/rund-ums-fahrzeug/ausstattung-technik-zubehoer/autonomes-fahren/technik-vernetzung/autonomes-fahren-staupilot-s-klasse/
Переводить я всё вручную здесь не буду, но можно обратить внимание на это: "weil Mercedes hier die Verantwortung übernimmt", что переводится как "поскольку "Мерседес" берёт здесь ответственность на себя".
Ваш перевод автоматизированный? Мои (конечно, ограниченные) познания немецкого говорят о том, что он неверен. Но вообще забавно, конечно - "казнить нельзя помиловать", получается, в статье написано.
В немецких газетах другая информация:
https://www.focus.de/auto/ratgeber/unterwegs/schneller-als-tesla-drive-pilot-mercedes-erhaelt-erste-serien-zulassung-fuer-autonomes-fahrsystem_id_24505560.html
(Примерный перевод: "Если автомобиль движется автономно и попадает при этом в аварию, за последствия отвечает производитель, а не водитель".)
Т. е., фактически, только в пробках? В нормальной ситуации (не пробка и не зона ремонта) такой маленькой скорости на автобане не может быть: рекомендуемая скорость по умолчанию 130, и даже если стоит типичное ограничение 120 - ехать там со скоростью 60 просто нельзя.
После перечитывания FIPS 186-4 (секция C.6) и поиска доп. информации по алгоритму Shawe-Taylor получилось выйти на упоминания алгоритма Maurer, который уже очень похож на то, что описано в статье ("Fast Generation of Secure RSA-Moduli with Almost Maximal Diversity", Maurer, 1989):
Кроме того, там дальше в статье, по-видимому, делаются дополнительные ухищрения, чтобы добиться более равномерной генерации случайных простых.
Поглядев ещё в статьях, нашёл ещё один близкий аналог - "Generating Provable Primes Efficiently on Embedded Devices" (Clavier, 2012). "Ядро" алгоритма там выглядит ещё ближе к вашему алгоритму:
и псевдокод алгоритма очень похож. Но есть и отличия - например, они стартуют не с решета Эратосфена, а с генерации числа до 2^32 с помощью тестов Миллера-Рабина. У них там много и других интересных соображений - про энтропию, про ускорение подбора случайных параметров путём поиска их в специальной форме, и т. п.
Спасибо за добавленные асимптотики. Это проясняет роль "s" и предварительного решета.
Насчёт алгоритма - мне казалось, что в FIPS 186-4 что-то похожее описывалось, но на самом деле, похоже, там другой алгоритм ("Shawe-Taylor"?).
Думаю, сравнение с другими алгоритмами по эффективности было бы очень наглядным!
Но всё-таки по-прежнему интересен вопрос с асимптотикой в "плохом" случае (я предполагаю, что говорить о "худшем" случае тут неинтересно, поскольку, видимо, алгоритм сильно завязан на рандоме). Сколько разных a нам может понадобиться для проверки одного (положим, "неудачно" выбранного) r? Или сколько, в среднем, r нам понадобится просмотреть?
Вопрос в том, какова стоимость этой гарантии.
Эта запись совершенно непонятна.
Вы же сами даёте ссылки на статьи с другими алгоритмами. Но, для определённости, пример - запуск серии тестов Миллера-Рабина (что, например, используется OpenSSL на практике).