Привет
Народ подскажите пожалуйста, существуют ли другие алгоритмы для нахождения числа 1/X , если Х- любое целое число, кроме естественно деления столбиком, если есть возможность применения умножения, сложения и вычитания. При этом решающим фактором является время выполнения деления.

Найдите книгу Генри Уоррен "Алгоритмические трюки для программистов". Вот тут AVR пытался объяснить некоторые принципы быстрого деления при помощи "магических чисел".

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

Другие алгоритмы существуют. И их не мало. Естественно, все зависит от реализации. Можно например применить итерационный алгоритм Ньютона нахождения x=1/a :

Xk+1= Xk*(2 - a*Xk).

В качестве начального значения можно брать любое число от 0 до 2/a. Например 2^(-m), где m это номер самой старшей значащей единицы в a.

Можно также воспользоваться полиномиальной аппроксимацией (ряды Тейлор, полиномы Чебышева, Лежандра и т.д.), таблично-интерполяционное приближение, специальные алгоритмы типа "цифра за цифрой" (он же CORDIC) и т.д. .

А еще можно поискать ответ на этот вопрос как в этой конфе так и на Телесистемах

и всёже самый лучший алгоритм деления на 1/X - это избегать деления =)
иногда стоит всёже еще раз пересмотреть весь реализуемый алгоритм -
часто деление не проходит по быстродействию/точности/занимаемым_ресурсам

могли бы немного более подробно о применении деления?

А вот за этот совет спасибо! А то я уже книжку хотел покупать.
Дело в том что я работаю с FPGA и библиотеку CORDIC-функций юзаю давно, но только для тригонометрических функций типа sin, tg, длины вектора и т.д., но я не знал, что с помощью этого можно и делить.
Но, после этого совета я снова порылся в библиотеке и обнаружил этот самый CORDIC divider. Так что спасибо еще раз.

Про скорость деления я немного загнул, скорей всего простота реализации важнее.

Дело в том что мне нужно посчитать отношение U/Udc, где Udc - относительно медленно изменяющееся напряжение и измеряемое намного реже U, но имеющее достаточно большой предел изменения, чтобы отказаться от таблиц. А напряжение U - очень быстрое, и результат деления нужно получить максимум за 1-2 такта. Так как в моей FPGA есть аппаратные умножители, которые работают за 1 такт, то я подумал, что наиболее оптимальным будет получать 1/Udc, а затем в каждом такте умножать это на U, чтобы было быстро.

Сообщение отредактировал syoma - Jul 31 2007, 07:30

Фигней оказался этот Cordic - так как результат 1/U - очень маленькое число - пришлось увеличить разрядность после точки - у меня все данные только с фиксированной точкой. В итоге сгенерился настолько большой VHDL код, что компилятор сказал, что это в FPGA не поместится.
В итоге я плюнул на все это и запрограммировал предложеный Самураем алгоритм Ньютона .
Так как диапазон результатов - от 1/4000 до 1/500, то проблем с выбором первого числа не было - взял наименьшее, что может получиться. В итоге получилась компактная и красивая реализация для FPGA с 2мя умножителями. При точности 1/2^21 результат 1/500 получился за 10 итераций. 1/3000 - за 4. У Cordica задержки получались от 30 циклов при меньшей точности.

Сообщение отредактировал syoma - Aug 5 2007, 08:43