Алгоритм разложения числа на цифры

TrollWINNT · 01-04-12 22:35:31

Суть задачи, нужно разложить двузначное десятичное число на 2 однозначных. Вроде все просто, но делать это будет 8 битный контроллер. Проблема в жестком ограничении по времени исполнения, а так же в том, что в контроллере нет аппаратного деления. Программное же деление выползает в длительную операцию. Может кто предложит красивый алгоритм? Пока что склоняюсь к тому, чтобы изначально хранить число 2мя цифрами, но это неудобно так как оно должно часто меняться.

ikkunan salvataja · 01-04-12 23:04:06

TrollWINNT пишет:

Вроде все просто, но делать это будет 8 битный контроллер.

С каким процессором? Как говорят телепаты в отпуске. И правильно ли я понял что максимальное число там будет 0110 0011b, или иначе говоря 63h?

MOP3E · 01-04-12 23:06:34

Двоично-десятичная арифметика в контроллере есть? Если есть - особо думать не о чем.

TrollWINNT · 01-04-12 23:22:26

ikkunan salvataja пишет:

С каким процессором? Как говорят телепаты в отпуске.

Не суть важно какой, требуется только алгоритм. Контроллер фирмы atmel серии atmega по предварительным прикидкам. Скорее всего atmega8, должен по коду вроде влезть.

ikkunan salvataja пишет:

И правильно ли я понял что максимальное число там будет 0110 0011b, или иначе говоря 63h?

Да, именно так.

MOP3E пишет:

Двоично-десятичная арифметика в контроллере есть? Если есть - особо думать не о чем.

Нету, только двоичная. Почти мгновенные операции сдвига и достаточно шустрое аппаратное умножение.

MOP3E · 02-04-12 00:21:45

Ну, можно тупо вычитать из числа 10 до тех пор, пока не получится отрицательное число. Максимум 10 итераций или вообще сделать это через ветвления. У кого другие варианты?

TrollWINNT · 02-04-12 00:45:37

MOP3E пишет:

Ну, можно тупо вычитать из числа 10 до тех пор, пока не получится отрицательное число.

Вариант интересный. Наверное стоит попробовать smile . Спасибо за идею. Итого навскидку тактов 40 будет, а если первым шагом вычесть 50 то и в 30 тактов наверное влезет.

Отредактировано TrollWINNT (02-04-12 01:05:29)

дохтур · 02-04-12 01:39:33

TrollWINNT пишет:

Почти мгновенные операции сдвига и достаточно шустрое аппаратное умножение.

Быстрое деление на 10:

y=((unsigned char)(x*51) + 51)>>9

DonDublon3 · 02-04-12 08:14:31

TrollWINNT пишет:

в контроллере нет аппаратного деления.

А что у нас есть в арсенале?

ikkunan salvataja · 02-04-12 08:49:21

MOP3E пишет:

Ну, можно тупо вычитать из числа 10 до тех пор, пока не получится отрицательное число

TrollWINNT пишет:

Вариант интересный. Наверное стоит попробовать

Не, ну я хренею с этих виндейцев. Значит так, берём исходное число, сохраняем. Далее сдвиг вправо без переноса на 3 позиции, сохраняем как промежуточный результат. Сдвиг вправо без переноса на 2 позиции и получившиеся вычитаем из ранее сохранённого промежуточного результата. Старшие разряды у нас есть. Умножаем это на 10, благо аппаратно умножать процессор умеет, вычитаем получившиеся из исходного и получаем младшие разряды.
Как пример, допустим имеем число 47, т.е. 00101111₂
После первого действия имеем 00000101₂ т.е 5, сохраняем его.
Ещё 2 сдвига и получаем 00000001₂, вычитаем его из сохранённого и получаем 00000100.

DonDublon3 · 02-04-12 16:03:15

ikkunan salvataja пишет:

