# [SOLVED]Decimal to ascii using reduced instruction cycles

Status
Not open for further replies.

#### ponnus

##### Full Member level 2
Hai,
I want to enter digits into a character array. For example, I want to enter decimal 123 as '1','2','3'.
But it should take only few instruction cycles.

I tried sprintf, but it is taking too much time.

I also tried to convert the decimal number to hex, separate each nibble of the hex ,add 0x30 to convert to ascii. But, decimal to hex conversion used division in that, which takes more time than actually needed.

So, is there any way to print digits to ascii or an easy method for division(such as using shifts) which use only few instruction cycles?

Thank you

• ponnus

### ponnus

Points: 2
Hai,
Thank you very much.....I'm having the same issue....
I'll check it....

Thanks

For a binary to decimal conversion that doesn't involve division/modulo function, you may want to review the double dabble algorithm. https://en.wikipedia.org/wiki/Double_dabble

In C-programming, itoa() or sprintf() are mostly the reasonable method.

For a binary to decimal conversion that doesn't involve division/modulo function, you may want to review the double dabble algorithm. http://en.wikipedia.org/wiki/Double_dabble

This is a great method but kind of tricky to apply in C at least when trying to get the most efficient code

In C-programming, itoa() or sprintf() are mostly the reasonable method.

Not the most efficient way for a microcontroller, for example in AVR the clocks that a utoa takes for three digit conversion is about 700 when a custom routine can do it in less that 1/4 of that.
sprintf is similarly inefficient (actually worse) so when looking for the most efficient code I don't think it is the way to go

- - - Updated - - -

By the way this is another implementation that achieves even less cycles that the previous link I have provided using a half-interval search algorithm
http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&p=1018577#1018577

This is a great method but kind of tricky to apply in C at least when trying to get the most efficient code
Yes, but it's the closest answer to the question in the original post ("using shifts").

Hai,
I want to enter digits into a character array. For example, I want to enter decimal 123 as '1','2','3'.
But it should take only few instruction cycles.
.......I also tried to convert the decimal number to hex, separate each nibble of the hex ,add 0x30 to convert to ascii. But, decimal to hex conversion used division in that, which takes more time than actually needed.

when you say decimal, what exactly do you mean ? is your data already in BCD form ?
I have to assume it is, otherwise why would you need/ want to convert to hex.

And if it is, then all you need to do is add 48 (0x30) to each, and you're done. If its packed, then a mask & swap is all the additional thats required. 3-4 cycles tops on an AVR

Or am i missing something......

Hai alexan_e,
I checked the link you provided. I found that ChaunceyGardiner has provided an efficient code for the conversion. But, unfortunately, I need to convert numbers greater than 1023. So, I'm checking your code 'ULongToStr ' for the conversion and will reply you back.

Actually, I'm using PIC24FJ128GA010 with 32MHz clock and C30 compiler. Suppose if the code takes 100 cycles to convert one number(say 123d) to ascii('1','2','3'), then time for the conversion in this device is (FOSC/2)*100. Sorry, if I am wrong

I'll try the code and i'm also planning to change my platform to dsPIC with 80MHz clock, hope I can run the program faster.

Hai kripacharya,

I've a number (say 20d or 14h). I want to split 2 and 0 and enter to a character array as '2' and '3'.
If I need '1' and '4', then I can easily do that as you said. but that's not what I needed.

Thanks

Okay so thats cleared up. But do you know what is your largest number to be converted ?
Generic library functions are designed to be able to handle unknown lengths, hence take longer. With a known length/ size I would think using the double dabble would probably be the fastest - as also suggested by FvM

Hai,
Now I changed my decision of converting larger numbers. i decided to print values from a 12 bit ADC.
So, I need to convert values upto 4095. i'm trying to edit the double dabber algorithm code which I got from the link provided by alexan_e.

Thanks

So, I need to convert values upto 4095. i'm trying to edit the double dabber algorithm code which I got from the link provided by alexan_e.

There was no function using the double dabber algorithm in the avrfreaks link I have provided, do you mean the link that FvM has provided to the wikipedia article that has a C function example?

- - - Updated - - -

