Перевод числа в строку
От: Аноним  
Дата: 11.12.09 14:48
Оценка:
Здравствуйте.
Стоит задача на ANSI С написать функцию перевода целого числа (4 байта) в диапазоне 0 — 999999 в строку символов ASCII.
Важна быстрота исполнения. Программа для 8-битного контроллера PIC, поэтому нужен алгоритм без деления, т.к. это действие получается весьма длительным. Может какой то табличный метод или что ещё?
Алгоритм с делением на 10 и + 0х30 к остатку не прелагать
Оперировать переменными не больше dword (4 байта).
Буду очень благодарен за помощь.
Re: Перевод числа в строку
От: dilmah США  
Дата: 11.12.09 14:59
Оценка: +1
в те времена когда такое было актуально люди придумали binary-coded decimal. В x86 даже машинные инструкции для работы с ними добавляли..
Re[2]: Перевод числа в строку
От: blackhearted Украина  
Дата: 11.12.09 17:03
Оценка:
Здравствуйте, dilmah, Вы писали:

D>в те времена когда такое было актуально люди придумали binary-coded decimal. В x86 даже машинные инструкции для работы с ними добавляли..


+ в PIC ,насколько я помню, тоже есть команды именно для BCD
Re: Перевод числа в строку
От: sysprg  
Дата: 11.12.09 21:19
Оценка: 4 (1)
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте.

А>Стоит задача на ANSI С написать функцию перевода целого числа (4 байта) в диапазоне 0 — 999999 в строку символов ASCII.
А>Важна быстрота исполнения. Программа для 8-битного контроллера PIC, поэтому нужен алгоритм без деления, т.к. это действие получается весьма длительным. Может какой то табличный метод или что ещё?

Пусть x — исходная величина (32-битная), p — рабочая 32-битная переменная, d — остаток от деления на 10 (очередная цифра), тогда:

p = x;
x = (x * 0xCCCD) >> 19;
if (p >= 0x14000) x = x | 0x2000;
d = p — x * 10;

В цикле последовательно получаем цифры с конца. Все умножения — 32-битные, в первом возможно переполнение на первой итерации цикла, но результат все равно будет правильным (можно устранить при желании и сам факт переполнения).
Проверка в if нужна только на первой итерации цикла.
Re[2]: Перевод числа в строку
От: sysprg  
Дата: 11.12.09 21:34
Оценка:
А> Стоит задача на ANSI С написать функцию перевода целого числа (4 байта) в диапазоне 0 — 999999 в строку символов ASCII.

Не заметил, что по условиям задачи там 6 девяток, а не 5 девяток... Это уже гораздо хуже, придется один раз все-таки сделать обычное деление на 10 — для получения одной из цифр и сведения задачи к x <= 99999. Либо, как вариант — потребуется команда умножения, которая дает 64-битный результат (или хотя бы 40-битный результат). Либо неоправданные ухищрения.
Re[2]: Перевод числа в строку
От: sysprg  
Дата: 11.12.09 23:12
Оценка:
Если не страшен переборный цикл (не более 9 тривиальных итераций) запускающийся только для чисел >= 100000, то для всех шестизначных чисел деление на 10 для главной итерации последовательно генерирующей цифры можно сделать так:

uint32 r, p, d;
r = 0;
while (x >= 100000) {
r = r + 10000;
x = x — 100000;
}
p = x;
x = (x * 0xCCCD) >> 19;
if (p >= 0x14000) x = x | 0x2000;
d = p — (x << 3) — (x + x);
x = x + r;

на выходе этого фрагмента в переменной d — остаток от деления на 10 (очередная цифра), а в переменной x — частное (для следующей итерации цикла). Команды делений нет вообще, делается не более 1 32-битного умножения на каждой итерации цикла.

Если пойти по пути развертки умножения в серию хитрых сдвигов и сложений, то можно обойтись и без особой обработки первой цифры, и даже без if в цикле. Но результирующий код будет несколько мутным для понимания.
Re[3]: Перевод числа в строку
От: sysprg  
Дата: 12.12.09 00:18
Оценка: 186 (2) :)
Вот упомянутый выше код для деления на 10 (с остатком) всех 6-значных чисел. Код без умножения, без циклов и без непонятных if, для тонких ценителей извращений:

