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]
