Information
- Rating
- Does not participate
- Date of birth
- Registered
- Activity
Specialization
Технический директор
Ведущий
Управление людьми
Проектирование архитектуры приложений
Linux
ООП
C++
Delphi
Проектирование баз данных
Многопоточность
Английский язык
Высокая доступность
Согласен, что такое может быть, если шагов в 3 раза меньше, но каждый шаг занимает в 4 раза больше времени. Но в данном случае это не так, число операций в одном шаге сравнимо у обоих методов. Но если хотите, можем замеры и по времени сделать.
Вы говорите об одном виде оптимизации, я я - о другом. Один и тот же алгоритм можно реализовать на разных ЯП и, очевидно, скорость работы будет разной, но число шагов останется одинаковым. Говоря про ускорение я имел в виду сокращение именно числа требуемых шагов для нахождения результата.
Я добавил в статью дополнительную информацию со сравнением количества потребных шагов для нахождения решения для двух методов - решета дельт и Ферма. Ускорение примерно в 3 раза в среднем может иметь практическую значимость, как считаете?
Основное описание метода я готовил именно для публикации здесь. Публикация препринта с именным методом - это защита от того, что кто-то с прищуренными глазами утащит его и опубликует под своим. Какие времена, такие и нравы. Предлагаю на этом закрыть тему моральных аспектов и сосредоточиться на главном.
Я добавил сравнительную таблицу непосредственно в статью после оценки сложности.
Я пока не знаю, как доказать это математически, но могу сделать это практически. Я взял 50 случайных пар простых 5-значных
и
и определил количество шагов для поиска решения. В 9 случаях из 50 метод решета дельт был медленнее метода Ферма - при близких
и
, в остальных случаях быстрее. Самое быстрое решение было на паре 17029*56737 - данным методом решение находится за 664 шага, а методу Ферма для этого требуется 5799 шагов, т.е. он в 8,73 раза медленнее на данном примере. В среднем получилось, что метод решета дельт быстрее метода Ферма примерно в 3 раза. Все решения, найденные данным методом, были найдены за менее чем
шагов.
Я подготовил таблицу с этими данными, но не могу вставить её в комментарий так, чтобы форматирование сохранилось (жду ответа от модераторов, как это сделать). Если вам всё ещё интересно, то давайте оставим споры и обвинения, и попробуем совместно улучшить описание метода. В конце концов, это пойдет на пользу всем.
Хорошо, я сам просил критиковать статью. Смотрите, ваш пример с 10 и 11 (N=11*10=110) решается данным методом так:
Множители:
Данное решение найдено на первом же шаге. Если мы не будем останавливать алгоритм, то найдем ещё два решения:
Множители:
Множители:
Как вы предлагаете улучшить статью, чтобы не было такого восприятия, какое было у вас?
Касательно счётчика: предлагаю вам дать мне, скажем, 5 полупростых чисел, где p и q различаются, скажем, на порядок. Прошу об этом вас, чтобы не было обвинений, что я подобрал числа. Только не давайте слишком большие, 9 или 10 разрядов вполне достаточно - я не хочу слишком долго ждать результат. Сравним число операций с методом Ферма, раз я сам выбрал его за эталон. Согласны?
В другой ветке комментариев я уже писал, что если есть решение, то оно будет найдено в любом случае не больше, чем за
операций, т.к. находятся сразу оба сомножителя, один из которых гарантированно меньше или равен корню из N. Т.е. не
, а
или
, как в статье. При каких условиях
Что касается подбора примеров, то в этом моя совесть совершенно чиста. Верите вы или нет, но я брал пару случайных простых чисел и работал с ними, ничего не подбирая. Если вы все ещё не убеждены, то я планирую написать статью об алгоритмической реализации данного метода и опубликовать код на GitHub - мы сможем измерить потребное количество операций для любых сомножителей на практике. Там, кстати, есть один парадокс, который я не понимаю и, возможно, вы сможете его объяснить. Он связан с ещё одной оптимизацией, которую я обнаружил опытным путём и не могу объяснить её математически - я слишком слаб для этого, поэтому я ничего не написал в статье про неё. Я вижу, что вы хорошо разбираетесь в математике и возможно поможете разобраться.
Смотрите, алгоритм рассматривает как отрицательные значения n, так и положительные. Да, вы правы, если p = 10 и q = 11, то D получится отрицательным и эта ветка никогда не найдет решение. Но алгоритм проверит и обратный случай, когда p = 11 и q = 10 - в этом случае решение будет найдено: D = 30 * 0 + 1 = 1. Посмотрите третий пример - ни при каких положительных значениях n решение не будет найдено, но оно найдено при отрицательном n. Ваш пример точно такой же - решения нет, когда мы считаем, что p < q, но оно есть, когда q > p. Из-за коммутативности операции умножения нет разницы, что мы примем за q, а что - за p, 10 или 11, но для алгоритма - есть. Мы пробуем оба варианта (знак у n).
Зачем пытаться разложить на множители простое число? Только для вычисления O-большого? Ну хорошо, пусть будет в невозможном случае O(N). Но меня не очень интересовали невозможные случаи, я рассматривал только случаи применения алгоритма для разложения на сомножители составных чисел.
Я имел в виду, что проверяются также взаимнопростые числа, как и в вашем предложении, только не все, о чем пишете вы, а подходящие. Это вопрос логики работы алгоритма же, а не конкретной формулы.
Никакого противоречия нет, D может иметь отрицательное значение. Смотрите 3 пример. Про асимптоту - не хуже лобового метода. Если делители есть, то один из них обязательно меньше или равен корню из N. Поскольку мы не ищем делители по отдельности, мы найдем оба не больше, чем за корень из N операций, как при линейном способе. Но на самом деле найдем скорее всего гораздо быстрее, чем линейным способом за счет фильтрации по дельтам.
Вы описали ровно то, что этот метод и делает. Только вы предложили проверять все взаимнопростые, а я проверяю только подходящие - те, которые прошли фильтр, для этого таблица дельт и нужна.
Это лишь математическая нотация. В реальном алгоритме умножения нет вообще. На самом деле каждое новое значение D вычисляется как член двух арифметических прогрессий - 2 операции сложения. Возможно, у меня будет время на вторую статью с описанием алгоритма с точки зрения программиста, в которой я опишу практическую реализацию алгоритма.
Если бы у нас был метод нахождения пересечения двух прогрессий - мы бы нашли ответ за одну операцию, т.к. все квадратные числа также являются членами прогрессии.
Что касается извлечения корня, тут без этого не обойтись. Но в библиотеке GMP есть быстрая функция проверки на то, является ли число полным квадратом - я использую её.
Откуда вы берете -1? И в статье, и в своем комментарии я написал, что там модуль от разницы, т.е. абсолютная величина - нет там минуса. По поводу линии и лобового метода - вы также ошибаетесь.
В основе — да, идея похожа на Ферма (хотя я и не вдохновлялся им, просто так получилось). Но в моём методе добавлена фильтрация по остаткам и таблица дельт, которая отсекает заведомо невозможные варианты. Это экономит шаги на практике и втором пример показывает, что выигрыш может быть ощутимым. Или он вас не убедил?
Любая конструктивная критика — на пользу. Во-первых, я закончил ВУЗ очень давно и я не математик, но я стараюсь разобраться в теме с инженерной и прикладной точки зрения, поэтому я могу допускать ошибки в математической нотации или формулировках. Прошу простить мне этот мой недостаток. Достаточно обоснованно указать на ошибки и я их исправлю. Во-вторых, есть некая разница в принятой математической нотации между советской/российской школой и западной. Непонятные вам обозначения могут быть вызваны этим. Что именно было непонятно? Я постараюсь объяснить.
Непонятно, что именно вы имеете в виду. Я написал о том, как я пришел к этим находкам. И я старался написать научно-популярную статью, понятную не только узким специалистам, поэтому объяснял очевидные для кого-то и без этого вещи.
Это не лапласиан. В общем да, что дельта принадлежит некому множеству. Я не был уверен в том, как это сделать правильно. Предложите лучшее обозначение, чтобы я исправил?
Наверное вы тут что-то не поняли. Я как раз и утверждаю ровно это и даю объяснение, почему это именно так для тех, кому это не очевидно. Более того, именно на этом факте и строится весь метод. Он является ключевым.
Будет считать, пока не переберет все
и
, но ничего не найдет. Как и абсолютно любой другой метод факторизации, который также ничего не найдёт. Это же очевидно. Нет?
Отличное замечание! Действительно, незачем. Это артефакт того, как я работал над алгоритмом. Я написал программу для проверки гипотезы и мне было лень считать большие полупростые, поэтому я наобум печатал что-то в районе десятка цифр, а потом факторизовал. Иногда получались числа, кратные 30 при этом, отсюда и эта строка. У меня, что называется, замылился глаз. Спасибо за то, что указали на это!
Разве на каждом шаге метода Ферма не нужно делать ровно ту же операцию, что и в решете дельт? Там ведь мы так же проверяем кандидаты на полный квадрат.
Что касается асимптотики — я сделал, что было в моих силах, но вполне мог допустить здесь ошибку. Я пытался получить помощь профессиональных математиков в этом вопросе, но всем было как-то не до того. Поможете исправить?
Верно!
Правильно, в остальных столбцах находятся числа, не являющиеся взаимно простыми с 30. Возможно, мое объяснение оказалось не очень понятным? Что касается 210 - можно попробовать, но вычислений будет больше, т.е. будет менее эффективно. По поводу n - там внутри простая математика. Если вы факторизуете полупростое число, то гарантированно рано или поздно найдете ответ. Как только получите квадратное число при переборе, можете останавливаться - вы нашли решение.
Очень странно, ещё вчера всё работало. Спасибо, что заметили! Поправил ссылку в статье.
В решении суда все написано. Как написано на главной странице вашего сайта:
Только есть маленькая проблемка — в РФ есть некоторые ограничения, установленные законом. А именно, в соответствие с Федеральным законом от 25.07.2002 №114-ФЗ «О противодействии экстремистской деятельности» одним из видов экстремисткой деятельности является массовое распространение заведомо экстремистских материалов:
Таким образом, ваша деятельность местами входит в противоречие с данным законом. И вы это знаете, и сознательно не выполняете. Только не надо заниматься демагогией и говорить, что анонимайзеры, прокси и vpn не запрещены. Да, сами по себе они не запрещены, но запрещено предоставлять с их помощью доступ к информации, признанной судом экстремистской. Такая простая конструкция слишком сложна для понимания?
А почему тогда интернет-провайдеры блокируют эту информацию? Ведь это не они пичкают пользователя ею, это сам пользователь так хочет. Следуя этой логике, можно дойти до умозаключения, что наркодилеры не совершают ничего противоправного, ведь «сам пользователь этого хочет», а желание клиента — закон.
В общем, что я вам рассказываю это все? Вы сами прекрасно все знаете и понимаете. Но по какой-то причине вы решили, что вам лучше быть кибер-борцами с непонятно чем, что мочиться против ветра — здорово. При этом у вас нет тех возможностей, что есть у Дурова, как мы видим. Если вам плевать на ваш бизнес, то мне тем более. Всего хорошего.