Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 13:00

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Быстрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 10:02 
Не в сети
Аватара пользователя

Зарегистрирован: Пт дек 26, 2008 21:16
Сообщения: 412
Откуда: Великий Новгород
Благодарил (а): 9 раз.
Поблагодарили: 4 раз.
Знатоки целочисленных алгоритмов вопрос к вам!
На контроллере MSP430 имеется аппаратный умножитель,
деление аппаратно не поддерживается. В случае если делитель
зараннее определенная константа все понятно заменяем деление
на умножение, на обратное число точнее :
Код:
a / b=((a+1) * (0x10000/b)) / 0x10000
где /0x10000 это 16 RSHIFT, (0x10000/b) вычисляется при компиляции.

Вот хотелось бы быстрых алгоритмов в случае если оба числа a/b переменные.
Деление в столбик не предлагать. :?:


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Бастрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 10:36 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
В простейшем случае можно просто сдвигом делить на степени двойки, игнорируя тот факт, что делитель может быть и не строго равен степени двойки. Но чем так плох столбик? Он будет достаточно быстр, с учетом того, что приближенное деление будет ну очень уж приближенным для переменного делителя.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 10:43 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Если делителей не сильно много, можно держать их обратные величины в табличке и вытаскивать по необходимости.

п.с. Исправил опечатку в топике.

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 11:33 
Не в сети
Аватара пользователя

Зарегистрирован: Пт дек 26, 2008 21:16
Сообщения: 412
Откуда: Великий Новгород
Благодарил (а): 9 раз.
Поблагодарили: 4 раз.
Хищник писал(а):
чем так плох столбик?
Только скоростью
И еще хотелось бы как то умножитель задействовать для ускорения.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 14:02 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
_Harry писал(а):
И еще хотелось бы как то умножитель задействовать для ускорения.

Ставим единичку в старшем разряде и умножаем ее на делитель. Если больше делимого, то сбрасываем разряд, если нет - оставляем. И так по всем разрядам частного. В принципе, это и есть "деление в столбик", но время работы пропорционально разрядности частного, и умножитель тут задействован.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 14:20 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
И развернуть деление в линейный код, чтобы на организацию цикла время не тратить.

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 17:59 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
WingLion писал(а):
И развернуть деление в линейный код, чтобы на организацию цикла время не тратить.

ДУмаю, что внутреннее устройство аппаратных умножителей реализует может чуть лучше те же алгоритмы (?)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 19:08 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
вопрос писал(а):
ДУмаю, что внутреннее устройство аппаратных умножителей реализует может чуть лучше те же алгоритмы (?)

В аппаратных умножителях нет алгоритмов как таковых.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 19:47 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июн 25, 2009 11:12
Сообщения: 412
Благодарил (а): 41 раз.
Поблагодарили: 8 раз.
_Harry писал(а):
Вот хотелось бы быстрых алгоритмов в случае если оба числа a/b переменные.
Деление в столбик не предлагать. :?:


Нуу если очень надо быстро, вот два умножения + таблица:
ftp://arith.stanford.edu/tr/asil99div.ps.gz
(Сам не пытался сделать)
:shock: :? :twisted:


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 20:19 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Хищник писал(а):
вопрос писал(а):
ДУмаю, что внутреннее устройство аппаратных умножителей реализует может чуть лучше те же алгоритмы (?)

В аппаратных умножителях нет алгоритмов как таковых.


Ну, нет, любое последовательное преобразование данных - это алгоритм, даже прееключение триггера можно считать частью алгоритма (если речь идёт о программе или микропрограмме - то да)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Чт май 20, 2010 20:24 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июн 25, 2009 11:12
Сообщения: 412
Благодарил (а): 41 раз.
Поблагодарили: 8 раз.
Хищник писал(а):
вопрос писал(а):
ДУмаю, что внутреннее устройство аппаратных умножителей реализует может чуть лучше те же алгоритмы (?)

В аппаратных умножителях нет алгоритмов как таковых.

http://en.wikipedia.org/wiki/Booth_encoding


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Пт май 21, 2010 01:01 
Не в сети
Аватара пользователя

Зарегистрирован: Пт дек 26, 2008 21:16
Сообщения: 412
Откуда: Великий Новгород
Благодарил (а): 9 раз.
Поблагодарили: 4 раз.
Хищник писал(а):
Ставим единичку в старшем разряде и умножаем ее на делитель.
Очень интересно и получаем переполнение делитель ведь больше единицы может быть.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Пт май 21, 2010 08:57 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
_Harry писал(а):
Очень интересно и получаем переполнение делитель ведь больше единицы может быть.

"В старшем" = "в самом старшем разряде частного, которое мы предполагаем". Существуют различные подходы к делению, наиболее распространены вида 32:16=16 (или 16:8=8), но тут ведь тоже есть та опасность, что делитель может быть небольшой, и в 16/8 разрядов результат не поместится. А переполнение не является катастрофой, поскольку означает лишь то, что в этот разряд единицу ставить не надо.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Пт май 21, 2010 09:42 
Не в сети
Аватара пользователя

Зарегистрирован: Пт дек 26, 2008 21:16
Сообщения: 412
Откуда: Великий Новгород
Благодарил (а): 9 раз.
Поблагодарили: 4 раз.
Хищник писал(а):
Существуют различные подходы к делению

Да и алгоритмы то же. Вобщем в столбик как делить мне понятно только это очень медленно
если учесть все аспекты. Кстати и умножитель здесь мало поможет потому что быстрее сдвигом получится.
Есть более "быстрые" способы. Хотя насколько они удобны на практике тоже вопрос.
Таблицы в качестве общего метода мне не пойдут хотя это наверно самый быстрый способ. Памяти тока он скушает больше чем все примитивы вместе взятые а контроллер не резиновый.
Пока в поиске :roll: Кто еще что предложит :?:


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстрое деление MSP430 ???
СообщениеДобавлено: Пт май 21, 2010 10:48 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Как вариант - рядом маленькую CPLD, и реализовать в ней деление аппаратно :) Будет один разряд каждым тактом, при частоте за сотню МГц.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

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


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

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB