Войти
ФлеймФорумПрограммирование

[Design by Committee] Fast Fourier transform (4 стр)

Страницы: 1 2 3 4 5 6 7 Следующая »
#45
10:42, 4 янв 2022

FordPerfect

> Т. е. натурально
Ну да.

> но вдруг найдутся герои, которым надо посчитать FFT от 10^10 элементов
Если у тебя конкретный тип поля за собственным тайпдефом, то пофигу на ptrdiff_t.

> пользовательскому коду её обернуть как себе удобнее - дело пары строчек.
Так нужно навязывать пользователю правильные решения, dbc же. Те, кому не нужен stride сами догадаются враппер написать, а все остальные будут запятые считать.

По поводу нейминга - в fftw, например, принято interleaved/split.

#46
11:03, 4 янв 2022

Suslik
> но я не придумал, как внятно поддерживать случай с только действительными данными. потом что трансформ-то действительных данных всё равно будет комплексным, хотя входные и выходные данные во многих случаях — действительные.
RDFT существует. Насколько оно нравится...

#47
11:25, 4 янв 2022

FordPerfect

Кстати, true dsp версии fft, вроде имеющихся в adsp и c6x/c5x, ещё берут на вход заранее посчитанные твидлы.

#48
18:38, 4 янв 2022

> В моей реализации dbc_fft_fc() примерно вдвое быстрее dbc_fft_fi().
Точнее вот так (из check_github_linux):

+ Показать

Возможно, провал при N>=1024 и поборю.

#49
20:17, 4 янв 2022

FordPerfect

Everfall актуален на данный момент?

ЗЫ. Хотя, блин, глупый вопрос. Хотя бы на момент комплексных умножений?

#50
20:42, 4 янв 2022

Как лучше: отдельные FFT/IFFT функции, или передавать forward/inverse параметром?

Ghost2
Вот α.3 на www.everfall.com:
http://www.everfall.com/paste/id.php?yrokqap6hlr4

#51
20:47, 4 янв 2022

Ghost2
> Ну да.
Т. е. всё ещё все параметры в одну структуру?
Делать структурку с {size/stride/real/imag} как Suslik предлагает - тоже неплохо выглядит.

#52
21:06, 4 янв 2022

FordPerfect

Да можно две, три, ну четыре. Я лично против 10+ параметров, как в blas.

#53
23:26, 4 янв 2022

Suslik
> и обязывать пользователя что-то туда вставлять — вообще не очевидно, входит ли в этот множитель сам 1/N или нет. я вот думал, что входит уже.
Гм. Т. е. так тоже неочевидно.
Всякие https://numpy.org/doc/stable/reference/routines.fft.html и им подобные принимают параметр, определяющий конвенцию (по сути enum). Мне казалось, что передавать float вместо дискретного селектора - естественное обобщение, но может оно и чревато.
По умолчанию - вроде 1 для FFT и 1/N для IFFT примерно везде, где я смотрел. Кто-то видел контрпримеры?
Т. е. для такой конвенции (это определение из Википедии) - есть шанс что кто-то споткнётся? Наверно есть...
https://www.mathworks.com/help/matlab/ref/fft.html - вообще похоже только такое, без выбора. Там хоть определение явно выписано, хотя и внизу страницы.
И вроде же там не
> а функция fft матлаба (которой многие пользуются) — [-N/2..N/2).

#54
23:30, 4 янв 2022

Ghost2
> Кстати, true dsp версии fft, вроде имеющихся в adsp и c6x/c5x, ещё берут на вход заранее посчитанные твидлы.
Я хочу минимум телодвижений пользователю (хотя бы в базовом использовании).
У меня даже инициализации как в KissFFT нету. Вот есть данные - можно сразу звать над ними FFT.
Дать такое опционально - может и осмысленно.

> По поводу нейминга - в fftw, например, принято interleaved/split.
Мне separate кажется более понятным, чем split. Мысли?

Кстати, кому как больше нравится?

