Комментарии 76
Было бы очень ценно показать «на пальцах».
Взять маленькую игровую матрицу (4x4 достаточно), показать её ПФ, показать результат умножения и результат обратного преобразования.
Каждый бы смог повторить в матлабе.
Взять маленькую игровую матрицу (4x4 достаточно), показать её ПФ, показать результат умножения и результат обратного преобразования.
Каждый бы смог повторить в матлабе.
Хорошая идея, матрицы сейчас сделаю. Вот только скрипты для матлаба предлагаю написать специалистам по матлабу.
Я же из C++ получу промежуточные изображения.
Я же из C++ получу промежуточные изображения.
Матлаб фтопку, даёшь православный сионизмъ!
(кроме шуток, примеры на матлабе уже задрали)
(кроме шуток, примеры на матлабе уже задрали)
Скрипт не важен. Нужны тестовые данные. Чтобы человек, далёкий от c++, хотящий повторить это в своём любимом maple/python/подставить-нужное, мог на каждом шаге видеть, правильно он двигается или сделал ошибку.
Скрипт на матлабе не содержал бы ничего, кроме идеи. Вам, видимо, нравится продираться сквозь malloc'и и макросы
Промежуточные изображения добавил в пост.
Спасибо.
У меня было предположение, что можно двигать эволюцию простым умножением без обратного преобразования на каждом шаге, и только после N шагов снять результат.
С примером я понял, что после каждого шага нужно применять пороговые фильтры, которые обнулят клетки с большими суммами и с маленькими, что невозможно сделать, оставаясь в спектральном представлении.
У меня было предположение, что можно двигать эволюцию простым умножением без обратного преобразования на каждом шаге, и только после N шагов снять результат.
С примером я понял, что после каждого шага нужно применять пороговые фильтры, которые обнулят клетки с большими суммами и с маленькими, что невозможно сделать, оставаясь в спектральном представлении.
powdertoy.co.uk/ — в этой «игре» симуляция «жизни» аналогичным образом сделана.
Насколько я знаю, в The Powder Toy используется обычный подсчёт соседей. Может быть Golly использует БПФ как один из вариантов, хотя там вроде Hashlife главный алгоритм.
все и так знают.
В этом месте по-подробнее. Все это кто? Все 292 тыс. пользователей хабра? :-)
Те, кто хорошо учился в университете на мат./физ. факультете — да, крайне вероятно знают.
Я например не знал, пока не разобрался с этим алгоритмом.
У вас логическая ошибка 
Те кто не прогуливал && вообще имел в расписании курс математического анализа.
Те кто не прогуливал && вообще имел в расписании курс математического анализа.
Не вполне согласен. Если «почувствовать» как работает БПФ, его можно применять, не вникая до самого дна внутренностей.
В этом и состоит разница между программированием как ремеслом, и программированием как искусством :-D
Зачастую нужно именно ремесло.
В этом и состоит разница между программированием как ремеслом, и программированием как искусством :-D
Зачастую нужно именно ремесло.
Поддерживаю вашего оппонента — после прочтения вашей заметки стало таки интересно, но вовсе не стало понятно. Надо ширше наверное. Спасибо
Что такое «полный смысл»? ДПФ двухточечной последовательности состоит из суммы и разности ее элементов (с точностью до нормирующего множителя); ДПФ одноточечной последовательности совпадает с ней самой. Никто смысла не теряет.
Вы знаете, терминологию не просто так люди придумали, а чтобы было более-менее понятно то, что говорят другие. Я вот этой фигней занимаюсь, сколько себя помню, но, уж извините, у Вас не понял ни одного слова. Что такое «спектральное поле»? Что такое «0 точка»? Дальше тоже непонятно. Не бывает никакой действующей частоты. Бывает действующее значение.
По существу: при любом количестве точек, начиная с одной, ДПФ сохраняет свой смысл, включая физическую интерпретацию амплитудного и фазового спектров.
По существу: при любом количестве точек, начиная с одной, ДПФ сохраняет свой смысл, включая физическую интерпретацию амплитудного и фазового спектров.
Мне кажется, что физикам и электронщикам как раз легче понимать смысл спектральных методов, чем математикам и программистам. Это же просто набор полосовых фильтров, не более того. Правда фильтры так хитро подобраны, что их частотные характеристики в сумме дают тождественную единицу, поэтому по их откликам можно восстановить исходный сигнал.
А понимать отдельно смысл ДПФ/БПФ по-моему и не нужно, потому что это просто схемы вычисления настоящего (интегрального) спектра. Причем БПФ вообще является на самом деле очень хитрой эксплуатацией идеи факторизации матрицы, реализующей ДПФ.
Про всю эту Фурьевскую магию написано очень много и есть книжки, где все очень хорошо разжевано (та же книжка Сато). Мне кажется, что вряд ли стоит все это повторно разжевывать на Хабре. А вот про приложения я собираюсь пару статей написать — про тот же Шазам и про передискретизацию картинок. А томография — очень специфичная тема и там само БПФ не так уж и важно на самом деле, ведь первые томографы вообще не обрабатывали получаемые картинки, а использовали аппаратно реализованное т.н. обратное проецирование и спектральные методы просто позволили улучшить качество картинки.
А понимать отдельно смысл ДПФ/БПФ по-моему и не нужно, потому что это просто схемы вычисления настоящего (интегрального) спектра. Причем БПФ вообще является на самом деле очень хитрой эксплуатацией идеи факторизации матрицы, реализующей ДПФ.
Про всю эту Фурьевскую магию написано очень много и есть книжки, где все очень хорошо разжевано (та же книжка Сато). Мне кажется, что вряд ли стоит все это повторно разжевывать на Хабре. А вот про приложения я собираюсь пару статей написать — про тот же Шазам и про передискретизацию картинок. А томография — очень специфичная тема и там само БПФ не так уж и важно на самом деле, ведь первые томографы вообще не обрабатывали получаемые картинки, а использовали аппаратно реализованное т.н. обратное проецирование и спектральные методы просто позволили улучшить качество картинки.
Это совсем не первый курс математического анализа.
Первый курс — это пределы и производные.
Преобразование Фурье — в лучшем случае четвёртый семестр.
Первый курс — это пределы и производные.
Преобразование Фурье — в лучшем случае четвёртый семестр.
может давать хорошую скорость для плотно заполненных полей, и быстро уходит в отрыв с ростом сложности правил и площади/объема суммирования
Но для классических правил оно все же будет заметно медленнее работать, чем прямое вычисление. В основном за счет большой константы перед N2 log N и за счет худшей локальности при обращении к памяти.
В среднем да, если конечно не брать в расчет варианты вроде «код на Python использует библиотеку на GPU/многопроцессорной системе».
Вот тут я понимаю Жизнь, даже музыка соответствующая www.youtube.com/watch?feature=player_detailpage&v=C2vgICfQawE
Хотелось бы ещё сравнения скорости с наивным алгоритмом, хотя бы простейшего — чтобы вообще представлять насколько это реально быстрее/медленнее на разных количествах суммируемых элементов. А вообще, конечно, БПФ отличная вещь, столько применений что многие даже в голову не приходят, как например этот, или там поиск подстрок какой-нибудь.
Да, думаю было бы полезно, вечером проведу замеры.
Это всё конечно хорошо, только речь о другом. В статье сравнивается на словах алгоритм с БПФ и наивный алгоритм для игры «Жизнь», без ДПФ. Вот о их скорости и вопрос.
Кстати, вы как-то странно противопоставляете ДПФ и БПФ, хотя БПФ — один из алгоритмов для вычисления ДПФ.
Кстати, вы как-то странно противопоставляете ДПФ и БПФ, хотя БПФ — один из алгоритмов для вычисления ДПФ.
У БПФ в данном случае асимптотика O(N^2 log N), а у наивного алгоритма — O(N^2), поэтому асимптотически соотношение как раз не в пользу первого, но тут N не такие большие и было бы интересно сравнить реальное время. Вы, видимо, не совсем поняли что с чем сравнивается. Кстати, основание логарифма тут вообще не важно, ни в статье ни в комментариях здесь мы всё равно мультипликативные константы не пишем (а логарифмы по разным основаниям как раз на такие константы отличаются).
«здесь мы всё равно мультипликативные константы не пишем (а логарифмы по разным основаниям как раз на такие константы отличаются»
— вот тут я не понял…
Мультипликативная константа — такая, на которую умножается (ну или делится :) ) Так как loga n = log2n / log2a, то в асимптотиках и не пишут обычно основание логарифма, также как и константы (я имею в виду, что не пишут например что количество операций в алгоритме равно 7*n, а пишут что O(n)).
«поэтому асимптотически соотношение как раз не в пользу первого, но тут N не такие большие и было бы интересно сравнить реальное время. Вы, видимо, не совсем поняли что с чем сравнивается.»
вы хотели что сравнить?
1.однобитный целочисленный алгоритм суммирования окружения клетки и БПФ на двойной точности?
2.Асимптота логарифма затормаживается, а N в квадрате — растёт как взрыв. Вы наверное перепутали. С ростом N — БПФ выигрывает всё сильнее…
Запишите асимптотики для БПФ в данном применении и для этого однобитового (хотя это не важно конечно) алгоритма, и увидите (n^2 log n против n^2).
Замеры скорости проведены, результаты в конце статьи.
А как обстоят дела с точностью БПФ и ошибками округления — не было проблем с этим?
Суммы округляются до ближайшего целого при проверках. Из-за того, что результаты БПФ напрямую в следующих итерациях не используются — ошибки не накапливаются.
Проблем не было, что не удивительно — приведенный пример вообще нагло считает все в double. Но думаю, было бы все хорошо и с single, и с фиксированной точкой.
Проблем не было, что не удивительно — приведенный пример вообще нагло считает все в double. Но думаю, было бы все хорошо и с single, и с фиксированной точкой.
Единственный минус БПФ — потребление памяти при таком подходе очень большое. Примерно в 64-128 раз больше по сравнении с битовым (или двухбитовым) представлением поля. Это может стать существенным минусом при больших размерах.
Вы что именно имеете в виду? В данном случае не столь важно, как в процессоре это считается, а сколько занимает массив из этих вещественных чисел. А он как раз занимает в 32 или 64 раза больше, чем одно- или двухбитовый.
Так сопроцессор в классическом виде — медленно но верно уходит в прошлое.
На x87 инструкциях быстрый FFT не написать.
Современный математический код использует SSEx инструкции — и разрядность вещественных чисел не больше 64.
80 бит вещественные числа — остались только для совместимости, и очень медленны по сравнению с SSEx.
На x87 инструкциях быстрый FFT не написать.
Современный математический код использует SSEx инструкции — и разрядность вещественных чисел не больше 64.
80 бит вещественные числа — остались только для совместимости, и очень медленны по сравнению с SSEx.
ИМХО, библиотека FFTW заоптимизирована вдоль и поперек — одна из лучших по производительности. Ничего существенно быстрее написать не получится
Только если заранее для всех размеров входных массивов создать и сохранить профили. Если же считать без профиля, то она почти не обгоняет стандартную реализацию FFT (которая без использования преобразования Уолша).
FFTW оптимизирует схему вычислений в алгоритме FFT с учетом конфигурации кэшей конкретного процессора. Если простыми словами, то он решает, до какого размера еще стоит разбивать последовательность на две (из четных и нечетных элементов) и потом сливать их спектры, а начиная с какого размера можно использовать прямое вычисление (на самом деле там все чуть сложнее). Эта оптимизация проводится для каждой длины исходной последовательности путем выполнения неких бенчмарков на конкретной машине и результаты сохраняются в файл профиля. Потом этот профиль можно использовать при вычислении БПФ.
Сравниваем скорость работы с «наивной» реализациейА если сравнить с HashLife?
Спасибо за статью. Как-то раньше не приходил в голову очевидный факт, что клеточные автоматы — это просто свёртка.
Это комбинация свёртки и дискретной (пороговой) функции.
Второй шаг не позволяет применить классический (непрерывный) мат. аппарат для анализа или прогнозирования.
Стивен Вольфрам доказал неприводимость клеточного автомата к более простой модели.
Второй шаг не позволяет применить классический (непрерывный) мат. аппарат для анализа или прогнозирования.
Стивен Вольфрам доказал неприводимость клеточного автомата к более простой модели.
Прошу прощения за некропост
дискретной (пороговой) функции… не позволяет применить классический (непрерывный) мат. аппарат для анализа или прогнозированияА почему нельзя применить какой-нибудь сигмоид?
Сигмоид даст лишь приближенное решение — которое обязательно разойдется с исходным через некоторое число итераций.
Кроме того, в непрерывном случае также существуют такие стабильные «решения» как поле, заполненное одинаковыми клетками со значением примерно 1/4. Ценность этих решений применительно к исходной игре «Жизнь» — сомнительна.
Кроме того, в непрерывном случае также существуют такие стабильные «решения» как поле, заполненное одинаковыми клетками со значением примерно 1/4. Ценность этих решений применительно к исходной игре «Жизнь» — сомнительна.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Игра Жизнь и преобразование Фурье