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 (Сам не пытался сделать) |
Автор: | вопрос [ Чт май 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 ??? |
Хищник писал(а): Существуют различные подходы к делению Да и алгоритмы то же. Вобщем в столбик как делить мне понятно только это очень медленно если учесть все аспекты. Кстати и умножитель здесь мало поможет потому что быстрее сдвигом получится. Есть более "быстрые" способы. Хотя насколько они удобны на практике тоже вопрос. Таблицы в качестве общего метода мне не пойдут хотя это наверно самый быстрый способ. Памяти тока он скушает больше чем все примитивы вместе взятые а контроллер не резиновый. Пока в поиске Кто еще что предложит |
Автор: | 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/ |