Целочисленное преобразование Фурье большого порядка

[postal]

Есть задача на процессорах ARM вычислять БПФ больших порядков (до 2^20). Работа с double медленна, потому хочется в целых числах. Я написал реализацию, которая работает нормально примерно до порядка 12. Потом (на порядках выше) все тонет в шумах. На просторах интернета тоже видел целочисленные реализации, но они тоже касаются маленьких порядков типа 2^8 или 2^10.

[Бахурин Сергей]

Можно узнать для чего потребовалось FFT такого размера?
Что значит тонет в шумах? Переполнение разрядности нигде не происходит?

[postal]

Да, тонуло не в шумах, а тонуло в переполнениях. Подчистил код, стало работать. Причем порядок можно ставить и больше 20.
Но вот незадача: я делал это все для скорости выполнения, а скорости так и не достиг. 64-разрядный int работает примерно в полтора раза медленнее, чем float, а 32-битный примерно так же, как и float, но его разрядности для порядка 20 не хватает.

[Бахурин Сергей]

Делайте промежуточные округления и не будет пепеполняться int32. Масштаб можно учесть по выходу

[IgorV]

Да, тонуло не в шумах, а тонуло в переполнениях. Подчистил код, стало работать. Причем порядок можно ставить и больше 20.
Но вот незадача: я делал это все для скорости выполнения, а скорости так и не достиг. 64-разрядный int работает примерно в полтора раза медленнее, чем float, а 32-битный примерно так же, как и float, но его разрядности для порядка 20 не хватает.

Можно еще больше удивиться если сравнить скорость выполнения например atan2 и сложения дублей. Они почти одинаковые плюс-минус, А это выворачивает как строить эффективные алгоритмы наизнанку.

[postal]

Делайте промежуточные округления и не будет пепеполняться int32. Масштаб можно учесть по выходу

Да, верно, разобрался. В принципе, и на int16 можно делать преобразование Фурье больших порядков. Проблема только в скорости выполнения: она почти не отличается от float. Я получил, что int16 от float на задаче расчета БПФ отличается примерно на 10%. Это не то, что я ожидал. На задаче расчета свертки я получил, что int16 от float отличается в ~8 раз в пользу int. Это на том же процессоре и с теми же ключами компиляции. Подозреваю, что источник такой радости - промахи кэша: при вычислении свертки их почти нет, а в БПФ есть.

[postal]

Можно еще больше удивиться если сравнить скорость выполнения например atan2 и сложения дублей. Они почти одинаковые плюс-минус, А это выворачивает как строить эффективные алгоритмы наизнанку.

Поясните, пожалуйста, подробнее. Это как-то касается БПФ?

[Бахурин Сергей]

Это касается в том смысле что на скорость влияет много неочевидных на первый взгляд факторов. Например расчёт и хранение поворотных множителей, или как осуществляется перенос данных из оперативной памяти в ядро. По хорошему надо смотреть что делает ядро? Молотит ли оно вычисления каждый такт, или занимается тем, что бегает в память, за каждым новым отсчетом и ждёт, когда данные подвезут.

[IgorV]

Можно еще больше удивиться если сравнить скорость выполнения например atan2 и сложения дублей. Они почти одинаковые плюс-минус, А это выворачивает как строить эффективные алгоритмы наизнанку.

Поясните, пожалуйста, подробнее. Это как-то касается БПФ?

Бахурин Сергей ответил.
Чаще всего БПФ - это не самоцель. Вокруг БПФ что-то еще вычисляться должно, я просто уже столкнулся с "не очевидными" сюрпризами по скорости вычисления. И что float и double - без разницы в ПК, но разница в МК. Тоже самое если сравнивать работу в интах и флоатах для ПК может быть быстрее в плавающей, но онднозначно инты рулят для средненьких МК.