Extracting Digits from a Number

[Kosio]

Hello,

I know of a way to extract digits from a number using the %10 and
divide by 10. But I am wondering if there is an algorithm out there
that does not use a divide by 10 feature.

The reason I ask is that I am programming on a RISC system where
division is quite expensive, and I want to be able to extract the
digits from an integer (the integer will be from 1 to 6 digits long,
and I know how many digits are in the number).

Any ideas?

 

[Walter Roberson]

I know of a way to extract digits from a number using the %10 and
divide by 10. But I am wondering if there is an algorithm out there
that does not use a divide by 10 feature.

The reason I ask is that I am programming on a RISC system where
division is quite expensive, and I want to be able to extract the
digits from an integer (the integer will be from 1 to 6 digits long,
and I know how many digits are in the number).

Any ideas?

branch tables, look-up tables, repeated subtraction, "manual"
division by 10 in binary (shifts, subtractions, multiplications)


An old posting
http://groups.google.ca/group/comp.os.msdos.programmer/msg/d5be552f2742b678
references
"Optimizing Integer Division by a Constant Divisor" by Robert Grappel
which was apparently in Dr. Dobbs... probably 15 years ago or so.

 

[David Resnick]

Hello,

I know of a way to extract digits from a number using the %10 and
divide by 10. But I am wondering if there is an algorithm out there
that does not use a divide by 10 feature.

The reason I ask is that I am programming on a RISC system where
division is quite expensive, and I want to be able to extract the
digits from an integer (the integer will be from 1 to 6 digits long,
and I know how many digits are in the number).

Any ideas?

As this is an algorithm question, not a "C" one, you might get
more opinions in comp.programming. You could get digits from a
table with 1000000 entries. Or do /1000 and %1000 and get them from a
table with 1000 entries. Since you care about efficiency, I assume
using sprintf is right out. I'm sure there are other ways...

-David

 

[Anonymous 7843]

I know of a way to extract digits from a number using the %10 and
divide by 10. But I am wondering if there is an algorithm out there
that does not use a divide by 10 feature.

The reason I ask is that I am programming on a RISC system where
division is quite expensive, and I want to be able to extract the
digits from an integer (the integer will be from 1 to 6 digits long,
and I know how many digits are in the number).

Any ideas?

Here are some thoughts, in no particular order:

1. There may be some compiler options to help you out. A lot
of RISC compilers (incl. gcc) default to the mostly widely
compatible instruction set for a given processor. If you are
willing to de-support older/cheaper versions of a CPU then
you may be able to take advantage of division in hardware.

8. An alternative is to ship two versions of a function, one
compiled for hardware division and one w/o. You can either
select at install time or run time whatever works best.

2. You may be able to exploit some redundancy in the input
data. Special-case -100 thru +100 or so in an array, and/or
cache the last several numbers outside that range. You
don't have to speed it up for all numbers, just most of the
ones actually encountered.

5. Don't store the numbers as numbers. Put them in bytes
or nybbles and when you need to do arithmetic on them,
the conversion to numbers will only require multiply and add,
not division, so it should be faster.

4. Depending on the abilities of the CPU and the dedication
of whoever implented stdlib.h on your platform, it is
theoretically possible that div() is faster than doing
separate % and / operations.

 

[Keith Thompson]

I know of a way to extract digits from a number using the %10 and
divide by 10. But I am wondering if there is an algorithm out there
that does not use a divide by 10 feature.

The reason I ask is that I am programming on a RISC system where
division is quite expensive, and I want to be able to extract the
digits from an integer (the integer will be from 1 to 6 digits long,
and I know how many digits are in the number).

