деление

 

BrAB

аксакал
★☆
Есмь такая штука - интеловский 8051. на нём нужно поделить 16-ти битное число на 10 с получением остатка. но команда деления - восьмибитная.
Как результат - то ли в силу тотального недосыпа, толи просто туплю, но идей кроме организации тупого цикла с выситанием у меня нет.
Итак, может кто из зубров просветит, как можно разделить 16ти битное число на 10 с использованием только 8ми битной команды деления? Ну или других команд (может как-то через сдвиг?)
Было у еврея всё плохо. Пришел за советом к равину. Тот - напиши над дверью - "Так будет не всегда". Стало всё ок. Пошел он благодарить. А тот ему - надпись не стирай. Злой чечен ползет на берег. ©Лермонтов  

hcube

старожил
★☆

Сначала делишь старший байт, запоминаешь бит переноса. Потом делишь младший байт + бит переноса. Результаты делений суммируешь.
Убей в себе зомби!  

BrAB

аксакал
★☆
hcube, 02.06.2004 09:13:11 :
Сначала делишь старший байт, запоминаешь бит переноса. Потом делишь младший байт + бит переноса. Результаты делений суммируешь.
 


Если честно, то не понял :)
Вот пример - делим 3515 на 10. по байтам это будет 13 - 187. Получаю:
13/10=1
187/10=18
Итого 19. Хм....... и потом:

>запоминаешь бит переноса
Читаю в руководстве по 8051: Флаг переноса сбрасывается в любом случае.
Т. е. какой смысл его запоминать, если он всегда 0?
Было у еврея всё плохо. Пришел за советом к равину. Тот - напиши над дверью - "Так будет не всегда". Стало всё ок. Пошел он благодарить. А тот ему - надпись не стирай. Злой чечен ползет на берег. ©Лермонтов  
RU Андрей Суворов #02.06.2004 14:40
+
-
edit
 

Андрей Суворов

координатор

BrAB, 02.06.2004 11:45:23 :
hcube, 02.06.2004 09:13:11 :
Сначала делишь старший байт, запоминаешь бит переноса. Потом делишь младший байт + бит переноса. Результаты делений суммируешь.
 


Если честно, то не понял :)
Вот пример - делим 3515 на 10. по байтам это будет 13 - 187. Получаю:
13/10=1
187/10=18
Итого 19. Хм....... и потом:

>запоминаешь бит переноса
Читаю в руководстве по 8051: Флаг переноса сбрасывается в любом случае.
Т. е. какой смысл его запоминать, если он всегда 0?
 


Он, наверно, хотел написать "запоминаешь остаток". Остаток потом нужно сдвинуть на четыре бита вместе с младшим байтом, опять поделить. И еще раз сдвинуть и еще раз поделить. Итого три деления, и два сдвига по четыре бита.
 
+
-
edit
 

-exec-

опытный

предыдущие ораторы имеют в виду, что нужно вспомнить как делить на бумаге столбиком.
 
US Сергей-4030 #03.06.2004 00:28
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Он, наверно, хотел написать "запоминаешь остаток". Остаток потом нужно сдвинуть на четыре бита вместе с младшим байтом, опять поделить. И еще раз сдвинуть и еще раз поделить. Итого три деления, и два сдвига по четыре бита.
 


Ммм.... а поподробнее можно - с примером?




Вообще-то, если призвать на помощь математику, то получаем (для беззнаковых значений, для знаковых - чуть более громоздко) такой алгоритм:

Возьмем число x. У него есть старший байт (u = x/256) и младший (l=x%256)

Тогда:

x= u*256 + l
x= u*250 + u*6 + l

x/10 = u*250/10+(6u+l)/10

x/10 = u*25 + (6u+l)/10

То есть алгоритм такой:

int division(int num) {
byte u=num/256; byte l=num%256;
int rem=6*u+l;
return u*25+(rem>256)?division(rem):rem/10;
}


