Talk:Iterated logarithm

Latest comment: 9 years ago by Skytopia in topic Iterative function as well as recursive?

Iterated log vs Ackermann

edit

"The disjoint set data structure's union and find operations" is given as an example algorithm using iterated log complexity, but Disjoint_set_data_structure mentions the (better) inverse Ackermann bound. -- hagman --195.227.74.194 10:11, 15 November 2006 (UTC)Reply

Yes, there's an old version that has iterated log complexity. I can't recall its name off the top of my head. CRGreathouse (t | c) 17:44, 15 November 2006 (UTC)Reply

Vs. "Law of"

edit

Do Iterated logarithm and Law of the iterated logarithm have something in common despite the name? --Abdull 13:31, 3 March 2006 (UTC)Reply

Figure 1

edit

It would be nice if Figure 1 illustrated the line segments shown with arrowheads 12.208.40.109 16:53, 30 May 2006 (UTC)Reply

I have corrected the caption on this diagram. The values on the y axis reveal that the graph is showing the natural logarithm of x, and thus calculating log*x, while the caption claimed to be calculating lg*x. It's still confusing, since the diagram is only referred to during the discussion of lg*x, but I think that's a lot better than having a clearly erroneous caption. --Weeble (talk) 15:40, 26 November 2007 (UTC)Reply

I can fix this. Dcoetzee 23:52, 26 November 2007 (UTC)Reply

Reference?

edit

I haven't finished reading it yet, but there's a mention of the iterated logarithm in Sublogarithmic Ambiguity that may be of use in the article. CRGreathouse (t | c) 07:19, 26 September 2006 (UTC)Reply

Another: Dr. Jamie Andrews suggests the possibility of an   algorithm for an NP-complete problem (rendiring P =? NP moot). [1] CRGreathouse (t | c) 05:10, 28 September 2006 (UTC)Reply

I read that paper, and the   bit was a joke. I don't mean "a joke" in the sense of "not adequately demonstrated" but rather "accompanied by a smiley and meant to be amusing." 74.74.206.149 (talk) 13:25, 6 February 2008 (UTC)Reply
Agreed, it was just making a point. CRGreathouse (t | c) 18:45, 6 February 2008 (UTC)Reply
Another: [2] CRGreathouse (t | c) 02:35, 14 August 2010 (UTC)Reply

Symmetric level-index arithmetic

edit

Is the log*n function the same as the   function described in Symmetric level-index arithmetic? Do the different names for the function (generalized logarithm vs. iterated logarithm) just come from the fact that they arose in different branches of math? --Rpresser 22:04, 10 March 2008 (UTC)Reply

They're almost the same:  , provided x ≥ 0. CRGreathouse (t | c) 22:57, 10 March 2008 (UTC)Reply

HTML log-star

edit

See Talk:Time complexity#HTML log-star for a discussion regarding how to write log* in Wikipedia. As a result of the discussion, I created the simple templates {{log-star}} and {{lg-star}} and edited this article as well. — Miym (talk) 21:20, 15 January 2010 (UTC)Reply

log* n

edit

Should be redirected here. —Preceding unsigned comment added by 193.126.183.46 (talk) 15:30, 22 June 2010 (UTC)Reply

But why? Does any article link to it? In any case, done. log* already redirected here since a long time ago. Shreevatsa (talk) 16:04, 22 June 2010 (UTC)Reply

Explanation of "well-defined" statement

edit

Quoting from the lead:

Mathematically, the iterated logarithm is well-defined not only for base 2 and base e, but for any base greater than  .

I'm a little rusty right now, so i couldn't readily explain to myself why would lower values not generate a sequence { } that grows up to infinity... It's obviously monotonically increasing, but i just don't see the reason why it would have a finite bound. Can anyone provide a hint? -- Jokes Free4Me (talk) 17:12, 12 July 2013 (UTC)Reply

Complexity of Fürer's algorithm

edit

I think the complexity of Fürer's algorithm is   (see Fürer's_algorithm), and not, as mentioned here, O(n log n 2lg* n). These bounds are different, because there is a "better" algorithm with complexity   (see also Fürer's_algorithm), which is even worse than O(n log n 2lg* n). So I think this must be corrected here.

Yes, changing expressions of the form aO(b) to O(ab) is a frequent mistake. I've fixed this one. Thanks for catching it. —David Eppstein (talk) 18:40, 21 December 2014 (UTC)Reply

Iterative function as well as recursive?

edit

The mathematical definition given is recursive. The very term has the word 'iterated' in it, and the iterative version is indeed simpler to understand. Should we give that as well? Here's some pseudo code of the function:

int iteratedLog (float n, float b) {
count = 0;
while (n >= 1.0) {
n = LogBase b (n);
count = count+1;
}
return count;
}

--Skytopia (talk) 11:57, 10 May 2015 (UTC)Reply