Sign in to follow this  
Drew_Benton

Quick Way to Get Number of Digits in an Integer

Recommended Posts

So I was in Discrete Math today and we were going over some lessons on recursion, fib sequences, etc... One of the concepts that was brought up was finding the run time of Euclidean's GCF. There is this theorem, Lame's theorem that does this. Now part of the proof tells that the number of digits is what determines the run time. Now what concerned me was the method that was used to get the number of digits. I was like "hmmmm" this could be interesting! So here it is, a quick method of getting the number of digits for an Integer.
 digits = floor( log10( abs( number ) ) ) + 1; 
This is demonstrated in this program.
#include <cmath>
#include <iostream>

int main( int argc, char* argv[] )
{
	int long number = 0;
	int digits = 0;

	for( int x = 0; x < 25; x++ )
	{
		number = rand();
                number != 0
		// digits = floor( log10( abs( number ) ) ) + 1;
                digits = floor( log10( abs( number != 0 ? number : 1 ) ) ) + 1;

		std::cout << "Original Number is: " << number << std::endl;
		std::cout << "Number of digits is: " << digits << std::endl;
		std::cout << std::endl;
	}

	return 0;
}


Which produces an output of:
Original Number is: 41
Number of digits is: 2

Original Number is: 18467
Number of digits is: 5

Original Number is: 6334
Number of digits is: 4

Original Number is: 26500
Number of digits is: 5

Original Number is: 19169
Number of digits is: 5

Original Number is: 15724
Number of digits is: 5

Original Number is: 11478
Number of digits is: 5

Original Number is: 29358
Number of digits is: 5

Original Number is: 26962
Number of digits is: 5

Original Number is: 24464
Number of digits is: 5

Original Number is: 5705
Number of digits is: 4

Original Number is: 28145
Number of digits is: 5

Original Number is: 23281
Number of digits is: 5

Original Number is: 16827
Number of digits is: 5

Original Number is: 9961
Number of digits is: 4

Original Number is: 491
Number of digits is: 3

Original Number is: 2995
Number of digits is: 4

Original Number is: 11942
Number of digits is: 5

Original Number is: 4827
Number of digits is: 4

Original Number is: 5436
Number of digits is: 4

Original Number is: 32391
Number of digits is: 5

Original Number is: 14604
Number of digits is: 5

Original Number is: 3902
Number of digits is: 4

Original Number is: 153
Number of digits is: 3

Original Number is: 292
Number of digits is: 3

Press any key to continue


Just thought this was very interesting [smile]. What do you think? It sure beats converting to a string then checking the length [wink] - Drew [edit] Thanks to smart_idiot for pointing out log(0) DNE That kind of takes the ease away from this since you have the check for 0 everytime, or you can just hope 0 isn't used [grin] [Edited by - Drew_Benton on March 28, 2005 2:29:43 PM]

Share this post


Link to post
Share on other sites
I see nothing fundamentally different from your code than with the code below, which itself is quite logical.


int digits(int n) {
int i;

if(!n) {
return 1;
}

for(i = 0; n; ++i) {
n /= 10;
}

return i;
}

Share this post


Link to post
Share on other sites
I had this one which doesn't involve division and it appears to be 300% faster [smile]


