Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Получение значения разряда десятичного числа

Автор: Matrex 6.4.2009, 16:11

Коллеги, помогите с алгоритмом функции, для получения значения разряда десятичного числа. Т.е.

myinttostr(235,0) результат =5
myinttostr(235,1) результат =3
myinttostr(235,2) результат =2

Проблема в том, что допускается использовать только операторы +, -, if, goto, and, xor, or и операции сдвига.

Да, это не задача для ВУЗа - в последующем этот алгоритм будет адаптирован к ассемблеру микроконтроллера PIC16F84 – поэтому такие ограничения по операциям.

Автор: Pavia 6.4.2009, 16:38

А сразу хранить числа в 10 формате smile

не предлогать?

Алгоритм простой
b:=a/10; делем на цело
с:=a-b*10 получаем остаток
goto к следующему разряду

деление на константу легко заменяется на умножение сдвиги и сложения.
Алгоритм лучше прочитать у Агнера Фога. Просто он у него он полностью расписан.

http://www.agner.org/optimize/optimizing_assembly.pdf

Автор: Matrex 6.4.2009, 16:58

В десятичном формате работать нельзя т.к. это полностью меняет алгоритм работы всего приложения.

По поводу Агнера Фога - он использует уножение... Правда умножение можно заменить сложением... Будем посмотреть...

А есть другие соображения?

Автор: Akina 6.4.2009, 17:21

А объём дополнительной памяти? критично?

В крайнем случае нечто типа решения "влоб":

Код


if arg2<2 goto l3
if arg1<200 goto l1
return 2
l1:
if arg1<100 goto l2
return 1
l2:
return 0
l3:
if arg1<100 goto l4
arg1=arg1-100
goto l3
l4:
if arg2=0 goto l999
if arg1<90 goto l5
return 9
l5:
...

Автор: Matrex 6.4.2009, 21:02

Насчет памяти для конкретно этого приложения не критично, поэтому решение "в лоб" допустимо. Я о чем то подобном думал – такая реализация относится к категории «от отчаяния» smile

.

Все таки должно быт простое оригинальное решение т.к. подобная задача должна же была как то решаться на слабых процессорах в которых нет деления и умножения (например Z80, и легендарный Spectrum)

Автор: maxim1000 6.4.2009, 21:51

числа 1, 10, 100, 1000, ... можно сохранить в памяти на этапе сборки
потом можно узнавать старшую цифру так:

Код


int ExtractAndRemoveHighestDigit(int &number,int digitIndex)
{
    const int weight=DegreesOfTen[digitIndex];
    int digit=0;
    while(number>=weight)
    {
        ++digit;
        number-=weight;
    }
    return digit;
}

тогда раскладывать число на цифры можно так:

Код


void ExtractAllDigits(int number,int *digits)
{
    for(int digitIndex=9;digitIndex>=0;--digitIndex)
        *digits++=ExtractAndRemoveHighestDigit(number,digitIndex);
]

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

Автор: Akina 6.4.2009, 22:48

Цитата(Matrex @ 6.4.2009, 22:02

)

Насчет памяти для конкретно этого приложения не критично, поэтому решение "в лоб" допустимо.

Я вообще-то эти вещи не связывал... как я понял, десятичную цифру надо выделять из байта? тогда можно подготовить 3 статических таблицы (или построить эти таблицы при старте прошивки/приложения) и находить ответ одним XLAT.

Автор: Matrex 7.4.2009, 08:40

Всем спасибо за советы. Вот нашел в своих старых asm проектах и переделал на Delphi (для наглядности). Реалезация похожа на то что предложил maxim1000:

Код


function TForm1.inttostrr(cx,s:integer):byte;
var al,dx,bx:integer;
    num:array [0..2] of byte;

procedure sub_dec;
label sub_dec2,sub_dec1;
begin
            al:=0;
sub_dec2:   cx:=cx-dx;
            if cx<0 then goto sub_dec1;
            al:=al+1;
            goto sub_dec2;
sub_dec1:   cx:=cx+dx;
            num[bx]:=al;
            bx:=bx+1;
end;

begin
            bx:=0;
            dx:=100;
            sub_dec;
            dx:=10;
            sub_dec;
            dx:=1;
            sub_dec;
            result:=num[s];
end;