p = x;
y = (x + x + x) << 2;
x = (y << 4) + y;
x = (x << 4) + y;
y = x << 12;
h = x >> 20;
x = y + x + p;
if (x < y) h = h + 1;
x = x >> 27;
h = h << 5;
x = x + h;
d = p — (x << 3) — (x + x);
Re[4]: Перевод числа в строку
От: Аноним  
Дата: 14.12.09 07:20
Оценка:
Здравствуйте, sysprg
Спасибо, буду поробовать. в последнем варианте, я так понимаю тоже в d — остаток, в x — частное?
Re[4]: Перевод числа в строку
От: Аноним  
Дата: 14.12.09 08:18
Оценка:
Здравствуйте, sysprg, Вы писали:

S>Вот упомянутый выше код для деления на 10 (с остатком) всех 6-значных чисел. Код без умножения, без циклов и без непонятных if, для тонких ценителей извращений:


S>p = x;

S>y = (x + x + x) << 2;
S>x = (y << 4) + y;
S>x = (x << 4) + y;
S>y = x << 12;
S>h = x >> 20;
S>x = y + x + p;
S>if (x < y) h = h + 1;
S>x = x >> 27;
S>h = h << 5;
S>x = x + h;
S>d = p — (x << 3) — (x + x);

Однако вот это у меня раза в полтора быстрее работает.....

void PrintfDWORD(BYTE* dest, DWORD number)
{
BYTE digit = 0;
DWORD num = 0;

num = number;
digit = (BYTE)(num / 100000);
*dest++ = digit + 0x30;
num -= (DWORD)digit * 100000;

digit = (BYTE)(num / 10000);
*dest++ = digit + 0x30;
num -= (DWORD)digit * 10000;

digit = (BYTE)(num / 1000);
*dest++ = digit + 0x30;
num -= (DWORD)digit * 1000;

digit = (BYTE)(num / 100);
*dest++ = digit + 0x30;
num -= (DWORD)digit * 100;

digit = (BYTE)(num / 10);
*dest++ = digit + 0x30;
num -= (DWORD)digit * 10;

*dest++ = (BYTE)num + 0x30;

*dest = 0;
}
Re[5]: Перевод числа в строку
От: Кодт Россия  
Дата: 14.12.09 10:45
Оценка: 18 (1)
Здравствуйте, <Аноним>, Вы писали:

А>Однако вот это у меня раза в полтора быстрее работает.....

На PIC? С ручной реализацией деления?
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Перекуём баги на фичи!
Re[5]: Перевод числа в строку
От: sysprg  
Дата: 14.12.09 16:24
Оценка:
Здравствуйте, Аноним, Вы писали:

А> Однако вот это у меня раза в полтора быстрее работает.....


Как правильно сказал Кодт проверять-то нужно не на Intel, а на твоем целевом PIC без команды деления. На Intel можно проверить предыдущий вариант (с умножением и циклом while), будет скорее всего еще быстрее деления. К тому же компилятор с высокой вероятностью все деления на константы заменил умножениями.
Re[6]: Перевод числа в строку
От: Аноним  
Дата: 15.12.09 07:13
Оценка:
Здравствуйте, sysprg, Вы писали:

S>Здравствуйте, Аноним, Вы писали:


А>> Однако вот это у меня раза в полтора быстрее работает.....


S>Как правильно сказал Кодт проверять-то нужно не на Intel, а на твоем целевом PIC без команды деления. На Intel можно проверить предыдущий вариант (с умножением и циклом while), будет скорее всего еще быстрее деления. К тому же компилятор с высокой вероятностью все деления на константы заменил умножениями.


Проверял в Протеусе с целевым пиком. Вывел на осцилографодну ногу и засек выдачей на неё время исполнения. Живого железа пока нет. Но Протеус ранее вполне адекватно отображал картину..
Re: Перевод числа в строку
От: Буравчик Россия  
Дата: 15.12.09 22:10
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>Здравствуйте.

