The iterated logarithm (written “log*” and read “log star”) is: “the number of times the logarithm function must be iteratively applied before the result is <= 1”.
Among other things, it’s useful in analyzing the running time of the Find
and Union operations in the union find
datastructure that uses path compression.
Here’s a ruby snippet that computes iterated logarithm values for numbers <= 2^65536 (i.e. 2^(2^16)).
def log_star(x)
return 0 if x <= 0
count = 0
while x >= 1 do
x = Math.log2(x)
count += 1
end
count
end
[0, 1, 2, 3, 4, 15, 16, 65535, 65536, 2**65535, 2**65536].map do |i|
if i <= 65536
"log* #{i}: #{log_star(i)}"
else
"log* 2^#{Math.log2(i).to_i}: #{log_star(i)}"
end
end
.tap do |res|
width = res.map(&:size).max
puts res.map {|x| x.rjust(width)}
end
$ ruby iterated_logarithm.rb
log* 0: 0
log* 1: 1
log* 2: 2
log* 3: 2
log* 4: 3
log* 15: 3
log* 16: 4
log* 65535: 4
log* 65536: 5
log* 2^65535: 5
log* 2^65536: 6