Было бы неплохо указать авторство рассматриваемых объектов. Обидно, когда забывают такие фамилии, как Лагранж, Ньютон. Было бы замечательно, если автор добавит пару параграфов про выбор узлов интерполяции, упомянув фамилию нашего математика Чебышева. На самом деле тема очень востребованная. В технических вузах обычно ее дают примерно на 2 курсе.
В статье сделано моделирование (ака Монте-Карло), распределение перестановок получено равномерное.
В конце статьи есть ссылка на оригинальную статью, там есть доказательства.
Да.
Именно поэтому существуют различные методы минимизации булевых функций. Но Они по большей части для ДНФ и КНФ.
Пример.
Это одна и та же функция. В одном и том же базисе.
заданная разработчиком логическая схема приводится к единому базису (И-НЕ, ИЛИ-НЕ)
ну я это и говорил. Схемотехника позволяет реализовать только эти элементы. А методы дискретной математики, работают по большей части для ДНФ, КНФ и полиномов. Поэтому, чтобы построить некоторую управляющую функцию надо сначала представить ее в виде ДНФ, КНФ или полинома (используя различные методы синтеза схем), а потом заменить все элементы их представлениями через И-НЕ, ИЛИ-НЕ.
Кстати, подходы к синтезу есть разные. Схемы можно строить минимизируя сложность, или максимизируя надежность. Если говорить о надежности, то при использовании любого из указанных базисов лучший результат не получить (есть базисы которые дают более высокие оценки надежности). Если интересно, могу ссылку дать на автореферат или диссертацию.
1) Генерируем равномерно распределенные случайные числа (например, в диапазоне 0..1) для каждого элемента последовательности, для которой мы хотим получить случайную перестановку.
В вашем случае, числами 0 и 1 не обойдешся. Rand должен давать случайные числа из диапазона шириной существенно большей числа элементов перестановки.
Предложенный метод, сильно напоминает тасование Кнута (вариант с сортировкой). У оригинального алгоритма Кнута (Фишера–Йетса) асимптотика O(n).
Асимптотическая оценка скорости сортировки в лучшем случае равна O(n log n), что несравнимо с оценкой O(n) скорости работы оригинального тасования Кнута. Cортирующий метод дает несмещенные перестановки, но он менее чувствителен к возможным проблемам генератора случайных чисел. Однако следует уделить особое внимание генерации случайных чисел, чтобы избежать повторения, поскольку алгоритм с сортировкой, в общем случае, не сортирует элементы случайно.
1. Если rand генерирует равномерно распределенные числа, то перестановки, полученные им, также будут иметь равномерное распределение. Думаю, если сделать проверку аналогичную той, что делал я в статье, то перестановки сгенерируются с равномерным распределением.
Про гарантированное распределение, тут все определяется качеством чисел, которые выдает rand.
2. Возможно, предложенный Санделиусом алгоритм и не самый быстрый, но не такой требовательный к качеству входной последовательности (смотрите в табличке третью строку там вероятность появления нулей 0,9, но перестановки все равно получаются равномерно распределенными).
С ростом n для вам будут нужны все более длинные числа с равномерным распределением в заданном диапазоне…
n=256 около 1700 бит
n=512 около 3900 бит
n=1024 около 8800 бит
n=2048 около 19600 бит
В каждом случае вам потребуется гарантировать (доказывать) независимость и равномерность распределения. этих чисел.
И если мне не изменяет память, чтобы номер преобразовать в подстановку вам потребуется делить длинные числа и находить остатки от деления длинных чисел.
А так, наверное, проблем больше не будет…
Вы немного не поняли. Сопоставить элементам массива биты, не означает записать их в этот массив. Массив Р содержит элементы, которые нужно переставить. В вашем случае будет так:
P=[1,2,3,4,5,6,7];
g=[0,1,0,1,1,0,1];
Тогда массивы Р0 и Р1:
P0=[1,3,6];
P1=[2,4,5,7];
Нужен ли в статье модельный пример? Мне казалось все достаточно понятным.
есть ли примеры практической пользы от представления логических
Плиномы Жегалкина или АНФ — удобное представление булевых функций. Их использование можно увидеть во многих работах. С полиномами работать проще и удобнее, чем с ДНФ или КНФ.
Можно сказать, что это одно из базовых понятий в дискретной математике. Например, понятие линейных функций (см. замкнутые классы, теорема о полноте) вводится с их использованием.
Еще одной особенностью является отсутствие фиктивных переменных в представлнии функции через АНФ.
для задач вроде проектирования микросхем операция «исключающее ИЛИ» является невыгодной: на ее реализацию требуется больше логических элементов, чем для базиса вроде «И-НЕ»
В вопросах схемотехники я, конечно, профан. Буду рад если меня поправят. Элементы типа и-не и или-не эффективно реализуются при помощи транзисторов. Более того, других вариантов нет, и ничего не остается, кроме как реализовать все остальные функции (или, и, не, xor) через и-не или или-не, чтобы использовать изученный математический аппарат.
Если найти представление какой-нибудь логической функции в виде полинома Жегалкина — есть ли польза от рассмотрения этого полинома на поле действительных чисел? Имеет ли такой полином какое-нибудь отношение к рассматриваемой логической функции, дает ли он пользу для ее анализа?
Понятие «поля» предпологает наличие двух операций сложения и умножения над элементами. «xor» и «и» вводятся над множеством {0,1}, а не над действительными числами. Может быть я неверно понимаю ваш вопрос?
Да, не удачно выразился. Не о велосипеде речь. Хотел сказать, что-то типа «найти подходящий генератор (проверенный, с нужными свойствами), отличный от стандартного, и реализовать его в своей программе», а получилось, как всегда.
Зачем изобретать велосипед, когда есть PCG32?
Я не хотел совсем касаться темы конкретных генераторов ПСЧ, хотелось только обратить внимание на важность их выбора.
Что касается конкретного генератора.
Тут выбор богатый, и PCG32 — это всего лишь один из многих. Если бы в решении этой задачи (генерации ПСЧ) все было бы так просто, то было бы ровно одно решение.
Каждый выбирает, то что ему подходит лучше для решения конкретной задачи. Это мое мнение, возможно оно ошибочно, но пока такая концепция меня не подводила.
Указанные алгоритмы несколько выходят за рамки данной заметки.
Vegas — алгоритм или лучше сказать, конкретное решение, приближающее распределение используемой случайной величины к |g(x)| / I. Иными словами выбирает плотность распределения пропорционально |g(x)| на сколько это возможно. О необходимости этого я говорил.
MISER — алгоритм, разбивает область интегрирования на две части рекурсивно до некоторой глубины. К каждой полученной области, применяется метод Монте-Карло. А количество итераций алгоритма в каждой области выбирается так, чтобы суммарная дисперсия получаемой оценки была минимальной.
Но, возможно, ссылка на библиотеку кому-то пригодится.
Спасибо, за комментарий. Полностью с вами согласен. Последние замечания в статье направлены больше на студенческую аудиторию. Например, я в студенческие годы (лет 13 назад) был удивлен результатом моделирования (при N>10^10).
Добавлю, что вариаций на тему генераторов случайных чисел очень много. Например, я часто использую для таких целей хорошо изученные криптографические алгоритмы (например, наши ГОСТы).
Вы видимо мой код посмотрели… Подскажите, где кушает память. Вы то вот написали код, который сгенерирует файлы sitemap.xml, которые не будут приняты поисковыми системами (часто сайтмапы не добираются до ограничения в 50000 ссылок, 10Мб достигается раньше).
В конце статьи есть ссылка на оригинальную статью, там есть доказательства.
Именно поэтому существуют различные методы минимизации булевых функций. Но Они по большей части для ДНФ и КНФ.
Пример.
Это одна и та же функция. В одном и том же базисе.
ну я это и говорил. Схемотехника позволяет реализовать только эти элементы. А методы дискретной математики, работают по большей части для ДНФ, КНФ и полиномов. Поэтому, чтобы построить некоторую управляющую функцию надо сначала представить ее в виде ДНФ, КНФ или полинома (используя различные методы синтеза схем), а потом заменить все элементы их представлениями через И-НЕ, ИЛИ-НЕ.
Кстати, подходы к синтезу есть разные. Схемы можно строить минимизируя сложность, или максимизируя надежность. Если говорить о надежности, то при использовании любого из указанных базисов лучший результат не получить (есть базисы которые дают более высокие оценки надежности). Если интересно, могу ссылку дать на автореферат или диссертацию.
Я правильно понимаю, FPGA — это ПЛИС по нашему?
В вашем случае, числами 0 и 1 не обойдешся. Rand должен давать случайные числа из диапазона шириной существенно большей числа элементов перестановки.
Предложенный метод, сильно напоминает тасование Кнута (вариант с сортировкой). У оригинального алгоритма Кнута (Фишера–Йетса) асимптотика O(n).
Асимптотическая оценка скорости сортировки в лучшем случае равна O(n log n), что несравнимо с оценкой O(n) скорости работы оригинального тасования Кнута. Cортирующий метод дает несмещенные перестановки, но он менее чувствителен к возможным проблемам генератора случайных чисел. Однако следует уделить особое внимание генерации случайных чисел, чтобы избежать повторения, поскольку алгоритм с сортировкой, в общем случае, не сортирует элементы случайно.
1. Если rand генерирует равномерно распределенные числа, то перестановки, полученные им, также будут иметь равномерное распределение. Думаю, если сделать проверку аналогичную той, что делал я в статье, то перестановки сгенерируются с равномерным распределением.
Про гарантированное распределение, тут все определяется качеством чисел, которые выдает rand.
2. Возможно, предложенный Санделиусом алгоритм и не самый быстрый, но не такой требовательный к качеству входной последовательности (смотрите в табличке третью строку там вероятность появления нулей 0,9, но перестановки все равно получаются равномерно распределенными).
n=256 около 1700 бит
n=512 около 3900 бит
n=1024 около 8800 бит
n=2048 около 19600 бит
В каждом случае вам потребуется гарантировать (доказывать) независимость и равномерность распределения. этих чисел.
И если мне не изменяет память, чтобы номер преобразовать в подстановку вам потребуется делить длинные числа и находить остатки от деления длинных чисел.
А так, наверное, проблем больше не будет…
P=[1,2,3,4,5,6,7]; g=[0,1,0,1,1,0,1];Тогда массивы Р0 и Р1:
P0=[1,3,6]; P1=[2,4,5,7];Нужен ли в статье модельный пример? Мне казалось все достаточно понятным.
Плиномы Жегалкина или АНФ — удобное представление булевых функций. Их использование можно увидеть во многих работах. С полиномами работать проще и удобнее, чем с ДНФ или КНФ.
Можно сказать, что это одно из базовых понятий в дискретной математике. Например, понятие линейных функций (см. замкнутые классы, теорема о полноте) вводится с их использованием.
Еще одной особенностью является отсутствие фиктивных переменных в представлнии функции через АНФ.
В вопросах схемотехники я, конечно, профан. Буду рад если меня поправят. Элементы типа и-не и или-не эффективно реализуются при помощи транзисторов. Более того, других вариантов нет, и ничего не остается, кроме как реализовать все остальные функции (или, и, не, xor) через и-не или или-не, чтобы использовать изученный математический аппарат.
Понятие «поля» предпологает наличие двух операций сложения и умножения над элементами. «xor» и «и» вводятся над множеством {0,1}, а не над действительными числами. Может быть я неверно понимаю ваш вопрос?
Да, не удачно выразился. Не о велосипеде речь. Хотел сказать, что-то типа «найти подходящий генератор (проверенный, с нужными свойствами), отличный от стандартного, и реализовать его в своей программе», а получилось, как всегда.
Я не хотел совсем касаться темы конкретных генераторов ПСЧ, хотелось только обратить внимание на важность их выбора.
Что касается конкретного генератора.
Тут выбор богатый, и PCG32 — это всего лишь один из многих. Если бы в решении этой задачи (генерации ПСЧ) все было бы так просто, то было бы ровно одно решение.
Каждый выбирает, то что ему подходит лучше для решения конкретной задачи. Это мое мнение, возможно оно ошибочно, но пока такая концепция меня не подводила.
Vegas — алгоритм или лучше сказать, конкретное решение, приближающее распределение используемой случайной величины к |g(x)| / I. Иными словами выбирает плотность распределения пропорционально |g(x)| на сколько это возможно. О необходимости этого я говорил.
MISER — алгоритм, разбивает область интегрирования на две части рекурсивно до некоторой глубины. К каждой полученной области, применяется метод Монте-Карло. А количество итераций алгоритма в каждой области выбирается так, чтобы суммарная дисперсия получаемой оценки была минимальной.
Но, возможно, ссылка на библиотеку кому-то пригодится.
Добавлю, что вариаций на тему генераторов случайных чисел очень много. Например, я часто использую для таких целей хорошо изученные криптографические алгоритмы (например, наши ГОСТы).