Угу, значит, это сильно урезанный функционал тех же GoodbyeDPI / ByeDPI[Android] / zapret. А в чём его преимущество перед уже существующими решениями? В том, что он проще? Тогда зачем все эти сложности в других приложениях, раз всё так просто?
Я примерно понимаю, как работают решения через WinDivert - он буквально становится вашей сетью и решает, какие пакеты будут в ней ходить (в частности, может дропать и даже спавнить пакеты). А тут какой механизм? Допустим, браузеру мы можем объяснить, что у нас тут прокся - иди туда. Иногда у отдельных приложений есть свои настройки прокси - тоже прописать можем. Есть ещё якобы глобальные настройки прокси в винде - а это как работает? Неужели любое приложение в системе при попытке куда-то зайти по интернету автоматически улетит сначала на прокси (причём абсолютно прозрачно)? А пиннинг сертификатов тут не помешает нигде?
Наконец, последний вопрос, не совсем про-данное решение, но всё же - а как эти дурилки согласовываются с защитой от DNS-спуфинга? Я до сих пор не понял, как грамотно настроить систему и браузеры, чтобы по дефолту резолвилось через Claudflare, а если не нашлось там, то фоллбэк на текущий дефолтный в системе (который, вроде, сообщает наш источник интернета, т.е. я это могу в свойствах соединения WiFi прочитать). Мне прям важно, чтобы был фоллбэк, а то до внутренних сайтов в сети достучаться не получится.
Да алгоритм тут не при чём! Читающие статью видят вот это (см. скриншот):
Якобы данное утверждение выполнено для всех p, q
Прежде, чем читать дальше, читатель подставляет p = 10, q = 11 сюда, от греха подальше. Видит D = -1 = 30n + 1. Это ни при каком n не выполнено, значит, автор где-то ошибся. Статью можно, в целом, закрывать. Что там какой-то алгоритм потом описывается - уже неважно.
Душню ли я? Есть такое... Но это прям сразу бросилось в глаза.
Что касается асимптотики, в другой ветке вам довольно хорошо расписали, почему не доказано наличие корня (если коротко - перебираются не числа до корня, а просто какие-то числа, которые могут дать два делителя в итоге, например, на последней итерации алгоритма).
Можете, кстати, добавить счётчик в программу и после разложения сравнить кол-во опробованных пар (n, δ), прежде чем получился квадрат, с корнем из N. Затем прогоните программу на всех числах подряд (составных, конечно, раз уж простые вы не поддерживаете). Честно интересно, насколько на практике выполняется ваше голословное утверждение.
Никакого противоречия нет, D может иметь отрицательное значение.
Да не в этом противоречие! Ещё раз повторяю: в статье приведено утверждение `D = p - q = 30n +δ`. Я предложил вам подставить туда p = 10 и q = 11. Мы получим слева минус единицу, а справа: 30n + 1 (сами так сказали в первом комментарии: "δ в этом случае будет 1"!). Вот оно - противоречие! 30n + 1 ни при каких n не равно минус единице.
Если делители есть, то один из них обязательно меньше или равен корню из N.
2) Ваша ошибка довольно интересная - вы забыли рассмотреть случай, когда на вход алгоритму подаётся простое число. "Если делители есть..." Это всё замечательно, ну а если их нет? Вот тут-то собака зарыта!
Ваш алгоритм будет перебирать n и δ в надежде, что 4N + (30n + δ)^2, пока не переберёт все кандидаты, а их у вас 2*N/30 для n и k(N) для δ. То бишь k(N) * N/15 проверок нужно сделать. Т.к. пятнадцать - константа, а k(N) - ограниченная функция, мы их выкидываем из асимптотики. Получаем O(N).
p - q в статье без модуля в этой строчке. Подставляем 10 и 11 - получаем противоречие.
По поводу линии и лобового метода - вы также ошибаетесь.
Просто сказать, что я ошибаюсь... маловато будет. Мою логику я расписал, так что либо укажите точное место, где я ошибся в рассуждениях (с цитатой!), либо признайте свою ошибку.
И я старался написать научно-популярную статью, понятную не только узким специалистам, поэтому объяснял очевидные для кого-то и без этого вещи.
Но почему-то функцию Эйлера и значок 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) 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), а что-то как минимум линейное (кроме совсем простых действий, скажем, чётность узнать). Предлагаю автору попробовать в этом разобраться.
Только вот ПМИ и ПИ на ФКН - как Мехмат "Математика" и Мехмат "Механика". ПИ не про сильные матан с дискреткой и алгосы с прогой. Там это всё гораздо слабее + есть ассемблер, архитектура и т.п. В статье, кстати, про Программную инженерию и речи не шло, а то можно было бы вспомнить ВШПИ МФТИ.
А как DoubleCommander по сравнению с Total Commander? Я точно и уверенно могу сказать после нескольких попыток юзать mc, что он полная чушь по сравнению с TotalCmd (как минимум из-за консольности). Надеюсь, эта прога ближе к нему, чем к mc.
Согласно инициативе регулятора, операторы связи обязаны предоставлять Роскомнадзору информацию, позволяющую идентифицировать средства связи и пользовательское оборудование в интернете
Потом:
В ответе на отзыв МТС в Роскомнадзоре настаивают, что проект не требует от операторов предоставлять сведения, составляющие тайну связи. Идентификация отдельных пользователей и их пользовательского оборудования не требуется
Что-то не кажется мне, что MSVC в C++20/23 прям уж хорошо соответствует стандарту. Как там обстоит вопрос с перегрузками? А синтаксис лямбд без явного указания скобочек (когда без аргументов) завезли?
Угу, значит, это сильно урезанный функционал тех же GoodbyeDPI / ByeDPI[Android] / zapret. А в чём его преимущество перед уже существующими решениями? В том, что он проще? Тогда зачем все эти сложности в других приложениях, раз всё так просто?
Я примерно понимаю, как работают решения через WinDivert - он буквально становится вашей сетью и решает, какие пакеты будут в ней ходить (в частности, может дропать и даже спавнить пакеты). А тут какой механизм? Допустим, браузеру мы можем объяснить, что у нас тут прокся - иди туда. Иногда у отдельных приложений есть свои настройки прокси - тоже прописать можем. Есть ещё якобы глобальные настройки прокси в винде - а это как работает? Неужели любое приложение в системе при попытке куда-то зайти по интернету автоматически улетит сначала на прокси (причём абсолютно прозрачно)? А пиннинг сертификатов тут не помешает нигде?
Наконец, последний вопрос, не совсем про-данное решение, но всё же - а как эти дурилки согласовываются с защитой от DNS-спуфинга? Я до сих пор не понял, как грамотно настроить систему и браузеры, чтобы по дефолту резолвилось через Claudflare, а если не нашлось там, то фоллбэк на текущий дефолтный в системе (который, вроде, сообщает наш источник интернета, т.е. я это могу в свойствах соединения WiFi прочитать). Мне прям важно, чтобы был фоллбэк, а то до внутренних сайтов в сети достучаться не получится.
Он уже есть, но смысл у него - применение указателя на член класса к объекту.
Да алгоритм тут не при чём! Читающие статью видят вот это (см. скриншот):
Прежде, чем читать дальше, читатель подставляет p = 10, q = 11 сюда, от греха подальше. Видит
D = -1 = 30n + 1. Это ни при каком n не выполнено, значит, автор где-то ошибся. Статью можно, в целом, закрывать. Что там какой-то алгоритм потом описывается - уже неважно.Душню ли я? Есть такое... Но это прям сразу бросилось в глаза.
Что касается асимптотики, в другой ветке вам довольно хорошо расписали, почему не доказано наличие корня (если коротко - перебираются не числа до корня, а просто какие-то числа, которые могут дать два делителя в итоге, например, на последней итерации алгоритма).
Можете, кстати, добавить счётчик в программу и после разложения сравнить кол-во опробованных пар (n, δ), прежде чем получился квадрат, с корнем из N. Затем прогоните программу на всех числах подряд (составных, конечно, раз уж простые вы не поддерживаете). Честно интересно, насколько на практике выполняется ваше голословное утверждение.
Да не в этом противоречие! Ещё раз повторяю: в статье приведено утверждение `D = p - q = 30n +δ`. Я предложил вам подставить туда p = 10 и q = 11. Мы получим слева минус единицу, а справа: 30n + 1 (сами так сказали в первом комментарии: "δ в этом случае будет 1"!). Вот оно - противоречие! 30n + 1 ни при каких n не равно минус единице.
2) Ваша ошибка довольно интересная - вы забыли рассмотреть случай, когда на вход алгоритму подаётся простое число. "Если делители есть..." Это всё замечательно, ну а если их нет? Вот тут-то собака зарыта!
Ваш алгоритм будет перебирать n и δ в надежде, что 4N + (30n + δ)^2, пока не переберёт все кандидаты, а их у вас 2*N/30 для n и k(N) для δ. То бишь k(N) * N/15 проверок нужно сделать. Т.к. пятнадцать - константа, а k(N) - ограниченная функция, мы их выкидываем из асимптотики. Получаем O(N).
На что отсылка?
p - qв статье без модуля в этой строчке. Подставляем 10 и 11 - получаем противоречие.Просто сказать, что я ошибаюсь... маловато будет. Мою логику я расписал, так что либо укажите точное место, где я ошибся в рассуждениях (с цитатой!), либо признайте свою ошибку.
Но почему-то функцию Эйлера и значок Z для обозначения множества целых чисел пояснять не стали.
Да не нужно тут специальных обозначений, просто напишите границы, в которых лежит δ. Если написать `0 <= δ < 30`, то читатель поймёт, что речь об обычном делении с остатком, где n - целая часть, а δ - остаток.
Думайте об этом так - когда читатель видит использование необъявленного символа (Δ), у него в голове вылетает исключение и статью он закрывает.
Ну да, а теперь подставьте 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) 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), а что-то как минимум линейное (кроме совсем простых действий, скажем, чётность узнать). Предлагаю автору попробовать в этом разобраться.
Для любителей Jetbrains - Силайт, для любителей LLVM - Клайт.
Только вот ПМИ и ПИ на ФКН - как Мехмат "Математика" и Мехмат "Механика". ПИ не про сильные матан с дискреткой и алгосы с прогой. Там это всё гораздо слабее + есть ассемблер, архитектура и т.п. В статье, кстати, про Программную инженерию и речи не шло, а то можно было бы вспомнить ВШПИ МФТИ.
А как DoubleCommander по сравнению с Total Commander? Я точно и уверенно могу сказать после нескольких попыток юзать mc, что он полная чушь по сравнению с TotalCmd (как минимум из-за консольности). Надеюсь, эта прога ближе к нему, чем к mc.
Если я не ошибаюсь, можно давать частичные права. Что конкретно хочет ботяра-то?
Если что, я с автором сообщения согласен, что это беспредел, просто решил дополнить.
Короче, каракатица сбивает эвристику поиска хищников в системе краба. Ему бы нейронку посильнее, да не был бы он уже крабом после этого!
У нас тут с некоторых пор кое-какие (кхе-кхе) узлы даже обычные TCP/UDP дропают.
Сначала (это до отзыва МТС):
Потом:
Эхх...
Что-то не кажется мне, что MSVC в C++20/23 прям уж хорошо соответствует стандарту. Как там обстоит вопрос с перегрузками? А синтаксис лямбд без явного указания скобочек (когда без аргументов) завезли?
Ну да.
Я на это отвечаю.
Для каждого нового репозитория ведь `--global` не нужен...?
Научные гипотезы могут быть либо опровергнутыми, либо ещё не опровергнутыми.