Не, ну я хренею с этих виндейцев. Значит так, берём исходное число, сохраняем. Далее сдвиг вправо без переноса на 3 позиции, сохраняем как промежуточный результат. Сдвиг вправо без переноса на 2 позиции и получившиеся вычитаем из ранее сохранённого промежуточного результата. Старшие разряды у нас есть.

При исходном числе 25 и многих других (найти не составляет труда) алгоритм врет. Хреней дальше.

TrollWINNT · 02-04-12 16:30:12

дохтур пишет:

Быстрое деление на 10:

Интересно, но для 8 битной логики не быстрее чем вычитание.

ikkunan salvataja пишет:

Не, ну я хренею с этих виндейцев. Значит так ...

От це здорово smile . То что нужно. Вариант морзе тоже в принципе лезет, но этот выходит заметно шустрее.

Огромное спасибо всем ответившим.

ikkunan salvataja · 02-04-12 16:36:42

TrollWINNT пишет:

От це здорово smile . То что нужно.

Только не забудь после

ikkunan salvataja пишет:

вычитаем получившиеся из исходного и получаем младшие разряды.

из старшего разряда вычесть 0 с заёмом, это как раз для этого

DonDublon3 пишет:

При исходном числе 25 и многих других (найти не составляет труда) алгоритм врет.

случая, шоб не врало.

Отредактировано ikkunan salvataja (02-04-12 16:37:52)

TrollWINNT · 02-04-12 16:36:50

DonDublon3 пишет:

При исходном числе 25 и многих других (найти не составляет труда) алгоритм врет. Хреней дальше.

А ведь точно. Значит пока что вариант Морзе самый простой по реализации.

DonDublon3 пишет:

А что у нас есть в арсенале?

Сдвиг вправо влево сложение вычитание умножение и сравнение www.gaw.ru/html.cgi/txt/doc/micros/avr/asm/start.htm

ikkunan salvataja · 02-04-12 16:41:19

ikkunan salvataja пишет:

из старшего разряда вычесть 0 с заёмом, это как раз для этого

Это команда sbc.

TrollWINNT · 02-04-12 16:44:08

ikkunan salvataja пишет:

из старшего разряда вычесть 0 с заёмом

Это как?

ikkunan salvataja · 02-04-12 17:01:21

TrollWINNT пишет:

Это как?

Это значит к вычитаемому будет добавлен CF, то есть если перед этим был перенос то по факту будет отнята 1, а не 0.
А можно тупо сравнить исходное и умноженное на 10 округлённое и если второе будет больше то уменьшить его на единицу и уже после этого проводить окончательное вычитание. Попозже внимательнее посмотрю систему команд этого проца и дам готовый вариант.

TrollWINNT · 02-04-12 17:18:00

ikkunan salvataja пишет:

Это значит к вычитаемому будет добавлен CF, то есть если перед этим был перенос то по факту будет отнята 1, а не 0.

Что то это начинает стремительно приближаться к варианту МОРЗЕ по времени smile .

Добавлено спустя 38 мин 43 с:
Пока что самый быстрый по времени вариант МОРЗЕ с тупым перебором. Он прада чуть больше по объему зато по прикидке почти вдвое быстрее алгоритма ikkunan salvataja.

ikkunan salvataja пишет:

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

Я все равно пишу на СИ. Могу конечно сделать отдельную функцию на асме, но вроде и так уже все лезет по времени.

ikkunan salvataja · 02-04-12 20:12:54

TrollWINNT пишет:

зато по прикидке почти вдвое быстрее алгоритма ikkunan salvataja.

По моим прикидкам получается несколько иное. У меня 28 или 29 тактов в зависимости от числа, у МОРЗЕ получается 16 при значениях меньше 10 и плюс 6 тактов для каждого лишнего десятка. То есть у меня в среднем за 28.5 такта, у МОРЗЕ за 43.2.
Был бы в этом процессоре нормальный сдвиг, т.е. сразу на несколько бит за такт, по типу как это в x86 реализовано, плюс умножение на непосредственное значение было бы на 6 тактов меньше.

