CODEWITHSUNDEEP
algorithmmathtime-complexitylogarithmcoding-efficiency
Aryaman
Aryaman

Reputation: 65

Does taking logrithm in a program taxes the computer?

No of digits can be calculated by a loop as well as taking log10. So which one is more efficient? Taking log is just one line statement but what happens internally can be more costly that a simple loop. In another case which is more efficient an n^2 algo with log or an n^2 algo without log using some more space complexity?

In more general sense , I want to ask that is taking log same as simple arithmetic operators that we do like (int a + int b) or the computer has to go some rigorous procedure within?

Upvotes: 2

Views: 135

Answers (2)

chux
chux

Reputation: 153517

To find the number of decimal digits of an integer repeatedly divide by 10.

The following approach works well for all integer types of various widths, negative numbers, zero and min/max of the type.

// Pseudo code
number_of_digits = 0
do  
  number_of_digits++
  n = n / 10
while n != 0

As OP is looking for a faster approach, consider profiling the performance against the above to find if the alternative (and likely more complex or fails for some integers) is worth the effort.

If you do not mind some complexity:

For signed integer types, using the negative absolute value, code avoid the usual problems with negating the minimum integer value.

Otherwise adjust for unsigned types.

// Pseudo code
count = 0
neg_abs = n < 0 ? n : -n
if (neg_abs <= -10**16) count += 16; neg_abs += 10**16
if (neg_abs <= -10**8)  count += 8;  neg_abs += 10**8
if (neg_abs <= -10000)  count += 4;  neg_abs += 10000
if (neg_abs <= -100)    count += 2;  neg_abs += 100
if (neg_abs <= -10)     count += 1;

Upvotes: 1

maraca
maraca

Reputation: 8743

This answer is only dealing with non-negative numbers, but it should be easy to make it work for negative numbers too. It also assumes 64 bit numbers are used.

I would never use log10 to calculate the number of digits. Because of the following reasons:

  • 0 is a one digit number and will fail using log10
  • log10 can also fail and give wrong results due to precision, e.g. in Java Math.log10(999999999999999999L) gives 18.0 instead of 17.999...something
  • log10 is usually calculated using taylor series and the result is a double, that's why we lose precision and floating point operations are more expensive than integer operations

If you want a one-liner, I would go with the simple: ("" + number).length()

You could repeatedly divide the number by 10 to get the result, but @YvesDaoust pointed out that multiplication is much faster.

Here would be a simple implementation:

// Java implementation, the highest long is about 9.2e18, so 19 digits
public int countDigits(long number) {
    if (number >= 1000000000000000000L) // otherwise n would overflow
        return 19;
    int count = 1;
    for (long n = 10;; n *= 10) {
        if (number < n)
            return count;
        count++;
    }
}

But if the expected numbers are evenly distributed, then we would have to check the most digits first and go backwards. This is because there are 10 numbers with 1 digit, 90 numbers with 2 digits, 900 with 3, 9000 with 4 and so on.

We can also precalculate the numbers. This would give something like this:

private static final long[] digitCount = new long[18];
static {
    digitCount[0] = 10;
    for (int i = 1; i < 18; i++) {
        digitCount[i] = digitCount[i - 1] * 10;
    }
}

public int countDigits(long number) {
    for (int i = 17; i >= 0; i--) {
        if (number >= digitCount[i])
            return i + 2;
    }
    return 1;
}

Upvotes: 1

Related Questions