dbc_fft_fc(...); // separate
dbc_fft_fi(...); // interleaved
dbc_fft_fs(...); // strided

или

dbc_fft_float_separate(...);
dbc_fft_float_interleaved(...);
dbc_fft_float_strided(...);

Представьте, что:
1. Вам такое читать.
2. Вам такое писать.

#55
2:24, 5 янв 2022

Если есть желающие сравнить по скорости (и точности) с KissFFT и FFTW (опционально, другими с https://github.com/project-gemmi/benchmarking-fft ) - приветствуется.

#56
3:07, 5 янв 2022

Ghost2
> Если у тебя конкретный тип поля за собственным тайпдефом, то пофигу на ptrdiff_t.
У меня тип называется dbcf_index, и можно сказать

#define dbcf_index int
#define DBC_FFT_IMPLEMENTATION
#include "dbc_fft.h"

и будет int. Только т. к. это часть API - говорить придётся при кажом включении dbc_fft.h, а не только для implementation.

#57
3:08, 5 янв 2022

Попробовал замерить.
Вроде на моей машине получается KissFFT в 5 раз медленнее моей.
Но я мог очень тупо накосячить.
Так что хотелось бы, чтобы кто независимо проверил.

#58
5:35, 5 янв 2022

FordPerfect
> Как лучше: отдельные FFT/IFFT функции, или передавать forward/inverse
> параметром?
как по мне, всё равно

> принимают параметр, определяющий конвенцию (по сути enum)
по-моему, указывая в явном виде конвенцию, пользователю гораздо проще получить хоть какой-то вариант (точнее, вариант, удовлетворяющей хоть какой-то конвенции). я за этот вариант. хотя в plain C нет строго типизированных enum'ов, так что всё равно боль.

> По умолчанию - вроде 1 для FFT и 1/N для IFFT примерно везде, где я смотрел.
> Кто-то видел контрпримеры?
есть вариант использовать 1/sqrt(N), чтобы множитель был одинаковый. я не знаю, где это применяется, но не думаю, что кто-то будет горевать, если ты на этот вариант забьёшь. 1 и 1/N — нормальный вариант.

> https://www.mathworks.com/help/matlab/ref/fft.html - вообще похоже только такое, без выбора. Там хоть определение явно выписано, хотя и внизу страницы.
я не помню, чем именно пользовались ребята, которые обсуждали решение уравнения пуассона (очевидно, не матлаб), но в их пакете было по умолчанию именно [-N/2, N/2) и для них это было настолько очевидно, что они даже не заморачивались это упоминать. например, вот здесь: https://cseweb.ucsd.edu/~alchern/projects/SchrodingersSmoke/Schro… gersSmoke.pdf в аппендиксе E приводятся формулы для собственных векторов операторов лапласа в конвенции [-N/2, N/2), опять же, нигде это не упоминается

FordPerfect
> dbc_fft_fc(...); // separate
> dbc_fft_fi(...); // interleaved
> dbc_fft_fs(...); // strided
> или
> dbc_fft_float_separate(...);
> dbc_fft_float_interleaved(...);
> dbc_fft_float_strided(...);
> Представьте, что:
> 1. Вам такое читать.
> 2. Вам такое писать.
я бы без вариантов второе выбрал хоть для чтения, хоть для написания. особенно если либу (или код с использованием либы) впервые вижу. ещё если интерфейс планируется типа-мультиязыковой, то можно подумать по поводу использования в именовании f32 вместо float и f64 вместо double — это писать короче и неоднозначностей меньше.

#59
6:53, 5 янв 2022

Suslik
> [-N/2, N/2)
Кстати, а в общем случае это [ceil(-N/2);ceil(+N/2))?

> подумать по поводу использования в именовании f32 вместо float и f64 вместо double — это писать короче и неоднозначностей меньше.
Спасибо. Как раз думал, что

dbc_fft_long_double_interleaved

таки стрёмненько. С другой стороны, long double не везде float80.

Страницы: 1 2 3 4 5 6 7 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.