Extracting Digits from a Number

In article <11************ **********@g47g 2000cwa.googleg roups.com>,
Kosio <aa********@gma il.com> 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. 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.o...be552f2742b678
references
"Optimizing Integer Division by a Constant Divisor" by Robert Grappel
which was apparently in Dr. Dobbs... probably 15 years ago or so.
--
"This was a Golden Age, a time of high adventure, rich living and
hard dying... but nobody thought so." -- Alfred Bester, TSMD

Kosio wrote:

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.programmin g. 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

In article <11************ **********@g47g 2000cwa.googleg roups.com>,
Kosio <aa********@gma il.com> 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.

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.

"Kosio" <aa********@gma il.com> writes:

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.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

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.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

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

In article <11************ **********@g47g 2000cwa.googleg roups.com> "Kosio" <aa********@gma il.com> writes:

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(unsigne d 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[i] = (int)c + '0';
a = a - (c << shift);
a += (a << 2);
shift--;
}
repr[6] = 0;
}
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

In article <11************ **********@g44g 2000cwa.googleg roups.com>,
Kosio <aa********@gma il.com> wrote:

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??
--
I was very young in those days, but I was also rather dim.
-- Christopher Priest

"Kosio" <aa********@gma il.com> wrote in message
news:11******** **************@ g47g2000cwa.goo glegroups.com.. .

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 microcontroller s, but here is the
basic algorithm that should do what you want in C.

void Bin2Ascii (int binval)
{
int plv[]={10,100,1000,1 0000,100000};
int place=5;
int retval;
if(binval > 999999) return;
while(place--)
{
retval=0;
while(binval>pl v[place])
{
binval-=(plv[place]);
retval++;
}
printf("%d\n",r etval); // Print Hundred thousands,ten
thousands,thous ands,hundreds
}
printf("%d\n",b inval); // print ones
}

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

Good luck,
Mike H.

Dik T. Winter wrote:

In article <11************ **********@g47g 2000cwa.googleg roups.com> "Kosio"
<aa********@gma il.com> writes:

> 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(unsigne d 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[i] = (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>
--
Eric Laberge