MOD, MUL, DIV вручную!

Привет всем!
Задача:
1. Написать процедуру знакового умножения, подобно IMUL
2. Написать процедуру беззнакового деления типа DIV
3. Написать процедуру остатка от деления

Все это на целых 32битных числах.
Вход: A, B
Выход: C

Написать эти процедуры, не используя MUL, IMUL, DIV, IDIV...

Я написал эти три задачи через SHL, ADD, SUB.
Хочу получить СУПЕР-ОПТИМАЛЬНЫЙ исходник!
Может кто-то занимался этим???
Хочу так, как это делает проц.

Могу выслать свой вариант, если это кому-то поможет упростить...
Получилось оптимально, хочу еще!!!
Но мне все же хочется увидеть СУПЕР-ОПТИМАЛЬНЫЙ вариант...

З.Ы. Бывают же ситуации, когда есть сдвиги, логика, сложение, а хочется все остальное =)

 

Если именно самый оптимальный - то он сильно зависит от того на какое число умножать/делить/брать остаток. И потом - где критерий оптимальности? По скорости, по размеру кода или данных??? Например, деление и взятие остатка иногда "табличатся", но вот размеры этих табличек могут быть большими (для больших делителей), а сам алгоритм - простой...

p.s. смахивает на курсовую или лабу...

 

Приведи его здесь, иначе действительно смахивает на попытку решить за счёт других.

 

Самые быстрые аппаратные умножители - матричные - принципиально не эмулируются программно Учите схемотехнику Аппаратура вообще плохо эмулируется, т.к. работает параллельно, а не последовательно.

Поэтому "как процессор" - не получится.

 

Меня посещала идея насчет таблиц...
Но я хочу максимально приблизиться к жизни тех, кто имеет МК, имеет ADD, SHL, SHR... А хочет иметь DIV, MUL, IMUL....

 

Интересно!
Поясни подробнее, почему нельзя достичь хорошей эмуляции?
Примеры и т.д.
Хотя бы мат.модель этого умножителя...

 

Код (Text):

1. // Умножение
2. int Mul(int A, int B)
3. {
4.     // Перевод чисел в обычную форму
5.     bool f1 = (A < 0), f2 = (B < 0);   
6.     A = f1 ? (-A) : A;
7.     B = f2 ? (-B) : B;
8.  
9.     // Ищем начало числа B
10.     int K; 
11.     for(K = 30; K >= 0; K--)  // 31 бит - знак, 30..0 биты - число
12.         if(B & (1 << K))
13.             break; 
14.  
15.     // Умножение
16.     int C = 0;
17.     while(K >= 0)
18.     {
19.         if(B & (1 << K))
20.             C += A << K;
21.         K--;
22.     }
23.    
24.     // Перевод числа C в расширенную форму
25.     C = (f1 ^ f2) ? (-C) : C;
26.     return C;
27. }

Код (Text):

1. // Деление
2. unsigned int Div(unsigned int A, unsigned int B)
3. {
4.     if(B == 0)
5.     {      
6.         throw string("\n#Error: Division by zero!\n");
7.         return 0;
8.     }
9.  
10.     // Ищем начало числа A
11.     int K; 
12.     for(K = 31; K >= 0; K--)  
13.         if(A & (1 << K))
14.             break; 
15.    
16.     // Деление
17.     unsigned int C = 0;
18.     while(A >= B)
19.     {
20.         unsigned int P = (B << K);
21.         if(P <= A)
22.         {
23.             C += 1 << K;
24.             A -= P;
25.         }
26.         K--;
27.     }
28.     return C;
29. }

Код (Text):

1. //Остаток от деления:
2. unsigned int Mod(unsigned int A, unsigned int B)
3. {
4.     if(B == 0)
5.     {      
6.         throw string("\n#Error: Division by zero!\n");
7.         return 0;
8.     }
9.    
10.     if(A < B)
11.         return A;
12.     if(A == B )
13.         return 0;
14.    
15.     // Ищем начало числа A
16.     int K; 
17.     for(K = 31; K >= 0; K--)
18.         if(A & (1 << K))
19.             break; 
20.    
21.     // Деление
22.     while(A >= B)
23.     {
24.         int P = (B << K);
25.         if(P <= A)
26.             A -= P;
27.         K--;
28.     }
29.     return A;
30. }

Хочу сделать лучше, оптимальнее!!!!!
Буду благодарен, если этот исходник будет сделан лучше...
Исходник можно АСМ, можно СИ....

