Комментарии 24
По ссылке на препринт открывает страницу с ошибкой : DOI Not Found.
Кажется, вот правильная
Очень странно, ещё вчера всё работало. Спасибо, что заметили! Поправил ссылку в статье.
Таблица огонь. Простые числа лежат только в указанных столбцах потому что в остальных лежат числа, делящиеся на делители 30. Почему именно 30? а не, например, 2*3*5*7=210?
Вот вы там перебираете n. Какая гарантия, что произойдет остановка (найдете такое число) и/или когда следует остановиться?
Правильно, в остальных столбцах находятся числа, не являющиеся взаимно простыми с 30. Возможно, мое объяснение оказалось не очень понятным? Что касается 210 - можно попробовать, но вычислений будет больше, т.е. будет менее эффективно. По поводу n - там внутри простая математика. Если вы факторизуете полупростое число, то гарантированно рано или поздно найдете ответ. Как только получите квадратное число при переборе, можете останавливаться - вы нашли решение.
Не в обиду автору, но читать было сложно. Много рукомахания, переоткрытие базовых фактов арифметики остатков, непонятные обозначения.
Просили критику? Ну, давайте по пунктам...
1) D = p - q = 30n + δ, где n - целое, а δ - ??? число. Что я должен был подумать при виде лапласиана Δ? Наверное, что дельта лежит во множестве дельт... Ah yes, the floor is made out of floor.
2) Утверждение, что δ ≡ |p-q| (mod 30) мне кажется странным. Возьмите p = 10, q = 11.
3) Почему-то автору неочевидно, что (хотя он специально сделал так, что каждый столбец таблицы содержит числа, дающие один конкретный остаток), что столбец произведения чисел из пары столбцов не зависит от самих чисел (x%30 * y%30 ≡ (xy)%30)
4) Очень хотелось посмотреть, как себя поведёт итоговый алгоритм на каком-нибудь простом числе, например, 10^9 + 7.
5) Первый шаг алгоритма - взять остаток от деления N на 30. Затем мы залезаем в таблицу и смотрим кандидаты-дельты. Во фрагменте таблицы из конца статьи я вижу строчку, соответствующую остатку 0. Зачем??? Если число разделилось на 30 нацело, мы уже получили разложение p=30, q=N/30.
6) Окей, ладно, допустим, там не ноль, значит, сидим и для каждой дельты перебираем возможные значения n: вычисляем (30n +δ)^2 + 4N и проверяем, не получился ли у нас точный квадрат... Стоп, а как мы это делаем? В статье про это ни слова! Вы уверены, что можно проверить, является ли число точным квадратом, не потеряв предполагаемый выигрыш от вашего алгоритма? Тут ведь даже асимптотика может сломаться.
7) Ну и об асимптотике... Она взята с неба. Во-первых, откуда корень взялся? Мы же перебираем для каждой дельты 2* N/30 == N / 15 значений n. Может, я пропустил где-то упоминание перебора до корня? Да нет, вроде... Во-вторых, для разных остатков по модулю 30 у вас разное кол-во допустимых дельт, т.е. k = k(N) на самом деле, а не константа. А если мы не хотим исследовать эту функцию, то можно сказать, что кол-во всевозможных расстояний между остатками конечное, а значит, k(N) ограничена, т.е. k(N) = O(1). Таким образом мы выкидываем k совсем. А если после этого выкинуть числовые константы, мы получаем что-то типа O(N). Ой.
8) Ну а если совсем по-хорошему, то надо учитывать, что так-то числа могут быть сколь угодно большими (иначе неинтересно), а значит, надо переходить в длинную арифметику. Тут уже сложность алгоритма традиционно измеряется относительно так называемой длины входа (в битах) и арифметические операции уже не O(1), а что-то как минимум линейное (кроме совсем простых действий, скажем, чётность узнать). Предлагаю автору попробовать в этом разобраться.
Любая конструктивная критика — на пользу. Во-первых, я закончил ВУЗ очень давно и я не математик, но я стараюсь разобраться в теме с инженерной и прикладной точки зрения, поэтому я могу допускать ошибки в математической нотации или формулировках. Прошу простить мне этот мой недостаток. Достаточно обоснованно указать на ошибки и я их исправлю. Во-вторых, есть некая разница в принятой математической нотации между советской/российской школой и западной. Непонятные вам обозначения могут быть вызваны этим. Что именно было непонятно? Я постараюсь объяснить.
переоткрытие базовых фактов арифметики остатков
Непонятно, что именно вы имеете в виду. Я написал о том, как я пришел к этим находкам. И я старался написать научно-популярную статью, понятную не только узким специалистам, поэтому объяснял очевидные для кого-то и без этого вещи.
Что я должен был подумать при виде лапласиана Δ? Наверное, что дельта лежит во множестве дельт...
Это не лапласиан. В общем да, что дельта принадлежит некому множеству. Я не был уверен в том, как это сделать правильно. Предложите лучшее обозначение, чтобы я исправил?
Утверждение, что δ ≡ |p-q| (mod 30) мне кажется странным. Возьмите p = 10, q = 11.Утверждение, что δ ≡ |p-q| (mod 30) мне кажется странным. Возьмите p = 10, q = 11.
в этом случае будет 1: 
.
Почему-то автору неочевидно, что (хотя он специально сделал так, что
каждый столбец таблицы содержит числа, дающие один конкретный остаток),
что столбец произведения чисел из пары столбцов не зависит от самих
чисел (x%30 * y%30 ≡ (xy)%30)
Наверное вы тут что-то не поняли. Я как раз и утверждаю ровно это и даю объяснение, почему это именно так для тех, кому это не очевидно. Более того, именно на этом факте и строится весь метод. Он является ключевым.
Очень хотелось посмотреть, как себя поведёт итоговый алгоритм на каком-нибудь простом числе,
Будет считать, пока не переберет все и 
, но ничего не найдет. Как и абсолютно любой другой метод факторизации, который также ничего не найдёт. Это же очевидно. Нет?
Первый шаг алгоритма - взять остаток от деления N на 30. Затем мы
залезаем в таблицу и смотрим кандидаты-дельты. Во фрагменте таблицы из
конца статьи я вижу строчку, соответствующую остатку 0. Зачем??? Если
число разделилось на 30 нацело, мы уже получили разложение p=30, q=N/30.
Отличное замечание! Действительно, незачем. Это артефакт того, как я работал над алгоритмом. Я написал программу для проверки гипотезы и мне было лень считать большие полупростые, поэтому я наобум печатал что-то в районе десятка цифр, а потом факторизовал. Иногда получались числа, кратные 30 при этом, отсюда и эта строка. У меня, что называется, замылился глаз. Спасибо за то, что указали на это!
Стоп, а как мы это делаем? В статье про это ни слова! Вы уверены, что
можно проверить, является ли число точным квадратом, не потеряв
предполагаемый выигрыш от вашего алгоритма?
Разве на каждом шаге метода Ферма не нужно делать ровно ту же операцию, что и в решете дельт? Там ведь мы так же проверяем кандидаты на полный квадрат.
Что касается асимптотики — я сделал, что было в моих силах, но вполне мог допустить здесь ошибку. Я пытался получить помощь профессиональных математиков в этом вопросе, но всем было как-то не до того. Поможете исправить?
И я старался написать научно-популярную статью, понятную не только узким специалистам, поэтому объяснял очевидные для кого-то и без этого вещи.
Но почему-то функцию Эйлера и значок Z для обозначения множества целых чисел пояснять не стали.
Предложите лучшее обозначение, чтобы я исправил?
Да не нужно тут специальных обозначений, просто напишите границы, в которых лежит δ. Если написать `0 <= δ < 30`, то читатель поймёт, что речь об обычном делении с остатком, где n - целая часть, а δ - остаток.
Думайте об этом так - когда читатель видит использование необъявленного символа (Δ), у него в голове вылетает исключение и статью он закрывает.
δ в этом случае будет 1
Ну да, а теперь подставьте p, q и δ в утверждение `p-q = 30n + δ`. Теперь видите проблему? `-1 = 30n + 1 <=> 30n = 2`. Ну это просто false для всех n. Вот почему я сказал, что утверждение кажется мне странным.
Разве на каждом шаге метода Ферма не нужно делать ровно ту же операцию, что и в решете дельт?
Да я как-то не думал про метод Ферма, когда это писал. Есть же и лобовой метод перебора до корня - там это не требуется (причём иногда метод Ферма медленнее лобового).
Что касается асимптотики — я сделал, что было в моих силах, но вполне мог допустить здесь ошибку
И я, и ещё один комментатор уже объяснили, что, да, вы допустили ошибку. И я уже вычислил правильную асимптотику - получилось O(N). Да, за линию. Да, хуже лобового метода. Мою логику я расписал в прошлом комментарии.
Что я могу посоветовать... Откройте Youtube, вбейте там в поиске "Борис Трушин арифметика остатков". Посмотрите выпуски "Ботай со мной" N34, 36 и 37. Плюс-минус 35 ещё.
А с асимптотикой... Посмотрите первую лекцию осеннего семестра по алгоритмам на лектории ФПМИ (1 курс, любой год), после этого возьмите лист А4 и проверьте, что
Функия cos(n)/sqrt(n) + 10000 есть O(1).
Если f(n) = O(n), то f(n) = O(n/2).
Где читать про длинную арифметику - сходу не скажу, но 100% сейчас должно быть в интернете.
-1 = 30n + 1 <=> 30n = 2.
Откуда вы берете -1? И в статье, и в своем комментарии я написал, что там модуль от разницы, т.е. абсолютная величина - нет там минуса. По поводу линии и лобового метода - вы также ошибаетесь.
Откуда вы берете -1?
p - q в статье без модуля в этой строчке. Подставляем 10 и 11 - получаем противоречие.
По поводу линии и лобового метода - вы также ошибаетесь.
Просто сказать, что я ошибаюсь... маловато будет. Мою логику я расписал, так что либо укажите точное место, где я ошибся в рассуждениях (с цитатой!), либо признайте свою ошибку.
Никакого противоречия нет, D может иметь отрицательное значение. Смотрите 3 пример. Про асимптоту - не хуже лобового метода. Если делители есть, то один из них обязательно меньше или равен корню из N. Поскольку мы не ищем делители по отдельности, мы найдем оба не больше, чем за корень из N операций, как при линейном способе. Но на самом деле найдем скорее всего гораздо быстрее, чем линейным способом за счет фильтрации по дельтам.
Это не лапласиан
Поясняю: то был тонкий намёк на то, что вам не известно про понятие лапласиана, иначе вы не выбрали бы этот символ (так как он уже занят и общепринят). То есть автоматически классифицирует вас в группу дилетантов, ищущих решения сложных задач простыми, но "хитрыми" способами.
Раз уж речь о закономерностях в распределении простых чисел, недавно наткнулся на публикацию Finding the nearest prime to any large integer (по ссылке PDF). Там все числа расположены по шестиугольной спирали, и утверждается, что простые числа лежат строго на двух из радиальных линий.
~200 лет?
В статье описан метод Ферма, только очень запутанно и громоздко. По сравнению со стандартным описанием разница в следующем:
1. Вместо разложения N=x^2 - y^2 ищется разложение 4N = m^2 - D^2 - это разумеется, безразлично
2. При переборе число D представляется не в виде sqrt(N) + k, в виде 30n+ δ - представлять число можно как угодно, это принципиально ни на что не влияет
Всё, что связано с числом 30 является элементарными рассуждениями об арифметике остатков. Конкретное число 30 не важно. По сути это сделано для уменьшения количества возможных значение δ при переборе D. Только это не имеет значения, потому что перебор идёт и по δ, и по n. При этом количество δ ограничено заранее известной небольшой константой, в вот n=O(N).
В разделе "Сложность алгоритма" множество ошибок:
1. В O-нотации пишутся коэффициенты k, 30, 2, 15, которые по сути являются константами
2. "В худшем случае (при 
) данный метод имеет сложность" - худший случай это когда разница между делителями большая, а не k=15
3."Однако, из-за того, что в среднем 
количество необходимых проверок уменьшается в 
раз, делая данный метод существенно быстрее для сравнимых значений 
." - вы сравниваете асимптотическую оценку метода Ферма (в которой уже нет констант) с оценкой "своего" алгоритма в которой дописали константы. Так просто некорректно делать
В основе — да, идея похожа на Ферма (хотя я и не вдохновлялся им, просто так получилось). Но в моём методе добавлена фильтрация по остаткам и таблица дельт, которая отсекает заведомо невозможные варианты. Это экономит шаги на практике и втором пример показывает, что выигрыш может быть ощутимым. Или он вас не убедил?
Интересная идея. Но я бы не переоценивал ее практическую значимость.
Сложность O(sqrt(N)*k/30).
Есть еще более простой метод, который почти не медленнее, проще для понимания, легче параллелится и все остальное.
Перебираем все числа до 2 до sqrt(N) и проверяем, являются ли они делителями N. Для ускорения проверяем не все числа, а только те, что взаимнопросты с 30 (вида 30k+d). Мы же простой делитель ищем.
Использование разности квадратов у вас довольно хитро и возможно действительно позволяет сократить количество различных дельт с 8 до 2, но требует больше вычислений. Тут возведение в квадрат, сумма, а потом извлечение корня вместо одного деления. Плюс надо еще как-то модифицировать алгоритм извлечения корня, чтобы сразу проверить на целочисленность. А потом еще надо вычислить сами делители. Не факт, что это будет быстрее на самом деле.
Еще интересный вопрос, а могли бы вы привести таблицу? Сдается мне, что оно не всегда сокращает количество дельт и для каких-то остатков N по модулю 30 может дать больше 8 дельт.
@VAEСмотрите, у вас конкурент. Только тут используется обычная, общепринятая, всем понятная нотация, нет исторических отсылок с зашкаливающим пафасом, метод формально описан и приведена оценка его скорости. И сложность материала автор адекватно поставил "средний". Ваши статьи по сравнению с этим никуда не годятся. И результат налицо. Основная идея через формулу разницы квадратов почти такая же как у вас, но тут люди ее принимают и плюсы статье ставят, в отличии от ваших статей, где почему-то одни хейтеры собрались.
Перебираем все числа до 2 до sqrt(N) и проверяем, являются ли они делителями N. Для ускорения проверяем не все числа, а только те, что взаимнопросты с 30 (вида 30k+d). Мы же простой делитель ищем.
Вы описали ровно то, что этот метод и делает. Только вы предложили проверять все взаимнопростые, а я проверяю только подходящие - те, которые прошли фильтр, для этого таблица дельт и нужна.
Использование разности квадратов у вас довольно хитро и возможно действительно позволяет сократить количество различных дельт с 8 до 2, но требует больше вычислений. Тут возведение в квадрат, сумма, а потом извлечение корня вместо одного деления. Плюс надо еще как-то модифицировать алгоритм извлечения корня, чтобы сразу проверить на целочисленность. А потом еще надо вычислить сами делители. Не факт, что это будет быстрее на самом деле.
Это лишь математическая нотация. В реальном алгоритме умножения нет вообще. На самом деле каждое новое значение D вычисляется как член двух арифметических прогрессий - 2 операции сложения. Возможно, у меня будет время на вторую статью с описанием алгоритма с точки зрения программиста, в которой я опишу практическую реализацию алгоритма.
Если бы у нас был метод нахождения пересечения двух прогрессий - мы бы нашли ответ за одну операцию, т.к. все квадратные числа также являются членами прогрессии.
Что касается извлечения корня, тут без этого не обойтись. Но в библиотеке GMP есть быстрая функция проверки на то, является ли число полным квадратом - я использую её.
Про препринт все-таки скажу, в глаза бросилось: называть свой метод по своей фамилии, при том что вы сами говорите, что не математик - это вопиющая пошлость.
Это же и главный критерий, по которой я пропускаю подобные статьи не читая (не в обиду автору). Настоящие математики называют свои работы по сути, а остальное делает уже история и признание других математиков. Например, оригинальная работа Чебышева про его знаменитые многочлены называется не "Многочлены Чебышева", а "О функциях, наименее уклоняющихся от нуля".
Решето дельт — простой способ раскладывать числа на множители, о котором вам не рассказывали