The function of the first link I have provided can be modified for 12bit values like
Code:
void adc2ascii(uint16_t value, char *str)
{
char *p = str;

if      (value > 3999) { *p++ = '4'; value -= 4000; }
else if (value > 2999) { *p++ = '3'; value -= 3000; }
else if (value > 1999) { *p++ = '2'; value -= 2000; }
else if (value > 999) { *p++ = '1'; value -= 1000; }
else 				  { *p++ = '0'; }

if      (value > 899) { *p++ = '9'; value -= 900; }
else if (value > 799) { *p++ = '8'; value -= 800; }
else if (value > 699) { *p++ = '7'; value -= 700; }
else if (value > 599) { *p++ = '6'; value -= 600; }
else if (value > 499) { *p++ = '5'; value -= 500; }
else if (value > 399) { *p++ = '4'; value -= 400; }
else if (value > 299) { *p++ = '3'; value -= 300; }
else if (value > 199) { *p++ = '2'; value -= 200; }
else if (value >  99) { *p++ = '1'; value -= 100; }
else 				  { *p++ = '0'; }

if      (value > 89) { *p++ = '9'; value -= 90; }
else if (value > 79) { *p++ = '8'; value -= 80; }
else if (value > 69) { *p++ = '7'; value -= 70; }
else if (value > 59) { *p++ = '6'; value -= 60; }
else if (value > 49) { *p++ = '5'; value -= 50; }
else if (value > 39) { *p++ = '4'; value -= 40; }
else if (value > 29) { *p++ = '3'; value -= 30; }
else if (value > 19) { *p++ = '2'; value -= 20; }
else if (value >  9) { *p++ = '1'; value -= 10; }
else if (p != str)   { *p++ = '0'; }

*p++ = value + '0';

*p = 0;
}

- - - Updated - - -

And this is the modified 12bit version of the one using the half-interval method which will be faster

Code:
void adc2ascii(uint16_t value, char *str)
{
char *p = str;

if (value > 2999)
{
if (value > 3999) { *p++ = '4'; value -= 4000; }
else             { *p++ = '3'; value -= 3000; }
}
else
{
if      (value > 1999) { *p++ = '2'; value -= 2000; }
else if (value >  999) { *p++ = '1'; value -= 1000; }
else 				   { *p++ = '0'; }
}

if (value > 499)
{
if (value > 699)
{
if      (value > 899) { *p++ = '9'; value -= 900; }
else if (value > 799) { *p++ = '8'; value -= 800; }
else                  { *p++ = '7'; value -= 700; }
}
else
{
if (value > 599) { *p++ = '6'; value -= 600; }
else             { *p++ = '5'; value -= 500; }
}
}
else
{
if (value > 299)
{
if (value > 399) { *p++ = '4'; value -= 400; }
else             { *p++ = '3'; value -= 300; }
}
else
{
if      (value > 199) { *p++ = '2'; value -= 200; }
else if (value >  99) { *p++ = '1'; value -= 100; }
else 				  { *p++ = '0'; }
}
}

if (value > 49)
{
if (value > 69)
{
if      (value > 89) { *p++ = '9'; value -= 90; }
else if (value > 79) { *p++ = '8'; value -= 80; }
else                 { *p++ = '7'; value -= 70; }
}
else
{
if (value > 59) { *p++ = '6'; value -= 60; }
else            { *p++ = '5'; value -= 50; }
}
}
else
{
if (value > 19)
{
if      (value > 39) { *p++ = '4'; value -= 40; }
else if (value > 29) { *p++ = '3'; value -= 30; }
else                 { *p++ = '2'; value -= 20; }
}
else
{
if      (value >  9) { *p++ = '1'; value -= 10; }
else if (p != str)   { *p++ = '0'; }
}
}

*p++ = value + '0';
*p = 0;
}

Last edited:
• ponnus

### ponnus

Points: 2
Oh,,Sorry...I meant this one .