Совершенно понятно, что ни рекурсивность ни "верхнеуровневость" не мешают - можно вполне реализовать на ассемблере без никаких проблем.

 
Это сообщение редактировалось 03.06.2004 в 00:39
US Сергей-4030 #03.06.2004 00:33
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Очевидно, что идти дальше:

x/10 = u*25 + (6u+l)/10 = u*25 +6u/10 + l/10 мы не можем ибо тогда будут ошибки округления
 
US Сергей-4030 #03.06.2004 00:37
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Редактирования почему-то иногда не отражаются... :( Страничка в кэше?
 
Это сообщение редактировалось 03.06.2004 в 02:45

SEA

втянувшийся

Как сказал -exec-, алгоритм хорошо виден, если вспомнить как мы делим столбиком (все цифры в примере 16тиричные):
 

SEA

втянувшийся

Но, все хорошо пока делимое не больше полбайта размером. Иначе возникает ситуация, когда так делить нельзя, поскольку одна из промежуточных операций деления требует 2х байтового делитея:
 

SEA

втянувшийся

Поэтому, если делить надо на скажем, на 10 - нет проблем, можно делать такой алгоритм.
Если надо делить на произвольное число - надо забыть об операции DIV AB и реализовать стандартное бинарное деление. В общем это то же самое деление столбиком, только не 16-ричное, а бинарное, и операции бинарного сдвига сразу нескольких байт.
 
+
-
edit
 

Mishka

модератор
★★☆
Поскольку тут Сергей уже почти разобрал и не надо общего алгоритма деления, а нужен остаток - то вот рассуждения.

Остаток от деления суммы равен сумме остатков от деления каждого члена суммы. Если эта сумма превосходит делитель, то продолжаем.

Итак,
x%10 = (250*u)%10 + (6*u)%10 + i%10
Остаток первого члена равен R1=0, его не учитываем.
Остаток от второго члена будет R2=6*(u%10)=6*r2.
Остаток от третьего члена R3=I%10.
Итого, R=6*r2+R3. Получили, что два деления 8-и битных, одно умножение - 8 битное, одно сложение. Если R>10, то рекурсивно.
Если охота потрахаться дальше с арифметикой остатков, то можно заметить, что у произведения 6*u периодичность остатков такая
6*0 - 0
6*1 - 6
6*2 - 2
6*3 - 8
6*4 - 4
6*5 - 0
6*6 - 6
6*7 - 2
6*8 - 8
6*9 - 4
...
Это и есть период - 0, 6, 2, 8, 4 - его можно зашить в массив от 0 до 9 - для скорости или честно делить (или даже от 0 до 4 - по длине периода). Очевидно, что, если мы выбираем из массива число не большее 8 и к нему добавляем число не большее 9 от R3, то сумма не превзойдет 17, поэтому рекурсию можно заменить на сравнение.

Пусть u=13, i=87
6*(13%10)+87%10=6*3+7=25 - 25%10=5. Если следовать рекурсивному варианту.
R[13%10]+87%10 = R[3]+7=15 15-10=5 - Если с проверкой и массивом.

Массив против деления и умножения. Тут надо считать такты. Скажем, на Искре 226, где деление и умножения не было, вариант с массивами был предпочтительнее, чем вызов подпрограммы деления/умножения.
 
US Сергей-4030 #03.06.2004 23:58
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Итого, R=6*r2+R3. Получили, что два деления 8-и битных, одно умножение - 8 битное, одно сложение. Если R>10, то рекурсивно
 


Причем максимальная глубина рекурсивного вложения, насколько я понимаю, равна единице.
 
+
-
edit
 

Mishka

модератор
★★☆
А вообще-то, это все нужно для преобразования чисел в печатный вид. Правильно я понял?

Вот что я использовал на ранних версиях НР - на которорых не было деления и умножения тоже.
Завел массив целых (это для unsigned)

code cpp
  1. int array[] = { 10000, 1000, 100, 10, 1 };

А потом сравнивал полученное число поочередно с элементами массива:

code cpp
  1.  
  2. cons char* to10( unsigned int val )
  3. {
  4.     static int array[] = { 10000, 1000, 100, 10, 1 };
  5.     static char r[ 20 ];
  6.  
  7.     int ix;
  8.     int rIx = 0;
  9.     int counter;
  10.     for ( ix = 0; ix < 5; ++ix )
  11.     {
  12.         if ( val >= array[ ix ] )
  13.         {
  14.             while ( val >= array[ ix ] )
  15.             {
  16.                 counter++;
  17.                 val -= array[ ix ];
  18.              }
  19.              r[ rIx++ ] = counter + '0';
  20.              counter = 0;
  21.         }
  22.     }
  23.     r[ rIx ] = '\0';
  24.     return r;
  25. }


Понятно, что для знаковых, я работал с абсолютным значение, а знак сразу заносил. Да, еще надо специальным образом обрабатывать случай, когда val==0x1000 - это часто специальный случай и может вызвать прерывание.


ЗЫ код писал по памяти, надо отлаживать.
 
Это сообщение редактировалось 04.06.2004 в 01:04
+
-
edit
 

hcube

старожил
★☆

Есть еще вариант - сдвигать. Вcе три регистра - делимое, делитель и результат. Поделили - сдвинули влево, то есть в плюс. Тогда у нас постепенно все число 'упадет' в верхнюю ячейку. Насколько конкретно двигать, на каждом шаге проверять - на это нужно не более 8 условных переходов ;-).
Убей в себе зомби!  
Это сообщение редактировалось 04.06.2004 в 12:15
+
-
edit
 

