2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Сортировка в БПФ
Сообщение12.01.2006, 15:04 


07/01/06
9
Лет 20 назад мною был получен один маленький результат, который мне до сих пор нравится. Речь идет об алгоритме Быстрого Преобразования Фурье, обрабатывающим массив данных из $2^n$ элементов и состоящим из двух частей: сортировки массива и экономных (быстрых) вычислений. Результат относится к сортировке. Меня заинтересовало, как минуя алгоритм сортировки узнать номер какого-либо элемента массива после сортировки, зная его номер до сортировки.
Решение оказалось простым. Надо записать номер элемента исходного массива в двоичном коде, прочитав это число в обратном направлении (справа налево) получаем номер того же элемента после сортировки.
Каждый номер состоит из n двоичных цифр, а элементы исходного массива пронумерованы от 0 до $2^n - 1$.
Пример: пусть массив имеет 128 элементов, т.е. n = 7, тогда например, четвертый элемент массива имеет номер 3=0000011, а после сортировки его номер 1100000=96 и он становится девяносто седьмым.
Результат не нашел практического применения. Мне кажется, что было бы неплохо иметь команду чтения двоичного числа справа налево. Это упростило бы сортировку в БПФ. Возможно также, что этот результат известен или очевиден специалистам.
Хочется узнать мнения уважаемых участников форума об этом результате и возможности его использования.

 Профиль  
                  
 
 
Сообщение12.01.2006, 15:07 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
:) Да, известен... Но уж насколько очевиден - это вопрос субъективный.... :) То, что очевидно для одного, совершенно непонятно для другого... Я вот до сих пор не понимаю, как этот алгоритм (алгоритм БПФ) работает.. :oops:

Указанный Вами результат использовался во всех встречавшихся мне (в интернете) реализациях алгоритма БПФ. Команды такой, увы, нет, но биты переставить можно (чем и занимаются)

 Профиль  
                  
 
 
Сообщение12.01.2006, 18:14 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
В некоторых специализированных процессорах подобные команды есть. Пример других экзотических команд - найти первый ненулевой бит и погасить его, записав номер бита в регистр. Погасить в две-три команды просто (x & (x-1)) а вот найти...

 Профиль  
                  
 
 
Сообщение12.01.2006, 18:27 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
Я имел в виду х86, конечно... :) В некоторых контроллерах каких только команд нет... Боюсь соврать, но у какого-то контроллера я видел даже команду транспонирования матрицы бит! :)

 Профиль  
                  
 
 
Сообщение13.01.2006, 04:30 


07/01/06
9
Большое спасибо за информацию! Как полезно иметь такой варинт общения, как форум.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group