комп стал побеждать не с помощью перебора и просчёта всех ходов.
Но:
комп играл миллионы партий сам с собой
Это и есть все тот же перебор и просчет ходов, только вынесенный в предподсчет и результат которого сархивирован в весах у нейросетки с какими-то потерями. Отличный прорыв в программировании и практическом применении перебора. Но качественного изменения сути алогоритма не произошло.
Просто перебирать все это долго и во время игры не будут человеки ждать 3 дня следующего хода. А когда датацентры миллионы часов процессороного времени эти же ходы считают до игры, а во время игры думают не так долго, это уже удобнее на практике.
Нет, у вас, кстати, надо проверять и не только взаимнопростые с 30 числа. Как раз потому что у вас другая логика алгоритма, основанная на другой формуле. Простой алгоритм использует формулу N=xk и перебирает x, ваш использует N=(x^2-k^2)/4 и тоже перебирает x. В простом, поскольку нас интересуют только простые x, можно исключить какие-то дельты. В вашем, поскольку разность квадратов должна давать определенный остаток по модулю 30, а квадраты дают только определенное подмножество остатоков, можно подобрать какие остатки должен иметь x. Тут другая логика отсечения, которая вытекает из выбранной формулы.
Нет, ваш метод не проверяет, делится ли N на 30n+d. Вы считаете делитель по формуле (30n+d-k)/2, если вычисленное k=sqrt(4N+(30n+d)^2) целое. За счет этого вы фильтруете какие-то дельты, да.
Это признак делимости на 9. А числа, получившиеся после одного шага алгоритма, всегда делятся на 9. Потому что abcd-dcba=1000a+100b+10c+d - 1000d-100c-10b-1a = 999a+90b-90c-999d = 9(111a+10b-10c-111d).
В произвольной системе счисления будет делимость на BASE-1, и признак там такой же - рекурсивная сумма цифр, пока не получится число в одну цифру.
И основанно это все на факте что, BASE = 1 (mod BASE-1).
Про препринт все-таки скажу, в глаза бросилось: называть свой метод по своей фамилии, при том что вы сами говорите, что не математик - это вопиющая пошлость.
Это чем-то мне напоминает замечательное открытие юных натуралистов, которые много месяцев изучали муравьев и нашли удивительную закономерность, что граница муравейников примерно в 3 раза длинее их ширины.
Интересная идея. Но я бы не переоценивал ее практическую значимость.
Сложность O(sqrt(N)*k/30).
Есть еще более простой метод, который почти не медленнее, проще для понимания, легче параллелится и все остальное.
Перебираем все числа до 2 до sqrt(N) и проверяем, являются ли они делителями N. Для ускорения проверяем не все числа, а только те, что взаимнопросты с 30 (вида 30k+d). Мы же простой делитель ищем.
Использование разности квадратов у вас довольно хитро и возможно действительно позволяет сократить количество различных дельт с 8 до 2, но требует больше вычислений. Тут возведение в квадрат, сумма, а потом извлечение корня вместо одного деления. Плюс надо еще как-то модифицировать алгоритм извлечения корня, чтобы сразу проверить на целочисленность. А потом еще надо вычислить сами делители. Не факт, что это будет быстрее на самом деле.
Еще интересный вопрос, а могли бы вы привести таблицу? Сдается мне, что оно не всегда сокращает количество дельт и для каких-то остатков N по модулю 30 может дать больше 8 дельт.
@VAEСмотрите, у вас конкурент. Только тут используется обычная, общепринятая, всем понятная нотация, нет исторических отсылок с зашкаливающим пафасом, метод формально описан и приведена оценка его скорости. И сложность материала автор адекватно поставил "средний". Ваши статьи по сравнению с этим никуда не годятся. И результат налицо. Основная идея через формулу разницы квадратов почти такая же как у вас, но тут люди ее принимают и плюсы статье ставят, в отличии от ваших статей, где почему-то одни хейтеры собрались.
629 - это не общий случай. Общий случай - это N. Так что вам надо алгебраически, через теорию чисел, теорвер, или как-то еще доказать, что в таблице КВК всегда встретится сильно раньше, чем 2*sqrt(N) (один sqrt(N) пропустим - тривиальную область можно не считать).
Мне же достаточно привести только один контр-пример, чтобы опровергнуть ваш общий случай. И я не поленился и такой пример нашел.
Для числа 999993 первый нетривиальный КВК встречается в позиции 332333. Это в 300 раз больше корня! Вы тут, конечно, возразите, что делитель 3 тут можно легко найти вручную, то вот вам более приземленный пример: N=1211. Первый нетривиальный КВК тут на позиции 139. Даже если пропустить тривиальную область и начать с 35, то это 104 строки надо проверить. Что в 3 раза больше sqrt(N). Чем больше N, и чем меньше относительно него один из делителей, тем дальше находится решающий интервал и тем дольше его искать.
Колонка Тп содержит ПНЧ, для любых чисел N в ней делитель находится быстрее (это общий случай).
Т.е. выбрасываем все ваши Законы Распределения Делителей и Модель, и ищем делитель просто среди нечетных чисел? Да, это и школьнику очевидно. Правда, это же и есть тривиальный метод. С тем лишь гениальным улучшением, что четные числа не проверятся, потому что они, очевидно, не могут быть делителями нечетного N. Вот эта вот идея - это то как ваша Модель приминяется? Вам не стыдно такое писать вообще?
Стоит еще привести доказательство минимальности. При K раундах каждая мышь дает k+1 исхода - сколько раундов она пережила, от 0 до K. Поэтому имея N мышей мы не можем получить более (K+1)^N различных исходов. Поэтому больше (K+1)^N проверить даже теоретически нельзя, потому что каждый исход должен указывать на одну колбу.
И ничего. Ровно так же, как когда перебор для 629 нашел делитель на 9-ом шаге. Это частный случай. Надо смотреть, сколько там шагов будет для всех чисел в среднем или в худшем случае. Но у вас этих оценок нет, как нет и описания собственно перебора. Вы таблицу по порядку строите? Или генерируете строки, как в какой-то вашей прошлой статье?
Тут прямо мета-ирония и иерархия пузырей получается. Да, эта схема работает. Пока. В произвольный момент времени она перестанет работать, когда критическая масса людей перестанет вестись. Кто успел на ней заработать - молодец. Кто войдет слишком поздно - потеряет деньги.
Вы утверждаете о его тривиальности, но пруфов этого я пока не вижу
Вы этот факт заметили в табличке, но даже не доказали. Вот вам все доказательство по шагам. Пусть x - "КВК", т.е. x^2 = k^2 (mod N) для какого-то k^2 < N. По определению остатка от деления получаем x^2 = m*N + k^2. Перенесем известное k^2 и применим формулу разности квадратов: (x-k)(x+k) = m*N. Каждый простой делитель N должен встретиться или в x-k или в x+k. Если x-k > 0 и x+k < N (x не из тривиальной что-там у вас было), то делители N попадают в разные множетиели, а значит x-k и x+k делятся на делители N. Вот x - КВК - по середине между двумя делящимеся x-k и x+k. Вот ваш решающий интервал и его середина.
Вся суть и основная идея в школьной формуле a^2-b^2 = (a-b)(a+b). Это тривиальная идея. Все ее доказательство - одна-две строчки школькой математики. Это не может быть сложным не очевидным профессианальному математику факт.
Я предложил очередной подход (модель), в котором имеется обоснование для успешной факторизации
Вы его даже не формализовали, чтобы говорить о том, что вы что-то предложили. Вы научились раскрашивать таблицу, нашли какие-то закономерности, которые на самом деле описываются тривиальными школьными формулами и все. Ваша работа имела бы ценность, если бы вы все ваши закономерности, вроде ЗРД (он же формула разности квадратов), или случая, когда rccc+1 раскладывается на смежные сомножители, или чисел близнецов, формализовали и доказали, записали в виде четкого и понятного метода (вроде - если А, то применяем формулу B, если C, то формулу D, и т.д.) После чего доказали какие-то факты о применимости вашего метода. Скажем, rccc+1 применим ко всем числам вида (k^2-4)/3 (Это ваши излюбленные примеры N=407 и N=55).
Потом уже вашу охапку критериев надо будет систематизировать и обобщить. Например все ваши частные случаи фактически применимы к числам, у которых фиксированна разность делителей. Вот уже вы решили задачу, когда разность делителей относительно небольшая, что хорошо дополняет тривиальный метод, при котором маленькие делители быстро находятся (ведь, если они большие, то их разность мала). Как-то их оба скрестив вы, может быть, могли бы вывести переборный метод с N^0.(3) в худшем случае. Пришлось бы какие-нибудь суммы рядов или интегралы и теорию чисел с теорией вероятности применить наверняка. Хотя это вряд ли. Но вот это был бы результат и сложный материал, а не вот эти ваши таблицы без единой формулы и доказательства. И фактически без математики.
Для N=629 в пределах ТКВК перебираем колонку tп, т.е. N:tп, на шаге 9, tп=17и
Это не доказательство общего случая. Так-то для 33 тупой перебор найдет делитель 3 уже на третьем шаге. Это значит, что этот наивный, известный сотни лет алгоритм - работает быстро? Все, ваш метод не нужен, ибо вот уже метод, который аж за 3 шага находит делители?
Для какого-нибудь числа из 20 знаков вашему методу понадобится условных 5 миллиардов строк перебрать, что фактически и есть sqrt(N). Если вы опишите мне ваш метод перебора (хоть раз его опишите уже, наконец-то! Часть про КВК мне очевидна, вопрос, как этот КВК найти), я вам смогу нагенерировать на компьютере сколько угодно чисел, где ваш перебор почти корень из N строк посмотрит.
Вообще, не обязательно состояния детерменированного НКА нумеровать именно так - битовой маской. Это лишь один из вариантов.
Если вводить тут концепцию детерминизации НКА, то это только запутывает. Суть-то не в том, чтобы получить состояние в виде одного числа. Суть в том, чтобы все вычисления делать одной битовой операцией.
Да, можно считать, что тут идет работа с ДКА, у которого вместо таблицы рассчитываются состояния. Но ведь так можно смотреть и на вообще любой НКА. Вместо таблицы с 2^n состояний тут по какому-то алгоритму идет рассчет нового состояния (хоть и с использованием таблицы на n состояний)
И вообще, на любую программу можно смотреть как на машину тьюринга. Концептуально одно и тоже, но смысла в этом маловато. Даже если какая-то оптимизация алгоритма вводит переходы чего-то влево/вправо и какие-то таблицы.
Еще есть игры серии X. Последняя X4 Foundation вышла недавно относительно. Но и в первых трех экономика симулируется весьма серъезно. Там можно понастроить фабрик и уронить цену ресурса почти в ноль. Можно уничтожить фабрики фракции в окресности, ресурса станет мало и цена взлетит в облака.
Но:
Это и есть все тот же перебор и просчет ходов, только вынесенный в предподсчет и результат которого сархивирован в весах у нейросетки с какими-то потерями. Отличный прорыв в программировании и практическом применении перебора. Но качественного изменения сути алогоритма не произошло.
Просто перебирать все это долго и во время игры не будут человеки ждать 3 дня следующего хода. А когда датацентры миллионы часов процессороного времени эти же ходы считают до игры, а во время игры думают не так долго, это уже удобнее на практике.
Итак, что написал я выше:
Что написали вы:
Т.е. вам надо найти строку xo=332333, как центр РИ. Ровно как я писал. Это сколько операций?
Нет, у вас, кстати, надо проверять и не только взаимнопростые с 30 числа. Как раз потому что у вас другая логика алгоритма, основанная на другой формуле. Простой алгоритм использует формулу N=xk и перебирает x, ваш использует N=(x^2-k^2)/4 и тоже перебирает x. В простом, поскольку нас интересуют только простые x, можно исключить какие-то дельты. В вашем, поскольку разность квадратов должна давать определенный остаток по модулю 30, а квадраты дают только определенное подмножество остатоков, можно подобрать какие остатки должен иметь x. Тут другая логика отсечения, которая вытекает из выбранной формулы.
Но ведь 998^2 = 996004 < 999993. Это квадрат в тривиальной области. Его нельзя исползовать для поиска делителя.
А как же решающие интервалы, КВК, Закон Распределения Делителей?
Вся модель сдулась до тупо 1,3,5,7,9...?
У вас ошибка в программе. 999993 не делится на 998, оно делится только на 3 и на 333331.
Как? Если там всего 4 шага, то приведите их, пожалуйста.
Нет, ваш метод не проверяет, делится ли N на 30n+d. Вы считаете делитель по формуле (30n+d-k)/2, если вычисленное k=sqrt(4N+(30n+d)^2) целое. За счет этого вы фильтруете какие-то дельты, да.
Это признак делимости на 9. А числа, получившиеся после одного шага алгоритма, всегда делятся на 9. Потому что abcd-dcba=1000a+100b+10c+d - 1000d-100c-10b-1a = 999a+90b-90c-999d = 9(111a+10b-10c-111d).
В произвольной системе счисления будет делимость на BASE-1, и признак там такой же - рекурсивная сумма цифр, пока не получится число в одну цифру.
И основанно это все на факте что, BASE = 1 (mod BASE-1).
Про препринт все-таки скажу, в глаза бросилось: называть свой метод по своей фамилии, при том что вы сами говорите, что не математик - это вопиющая пошлость.
Это чем-то мне напоминает замечательное открытие юных натуралистов, которые много месяцев изучали муравьев и нашли удивительную закономерность, что граница муравейников примерно в 3 раза длинее их ширины.
Интересная идея. Но я бы не переоценивал ее практическую значимость.
Есть еще более простой метод, который почти не медленнее, проще для понимания, легче параллелится и все остальное.
Перебираем все числа до 2 до sqrt(N) и проверяем, являются ли они делителями N. Для ускорения проверяем не все числа, а только те, что взаимнопросты с 30 (вида 30k+d). Мы же простой делитель ищем.
Использование разности квадратов у вас довольно хитро и возможно действительно позволяет сократить количество различных дельт с 8 до 2, но требует больше вычислений. Тут возведение в квадрат, сумма, а потом извлечение корня вместо одного деления. Плюс надо еще как-то модифицировать алгоритм извлечения корня, чтобы сразу проверить на целочисленность. А потом еще надо вычислить сами делители. Не факт, что это будет быстрее на самом деле.
Еще интересный вопрос, а могли бы вы привести таблицу? Сдается мне, что оно не всегда сокращает количество дельт и для каких-то остатков N по модулю 30 может дать больше 8 дельт.
@VAEСмотрите, у вас конкурент. Только тут используется обычная, общепринятая, всем понятная нотация, нет исторических отсылок с зашкаливающим пафасом, метод формально описан и приведена оценка его скорости. И сложность материала автор адекватно поставил "средний". Ваши статьи по сравнению с этим никуда не годятся. И результат налицо. Основная идея через формулу разницы квадратов почти такая же как у вас, но тут люди ее принимают и плюсы статье ставят, в отличии от ваших статей, где почему-то одни хейтеры собрались.
629 - это не общий случай. Общий случай - это N. Так что вам надо алгебраически, через теорию чисел, теорвер, или как-то еще доказать, что в таблице КВК всегда встретится сильно раньше, чем 2*sqrt(N) (один sqrt(N) пропустим - тривиальную область можно не считать).
Мне же достаточно привести только один контр-пример, чтобы опровергнуть ваш общий случай. И я не поленился и такой пример нашел.
Для числа 999993 первый нетривиальный КВК встречается в позиции 332333. Это в 300 раз больше корня! Вы тут, конечно, возразите, что делитель 3 тут можно легко найти вручную, то вот вам более приземленный пример: N=1211. Первый нетривиальный КВК тут на позиции 139. Даже если пропустить тривиальную область и начать с 35, то это 104 строки надо проверить. Что в 3 раза больше sqrt(N). Чем больше N, и чем меньше относительно него один из делителей, тем дальше находится решающий интервал и тем дольше его искать.
Т.е. выбрасываем все ваши Законы Распределения Делителей и Модель, и ищем делитель просто среди нечетных чисел? Да, это и школьнику очевидно. Правда, это же и есть тривиальный метод. С тем лишь гениальным улучшением, что четные числа не проверятся, потому что они, очевидно, не могут быть делителями нечетного N. Вот эта вот идея - это то как ваша Модель приминяется? Вам не стыдно такое писать вообще?
Стоит еще привести доказательство минимальности. При K раундах каждая мышь дает k+1 исхода - сколько раундов она пережила, от 0 до K. Поэтому имея N мышей мы не можем получить более (K+1)^N различных исходов. Поэтому больше (K+1)^N проверить даже теоретически нельзя, потому что каждый исход должен указывать на одну колбу.
Там сильно более сложная версия задачи. Надо найти минимальное количество подопытных, чтобы опеределить отраву за K раундов.
И ничего. Ровно так же, как когда перебор для 629 нашел делитель на 9-ом шаге. Это частный случай. Надо смотреть, сколько там шагов будет для всех чисел в среднем или в худшем случае. Но у вас этих оценок нет, как нет и описания собственно перебора. Вы таблицу по порядку строите? Или генерируете строки, как в какой-то вашей прошлой статье?
Тут прямо мета-ирония и иерархия пузырей получается. Да, эта схема работает. Пока. В произвольный момент времени она перестанет работать, когда критическая масса людей перестанет вестись. Кто успел на ней заработать - молодец. Кто войдет слишком поздно - потеряет деньги.
Вы этот факт заметили в табличке, но даже не доказали. Вот вам все доказательство по шагам.
Пусть x - "КВК", т.е. x^2 = k^2 (mod N) для какого-то k^2 < N. По определению остатка от деления получаем x^2 = m*N + k^2. Перенесем известное k^2 и применим формулу разности квадратов: (x-k)(x+k) = m*N. Каждый простой делитель N должен встретиться или в x-k или в x+k. Если x-k > 0 и x+k < N (x не из тривиальной что-там у вас было), то делители N попадают в разные множетиели, а значит x-k и x+k делятся на делители N. Вот x - КВК - по середине между двумя делящимеся x-k и x+k. Вот ваш решающий интервал и его середина.
Вся суть и основная идея в школьной формуле a^2-b^2 = (a-b)(a+b). Это тривиальная идея. Все ее доказательство - одна-две строчки школькой математики. Это не может быть сложным не очевидным профессианальному математику факт.
Вы его даже не формализовали, чтобы говорить о том, что вы что-то предложили. Вы научились раскрашивать таблицу, нашли какие-то закономерности, которые на самом деле описываются тривиальными школьными формулами и все.
Ваша работа имела бы ценность, если бы вы все ваши закономерности, вроде ЗРД (он же формула разности квадратов), или случая, когда rccc+1 раскладывается на смежные сомножители, или чисел близнецов, формализовали и доказали, записали в виде четкого и понятного метода (вроде - если А, то применяем формулу B, если C, то формулу D, и т.д.) После чего доказали какие-то факты о применимости вашего метода. Скажем, rccc+1 применим ко всем числам вида (k^2-4)/3 (Это ваши излюбленные примеры N=407 и N=55).
Потом уже вашу охапку критериев надо будет систематизировать и обобщить. Например все ваши частные случаи фактически применимы к числам, у которых фиксированна разность делителей. Вот уже вы решили задачу, когда разность делителей относительно небольшая, что хорошо дополняет тривиальный метод, при котором маленькие делители быстро находятся (ведь, если они большие, то их разность мала). Как-то их оба скрестив вы, может быть, могли бы вывести переборный метод с N^0.(3) в худшем случае. Пришлось бы какие-нибудь суммы рядов или интегралы и теорию чисел с теорией вероятности применить наверняка. Хотя это вряд ли. Но вот это был бы результат и сложный материал, а не вот эти ваши таблицы без единой формулы и доказательства. И фактически без математики.
Это не доказательство общего случая. Так-то для 33 тупой перебор найдет делитель 3 уже на третьем шаге. Это значит, что этот наивный, известный сотни лет алгоритм - работает быстро? Все, ваш метод не нужен, ибо вот уже метод, который аж за 3 шага находит делители?
Для какого-нибудь числа из 20 знаков вашему методу понадобится условных 5 миллиардов строк перебрать, что фактически и есть sqrt(N). Если вы опишите мне ваш метод перебора (хоть раз его опишите уже, наконец-то! Часть про КВК мне очевидна, вопрос, как этот КВК найти), я вам смогу нагенерировать на компьютере сколько угодно чисел, где ваш перебор почти корень из N строк посмотрит.
Ну так эквивалентность же. Значит любую реализацию НКА можно рассматривать как работу с некоторым эквивалентным ДКА. Но статья и алгоритм не об этом.
Вообще, не обязательно состояния детерменированного НКА нумеровать именно так - битовой маской. Это лишь один из вариантов.
Если вводить тут концепцию детерминизации НКА, то это только запутывает. Суть-то не в том, чтобы получить состояние в виде одного числа. Суть в том, чтобы все вычисления делать одной битовой операцией.
Да, можно считать, что тут идет работа с ДКА, у которого вместо таблицы рассчитываются состояния. Но ведь так можно смотреть и на вообще любой НКА. Вместо таблицы с 2^n состояний тут по какому-то алгоритму идет рассчет нового состояния (хоть и с использованием таблицы на n состояний)
И вообще, на любую программу можно смотреть как на машину тьюринга. Концептуально одно и тоже, но смысла в этом маловато. Даже если какая-то оптимизация алгоритма вводит переходы чего-то влево/вправо и какие-то таблицы.
Еще есть игры серии X. Последняя X4 Foundation вышла недавно относительно. Но и в первых трех экономика симулируется весьма серъезно. Там можно понастроить фабрик и уронить цену ресурса почти в ноль. Можно уничтожить фабрики фракции в окресности, ресурса станет мало и цена взлетит в облака.