TrollWINNT · 02-04-12 20:33:56

ikkunan salvataja пишет:

По моим прикидкам получается несколько иное. У меня 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 раз. правда туда еще дохрена чего дописывать smile

MOP3E · 02-04-12 20:56:59

ikkunan salvataja пишет:

По моим прикидкам получается несколько иное. У меня 28 или 29 тактов в зависимости от числа, у МОРЗЕ получается 16 при значениях меньше 10 и плюс 6 тактов для каждого лишнего десятка. То есть у меня в среднем за 28.5 такта, у МОРЗЕ за 43.2.

1. Начинаем с середины.
2. Втыкаем +/-20 или 30 в нужную сторону.
3. Ещё максимум три итерации по 10 - и мы нашли нужное число.

Итого, не больше 5 итераций. Получается максимум 36 тактов или, в среднем, 22. Но, конечно, объём страдает. smile

TrollWINNT · 02-04-12 21:39:29

MOP3E пишет:

Итого, не больше 5 итераций. Получается максимум 36 тактов или, в среднем, 22. Но, конечно, объём страдает.

У меня примерно те же результаты, единственное что при сильно мелком дроблении уже ничего почти не выигрываем. Но ветвление шустрее вычитания/сложения. Даже глядя на автоматически сформированый компилятором ASM код выходит тактов 25 на глаз. Ну естественно можно еще оптимизировать чутка, но в принципе уже нормально.

ikkunan salvataja · 02-04-12 22:00:01

TrollWINNT пишет:

Даже глядя на автоматически сформированый компилятором ASM код выходит тактов 25 на глаз.

Это с учётом 9-ти тактов необходимых на загрузку числа из памяти в регистр и двух преобразованных значений из регистров в память?
Хочу посмотреть.

TrollWINNT · 02-04-12 22:25:25

ikkunan salvataja пишет:

Это с учётом 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 тактов, но код не оптимален. Это все же черновик smile

Форум StopLinux

Объявление

#1 01-04-12 22:35:31

Алгоритм разложения числа на цифры

#2 01-04-12 23:04:06

Re: Алгоритм разложения числа на цифры

#3 01-04-12 23:06:34

Re: Алгоритм разложения числа на цифры

#4 01-04-12 23:22:26

Re: Алгоритм разложения числа на цифры

#5 02-04-12 00:21:45

Re: Алгоритм разложения числа на цифры

#6 02-04-12 00:45:37

Re: Алгоритм разложения числа на цифры

#7 02-04-12 01:39:33

Re: Алгоритм разложения числа на цифры

#8 02-04-12 08:14:31

Re: Алгоритм разложения числа на цифры

#9 02-04-12 08:49:21

Re: Алгоритм разложения числа на цифры

#10 02-04-12 16:03:15

Re: Алгоритм разложения числа на цифры

#11 02-04-12 16:30:12

Re: Алгоритм разложения числа на цифры

#12 02-04-12 16:36:42

Re: Алгоритм разложения числа на цифры

#13 02-04-12 16:36:50

Re: Алгоритм разложения числа на цифры

#14 02-04-12 16:41:19

Re: Алгоритм разложения числа на цифры

#15 02-04-12 16:44:08

Re: Алгоритм разложения числа на цифры

#16 02-04-12 17:01:21

Re: Алгоритм разложения числа на цифры

#17 02-04-12 17:18:00

Re: Алгоритм разложения числа на цифры

#18 02-04-12 20:12:54

Re: Алгоритм разложения числа на цифры

#19 02-04-12 20:33:56

Re: Алгоритм разложения числа на цифры

#20 02-04-12 20:56:59

Re: Алгоритм разложения числа на цифры

#21 02-04-12 21:39:29

Re: Алгоритм разложения числа на цифры

#22 02-04-12 22:00:01

Re: Алгоритм разложения числа на цифры

#23 02-04-12 22:25:25

Re: Алгоритм разложения числа на цифры

Подвал форума