443,983 Members | 1,597 Online Need help? Post your question and get tips & solutions from a community of 443,983 IT Pros & Developers. It's quick & easy.

# Extracting Digits from a Number

 P: n/a 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? Nov 15 '05 #1
13 Replies

 P: n/a In article <11**********************@g47g2000cwa.googlegroups .com>, Kosio wrote:I know of a way to extract digits from a number using the %10 anddivide by 10. But I am wondering if there is an algorithm out therethat does not use a divide by 10 feature. The reason I ask is that I am programming on a RISC system wheredivision is quite expensive, and I want to be able to extract thedigits 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 Nov 15 '05 #2

 P: n/a 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 Nov 15 '05 #3

 P: n/a In article <11**********************@g47g2000cwa.googlegroups .com>, Kosio 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. Nov 15 '05 #4

 P: n/a "Kosio" 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_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 15 '05 #5

 P: n/a 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_Keith) ks***@mib.org San Diego Supercomputer Center <*> 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 Nov 15 '05 #6

 P: n/a In article <11**********************@g47g2000cwa.googlegroups .com> "Kosio" 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; 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 = 0; } -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ Nov 15 '05 #7

 P: n/a In article <11**********************@g44g2000cwa.googlegroups .com>, Kosio wrote:My reasoning is that I want to send a number to a 7 segment, 8-digitLED display, but I have to know each individual number to set thedisplay. These numbers will be updated fairly often. In the old days, there were dedicated chips for this purpose... I am using anSPI protocol to send data between the micro and the LED Display...Basically I send the numbers digit by digit to the display, so I needto 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 thiscompiler, but with limited ROM space on the micro (and I'm tight as itis already), two lines of division code take up roughly 3% of myprogram 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 Nov 15 '05 #8

 P: n/a "Kosio" 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. Nov 15 '05 #9

 P: n/a Dik T. Winter wrote: In article <11**********************@g47g2000cwa.googlegroups .com> "Kosio" 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; 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 = 0; } Where does the black magic behind this function come from? -- Eric Laberge Nov 15 '05 #10

 P: n/a 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; 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 = 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. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ Nov 15 '05 #11 