Code:
void adc2ascii(unsigned short value)
{
unsigned char v, a, b;
if (value > 499)
{
if (value > 799)
{
if (value > 999)
{
// Treated as a special case as there
// are only 24 values above 999
str = '1';
str = '0';

v = value - 1000;
if      (v > 19) { str = '2'; v -= 20; }
else if (v >  9) { str = '1'; v -= 10; }
else             { str = '0'; }

str = v + '0';
str = 0;
return;
}

if (value > 899) { a = '9'; v = value - 900; }
else             { a = '8'; v = value - 800; }
}
else if (value > 699) { a = '7'; v = value - 700; }
else if (value > 599) { a = '6'; v = value - 600; }
else                  { a = '5'; v = value - 500; }
}
else if (value > 299)
{
if (value > 399) { a = '4'; v = value - 400; }
else             { a = '3'; v = value - 300; }
}
else if (value > 199) { a = '2'; v = value - 200; }
else if (value >  99) { a = '1'; v = value - 100; }
else                  { a = '0'; v = value; }

if (v > 49)
{
if (v > 69)
{
if      (v > 89) { b = '9'; v -= 90; }
else if (v > 79) { b = '8'; v -= 80; }
else             { b = '7'; v -= 70; }
}
else if (v > 59) { b = '6'; v -= 60; }
else             { b = '5'; v -= 50; }
}
else if (v > 19)
{
if      (v > 39) { b = '4'; v -= 40; }
else if (v > 29) { b = '3'; v -= 30; }
else             { b = '2'; v -= 20; }
}
else if (v > 9) { b = '1'; v -= 10; }
else            { b = '0'; }

if (a == '0')
{
if (b == '0')
{
str = v + '0';
str = 0;
}
else
{
str = b;
str = v + '0';
str = 0;
}
}
else
{
str = a;
str = b;
str = v + '0';
str = 0;
}
}

But the code using half interval time is suitable for my application..Thanks

But the code using half interval time is suitable for my application..Thanks

It basically uses a binary search pattern.
For the modified version that works with 12bit values (0-4095) refer to the second function in my previous post, I believe that this method gives the best compromise between speed and size.

A conversion based on a flash lookup table would be almost instant but it takes a lot of space.

• ponnus

### ponnus

Points: 2
Hello!

As there are many microcontrollers in the 12-bit ADC range, another way to do it
is to use a multiplication instead of a division (if dividing by 10, use a coefficient
for 1/10). This way you can perform a division by 10 in a few clocks (I just tried
with MSP430 : 2 clocks for the multiplication by 1/10, and 2 to move the result)
and also 2 clocks for the x10 multiplication.

And the bonus: no huge lookup table, no endless if-else statements. It can be
written a little bit shorter at the expense of efficiency (with a loop).

Here is the trick. Example with a = 1234.

1. Divide by 10, obtain 123
2. Multiply 123 by 10, obtain 1230
3. Last digit is the original value (1234) to which 1230 has been subtracted.
4. Set the original value to 123, repeat the trick until done.

As for the code (see below), without further optimization than the normal one (low optimization),
I get 100 clocks for this method, vs 82 ~ 91 for the half interval method above. The variation
is due to the number of if..else needed for a given number.

BUT: this method can translate any number from 0 to 9999, so the range is twice the
half-interval method.

NB: This code is not portable. It is efficient because of the hardware multiplier.
It can be done without hardware multiplier by using 32 bit multiplications and would
also be quite fast, I believe.

Code C - [expand]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include "MSP430F5529.h"
#include "Types.h"

void adc2ascii(uint16 value, char *str) ;
void IToA(uint16 value, char * str);

char str1;
char str2;

void main(void) {
uint16 i;
uint16 div10, trick10;
MPY = 6554;
for(i = 100 ; i < 200 ; ++i) {
IToA(i, str1);      //  Runs in 100 clocks for range [0..9999] (*)
adc2ascii(i, str2);     //  Runs in 82 to 91 clocks for range [0..4999]
}
}

// (*) The above figures are given for MSP430F5529, IAR compiler, with low optimization
//
void IToA(uint16 value, char * str) {
//  Get d0
MPY = 6554;                 //  Divide by 10
OP2 = value;                //  Example val = 1234
MPY=10;                     //  Multiply by 10
OP2 = RES1;                 //  Recycle last result as an operand to multiply it back by 10
str = '0' + value - RES0;
value = OP2;                //  Use last operand (that was divided by 10 as a new value, and do the same stuff again.
MPY = 6554;
OP2 = value;
MPY=10;
OP2=RES1;
str = '0' + value - RES0;
value = OP2;
MPY = 6554;
OP2 = value;
str = '0' + RES1;
MPY=10;
OP2=RES1;
str = '0' + value - RES0;
}

