1

What is the time complexity of log10 function in cmath ? Its nowhere mentioned on the internet. Does anyone know for sure ?

Later edit: My initial question was if the following code is faster.

int numOfDigits(int n) {
  return (int)log10(n) + 1;
}

than this 

int numOfDigits(int n) {
  int count = 0;
  while(n) {
    count ++;
    n /= 10;
  }
  return 0;
}

i know for sure that the second function time complexity is O(log(n)). What's the time complexity of the first function.

royer
  • 35
  • 1
  • 7
  • 2
    I expect in a typical implementation it is bounded by a constant time, barring external factors such as cache conflicts. The overall algorithm is to separate the exponent and significand of the floating-point operand, multiply the exponent by a conversion factor, evaluate a fixed (and highly engineered) polynomial to get the log of the significand, and add them. – Eric Postpischil May 17 '20 at 20:34
  • 2
    That's probably because there is no requirement imposed by standard, so it's entirely up to implementation. – Yksisarvinen May 17 '20 at 20:35
  • 1
    Does this answer your question? [What is the complexity of the log function?](https://stackoverflow.com/questions/7317414/what-is-the-complexity-of-the-log-function) – Nelewout May 17 '20 at 20:35
  • I read that post but it doesnt answer my question. I wanted something more exact so to speak. – royer May 17 '20 at 20:36
  • Is it ok to assume that its takes O(1) time ? – royer May 17 '20 at 20:37
  • @michael_blaze You can dig up implementations used by your (or other major) compilers, and analyze the complexity of the code. – HolyBlackCat May 17 '20 at 20:50
  • @michael_blaze: We cannot tell you if it is okay to assume because you have not specified what is at stake or what C++ implementation you are using. If you want your program to perform pleasantly, sure it is okay to assume. If you want to guarantee real-time control of life-critical machinery, it is not okay to assume. – Eric Postpischil May 17 '20 at 23:23
  • @Eric Postpischil to be honest i feel like i made this question sound really important )). Well its "nothing at stake".I just asked this question out of curiosity because one of friends wanted a faster way to get the number of digits and i came up with "log10" approuch. – royer May 18 '20 at 09:37

1 Answers1

2

The standard does not specify complexity requirement for the log10 function.

However, I would expect a reasonable implementation to have constant complexity.

eerorika
  • 232,697
  • 12
  • 197
  • 326