Before you consider using an algorithm other than the obvious one, do
some actual performance measurements. If extracting digits is really
a bottleneck, then by all means do as much optimization as you need.
(I don't have any good ideas about how to do that.) But if it's not a
bottleneck, don't bother making it faster.

Why do you need the decimal digits? The most obvious reason is for
human-readable output; in that case, the time to perform the output is
likely to exceed the time to extract the digits. If it's not for
human-readable output, consider whether you can use octal or
hexadecimal digits instead.

 

[Kosio]

Before you consider using an algorithm other than the obvious one, do
some actual performance measurements. If extracting digits is really
a bottleneck, then by all means do as much optimization as you need.
(I don't have any good ideas about how to do that.) But if it's not a
bottleneck, don't bother making it faster.

Why do you need the decimal digits? The most obvious reason is for
human-readable output; in that case, the time to perform the output is
likely to exceed the time to extract the digits. If it's not for
human-readable output, consider whether you can use octal or
hexadecimal digits instead.

My reasoning is that I want to send a number to a 7 segment, 8-digit
LED display, but I have to know each individual number to set the
display. These numbers will be updated fairly often. I am using an
SPI protocol to send data between the micro and the LED Display...
Basically I send the numbers digit by digit to the display, so I need
to know individual digits of the numbers passed to the micro.

I'll have to look more into how the division algorith works on this
compiler, but with limited ROM space on the micro (and I'm tight as it
is already), two lines of division code take up roughly 3% of my
program space.

Thanks for the advice all,
Aaron

 

[Dik T. Winter]

> I know of a way to extract digits from a number using the %10 and
> divide by 10. But I am wondering if there is an algorithm out there
> that does not use a divide by 10 feature.
>
> The reason I ask is that I am programming on a RISC system where
> division is quite expensive, and I want to be able to extract the
> digits from an integer (the integer will be from 1 to 6 digits long,
> and I know how many digits are in the number).

If you have 64 bit integers the following will do it:

char repr[7];

void convert(unsigned long long z) {
unsigned long long a = z * 687195;
unsigned long long c;
int shift = 36;
int i;
for(i = 0; i < 6; i++) {
c = a >> shift;
repr = (int)c + '0';
a = a - (c << shift);
a += (a << 2);
shift--;
}
repr[6] = 0;
}

 

[Walter Roberson]

My reasoning is that I want to send a number to a 7 segment, 8-digit
LED display, but I have to know each individual number to set the
display. These numbers will be updated fairly often.

In the old days, there were dedicated chips for this purpose...

I am using an
SPI protocol to send data between the micro and the LED Display...
Basically I send the numbers digit by digit to the display, so I need
to know individual digits of the numbers passed to the micro.

Does that imply that you are sending the digits in sequence?
That's a bit different than the task of being able to extract an
arbitrary digit from the middle of a number.

Does the protocol allow the least significant digit to be sent
first?

I'll have to look more into how the division algorith works on this
compiler, but with limited ROM space on the micro (and I'm tight as it
is already), two lines of division code take up roughly 3% of my
program space.

You only have about 64 instruction locations available for your
entire program??

 

[Mike H]

Hello,

I know of a way to extract digits from a number using the %10 and
divide by 10. But I am wondering if there is an algorithm out there
that does not use a divide by 10 feature.

The reason I ask is that I am programming on a RISC system where
division is quite expensive, and I want to be able to extract the
digits from an integer (the integer will be from 1 to 6 digits long,
and I know how many digits are in the number).

Any ideas?

I usually use assembler when programming microcontrollers, but here is the
basic algorithm that should do what you want in C.

void Bin2Ascii (int binval)
{
int plv[]={10,100,1000,10000,100000};
int place=5;
int retval;
if(binval > 999999) return;
while(place--)
{
retval=0;
while(binval>plv[place])
{
binval-=(plv[place]);
retval++;
}
printf("%d\n",retval); // Print Hundred thousands,ten
thousands,thousands,hundreds
}
printf("%d\n",binval); // print ones
}

This should be faster and and consume less space than a general division
function.

Good luck,
Mike H.

 

[Eric Laberge]

I know of a way to extract digits from a number using the %10 and
divide by 10. But I am wondering if there is an algorithm out there
that does not use a divide by 10 feature.

The reason I ask is that I am programming on a RISC system where
division is quite expensive, and I want to be able to extract the
digits from an integer (the integer will be from 1 to 6 digits long,
and I know how many digits are in the number).

If you have 64 bit integers the following will do it:

char repr[7];

void convert(unsigned long long z) {
unsigned long long a = z * 687195;
unsigned long long c;
int shift = 36;
int i;
for(i = 0; i < 6; i++) {
c = a >> shift;
repr = (int)c + '0';
a = a - (c << shift);
a += (a << 2);
shift--;
}
repr[6] = 0;
}

<OT, about algorithms>
Where does the black magic behind this function come from?
</OT>

 

[Dik T. Winter]

> Dik T. Winter wrote: ....

> > > I know of a way to extract digits from a number using the %10 and
> > > divide by 10. But I am wondering if there is an algorithm out there
> > > that does not use a divide by 10 feature.

....
> > If you have 64 bit integers the following will do it:
> >
> > char repr[7];
> >
> > void convert(unsigned long long z) {
> > unsigned long long a = z * 687195;
> > unsigned long long c;
> > int shift = 36;
> > int i;
> > for(i = 0; i < 6; i++) {
> > c = a >> shift;
> > repr = (int)c + '0';
> > a = a - (c << shift);
> > a += (a << 2);
> > shift--;
> > }
> > repr[6] = 0;
> > }

>
> Where does the black magic behind this function come from?

No black magic. I found this kind of algorithm a long time ago for
three digit numbers. The multiplier is 41 and the starting shift is 12.
The idea is that division by a power of 2 is cheaper than a generic
division. So to convert an "n" digit number using multiplication and
shifts only you look for a power of 2 such that the following holds
(note that ^ means exponentiation here):
Say the power of 2 is p = 2^k
Calculate r = p/(10^(n-1)) + 1.
When r * (10^n - 1)/p == 9 you have a valid set of numbers.
You take the smallest k such that this holds (and start with the smallest
k such that p > 10^n - 1). Your multiplier is r, the starting shift is k.

Let us try it for 3 digit numbers. The smallest power of 2 exceeding 999
is 1024 == 2^10. r == 11. 11 * 999 / 1024 == 10. Wrong. Goto 2048 ==
2^11. r == 21. 21 * 999 / 2048 == 10. Wrong. Goto 4096 == 2^12.
r == 41. 41 * 999 / 4096 == 9. Check.

And the final reason this kind of algorith works is because (from the
three conditions above) you have that for any n-digit number z:
z < r * 10^(n-1) * z / p < z + 1,
but that is just mathematics.

 

[SM Ryan]

# I know of a way to extract digits from a number using the %10 and
# divide by 10. But I am wondering if there is an algorithm out there
# that does not use a divide by 10 feature.
#
# The reason I ask is that I am programming on a RISC system where
# division is quite expensive, and I want to be able to extract the
# digits from an integer (the integer will be from 1 to 6 digits long,
# and I know how many digits are in the number).

static void decimalassign(char *accumulator,char *value,int N) {
int n = strlen(value); if (n>N) n = N;
memset(accumulator,'0',N-n);
strcpy(accumulator+(N-n),value);
}
static void decimaladd(char *accumulator,char *addend,int N) {
int i,c;
for (i=N-1,c=0; i>=0; i--) {
int d = c+(accumulator-'0')+(addend-'0');
c = d>9; if (c) d -= 10;
accumulator = d+'0';
}
}
void decimalconvert(char *radix10,unsigned radix2,int N) {
char power2[N+1];
decimalassign(radix10,"0",N);
decimalassign(power,"1",N);
while (radix2) {
if (radix2&1) decimaladd(accumulator,power2,N);
decimaladd(power2,power2,N);
assert(radix2 > radix2>>1);
radix2 >>= 1;
}
}

static void spacefill(char *accumulator,int N) {
int i; for (i=0; i<N-2; i++) {
if (accumulator=='0') accumulator = ' ';
else break;
}
}
static void zerotrim(char *accumulator,int N) {
int i; for (i=0; i<N-2; i++) {
if (accumulator!='0') return accumulator+i;
}
return accumulator+N-1;
}

 

[Thad Smith]

My reasoning is that I want to send a number to a 7 segment, 8-digit
LED display, but I have to know each individual number to set the
display. These numbers will be updated fairly often.

Let's do a timing estimate and see if there is a problem. Unless you
are doing something like labelling frames in a high-speed motion camera,
you probably are generating data for human reading. An update speed
faster than about 20 numbers/second simply generates a blur. I think
you would need to be slower than about 5 numbers/second to have
intermediate numbers readable. Let's say that you update an 8 digit
display 10 times/second (rather fast). That would mean generating 80
digits /second. If a 32-bit integer division routine took 400
instructions on an 8-bit processor, the conversion for one second of
display (10 updates) would take about 32000 instructions. At 1 mips,
that is 32 ms., which is about 3% of the processor load, which would be
adequate for most uses. Adjust the numbers for your particular application.


Thad

 

[Mike H]

Let's do a timing estimate and see if there is a problem. Unless you are
doing something like labelling frames in a high-speed motion camera, you
probably are generating data for human reading. An update speed faster
than about 20 numbers/second simply generates a blur. I think you would
need to be slower than about 5 numbers/second to have intermediate numbers
readable. Let's say that you update an 8 digit display 10 times/second
(rather fast). That would mean generating 80 digits /second. If a 32-bit
integer division routine took 400 instructions on an 8-bit processor, the
conversion for one second of display (10 updates) would take about 32000
instructions. At 1 mips, that is 32 ms., which is about 3% of the
processor load, which would be adequate for most uses. Adjust the numbers
for your particular application.

I don't think the speed of actually updating the display is usually the
issue. In my experience the problem is that you have other very speed
intensive things to be doing so you have to cut time from any place
possible. Of course it would seem logical to use a processor better suited
to the job, but specs usually dictate what you have to work with. Most of
the time this results in using smaller/cheaper parts running at lower speeds
to consume less power...etc...
I think were getting a little off topic now ;-)

Mike H.