int Digits(const int number)
{
int digits = 0;
int step = 1;
while (step <= number) {
digits++;
step *= 10;
}
return digits ? digits : 1;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Prototype
I had this one which doesn't involve division and it appears to be 300% faster [smile]


int Digits(const int number)
{
int digits = 0;
int step = 1;
while (step <= number) {
digits++;
step *= 10;
}
return digits ? digits : 1;
}

I think if you initialize digits to 1, and step to 10, you can just return digits without the branch at the end.

Share this post


Link to post
Share on other sites
[edit] Whoa I type slow [lol]

Quote:
Original post by doho
I see nothing fundamentally different from your code with the code below, which is quite logical.


You are right, but having:


int digits( int n )
{
return floor( log10( abs( number != 0 ? number : 1 ) ) ) + 1;
}
is a new way that I've never seen before. Like I said, it's far from efficient, your examples are much faster than mine ( I just looked at the asm listing), but I think it is quite interesting nevertheless. [smile] I mean this was done around the mid 1800's in a proof!

Share this post


Link to post
Share on other sites
This forum isn't exactly meant for homework, but its an interesting subject so I want to inject some code, and see if we can get some people to show their interesting ways to do this.


int digits( int n )
{
int i=0;
if (n<0) n= -n;
while (n)
{
n/=10;
i++;
}
return i;
}



No biggy of course, everyone should be able to do this. So, now lets see some impressive methods.

Share this post


Link to post
Share on other sites
Quote:
Original post by Inmate2993
This forum isn't exactly meant for homework, but its an interesting subject so I want to inject some code, and see if we can get some people to show their interesting ways to do this.

*** Source Snippet Removed ***

No biggy of course, everyone should be able to do this. So, now lets see some impressive methods.


It would appear that you are the only one who considered the possibility of negative numbers.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave Hunt
It would appear that you are the only one who considered the possibility of negative numbers.

I thought I covered that in my case. The
if (n<0) n= -n; 
part isn't needed.

Share this post


Link to post
Share on other sites
Crazy... log[2] right-shifts, one multiplication and log[2] plus one addition. Significantly faster than log[10] divisions and log[10] additions or even log[10] multiplications and log[10] additions most likely.


count = 0
while 1:
if n < 0:
n = -n
if n == 0:
break
n = n >> 1
count = count + 1
return floor(count * 0.30103)+1


Share this post


Link to post
Share on other sites
Fine, I'll compete. Let's do binary search in a look-up table to avoid multiplications.

Develop clever algorithm in Python:

>>> def digits(n):
(low, high) = (0, 9)
lut = [10 ** x for x in range(1, 10)]
while low != high:
test = (low + high) / 2
if n < lut[test] : high = test
else: low = test + 1
return low + 1
# Some unit tests:
>>> [digits(int('9' * n)) for n in range(1, 10)]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> [digits(int('1' + '0' * n)) for n in range(1, 10)]
[2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> digits(0)
1


Translate to C++:

// Assuming 32-bit integers.
const int lut[9] = { 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000 };
inline int digits(int n) {
int low = 0; int high = 10;
while (low != high) {
int test = (low + high) / 2;
if (n < lut[test]) { high = test; }
else { low = test + 1; }
}
return low + 1;
}


Anyone care to unroll the loop manually, or generate the look-up table at compile time via TMP? Perhaps specialize for other sizes of numeric type? Or for that matter, handle negative numbers? :) (When printing, you kinda want the negative sign to be counted as an extra digit, but for other algorithms you'd prefer it weren't... hmm.)

Share this post


Link to post
Share on other sites
Quote:
Original post by doho
Quote:
Original post by Dave Hunt
It would appear that you are the only one who considered the possibility of negative numbers.

I thought I covered that in my case. The
if (n<0) n= -n; 
part isn't needed.


By Jove, you're right. I didn't pay close enough attention to your for loop conditional. Sorry.

Share this post


Link to post
Share on other sites
sleepy right now, but here is something:


int numDigits(int n)
{
for(int i=1,int numDigits=0;;i>n?(return numDigits):(numDigits++,i*=10)); //buggy!
return -1;
}


It prolly has some dumb bug as usual, but I will try it later tomorrow.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sagar_Indurkhya
sleepy right now, but here is something:

*** Source Snippet Removed ***
It prolly has some dumb bug as usual, but I will try it later tomorrow.

I like this one. Scoping rules probably wouldn't cause a collision with numDigits identifier, but just to be safe I'd recommend never doing that ever again. =D

Share this post


Link to post
Share on other sites
Quote:
Original post by Inmate2993
Quote:
Original post by Sagar_Indurkhya
sleepy right now, but here is something:

*** Source Snippet Removed ***
It prolly has some dumb bug as usual, but I will try it later tomorrow.

I like this one. Scoping rules probably wouldn't cause a collision with numDigits identifier, but just to be safe I'd recommend never doing that ever again. =D


Thanks! It's not often that I write code that considered nifty.

I am sure it can be further optimized, and can garuntee you that any self respecting compiler would further optimizer it.

Share this post


Link to post
Share on other sites
You probably have so many errors having to do with unspecified order of operations in there that I don't even want to think about it.

*EDIT* Never mind, looked closer.

Nice!

Share this post


Link to post
Share on other sites
I am confused. I dropped out of my discrete class, twice actually before just dropping out of school all together, but is one log call some much slower then a bunch of multiplication or division? What is the O(log10)? I guess I don't know how the log10 call works. If it is doing the multiplication in the background then you might be able to optimize it given some restrictions that it doesn't account for. But it seems to me that looping through something, while not immediately, would be much slower the more digits you have.

If anyone knows how the log10 function works I would love to know. I know how to approximate sin and cos from calculus but I can't remeber learning about log. it may seem strange that I want to know after dropping out of school, but it wasn't the learning that drove me away, it was all the homework.

Share this post


Link to post
Share on other sites
Quote:
Original post by StubornAH
I am confused. I dropped out of my discrete class, twice actually before just dropping out of school all together, but is one log call some much slower then a bunch of multiplication or division? What is the O(log10)? I guess I don't know how the log10 call works. If it is doing the multiplication in the background then you might be able to optimize it given some restrictions that it doesn't account for. But it seems to me that looping through something, while not immediately, would be much slower the more digits you have.

If anyone knows how the log10 function works I would love to know. I know how to approximate sin and cos from calculus but I can't remeber learning about log. it may seem strange that I want to know after dropping out of school, but it wasn't the learning that drove me away, it was all the homework.



i've also got no idea how log10 works.

Intlog10 is easy. (just count up numbers, ect.)
Floatlog10 is hard. (i have no idea how to do this, without a lut).

Basically, we need to find a f, so that 10^i * 10^f = n

With a lut of all f from 0-1, (which is the range), we could probably implement this in a binary search, and it would be pretty fast.

You would end up with quite a few mults tho. (or divs, if you don't have a 1/pow10 lut.)

From,
Nice coder

Share this post


Link to post
Share on other sites
ok, you asked for it.

The......

SUPER DOOPER MEGA HAPPY FLOATING POINT MULTI-BIT PRECISION LOGORITHM BASE 10 FUNCTION!!!!!

[lol]

intlut = {0, 1, 10, 100, 1000, 10000, 100000, 100000, 1000000, 10000000, 100000000}

floatlut = {1/10^0.1, 1/10^0.2, 1/20^0.3, ect.}

You could probably get some nice precision from the lut.


max = 11;
min = 0;
while (1){
g = (min + max) >> 1;
if (g = max) {break;} //Your finished.
k = intlut[g];
if (k > x) {
max = g
} else {min = g}
}


Really spazed out code for a binary search for the integer log of a number. (which is what were doing).

Next, is the really spazed out code for doing a binary search for the floating point log of a number.


Goal = x / lut[g]; //Find the floating point portion of this. You can use a mult w/ a table if you want.
//This is the goal for the floating point target to hit.
max = Somevalue;
min = 0;
h = g;
while(1) {
g = (min + max) >> 1;
if (g = max) {break;}
if (fraclut[g] > goal) {max = g;}
else {min = g}
}
return (fraclut[g] * intlut[h]);


Does this seem ok?

From,
Nice coder

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this