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? 13 15921
In article <11**********************@g47g2000cwa.googlegroups .com>,
Kosio <aa********@gmail.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, lookup 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.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
In article <11**********************@g47g2000cwa.googlegroups .com>,
Kosio <aa********@gmail.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 desupport 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. Specialcase 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********@gmail.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
humanreadable 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
humanreadable output, consider whether you can use octal or
hexadecimal digits instead.

Keith Thompson (The_Other_Keith) 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 humanreadable 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 humanreadable output, consider whether you can use octal or hexadecimal digits instead.
 Keith Thompson (The_Other_Keith) 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, 8digit
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**********************@g47g2000cwa.googlegroups .com> "Kosio" <aa********@gmail.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(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[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**********************@g44g2000cwa.googlegroups .com>,
Kosio <aa********@gmail.com> wrote: My reasoning is that I want to send a number to a 7 segment, 8digit 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********@gmail.com> wrote in message
news:11**********************@g47g2000cwa.googlegr oups.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 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.
Dik T. Winter wrote: In article <11**********************@g47g2000cwa.googlegroups .com> "Kosio" <aa********@gmail.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(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[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
In article <3H*********************@wagner.videotron.net> de********@myrealbox.com writes: 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[i] = (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^(n1)) + 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 ndigit number z:
z < r * 10^(n1) * z / p < z + 1,
but that is just mathematics.

dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
# 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',Nn);
strcpy(accumulator+(Nn),value);
}
static void decimaladd(char *accumulator,char *addend,int N) {
int i,c;
for (i=N1,c=0; i>=0; i) {
int d = c+(accumulator[i]'0')+(addend[i]'0');
c = d>9; if (c) d = 10;
accumulator[i] = 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<N2; i++) {
if (accumulator[i]=='0') accumulator[i] = ' ';
else break;
}
}
static void zerotrim(char *accumulator,int N) {
int i; for (i=0; i<N2; i++) {
if (accumulator[i]!='0') return accumulator+i;
}
return accumulator+N1;
}

SM Ryan http://www.rawbw.com/~wyrmwif/
OOOOOOOOOO! NAVY SEALS!
Kosio wrote: 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.
My reasoning is that I want to send a number to a 7 segment, 8digit 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 highspeed 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 32bit integer division routine took 400
instructions on an 8bit 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
"Thad Smith" <Th*******@acm.org> wrote in message
news:43***********************@auth.newsreader.oct anews.com... Kosio wrote: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.
My reasoning is that I want to send a number to a 7 segment, 8digit 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 highspeed 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 32bit integer division routine took 400 instructions on an 8bit 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. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: lecichy 
last post by:
Hello
Heres the situation:
I got a file with lines like:
name:second_name:somenumber:otherinfo
etc with different values between colons ( just like passwd file)
What I want is to extract...

by: D. Alvarado 
last post by:
Hello,
Can regular expressions help me here? I want to extract a number
from a string which will always be of the form "parameter###" where
"###" is an arbitrary number of numeric digits. So if...

by: Raphi 
last post by:
Hi,
I'm trying to clean up a large database in Access. I have one field for
address, which needs to be broken up into Street Number, Street Name, and
Street Label (St., Road, etc.)
The...

by: ORC 
last post by:
Is there an easy way to extract a number from a string like:
result = ExtractNumber("this is a 4 string");
which should give the result = 4;
Thanks
Ole

by: RonHouston 
last post by:
Hi,
I was wondering if someone could help me on this one.
Is there anyway to format a string/integer etc so that it always outputs a 4 digits number?
thank you.
Ron.

by: iheartvba 
last post by:
I am trying to extract numbers from a string in the access query builder, all I need is the position of the numbers so the instr function will do. However I need a code like InStr(.,"") where ] ""...

by: joan fruchtalle 
last post by:
Hi,
I am working on a VoIP project, in that there is a small task of extracting Port Number from the incoming SDP which is stored in a Buffer.
Let me say it in another way, I have a text which...

by: isladogs 
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...

by: ryjfgjl 
last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...

by: taylorcarr 
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...

by: Charles Arthur 
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone

by: ryjfgjl 
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and timeconsuming...

by: emmanuelkatto 
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel

by: BarryA 
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...

by: Sonnysonu 
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by columnwise with in the specific length.
suppose the i have to...

by: Hystou 
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
 