А>Стоит задача на ANSI С написать функцию перевода целого числа (4 байта) в диапазоне 0 — 999999 в строку символов ASCII.
А>Важна быстрота исполнения. Программа для 8-битного контроллера PIC, поэтому нужен алгоритм без деления, т.к. это действие получается весьма длительным. Может какой то табличный метод или что ещё?
А>Алгоритм с делением на 10 и + 0х30 к остатку не прелагать
А>Оперировать переменными не больше dword (4 байта).
А>Буду очень благодарен за помощь.

Можно так.

Делим на 1000. Вход — х, выход частное div и остаток mod. Числа за знаком
div = ( (x << 10) + (x << 4) + (x << 3) + x) >> 20          // div = x * 1049 / 1048576
mod = x - (div << 10) + (div << 5) - (div << 3)             // mod = x - div * 1000
if (mod < 0) {                                              // хитрая коррекция
  div--;
  mod = 1000 + mod
}


Далее, представление чисел от 0 до 999 находим по таблицам.

Если без таблиц, то для чисел < 1000 можно использовать следующее деление на 10:
y = (x << 1) + x                                  // y = x * 3
div = ( (y << 6) + (y << 2) + x ) >> 11           // div = x * 205 / 2048
mod = x - (div << 3) - (div << 1)                 // mod = x - div * 10
... << RSDN@Home 1.2.0 alpha 4 rev. 1302>>
Best regards, Буравчик
Re[2]: Перевод числа в строку
От: sysprg  
Дата: 15.12.09 23:16
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>Если без таблиц, то для чисел < 1000 можно использовать следующее деление на 10:

Б>   y = (x << 1) + x                                  // y = x * 3
Б>   div = ( (y << 6) + (y << 2) + x ) >> 11           // div = x * 205 / 2048
Б>   mod = x - (div << 3) - (div << 1)                 // mod = x - div * 10

До 1000 можно еще одним тактом меньше:

p = x;
x = (x << 1) + x;
x = (p << 8) - x - (x << 4);
x = x >> 11;
d = p - (x << 3) - (x + x);

В x новое частное, в d — остаток (цифра). Тут (p << 8) считается параллельно с предыдущими командами, (x << 4) во время вычитания
Re: Перевод числа в строку
От: Аноним  
Дата: 16.12.09 22:47
Оценка:
Код внизу. Сложность 10 * 6 (число цифр * число разрядов). Делений нет. Надеюсь, что поможет.

#include <assert.h>
#include <stdio.h>

void print(int n)
{
    assert(0 <= n          );
    assert(     n <= 999999);

    static const int degrees[] = {
        100000,
         10000,
          1000,
           100,
            10,
             1,
             0
    };

    int r = n;
    for (const int *p = degrees; *p != 0; ++p) {
        if (n >= *p || *p == 1) {
            int c = 0;
            while (r >= *p) {
                ++c;
                r -= *p;
            }
            putc("0123456789"[c], stdout);
        }
    }
}

void testPrint(int n)
{
    printf("%d ", n);
    print(n);
    putc('\n', stdout);
}

int main()
{
    testPrint(0);
    testPrint(4);
    testPrint(40);
    testPrint(46);
    testPrint(123456);
    testPrint(999999);
}
Re[3]: Перевод числа в строку
От: dilmah США  
Дата: 17.12.09 08:35
Оценка:
S> Тут (p << 8) считается параллельно с предыдущими командами, (x << 4) во время вычитания

на PIC параллельно??
Re[2]: Перевод числа в строку
От: Кодт Россия  
Дата: 17.12.09 12:10
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>Делим на 1000. Вход — х, выход частное div и остаток mod. Числа за знаком


А если div = x*2097/2097152 ? Тогда хватит точности, чтобы обойтись без коррекции отрицательного остатка. И из дворда не вылезем.
div = ((x<<11) + (x<<4) + (x<<5) + x) >> 21
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Перекуём баги на фичи!
Re[3]: Перевод числа в строку
От: Буравчик Россия  
Дата: 17.12.09 18:45
Оценка: 64 (1)
Здравствуйте, Кодт, Вы писали:

К>А если div = x*2097/2097152 ? Тогда хватит точности, чтобы обойтись без коррекции отрицательного остатка. И из дворда не вылезем.

К>div = ((x<<11) + (x<<4) + (x<<5) + x) >> 21