GrayCat

координатор

Вот на PIC-ах, вообще без аппаратного MUX/DIV, для вывода двоичных чисел в десятичной форме используется некий хитрющщий алгоритм из сдвигов и "десятичных коррекций" отдельных нибблов, все это в цикле столько раз, сколько бит в исходном числе. На выходе получается "упакованный BCD" — в каждом ниббле по цифре от 0 до 9. Может, попытаться этот алгоритм адаптировать? Тут, правда, без всяких "остатков".

Кстати, алгоритм хорош еще тем, что выполняется за одинаковое количество тактов независимо от числа.
Gray ©at <i>[Семейство кошачих]</i>  

BrAB

аксакал
★☆
Mishka, 03.06.2004 23:38:42 :
А вообще-то, это все нужно для преобразования чисел в печатный вид. Правильно я понял?
 


Колдун, однако! Именно. Полность задание выглядит так - ввести 12 бит с АЦП и вывести это число на 4 семисегментных индикатора.

Всем огромное спасибо. Даже не ожидал такого внимания. А сейчас я пошёл переваривать всё вышенаписнное :-)
Было у еврея всё плохо. Пришел за советом к равину. Тот - напиши над дверью - "Так будет не всегда". Стало всё ок. Пошел он благодарить. А тот ему - надпись не стирай. Злой чечен ползет на берег. ©Лермонтов  
+
-
edit
 

GrayCat

координатор

BrAB>Полность задание выглядит так - ввести 12 бит с АЦП и вывести это число на 4 семисегментных индикатора.

Во, вот для этого как раз больше всего подходит алгоритм, упомянутый мной чуть выше. После него остается только перекодировать полученные нибблы в 7-сегм. представление, и выплюнуть на индикатор. Если интересно, приведу аглоритм более подробно.
Gray ©at <i>[Семейство кошачих]</i>  

SEA

втянувшийся

Собственно говоря, задача заключается в преобразовании 16-ричного в 10-ричное число. Но, для 3-х нибблового числа пожалуй эффективнее всего будет алгоритм, который предложил Сергей-4030.

 
US Сергей-4030 #04.06.2004 23:09
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Но, для 3-х нибблового числа пожалуй эффективнее всего будет алгоритм, который предложил Сергей-4030.
 


Во! :) Молодец я, дайте мне скорей конфетку. ;)
 

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru