0

While comparing stupendously large numbers it can be useful to take a logarithm, or even iterations of logarithms, of the number to reduce its to 'human-sized scale'. In the context of computer programming some languages, such as Python, will default to having arbitrary integer sizes but not arbitrary floating point precision. Sometimes the default float precision prohibits the casting of a sufficiently-large integer to float, which happens with most implementations of logarithmic functions.

While listening to Diggy Diggy Hole, I was inspired to define the following iterative function:

def dig(n):
    count = 0

while len(str(n)) > 1:
    n = len(str(n))
    count += 1

return count

This function easily avoids casting to floats and still induces a partial order on the size of integers. By default I am assuming base 10 in dig, but the general idea should apply to different bases if it is desired.

I'm very doubtful that I'm the first person to think of this function, but the appropriate search engine terms are evading me. What is this function conventionally called?

Galen
  • 1,828

1 Answers1

0

This is called an iterated logarithm, commonly notated $\log^*(n)$. Based on the notation, it's sometimes pronounced "log-star".

Troposphere
  • 7,158
  • That is really close to what I'm talking about, however the iterative logarithm of an integer doesn't always return an integer as Dig(n) does. – Galen Jun 09 '21 at 14:56
  • @Galen: The output of $\log^*(n)$ is always an integer. In the definition shown by Wikipedia it doesn't round intermediate results to integers like yours does, but that doesn't actually affect what the result (i.e. the number of iterations) ends up being. – Troposphere Jun 09 '21 at 15:16
  • 1
    Depending on how you set up the exact stop condition, it might be that $\log^*(n)$ returns $1$ more than your function does, or it might differ by $1$ at input values that are exact power towers of your base -- such minor distinctions won't generally be interpreted to make it less worthy of the name "iterated logarithm", though. – Troposphere Jun 09 '21 at 15:19