Forth
http://fforum.winglion.ru/

Быстрое деление MSP430 ???
http://fforum.winglion.ru/viewtopic.php?f=39&t=2603
Страница 1 из 2

Автор:  _Harry [ Чт май 20, 2010 10:02 ]
Заголовок сообщения:  Быстрое деление MSP430 ???

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

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

Автор:  Hishnik [ Чт май 20, 2010 10:36 ]
Заголовок сообщения:  Re: Бастрое деление MSP430 ???

В простейшем случае можно просто сдвигом делить на степени двойки, игнорируя тот факт, что делитель может быть и не строго равен степени двойки. Но чем так плох столбик? Он будет достаточно быстр, с учетом того, что приближенное деление будет ну очень уж приближенным для переменного делителя.

Автор:  WingLion [ Чт май 20, 2010 10:43 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

Если делителей не сильно много, можно держать их обратные величины в табличке и вытаскивать по необходимости.

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

Автор:  _Harry [ Чт май 20, 2010 11:33 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

Хищник писал(а):
чем так плох столбик?
Только скоростью
И еще хотелось бы как то умножитель задействовать для ускорения.

Автор:  Hishnik [ Чт май 20, 2010 14:02 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

_Harry писал(а):
И еще хотелось бы как то умножитель задействовать для ускорения.

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

Автор:  WingLion [ Чт май 20, 2010 14:20 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

И развернуть деление в линейный код, чтобы на организацию цикла время не тратить.

Автор:  вопрос [ Чт май 20, 2010 17:59 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

WingLion писал(а):
И развернуть деление в линейный код, чтобы на организацию цикла время не тратить.

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

Автор:  Hishnik [ Чт май 20, 2010 19:08 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

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

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

Автор:  dynamic-wind [ Чт май 20, 2010 19:47 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

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


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

Автор:  вопрос [ Чт май 20, 2010 20:19 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

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

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


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

Автор:  dynamic-wind [ Чт май 20, 2010 20:24 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

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

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

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

Автор:  _Harry [ Пт май 21, 2010 01:01 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

Хищник писал(а):
Ставим единичку в старшем разряде и умножаем ее на делитель.
Очень интересно и получаем переполнение делитель ведь больше единицы может быть.

Автор:  Hishnik [ Пт май 21, 2010 08:57 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

_Harry писал(а):
Очень интересно и получаем переполнение делитель ведь больше единицы может быть.

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

Автор:  _Harry [ Пт май 21, 2010 09:42 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

Хищник писал(а):
Существуют различные подходы к делению

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

Автор:  Hishnik [ Пт май 21, 2010 10:48 ]
Заголовок сообщения:  Re: Быстрое деление MSP430 ???

Как вариант - рядом маленькую CPLD, и реализовать в ней деление аппаратно :) Будет один разряд каждым тактом, при частоте за сотню МГц.

Страница 1 из 2 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/