Люди, которые прогают дешевые МК должны сами делать MUL, DIV....
Они делают это супер-оптимально, по вполне понятным причинам
Я не прогаю МК(это пока, на данный момент))).
Но я хочу знать, как мне сделать СУПЕР-КРУТОЕ *,/,% ручками...

 

Я же говорю - он работает параллельно, а не последовательно. Матричный умножитель - асинхроннрое устройство, он построен не на базе n-разрядного сумматора и счётчика, а из n^2 одноразрядных сумматоров, соеденённых в виде матрицы. Все n^2 сумматоров работают параллельно, скорость умножения - 2n скоростей работы одноразрядного сумматора.

Сейчас посмотрю, что в сети есть хорошего.. А если на бумаге - например книжка Угрюмов Е.П. "Цифровая схемотехника" - вроде не плохая, и умножитель там есть точно. Сам её не читал, преподаватель советовал

 

http://www.andraka.com/multipli.htm, я имел ввиду "Carry Save Array Multipliers". Объяснений там конечно нет, зато картинка есть Только насчёт самых быстрых я возможно поторопился, там ещё несколько интересных вариантов описано, сам пока не разобрался Но все такие варианты программно не реализуемы по определению.

 

sergh

Думаю, что самый быстрый умножитель - это обычный аналоговый транзистор Только данные сначала нужно через ADC пропустить, а потом обратно через DAC оцифровать.

 

Это все хорошо и интересно, но это так для общего развития!
А кто-нибудь оптимизирует мой исходник?

 

microprogs
Если хочешь приблизится к аппаратной реализации умножений/делений - пиши на verilog'е ну или хотя бы на vhdl. Там и пригодятся всякие блочно/параллельные схемы...

Как человек программировавший, наверное, десятки разных мк, могу сказать, что "супер-навороченного" там ничего нет. У каждого мк свой подход к этим процедурам, т.к. наборы команд и скорости их выполнения сильно разные (есть мк которые не умеют, например, сдвигать на произвольные значения, а есть у которых сдвиг совмещен со сложением, что удобно). Единого оптимального алгоритма НЕТ и быть и не может. А где-то можно и твой алгоритм считать достаточно оптимальным.

p.s. а вообще а чем проблема? возьми ассемблерные исходники библиотек от разных мк и посмотри как там всякое взятие остатка сделано, начни с pic16ххх, а потом глянь на adsp21xxx и попробуй после этого соорудить единый алгоритм ...

 

А почему "ну или хотя бы"? Verilog - сильно лучше? Не как наезд, а как вопрос - я только VHDL-ем более-менее владею.

 

Verilog vs. VHDL - это примерно как Turbo Pascal vs. Delphi. С одной стороны, Verilog лучше, но с другой - этот язык мёртв.

 

Ну хоть немного поподробнее проясни-то! Почему лучше, почему мёртв? Не обязательно многостраничный трактат с описанием и сравнением, я немного в теме, общих слов скорее всего хватит.
Особенно про мёртв - до сих пор такого мнения не слышал, даже среда, в которой я работал (Quartus Altera 5.0) Verilog подерживает.

 

sergh

googl: VHDL vs. Verilog

В IEEE решили, что Verilog - отстой, тормозящий развитие VLSI/ASIC, и приняли стандарт VHDL. Но почему-то 10 лет спустя разработчики продолжают пользоваться Verilog'ом. За что так не любят Verilog? - думаю, что за "низкоуровневость".

Я с этим мнением тоже не согласен, хотя использую VHDL, идя на поводу у умных дядек из IEEE.

В Альтере не дураки, чтобы прекращать поддержку довольно популярного языка. А поддержка полного стандарта VHDL (и нормальной оптимизации) им оказалась не под силу - вот и акцентируют использование Verilog'а. У Xilinx дела обстоят немного лучше.

 

2microprogs
Это в бау вас такими задачками (м)учат?..

 

Хм... Бау =)
Только не мучают, а я сам придумал эту задачу! =)
И преподу ее порекомендовал, чтобы вся группа помучалась =), т.к. я хочу реальный кодинг, хоть в ЯВУ, хоть в Асме!!!
А реальный кодинг никто кроме себя самого не сделает
А универ - это банальный закос от армии, там никогда не будет того, что есть в серии книг, и то что может встретиться в жизни... Универ - всего лишь направление, а вот развитие направления - это личное дело
Поэтому кодить-кодить и еще раз кодить на всем!!! Под все!!! =)

 

2microprogs
Да Вы, Александр, просто романтик

 

Навязчивых личностей теперь принято называть романтиками?

ЗЫ: Не в обиду будет сказано.