IMO, whoever uses logstar is merely showing off*, because for all intents and purposes you can just use 4 and be done with it. I would be more impressed if the person can use ackermann~^:_1. Still showing off but what a show!
(* e.g. My geewhiz algorithm is not O(n) but almost as good, O(n*logstar n).) On Mon, Jul 7, 2014 at 9:05 AM, Dan Bron <[email protected]> wrote: > I wrote: > > [log*(n)] can be expressed directly in J using agenda (@.): > > > > logstar =: 0:`(1+$:@^.)@.(1<:])"0 > > > > But this feels fairly "procedural". All the work is in the recursion. > > Is there a more elegant way to express it? > > Roger responded: > > In practice log* (at least for base 2) can have only a very few values, > > so something involving I. should work quite well. > > > > f=: 1&<: + (^^:(1 2 3)1)&I. > > This is neat! Thanks for the idea. > > How would you extend it to handle large numbers? For example, Wikipedia > has a table of values up to 2^65536 (that is, 2^2^2^2^2 or ^/5#2), but: > > f 2^65536x > |domain error: f > | f 2^2^16 > > whereas the less-than-satisfying recursive approach can tackle it: > > logstar 2^65536x > 4 > > Anyway, I think what bugs me about logstar, more than anything else, is the > recursion. So I suppose we could stick with a fundamentally iterative > approach, but hide some of the infrastructure by using one of J's more > elegant tools, the adverb ^:a: : > > # <.@^.^:(>&1)^:a: 2^65536x > 5 > > Though because extended integers and floating point values don't mix, I had > to cheat a little and take the floor of the log. I can't imagine a > scenario where this would effect the outcome (unless logstar is later > extended to take one non-integral values, such that log*(5) would be > [infinitesimally] larger than log*(4) ). > > -Dan > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