void adc2ascii(uint16 value, char *str) {
char *p = str;
if (value > 2999) {
if (value > 3999) {
*p++ = '4';
value -= 4000;
}
else {
*p++ = '3';
value -= 3000;
}
}
else {
if(value > 1999) {
*p++ = '2';
value -= 2000;
}
else if(value >  999) {
*p++ = '1';
value -= 1000;
}
else {
*p++ = '0';
}
}
if (value > 499) {
if (value > 699) {
if (value > 899) {
*p++ = '9';
value -= 900;
}
else if (value > 799) {
*p++ = '8';
value -= 800;
}
else {
*p++ = '7';
value -= 700;
}
}
else {
if (value > 599) {
*p++ = '6';
value -= 600;
}
else {
*p++ = '5';
value -= 500;
}
}
}
else {
if (value > 299) {
if (value > 399) {
*p++ = '4';
value -= 400;
}
else {
*p++ = '3';
value -= 300;
}
}
else {
if (value > 199) {
*p++ = '2';
value -= 200;
}
else if (value >  99) {
*p++ = '1';
value -= 100;
}
else {
*p++ = '0';
}
}
}
if (value > 49) {
if (value > 69) {
if (value > 89) {
*p++ = '9';
value -= 90;
}
else if (value > 79) {
*p++ = '8'; value -= 80;
}
else {
*p++ = '7';
value -= 70;
}
}
else {
if (value > 59) {
*p++ = '6';
value -= 60;
}
else {
*p++ = '5';
value -= 50;
}
}
}
else {
if (value > 19) {
if (value > 39) {
*p++ = '4';
value -= 40;
}
else if (value > 29) {
*p++ = '3';
value -= 30;
}
else {
*p++ = '2';
value -= 20;
}
}
else {
if (value >  9) { *p++ = '1'; value -= 10; }
else if (p != str)   { *p++ = '0'; }
}
}
*p++ = value + '0';
*p = 0;
}

Dora.

Hai,
Now my program seems to be more faster. Thanks for the help.....

Hai Dora,
Now,I am actually using PIC24 which has a 16 bit architecture. But, I'll be porting the code to dsPIC, which is also of 16 bit architecture. It has a 16 bit hardware multiplier. So, I think it'll take more time, when this code runs on a 16-bit microcontroller. Thanks for the suggestion

Hello!

Actually you can do that kind of fake division if you can do 16 bit x 16 bit integer multiplication
and get the result on 32 bits (or on 2 16-bit) registers.
Of course the 16 x 16 multiplication is not very efficient without a hardware multiplier, but anyway
it's better than doing a division. But be careful: 6554 is a rounded value of 1/10. The error is
2 lsbs on 16 bits, so it works well (error free) until 14 bits only.

Beside this, I have also looked at the double dabble algorithm mentioned above. But it looks
very inefficient. There are 3 nested loops, one up to n, whatever it is, and the other up to 16,
and inside these 2 nested loops, there is a third one called twice.
Without reading further, let's be optimistic: n and nscratch are small, we have a small number
of loops, which should be 2*(nscratch - smin)*16*n
Here are only the loops of the double dabble algorithm:

Code C - [expand]1
2
3
4
for (i=0; i < n; ++i) {
for (j=0; j < 16; ++j) {
for (k=smin; k < nscratch; ++k)
for (k=smin; k < nscratch-1; ++k) {

This is a lot. Even if n = 2, nscratch - smin = 2, we would have 128 loops. On my favorite processor,
this would mean 1280 clocks doing nothing worth. And on top of that there is some memory allocation
(malloc and calloc) which makes absolutely no sense for a few bytes. Even less sense on a microcontroller.

BUT: looking at the principle on wikipedia, I think it should be extremely efficient to do it with
some kind of PLD. Or FPGA. I'm not sure whether it can be done in combinatory logic but even
in sequential, it should take just the number of bits to shift. 16 clocks to transform 16 bits, etc...

Dora,

Last edited:

Status
Not open for further replies.