Тогда появляется другая аномалия — остатки больше или равные 1000.
В то же время действие if (mod > 0) по идее быстрее, чем if (mod > 1000), т.к. появляется дополнительная команда CMP mod, 1000 (или что-то похожее).

И если идти по этому пути, то лучше использовать div = x * 131 / 131072.
Число 2097 содержит 4 единичных бита, а 131 — три, следовательно действий меньше:
div = ((x<<7) + (x<<1) + x) >> 17




Вот таблица:
Строка = (точность, (множитель, битовая длина множителя, битовое представление множителя, количество единичных бит в множителе, степень двойки делителя)

div = x * множитель / 2^степень_двойки_делителя

Причем необходимо:
— чтобы точность была < 1e-6
— битовая длина множителя <= 12
— количество единичных бит минимально

(1.6391277311150754e-10,(536871,20,"10000011000100100111",8,29))
(1.6391277311150754e-10,(1073742,21,"100000110001001001110",8,30))
(1.6391277311150754e-10,(2147484,22,"1000001100010010011100",8,31))
(3.017485141962317e-10,(2147483,22,"1000001100010010011011",9,31))
(7.67409801503971e-10,(1073741,21,"100000110001001001101",8,30))
(1.6987323761194495e-9,(268435,19,"1000001100010010011",7,28))
(1.6987323761194495e-9,(536870,20,"10000011000100100110",7,29))
(2.0265579223424646e-9,(67109,17,"10000011000100101",6,26))
(2.0265579223424646e-9,(134218,18,"100000110001001010",6,27))
(2.0265579223424646e-9,(268436,19,"1000001100010010100",6,28))
(5.4240226745813636e-9,(134217,18,"100000110001001001",6,27))
(1.2874603271505192e-8,(16777,15,"100000110001001",5,24))
(1.2874603271505192e-8,(33554,16,"1000001100010010",5,25))
(1.2874603271505192e-8,(67108,17,"10000011000100100",5,26))
(1.692771911619012e-8,(33555,16,"1000001100010011",6,25))
(4.6730041503885433e-8,(8389,14,"10000011000101",5,23))
(4.6730041503885433e-8,(16778,15,"100000110001010",5,24))
(7.247924804689582e-8,(2097,12,"100000110001",4,21))
(7.247924804689582e-8,(4194,13,"1000001100010",4,22))
(7.247924804689582e-8,(8388,14,"10000011000100",4,23))
(1.6593933105466668e-7,(4195,13,"1000001100011",5,22))
(4.043579101562292e-7,(1049,11,"10000011001",4,20))
(4.043579101562292e-7,(2098,12,"100000110010",4,21))
(5.493164062500208e-7,(131,8,"10000011",3,17))
(5.493164062500208e-7,(262,9,"100000110",3,18))
(5.493164062500208e-7,(524,10,"1000001100",3,19))
(5.493164062500208e-7,(1048,11,"10000011000",3,20))
(1.3580322265624792e-6,(525,10,"1000001101",4,19))
(3.265380859374979e-6,(263,9,"100000111",4,18))
(7.080078124999979e-6,(33,6,"100001",2,15))
(7.080078124999979e-6,(66,7,"1000010",2,16))
(7.080078124999979e-6,(132,8,"10000100",2,17))
(8.17871093750002e-6,(65,7,"1000001",2,16))
(2.343750000000002e-5,(1,1,"1",1,10))
(2.343750000000002e-5,(2,2,"10",1,11))
(2.343750000000002e-5,(4,3,"100",1,12))
(2.343750000000002e-5,(8,4,"1000",1,13))
(2.343750000000002e-5,(16,5,"10000",1,14))
(2.343750000000002e-5,(32,6,"100000",1,15))
(3.759765624999998e-5,(17,5,"10001",2,14))
(9.863281249999998e-5,(9,4,"1001",2,13))
(2.2070312499999998e-4,(5,3,"101",2,12))
(4.6484375e-4,(3,2,"11",2,11))
(9.53125e-4,(1,1,"1",1,9))
(9.53125e-4,(2,2,"10",1,10))

... << RSDN@Home 1.2.0 alpha 4 rev. 1302>>
Best regards, Буравчик
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.