Should use closed-form fibonacci function #1

Closed
isaacs opened this Issue Oct 3, 2011 · 14 comments

Projects

None yet

6 participants

@isaacs
isaacs commented Oct 3, 2011

It would be much more performant to calculate the fibonacci number like so:

function fib (n) {
  var a=1
    , b=0
  while (0 > n--) {
    var c = b
    b = b + a
    a = c
  }
  return b
}

Perhaps it might make sense to add this as a separate endpoint?

@glenjamin
Owner

I've now implemented this as in #7 - which keeps the recursive step - thus making it easier to work in releasing the loop periodically.

@glenjamin glenjamin closed this Oct 4, 2011
@jkff
jkff commented Oct 4, 2011

Actually there's a logarithmic-time algorithm, guys... Google it.

@isaacs
isaacs commented Oct 4, 2011

@jkff GIST OR GTFO.

@bcjordan
bcjordan commented Oct 4, 2011
while (0 > n--) {

Should be < instead of >.

@isaacs
isaacs commented Oct 4, 2011

True that. need tdd on this thing.

@leonth
leonth commented Oct 4, 2011

Seriously guys, it's O(1).

var PHI = (1 + Math.sqrt(5)) / 2;
function fib(n) {
    return Math.round(Math.pow(PHI, n) / Math.sqrt(5));
}
@glenjamin
Owner

See issue #4

On 4 Oct 2011, at 18:34, leonth
reply@reply.github.com
wrote:

Seriously guys, it's O(1).

var PHI = (1 + Math.sqrt(5)) / 2;
function fib(n) {
   return Math.round(Math.pow(PHI, n) / Math.sqrt(5));
}

Reply to this email directly or view it on GitHub:
#1 (comment)

@jkff
jkff commented Oct 4, 2011

@leonth For which range of inputs does it give an exact answer?

@leonth
leonth commented Oct 4, 2011

Okay, my bad...

@ghost
ghost commented Oct 5, 2011

@leonth I'm not sure about this, but I don't think that Math.pow is O(1). The compiler could do some extremely aggressive optimization by precomputing various powers of the known base, but this is a bit much to expect. I'd call it O(lg(n))

@bdonlan
bdonlan commented Oct 5, 2011

O(lg(n)) at a minimum is required for exact output - as you're producing an output string of O(n) bits. I don't know offhand what the complexity of exact (arbitrary-precision with irrationals) pow/round would be - probably something quite large; certainly larger than the O(n lg n) solution adding arbitrary-precision integers. However, if you're using doubles (possibly a bad idea; after n> 50something you'll start rounding) it will be O(1); it'll be essentially doing modular exponentiation with a fixed modulus.

@ghost
ghost commented Oct 6, 2011

@bdonlan How do you do modular exponentiation in constant time? Exponentiation by squaring is lg(n)

@bdonlan
bdonlan commented Oct 12, 2011

@bpgordon doubles have fixed maximum range; therefore n is a constant, so O(1). At the silicon level we're talking about a fixed upper bound on how many cycles any operation with a double will take. Hence my comments on exact output; doubles won't work for very high parameters.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment