Comments / Profile of lightln2 / Habr

Oleg T@lightln2

программист

Subscribers

ProfileArticles6PostsNewsComments174

Тайна чисел‑близнецов

lightln2 Oct 1 at 09:20

я тоже против

Тайна чисел‑близнецов

lightln2 Sep 30 at 12:52

А можно как-то в статье упомянуть что, собственно, сделано, желательно, в общепринятых математических терминах? а то

Закономерность расположения составных чисел в рядах B(b) = 6b-1 и С© = 6с+1 позволяет создать решето для чисел‑близнецов

А вот Терренс Тао утверждает, что это принципиально невозможно!

Создан новый тип игральных костей, которые гарантируют отсутствие ничьей при определении победителя

lightln2 Sep 14 at 13:16

вроде бы, можно. Вот тут доказано, что всегда можно найти N permutation-fair кубиков, правда, разного размера. Но, насколько я понимаю, их всегда можно свести к кубикам одного размера (взяв наибольшее общее частное их количества граней, потом повторив каждую грань столько раз, что все кубики будут одинаковыми, но с повторяющимися числами, потом заменив каждое повторяющееся число на последовательность чисел, и увеличив все числа больше его соответственно).

Создан новый тип игральных костей, которые гарантируют отсутствие ничьей при определении победителя

lightln2 Sep 14 at 03:48

Я понимаю, что это перевод, но все же на Хабре хочется технических подробностей. Собсвенно, тут в комментариях люди пытаются угадать, что же за задача решается. В статье нет ни формулировки, ни решения.

Вместо статьи о том, что математики делают математику, один бородатый, а второй из Канады, хочется видеть что-то вроде такой статьи:

Сформулировать условие - n игроков бросают n кубиков с d гранями каждый, с различными числами на гранях 1 … nd. Выигрывает тот, кто выкинул максимальное число. Можно ли обеспечить равновероятность выигрыша каждым игроком?

Рассказать, что есть разные варианты задачи

каждый игрок выигрывает с равной вероятностью
любые k <= n игроков могут взять произвольные k кубиков и выиграть с равной вероятностью
результат обеспечивает любую перестановку игроков с равной вероятностью

Упомянуть, что для более простых условий есть тривиальные решения:

если разрешена ничья, то можно в случае ничьи продолжать кидать кубики, матожидание количества бросков будет константа
если можно брать разные кубики, то можно взять кубики с n, n-1, …, 1 гранями, и их результат будет задавать произвольную перестановку с равной вероятностью

В комментариях уже написали, что для двух игроков есть тривиальное решение (1,4) и (2,3) Для трех игроков уже надо искать брутфорсом, перебирая все варианты, простой скрипт на питоне выдает несколько решений, например, (0, 4, 8, 11, 13, 15) (1, 5, 6, 10, 12, 17) (2, 3, 7, 9, 14, 16).

Проверка, что кубики удовлетворяют условию задачи, делается за O(d^n), но можно применить оптимизацию, похожую на merge sort, ускоряющую ее до O(dn) (очень похоже на те самые всеми нелюбимые leetcode-задачи!).

При этом количество вариантов размещения чисел на кубиках растет экспоненциально, поэтому для трех достаточно скрипта на питоне, для четырех надо писать умные оптимизации, а для пяти чуваки решали задачу 15 лет, и до сих пор не знают, оптимально ли найденное решение.

Что математики говорят про влияние ИИ на математику?

lightln2 Sep 11 at 13:16

В общем, TLDR: LLM-ы в математике (как и в программировании), очень хорошо генерят write-only доказательство (код), решающий одну конкретную задачу. Сделать доказательства (код) переиспользуемыми, тем более, законтрибьютить в теорию (стандартную библиотеку), это они (пока?) не умеют.

Математики до сих пор не уверены, как быстрее всего перемножать числа

lightln2 Aug 28 at 10:46

а все-таки, где про это почитать? Там вроде должны быть физические ограничения на логические элементы - чтобы сделать сложение/умножение за O(1), надо, чтобы NAND элементы имели O(n) входов и выходов, что линейно увеличивает паразитную ёмкость, что замедляет распространение сигнала.

Необратимая операция: как печатать чек, если непонятно, напечатался ли он

lightln2 Aug 6 at 10:12

Спасибо, интересно с точки зрения архитектуры. А можно пояснение для тех, кто не в курсе?

