Страницы 1
Суть задачи, нужно разложить двузначное десятичное число на 2 однозначных. Вроде все просто, но делать это будет 8 битный контроллер. Проблема в жестком ограничении по времени исполнения, а так же в том, что в контроллере нет аппаратного деления. Программное же деление выползает в длительную операцию. Может кто предложит красивый алгоритм? Пока что склоняюсь к тому, чтобы изначально хранить число 2мя цифрами, но это неудобно так как оно должно часто меняться.
Нет, так мы целей гнусных не достигнем... / В.П. Вишневский
Неактивен
Вроде все просто, но делать это будет 8 битный контроллер.
С каким процессором? Как говорят телепаты в отпуске. И правильно ли я понял что максимальное число там будет 0110 0011b, или иначе говоря 63h?
Yesterday it worked.
Today it is not working.
Windows is like that.
Неактивен
С каким процессором? Как говорят телепаты в отпуске.
Не суть важно какой, требуется только алгоритм. Контроллер фирмы atmel серии atmega по предварительным прикидкам. Скорее всего atmega8, должен по коду вроде влезть.
И правильно ли я понял что максимальное число там будет 0110 0011b, или иначе говоря 63h?
Да, именно так.
Двоично-десятичная арифметика в контроллере есть? Если есть - особо думать не о чем.
Нету, только двоичная. Почти мгновенные операции сдвига и достаточно шустрое аппаратное умножение.
Нет, так мы целей гнусных не достигнем... / В.П. Вишневский
Неактивен
Ну, можно тупо вычитать из числа 10 до тех пор, пока не получится отрицательное число.
Вариант интересный. Наверное стоит попробовать . Спасибо за идею. Итого навскидку тактов 40 будет, а если первым шагом вычесть 50 то и в 30 тактов наверное влезет.
Редактировался TrollWINNT (02-04-12 02:05:29)
Нет, так мы целей гнусных не достигнем... / В.П. Вишневский
Неактивен
Почти мгновенные операции сдвига и достаточно шустрое аппаратное умножение.
Быстрое деление на 10:
y=((unsigned char)(x*51) + 51)>>9
Бывает, новые пользователи перезагружают компьютер, потому что не знают, как ещё можно выйти из vi
Ну ты пруфами не сыпь © Skynet2015
Провокатор хуев -) Я к тебе в твою конторку инсайдера зашлю, ты даже не узнаешь в какой момент тебя поимели -) © Rector, 2010-2015
Неактивен
в контроллере нет аппаратного деления.
А что у нас есть в арсенале?
"Фу бля, крохобор вонючий" (с) Svart Testare
Неактивен
Ну, можно тупо вычитать из числа 10 до тех пор, пока не получится отрицательное число
Вариант интересный. Наверное стоит попробовать
Не, ну я хренею с этих виндейцев. Значит так, берём исходное число, сохраняем. Далее сдвиг вправо без переноса на 3 позиции, сохраняем как промежуточный результат. Сдвиг вправо без переноса на 2 позиции и получившиеся вычитаем из ранее сохранённого промежуточного результата. Старшие разряды у нас есть. Умножаем это на 10, благо аппаратно умножать процессор умеет, вычитаем получившиеся из исходного и получаем младшие разряды.
Как пример, допустим имеем число 47, т.е. 00101111₂
После первого действия имеем 00000101₂ т.е 5, сохраняем его.
Ещё 2 сдвига и получаем 00000001₂, вычитаем его из сохранённого и получаем 00000100.
Yesterday it worked.
Today it is not working.
Windows is like that.
Неактивен
Не, ну я хренею с этих виндейцев. Значит так, берём исходное число, сохраняем. Далее сдвиг вправо без переноса на 3 позиции, сохраняем как промежуточный результат. Сдвиг вправо без переноса на 2 позиции и получившиеся вычитаем из ранее сохранённого промежуточного результата. Старшие разряды у нас есть.
При исходном числе 25 и многих других (найти не составляет труда) алгоритм врет. Хреней дальше.
"Фу бля, крохобор вонючий" (с) Svart Testare
Неактивен
Быстрое деление на 10:
Интересно, но для 8 битной логики не быстрее чем вычитание.
Не, ну я хренею с этих виндейцев. Значит так ...
От це здорово . То что нужно. Вариант морзе тоже в принципе лезет, но этот выходит заметно шустрее.
Огромное спасибо всем ответившим.
Нет, так мы целей гнусных не достигнем... / В.П. Вишневский
Неактивен
От це здорово smile . То что нужно.
Только не забудь после
вычитаем получившиеся из исходного и получаем младшие разряды.
из старшего разряда вычесть 0 с заёмом, это как раз для этого
При исходном числе 25 и многих других (найти не составляет труда) алгоритм врет.
случая, шоб не врало.
Редактировался ikkunan salvataja (02-04-12 17:37:52)
Yesterday it worked.
Today it is not working.
Windows is like that.
Неактивен
При исходном числе 25 и многих других (найти не составляет труда) алгоритм врет. Хреней дальше.
А ведь точно. Значит пока что вариант Морзе самый простой по реализации.
А что у нас есть в арсенале?
Сдвиг вправо влево сложение вычитание умножение и сравнение http://www.gaw.ru/html.cgi/txt/doc/micr … /start.htm
Нет, так мы целей гнусных не достигнем... / В.П. Вишневский
Неактивен
из старшего разряда вычесть 0 с заёмом, это как раз для этого
Это команда sbc.
Yesterday it worked.
Today it is not working.
Windows is like that.
Неактивен
из старшего разряда вычесть 0 с заёмом
Это как?
Нет, так мы целей гнусных не достигнем... / В.П. Вишневский
Неактивен
Это как?
Это значит к вычитаемому будет добавлен CF, то есть если перед этим был перенос то по факту будет отнята 1, а не 0.
А можно тупо сравнить исходное и умноженное на 10 округлённое и если второе будет больше то уменьшить его на единицу и уже после этого проводить окончательное вычитание. Попозже внимательнее посмотрю систему команд этого проца и дам готовый вариант.
Yesterday it worked.
Today it is not working.
Windows is like that.
Неактивен
Это значит к вычитаемому будет добавлен CF, то есть если перед этим был перенос то по факту будет отнята 1, а не 0.
Что то это начинает стремительно приближаться к варианту МОРЗЕ по времени .
Добавлено спустя 38 мин 43 с:
Пока что самый быстрый по времени вариант МОРЗЕ с тупым перебором. Он прада чуть больше по объему зато по прикидке почти вдвое быстрее алгоритма ikkunan salvataja.
Попозже внимательнее посмотрю систему команд этого проца и дам готовый вариант.
Я все равно пишу на СИ. Могу конечно сделать отдельную функцию на асме, но вроде и так уже все лезет по времени.
Нет, так мы целей гнусных не достигнем... / В.П. Вишневский
Неактивен
зато по прикидке почти вдвое быстрее алгоритма ikkunan salvataja.
По моим прикидкам получается несколько иное. У меня 28 или 29 тактов в зависимости от числа, у МОРЗЕ получается 16 при значениях меньше 10 и плюс 6 тактов для каждого лишнего десятка. То есть у меня в среднем за 28.5 такта, у МОРЗЕ за 43.2.
Был бы в этом процессоре нормальный сдвиг, т.е. сразу на несколько бит за такт, по типу как это в x86 реализовано, плюс умножение на непосредственное значение было бы на 6 тактов меньше.
Yesterday it worked.
Today it is not working.
Windows is like that.
Неактивен
По моим прикидкам получается несколько иное. У меня 28 или 29 тактов в зависимости от числа, у МОРЗЕ получается 16 при значениях меньше 10 и плюс 6 тактов для каждого лишнего десятка.
Ну если делать тупо по цепочке может и так. Но никто ж не мешает поделить на группы. Тем более что ветвление это одна команда. Сейчас у меня разбивка идет на 3 группы в каждой по 3-4 ветвления то есть в идеале 8 тактов максимум и плюс пусть тактов даже десять на умножение вычитание и.т.п. Ну естественно си накладывает свой отпечаток, на асме думаю еще бы раза в 2 быстрее вышло.
Примерно такой черновой вариант вышел.
char dig[2]={0,0};
char ZI=45,z;
if (ZI >= 70)
{
if (ZI < 100) z = 9;
if (ZI < 90) z = 8;
if (ZI < 80) z = 7;
}
else if(ZI>=40)
{
if (ZI < 70) z = 6;
if (ZI < 60) z = 5;
if (ZI < 50) z = 4;
}
else
{
if (ZI < 40) z = 3;
if (ZI < 30) z = 2;
if (ZI < 20) z = 1;
if (ZI < 10) z = 0;
}
dig[0] = z;
dig[1] = ZI-(z*10);
Позже можно глянуть генерируемый код и если не будет хватать времени подчистить и вынести в отдельную функцию на асме, но пока запас в 6-8 раз. правда туда еще дохрена чего дописывать
Нет, так мы целей гнусных не достигнем... / В.П. Вишневский
Неактивен
Итого, не больше 5 итераций. Получается максимум 36 тактов или, в среднем, 22. Но, конечно, объём страдает.
У меня примерно те же результаты, единственное что при сильно мелком дроблении уже ничего почти не выигрываем. Но ветвление шустрее вычитания/сложения. Даже глядя на автоматически сформированый компилятором ASM код выходит тактов 25 на глаз. Ну естественно можно еще оптимизировать чутка, но в принципе уже нормально.
Нет, так мы целей гнусных не достигнем... / В.П. Вишневский
Неактивен
Даже глядя на автоматически сформированый компилятором ASM код выходит тактов 25 на глаз.
Это с учётом 9-ти тактов необходимых на загрузку числа из памяти в регистр и двух преобразованных значений из регистров в память?
Хочу посмотреть.
Yesterday it worked.
Today it is not working.
Windows is like that.
Неактивен
Это с учётом 9-ти тактов необходимых на загрузку числа из памяти в регистр и двух преобразованных значений из регистров в память?
Нет, без учета загрузки.
; 0000 0066 if (ZI>=70){
LDD R26,Y+1
CPI R26,LOW(0x46)
BRLO _0xA
; 0000 0067 if (ZI<100)z=9;
CPI R26,LOW(0x64)
BRSH _0xB
LDI R30,LOW(9)
ST Y,R30
; 0000 0068 if (ZI<90)z=8;
_0xB:
LDD R26,Y+1
CPI R26,LOW(0x5A)
BRSH _0xC
LDI R30,LOW(8)
ST Y,R30
; 0000 0069 if (ZI<80)z=7;
_0xC:
LDD R26,Y+1
CPI R26,LOW(0x50)
BRSH _0xD
LDI R30,LOW(7)
ST Y,R30
; 0000 006A }
_0xD:
; 0000 006B else if(ZI>=40){
RJMP _0xE
_0xA:
LDD R26,Y+1
CPI R26,LOW(0x28)
BRLO _0xF
; 0000 006C if (ZI<70)z=6;
CPI R26,LOW(0x46)
BRSH _0x10
LDI R30,LOW(6)
ST Y,R30
; 0000 006D if (ZI<60)z=5;
_0x10:
LDD R26,Y+1
CPI R26,LOW(0x3C)
BRSH _0x11
LDI R30,LOW(5)
ST Y,R30
; 0000 006E if (ZI<50)z=4;
_0x11:
LDD R26,Y+1
CPI R26,LOW(0x32)
BRSH _0x12
LDI R30,LOW(4)
ST Y,R30
; 0000 006F }
_0x12:
; 0000 0070 else {
RJMP _0x13
_0xF:
; 0000 0071 if (ZI<40)z=3;
LDD R26,Y+1
CPI R26,LOW(0x28)
BRSH _0x14
LDI R30,LOW(3)
ST Y,R30
; 0000 0072 if (ZI<30)z=2;
_0x14:
LDD R26,Y+1
CPI R26,LOW(0x1E)
BRSH _0x15
LDI R30,LOW(2)
ST Y,R30
; 0000 0073 if (ZI<20)z=1;
_0x15:
LDD R26,Y+1
CPI R26,LOW(0x14)
BRSH _0x16
LDI R30,LOW(1)
ST Y,R30
; 0000 0074 if (ZI<10)z=0;
_0x16:
LDD R26,Y+1
CPI R26,LOW(0xA)
BRSH _0x17
LDI R30,LOW(0)
ST Y,R30
; 0000 0075 }
_0x17:
_0x13:
_0xE:
; 0000 0076 dig[0]=z;
LD R30,Y
STD Y+2,R30
; 0000 0077 dig[1]=ZI-(z*10);
LDD R22,Y+1
CLR R23
LD R26,Y
LDI R30,LOW(10)
MUL R30,R26
MOVW R30,R0
MOVW R26,R30
MOVW R30,R22
SUB R30,R26
STD Y+3,R30
Где то 30 тактов, но код не оптимален. Это все же черновик
Нет, так мы целей гнусных не достигнем... / В.П. Вишневский
Неактивен
Страницы 1