CODEWITHSUNDEEP
c++calgorithm
mohit
mohit

Reputation: 6044

How to retrieve the first decimal digit of number efficiently

One obvious solution is:

int n = 2134;
while(n > 9)
    n /= 10;

which takes linear time. Could we do any faster?

Is this any faster than linear time:

char s[100];
sprintf(s, "%d", n);
n = s[0]-'0';

Which are the other ways (efficiency is primary concern)?
I've seen this, except that I need to find only the first digit. (Also, I don't understand the answer).

Upvotes: 14

Views: 26636

Answers (13)

Gianluca Ghettini
Gianluca Ghettini

Reputation: 11628

Another solution: store all your values in BCD format, big endian. Access the first nibble to get the first digit

Es.

Decimal value: 265
BCD format: 0010-0110-0101

Upvotes: 0

Afrah
Afrah

Reputation: 1

    for(int i=0; i<n; i++)
    {  
        e=5; //Specify the number of digits in the number OR Exponential value of 10
        while(e>=0)
        {   
            tenp=pow(10,e); //#include <math.h>
            if(arr[i]/tenp!=0)
            {
                q[i][e]=arr[i]/tenp%10;
            }
            e--;
        }
    }

However, this code's complexity shall be O(n^2), which in undesirable.

Upvotes: 0

RedKid
RedKid

Reputation: 1

First make a double variable in which the number is saved. Then divide that number by 10 in a loop to make the number continuously lose a digit, until it is a 1-digit number. cast the double variable to int to round it down. The result will then be the previously first decimal digit.

The code will run in O(log(n)).

#include <iostream>

using namespace std;

int main() {
    double a;
    cin >> a;
    while (true) {
        a /= 10;
        if (a < 10) {
            a = int(a);
            cout << a;
            break;
        }
    }
    return 0; 
}

Upvotes: -2

Dumitriu Sebastian
Dumitriu Sebastian

Reputation: 162

int FirstDigit ( int Number ) {

    // to obtain the <number of digits -1> use this math formula:

    int DigitsInNumber = (int) lg(Number);           

    long TenExpon = pow(10, DigitsInNumber);

    return (Number / TenExpon);                //first digit
}

also: lg(n) = ln(n) / ln(10);

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308130

Here's a kind of variation on a binary search. Like a binary search it is O(log n). Whether it's faster will depend on how fast you can do integer division.

if (n >= 100000000)
    n /= 100000000
if (n >= 10000)
    n /= 10000
if (n >= 100)
    n /= 100
if (n >= 10)
    n /= 10

The method expands easily for integers with a larger range.

Upvotes: 4

S J
S J

Reputation: 3220

You Can Do simply This :

//Shashank Jain
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int num,fdigit;
    cin>>num;
    if(num<0)
        num*=-1;
    int l=log10(num); // l = (length of number -1)

    fdigit=num/pow(10,l);

    cout<<fdigit<<endl;
    return 0;
}

Upvotes: 3

anatolyg
anatolyg

Reputation: 28241

Some processors have instructions that calculate "how big" a number is, very quickly (see http://en.wikipedia.org/wiki/Leading_zero_count). This can be used to quickly choose a power of 10, and divide by it, instead of dividing by 10 repeatedly.

Suppose you are given a function clz that calculates the number of leading zero bits in a number's binary representation (0...32). Then, you can use a lookup table that gives the proper power of 10 for each number of leading zeros.

uint32_t powers_of_10[33] = {
    1000000000, 1000000000,
    100000000, 100000000, 100000000,
    10000000, 10000000, 10000000,
    1000000, 1000000, 1000000, 1000000,
    100000, 100000, 100000,
    10000, 10000, 10000,
    1000, 1000, 1000, 1000,
    100, 100, 100,
    10, 10, 10,
    1, 1, 1, 1, 1
};

int CalcFirstDecimalDigit(uint32_t x)
{
    int leading_zeros = clz(x);
    x /= powers_of_10[leading_zeros];
    if (x >= 10)
        return 1;
    else
        return x;
}

Upvotes: 23

G.w. Weil
G.w. Weil

Reputation: 21

if you number is x9x8x7x6x5x4x3x2x1 then you just divide by 10^8 so you need: The best way to find how many digit number have. You can use Binary search/

Upvotes: -2

Gianluca Ghettini
Gianluca Ghettini

Reputation: 11628

you can do it in O(1) constant time but at expense of a very large memory usage. It's the same old time/memory trade off.

You can create a lookup table of 2^31 entries (signed int), 4 bits per entry (with 4 bits you can encode the first digit 1-9 of the number in decimal representation).

then you can use you int to access the lookup table and get the first digit in O(1). the lookup table will take 2^31 * 4 bits -> 1024 Mbytes

it's the fastest way I can think of...

Upvotes: 3

MrSmith42
MrSmith42

Reputation: 10151

e.g. for in 32 bit unsigned:

Step 1: determine (by binary search) in which of the following intervals the value is: 

0 .. 9
10 .. 99
100 .. 999
1000 .. 9999
10000 .. 99999
100000 .. 999999
1000000 .. 9999999
10000000 .. 99999999
100000000 .. 999999999
1000000000 .. 4294967295

takes max 4 compares

Step 2:

Than calculate the leading digit by one division.

Upvotes: 14

Mats Petersson
Mats Petersson

Reputation: 129344

I'm pretty sure that sprintf (as I assume it is) will be SIGNIFICANTLY slower. You could do some optimization to reduce the number of divide operations (which is one of the slowest instructions on nearly all processors).

So one could do something like this:

 while(n > 10000)
   n /= 1000;

 while(n >= 9)
   n /= 10;

That is, of course, if speed is really important.

Upvotes: 6

TonyK
TonyK

Reputation: 17114

Your first solution (assuming that n is known to be >= 0) is nearly optimal, and I think it could only be substantially improved by using in-line assembly language. But that would only be worthwhile if you were processing millions of such numbers.

Your second solution is -- how can I put this nicely? -- more of a Java-ish approach: Performance? La-di-da, who cares...

Upvotes: 0

Mihai Maruseac
Mihai Maruseac

Reputation: 21435

Your second example should use sprintf. Anyway, it cannot be faster since the entire number is printed, thus all digits are searched.

The linked question/answer uses a property of logarithm: for a number of x digits, it's base 10 logarithm is between x and x+1. But, due to floating point errors this method doesn't really work properly in some cases. Also, take into consideration the fact that doing floating point is slower than doing integer arithmetic.

Thus, the simplest solution is also the faster.

Upvotes: 5

Related Questions