фискальный документ и чек - это одно и то же?
что значит “печать”? реально физическая печать на реально физической бумажке? зачем? и что потом делают с бумажками, появляющимися [размер фермы / 0.7] в секунду?

OpenAI заявила о 10 математических прорывах: достижения новой модели Astra

lightln2 Aug 2 at 13:13

На самом деле, многие задачи и человеческими математиками решаются нахождением каких-то совершенно невообразимых примеров или контрпримеров. Что не удивительно, это в основном молодые математики, которые могут потратить огромное количество времени на задачи, которые непонятно как решать. Потом все остальные офигевают, как вообще до такого можно было додуматься.

Начиная с Рамануджана, который (пока что) на несколько порядков уделывает LLM-ы по нахождению безумных тождеств (и решению проблем, похожих на эту), и кончая классикой жанра - нахождением безумной вспомогательной функции для решения задачи о упаковке восьмимерных сфер (https://arxiv.org/abs/1603.04246). По таким прорывам можно писать отдельный обзор (я, навскидку, могу без гугла около десятка вспомнить).

Так что я скорее сошлашусь с комментаторами, утверждающими, что LLM тут решает задачи, которые и человекам под силу, просто до них пока никто не добрался. Тут интересный вопрос, можно ли будет такое поставить на поток в стиле Рамануждана.

HashLife на питоне

lightln2 Jul 18 at 14:43

Берем длинную палку длинной L шириной 1

да, вы правы.

Кстати, если вот как вы там обобщаете на окрестность p x p, то там скорость света вообще может быть p/2 и, похоже, периметр надо будет делать еще больше.

вроде, не надо: для $p^{k+1} \times p^{k+1} \to p^k \times p^k$ за k шагов скорость света . Чтобы перейти $p^k \to p^{k+1}$ , у нас есть периметр шириной $(p^{k+1} - p^k) / 2$ клеток, то есть, мы можем сделать $\frac{ (p^{k+1} - p^k) / 2 } {(p-1)/2} = p^k$ шага, именно это и делается, если взять массив $(2p-1) \times (2p-1)$ , положить в центр узел $p^k \times p^k$ и сделать один этап эволюции.

HashLife на питоне

lightln2 Jul 18 at 13:27

Как это делается для дерева 2x2 вообще? В вашей реализации выше я такой обработки не нашел. Кажется, можно поместить состояние в центр массива 3x3 и сделать 4 эволюции блоков 2x2 и получить 4 квадранта ответа

Тут я, похоже, ошибся: я хотел упростить, и корень $s^k \times s^k$ увеличиваю дважды до $s^{k+2}$ , и делаю ему evolve, и проблема в вашем агрументе про скорость света. Тут оно работает, потому что живые клетки в стандартных правилах “жизни” не могут двигаться быстрее, чем на T/2 клеток за T шагов, поэтому в корне всегда достаточно пустого периметра. Но для произвольного автомата, вы правы, поле может разрастить быстрее.

Поэтому, видимо, в общем случае надо делать последний этап в эволюции:

Для 3x3: 9x9 -> 7x7 -> 5x5 -> 3x3, нужен один этап 5x5 -> 3x3
для 2x2: 4x4 -> 3x3 -> 2x2, нужен один этап 3x3 -> 2x2
для $p \times p$ : один этап $2p - 1 \times 2p - 1 \to p \times p$

то это упрощает код

Интересно, я в этом направлении не думал. А у вас есть код посмотреть? Я пытался делать мапу 0 -> 0, 1 -> 1, там немного упрощается база рекурсии, но не сильно.

HashLife на питоне

lightln2 Jul 18 at 11:01

Я поразмышлял на досуге, тут вообще получается интересно.

Рассмотрим обобщенный клеточный автомат, у которого состояние клетки зависит от целой окрестности $p \times p$ , p = 3,5,7,… нечётно (в частном случае, может быть обычный автомат, в котором мы ходим сразу на шагов). Тогда тот же подход позволяет использовать $p \times p$ -дерево, с листом $1 \times 1$ , и эволюцией поля в этапов

$p^2 \times p^2 \to (p^2 - (p-1)) \times (p^2 - (p-1)) \to (p^2 - 2(p-1)) \times (p^2 - 2(p-1)) \dots \to p \times p$

Тогда эволюция узла будет $p^k \times p^k \to p^{k-1} \times p^{k-1}$ за $p^{k-1}$ шагов.

Но также мы можем поменять размер листа $1 \times 1 \to d \times d$ , тогда база эволюции будет $(p-1+d) \times (p-1+d) \to d \times d$ . Если мы подберем d так, чтобы было маленькое и целое, то мы можем сделать эволюцию в $s \times s$ дереве, узла $s^kd \times s^kd \to s^{k-1}d \times s^{k-1}d$ за $s^{k-1}$ шагов. То есть, мы разменяли часло шагов на размер узла и сложность его эволюции.

Альтернативно, мы можем сделать s степенью маленького целого, тогда можно уменьшить размер узла. Например, вместо $4 \times 4$ -дерева можно взять квадродерево, но в эволюции раскрывать не два уровня вложенности, а четыре. То есть, мы разменяли число шагов и сложность эволюции на размер узла.

Например, возьмем - стандартную окрестность. Тогда стандартная эволюция в $3 \times 3$ -дереве с листом $1 \times 1$ - мой вариант, или, если возьмем , будет эволюция в квадродереве с листом $2 \times 2$ - классический hashlife!

Если взять , то есть варианты:

$5 \times 5$ -дерево, лист $1 \times 1$ ,
$3 \times 3$ -дерево, лист $2 \times 2$ ,
квадродерево, лист $3 \times 3$ .

Для варианты:

$7 \times 7$ -дерево, лист $1 \times 1$ ,
$4 \times 4$ -дерево, лист $2 \times 2$ (можно использовать квадродерево, и раскрывать 4 уровня),
$3 \times 3$ -дерево, лист $3 \times 3$ ,
квадродерево, лист $6 \times 6$ .

В общем, в этом подходе, вариант $3 \times 3$ (и $p \times p$ в общем случае) является “естессвенным”, а hashlife получается как размен скорости эволюции на размер дерева и сложности шага эволюции. Было бы интересно провести анализ, но мне кажется, если все учесть, то асимптотически все варианты будут одинаковы.

Говорят, спортивное программирование портит код. Почему я с этим не согласен

lightln2 Jul 17 at 09:00

Бизнес разный бывает. В гугле/яндексе есть департаменты, разрабатывающие новые технологии, в high-frequency trading часто берут исключительно по успехам на олимпиадах. Кроме бизнеса бывает еще опен-сорс и research-проекты, для которых олимпиадный опыт более релевантен, чем бизнес-опыт. Конечно, таких мест в процентном соотношении мало, но туда трудно пробиться без олимпиадного опыта.

HashLife на питоне

lightln2 Jul 17 at 06:40

Как у вас, надо будет всех внуков корня квадро-дерева выписать в квадрат 4x4

Я сделал аналогичный код для квадродерева, по сложности получается примерно таким же! Усложняется эволюция листа, но упрощается эволюция корня. На моем примере вариант с квадродеревом работает в три раза быстрее, но при этом количество обработанных узлов - в пять раз меньше (то есть, время обработки одного узла сильно хуже, по крайней мере, в данной реализации на питоне).

hashlife3x3

hashlife2x2

Но все равно мне вариант с 3x3 кажется интуитивно более понятным.

HashLife на питоне

lightln2 Jul 16 at 21:41

Это сильно эффективнее вашего варианта со сторонами из степени 3.

Эффективность зависит только от количества разных узлов. Насколько я понимаю, ваши вычисления касаются случайной популяции, при которой количество узлов экспоненциально, и hashlife работает медленно. В реальности он хорошо работает на регулярных структурах, и там все зависит от того, как именно они регулярны. Если есть много структур с симметрией сдвига кратной степерям двойки, то стандартный hashlife будет лучше. Если кратной степеням тройки - то мой вариант.

Откуда вы вообще 3 взяли?

Я делал оба варианта hashlife для версии клеточного автомата (не “жизнь”, но не принципиально), в которой много структур, симметричных относительно сдвига на 3^k клеток, но не на 2^k. Моя версия действительно была быстрее (в пять раз), но что я не ожидал, что реализация будет проще, чем квадродерево. К тому же, мне идея эволюции квадрата 3x3 кажется более естесственной, чем 4x4 - собственно, я и хотел этим поделиться.

Была еще и другая конфигурация, в которой симметрия была фрактальной со сдвигом 2^k. Ожидаемо, там стандартный hashlife работал за логарифм, а мой вариант вырождался в линию.

У меня недостаточно данных, чтобы утверждать, какой из вариантов лучше на практике в среднем. Навскидку, вариант с квадродеревом требует меньше памяти, но вариант с 3x3-деревом легче написать и отладить.

Самовлюблённые числа: когда нарциссизм и бесполезность вдохновляют

lightln2 May 19 at 15:08

С этим сложно поспорить, но можно переформулировать задачу как найти такие $a_1, \dots, a_n < B$ , что

$\sum{B^i a_i} = \sum{a_i^n}$

что является частным случаем диофантовых уравнений! А вообще, статья интересная, спасибо! Не хватает только списка самих чисел.

Структуры данных на практике. Глава 15: Графы и их обход с эффективным использованием кэша

lightln2 May 11 at 21:08

А по теме, есть хорошая лекция от MIT про оптимизацию BFS, с акцентом на многопоточность, но и однопоточные оптимизации тоже раскрываются. Там, кстати, рассказывают, как именно считаются эти cache misses, и как оптимизации их улучшают.

Это все если граф влезает в память. BFS для графов, которые не влезают в память - это отдельный мир, с десятилетиями научных исследований и сотней эзотерических алгоритмов.

Структуры данных на практике. Глава 15: Графы и их обход с эффективным использованием кэша

lightln2 May 11 at 21:00

Что мне больше всего тут непонятно, это как там на графе из 500 вершин и 6000 ребер даже в самой оптимизированной версии насчиталось почти миллион cache misses.

Ну и вообще, я посмотрел в оригинал, он оставляет странное впечатление - товарищ работает с низкоуровневым программированием, пишет книгу аж из 20 глав, в ней все баззворды на своих местах. Но он зациклен на cache misses, и его аргументация местами очень странная. То ли очень неаккуратно написано (при чем тут Radix Tree?), то ли вообще цифры с потолка взяты.

Беззнаковые размеры: пять лет назад мы совершили ошибку

lightln2 May 10 at 08:38

Кажется, автор еще забыл упомянуть, что переполнение знаковых - это undefined behavior в C++, если делать offset/length знаковыми, то это придется как-то чинить.

Но совсем избавляться от беззнаковых тоже кажется не самой лучшей идеей, тогда, как в Яве, придется вводить оператор “>>>” (беззнаковый сдвиг вправо), и будут проблемы с поддержкой форматов хранения, где значения беззнаковые, например, массив uint8.

Но когда корректность важнее скорости, то имхо, знаковые оффсеты и длины массивов кажутся хорошим компромисом: можно вставить дополнительные проверки на неотрицательность при создании массива и обращении к его элементам (в 99% случаев оно не скажется на производительности, так как проверка будет на свободном ALU-порту, и branch prediction тоже отработает параллельно)

В общем, мне нравится подход как в C#, придуманный много лет назад:

длины и оффсеты массивов знаковые, исключения при обращениях out-of-bounds
есть беззнаковые, если нужны, более-менее разумные правила автоматического преобразования
если важно не поймать overflow, есть опциональный checked{} контекст, в котором оно вызовет исключение
Eсли надо выжать последние полпроцента производительности, есть unsafe{} контекст, в котором можно создать массив байт через malloc, и дальше уже с ним извращаться, как душе угодно.

Не бойтесь динамического программирования

lightln2 Apr 1 at 09:18

Многие, кто работают в гугле/яндексе пишут дп регулярно. Но конкретно

использовать в реальном рабочем процессе

Вы это делаете каждый день, когда выполняете git diff - он основан на алгоритме Майерса, варианте Longest Common Subsequence Problem, являющегося классикой DP!

Игра в угадайку

lightln2 Apr 1 at 07:15

Спасибо, отличный обзор! Тем не менее, хотел бы указать на потенциально не раскрытые вами подходы:

Теория игр и теорема минимакса - представить задачу как игру, где один игрок выбирает число, не противоречащее предыдущим проверкам, а второй пытается его угадать за минимальное число проверок.
Иммунные алгоритмы - если честно, я мало что при них знаю, но ученые, с ними работающие, утверждают, что это гораздо круче генетических алгоритмов!
Целочисленное Линейное Программирование - вроде должно работать, потому что каждое угадывание задает линейное ограничение (то есть, гиперплоскость в одномерном пространстве)!

2 3 ...

8 9