Отправлено SM 24 июля 2004 г. 11:02 В ответ на: Может кто-нибудь подсказать, есть ли быстрые алгоритмы вычисления АКФ (автокорреляционной функции)? отправлено Бяка 24 июля 2004 г. 00:16

• Насколько я понимаю (N*logN)*(N*logN) да плюс еще ^2 и abs - это немного больше N^2, которое если влоб делать. Или я ошибаюсь? — Бяка   (24.07.2004 14:42, пустое)
  • Вы обсчитались там 2*N*logN + N умножений и модулей, что при определенном N ,будет всяко выгоднее чем деланье N^2 в лоб. — andy_P   (24.07.2004 17:46, пустое)
    • А зачем N умножений, если не секрет? — SM   (24.07.2004 20:00, пустое)
      • Правильно, N умножений мало, надо 2N. Плюс N сложений. Итого 2N умложений. — -=ВН=-   (26.07.2004 15:13, пустое)
      • На сколько я понимаю умножения это то что у Вас ^2.+ — andy_P   (26.07.2004 14:46, 191 байт)
        • нет. Модуль это sqrt(im^2+re^2). Если это возвести в квадрат - то пропадет корень, и более ничего. — SM   (26.07.2004 15:01, пустое)
          • Сдаюсь :-) Вы правы и ВН тоже прав.+ — andy_P   (26.07.2004 15:40, 190 байт)
  • ^2 это как раз то, что не надо делать, просто не считать корень для модуля. — SM   (24.07.2004 15:46, пустое)
  • Иногда N^2 бывает гораздо быстрее N*log(N). Например тупая корреляция на 55xx - MAC::MAC - два умножения и сложения за такт. а FFT комплексное однако, и алгоритм сложнее, и памяти больше жрет, и TwiddleTable надо в памяти хранить да и битреверс делать. — AntZ   (24.07.2004 15:45, пустое)
    • Битреверс можно не делать в данном случае (+) — SM   (24.07.2004 16:12, 217 байт)
      • Тогда надо будет писать разные процедуры FFT и iFFT — AntZ   (26.07.2004 08:16, пустое)
        • ну да — SM   (26.07.2004 15:02, пустое)
  • Прошу прощения, действительно ошибаюсь. Спасибо. — Бяка   (24.07.2004 14:45, пустое)