fibinocci series

[Antonio Contreras]

nelu said:


All these are sub-optimal solutions to the Fibonacci problem.

<OT>
Aside of pre-computing all fibonacci numbers up to a certain position
in the series, storing them in a const array and returning the
requested element (which barely deserves the name of algorithm) I know
of no better way to compute Fibonacci numbers than iterating. Do you
happen to know one?
</OT>

 

[Zara]

<OT>
Aside of pre-computing all fibonacci numbers up to a certain position
in the series, storing them in a const array and returning the
requested element (which barely deserves the name of algorithm) I know
of no better way to compute Fibonacci numbers than iterating. Do you
happen to know one?
</OT>

<OT>

Google for "fibonacci algorithm" yields at least this interesting
result:

http://www.ics.uci.edu/~eppstein/161/960109.html

Best regards
</OT>

 

[Dik T. Winter]

> > unsigned long fib(unsigned long n)
> > {
> > return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
> >}

>
> I don't know, but it runs in O(2^n) time. It's hardly the most
> effective way of calculating even one [which can be done in O(N)],

Make that O(1).

 

[Jordan Abel]

unsigned long fib(unsigned long n)
{
return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
}

I don't know, but it runs in O(2^n) time. It's hardly the most
effective way of calculating even one [which can be done in O(N)],

Make that O(1).

Yes, but doing it in O(N) is trivial, and you get O(1) per item for
purposes of the specific problem stated for free.

 

[John Bode]

<OT>
Aside of pre-computing all fibonacci numbers up to a certain position
in the series, storing them in a const array and returning the
requested element (which barely deserves the name of algorithm) I know
of no better way to compute Fibonacci numbers than iterating. Do you
happen to know one?
</OT>

Solve the recurrence relation and use the resulting algebraic formula:

(1 + sqrt(5))^n - (1 - sqrt(5))^n
F[n] = -----------------------------------
2^n * sqrt(5)

 

[Jordan Abel]

<OT>
Aside of pre-computing all fibonacci numbers up to a certain
position in the series, storing them in a const array and
returning the requested element (which barely deserves the name
of algorithm) I know of no better way to compute Fibonacci
numbers than iterating. Do you happen to know one?
</OT>

Solve the recurrence relation and use the resulting algebraic
formula:

(1 + sqrt(5))^n - (1 - sqrt(5))^n
F[n] = -----------------------------------
2^n * sqrt(5)

In the case where you are printing all of F[0]..F[n], though, the
iterative solution [which only uses integer arithmetic] may indeed
be faster though.

 

[Antonio Contreras]

<OT>
Aside of pre-computing all fibonacci numbers up to a certain position
in the series, storing them in a const array and returning the
requested element (which barely deserves the name of algorithm) I know
of no better way to compute Fibonacci numbers than iterating. Do you
happen to know one?
</OT>

Solve the recurrence relation and use the resulting algebraic formula:

(1 + sqrt(5))^n - (1 - sqrt(5))^n
F[n] = -----------------------------------
2^n * sqrt(5)

About 10 min after posting I remembered that you could approximate
Fibonacci number rounding powers of the "golden relation".

But, since this involves floating point numbers and calculating powers
of them, would that be faster than simply iterating?

OTOH in the link provided by Zara showed a method using integer
matrices along with a square and multiply algorithm that seems to be
the best one.

 

[nelu]

I was talking about possible implementations that would help him learn
different methods of solving that problem, not about solving the
algebraic problem and displaying the result of one equation. I thought
he wanted to learn about algorithms. Sorry if I was misunderstood.

 

[nelu]

"series (0 1 1 2 3 5 8 ...)an input is get from user to calculate how
many numbers to be printed.I am using turbo c++."

In fact, both tail recursion and iteration are faster for this purpose
than solving that formula for each of the numbers.

 

[Dik T. Winter]

> > > > unsigned long fib(unsigned long n)
> > > > {
> > > > return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
> > > >}
> > >
> > > I don't know, but it runs in O(2^n) time. It's hardly the most
> > > effective way of calculating even one [which can be done in O(N)],

> >
> > Make that O(1).

>
> Yes, but doing it in O(N) is trivial, and you get O(1) per item for
> purposes of the specific problem stated for free.

No, you get O(1) when you calculate a single fibonacci number the fastest
way: for n >= 0: round(pow((sqrt(5) + 1)/2, n) / sqrt(5))).

 

[Dave Vandervies]

nelu said:


All these are sub-optimal solutions to the Fibonacci problem.

--------
(lambda (n)
(let ((foo (lambda (last-1 last-2 nleft f)
(if (= nleft 0)
last-1
(f (+ last-1 last-2) last-1 (- nleft 1) f)))))
(cond ((not (integer? n)) 'must-be-integer ;not fully general!
(< n 0) 'must-be-nonnegative
(= n 0) 1
(= n 1) 1
#t (f 1 1 (- n 1) f)))))
--------
Tail-recursive, and I'm quite sure it's not suboptimal, at least not as
suboptimal as I think you're claiming.

A few minor changes and it becomes a complete solution to the OP's
problem, just not in the right language:
--------
(lambda (n)
(let ((foo (lambda (last-1 last-2 nleft f)
(if (= nleft 0)
last-1
(begin (print (+ last-1 last-2)) ;ugly!
(newline)
(f (+ last-1 last-2) last-1 (- nleft 1) f))))))
(cond ((not (integer? n)) 'must-be-integer ;not fully general!
(< n 0) 'must-be-nonnegative
(= n 0) (begin (print 1)
(newline)
1)
(= n 1) (begin (print 1)
(newline)
(print 1)
(newline)
1)
#t (begin (print 1)
(newline)
(print 1)
(newline)
(f 1 1 (- n 1) f))))))

 

[John Bode]

Richard Heathfield wrote:
nelu said:

using simple recursion, tail recursion or iterations?

All these are sub-optimal solutions to the Fibonacci problem.

<OT>
Aside of pre-computing all fibonacci numbers up to a certain
position in the series, storing them in a const array and
returning the requested element (which barely deserves the name
of algorithm) I know of no better way to compute Fibonacci
numbers than iterating. Do you happen to know one?
</OT>

Solve the recurrence relation and use the resulting algebraic
formula:

(1 + sqrt(5))^n - (1 - sqrt(5))^n
F[n] = -----------------------------------
2^n * sqrt(5)

In the case where you are printing all of F[0]..F[n], though, the
iterative solution [which only uses integer arithmetic] may indeed
be faster though.

Oh, yeah. I was thinking in terms of computing a single arbitrary
number. If you're going to print out the whole series you might as
well use the iterative method.

 

[nelu]

I think they were referring to the fact that the value of F(n) can be
calculated faster that to calculate all the values between F(0) and
F(n). Unfortunately, that's not what the question was.

I like your lisp code .

 

[Walter Roberson]

I think they were referring to the fact

They who? Please quote context for your postings, as most people do
not use googlegroups.

that the value of F(n) can be
calculated faster that to calculate all the values between F(0) and
F(n). Unfortunately, that's not what the question was.

When your posting is taken by itself, without context, F(n) has no meaning.

I like your lisp code .

I didn't post any lisp code... but you failed to quote or attribute
to anyone so we don't know who "your" is in this sentance.

 

[nelu]

Sorry, I wasn't paying attention to the fact that the Reply link on
Google Groups does not work as I thought it would. The reply was meant
for Dave Vandervies. I will pay more attention in the future. Thanks
for the heads up.

 

[William Hughes]

...
unsigned long fib(unsigned long n)
{
return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
}

I don't know, but it runs in O(2^n) time. It's hardly the most
effective way of calculating even one [which can be done in O(N)],

Make that O(1).

Yes, but doing it in O(N) is trivial, and you get O(1) per item for
purposes of the specific problem stated for free.

No, you get O(1) when you calculate a single fibonacci number the fastest
way: for n >= 0: round(pow((sqrt(5) + 1)/2, n) / sqrt(5))).

Yes, but this only works for small values of n

-William Hughes

 

[Dave Vandervies]

I think they were referring to the fact that the value of F(n) can be
calculated faster that to calculate all the values between F(0) and
F(n). Unfortunately, that's not what the question was.

Yep. And it's Rather Less Suboptimal to adapt an iterative or tail-
recursive single-value calculation to print all the preceding values as
well than to do the same with a closed-form calculation.

(I'd actually thought RH was referring to the suboptimality of an
iterative or recursive solution that only passes around one value at
a time. That would have been Rather Suboptimal.)

I like your lisp code .

It wasn't lisp. Well, it might have been lisp, but it wasn't Lisp.
(At least, I don't think so.) If I'm not mistaken, Common Lisp puts
functions and ordinary values in different namespaces and gives you a hoop
to jump through to call a function through an ordinary name (as opposed
to through a name used to define a function), which Scheme doesn't.

For bonus points, what was the bug? (It's a fairly simple one, you
should be able to find it by careful inspection even if you don't know
the language, and it'll show up pretty obviously if you try to run it.)


dave
(you really thought I'd post a bug-free homework solution, even in the
wrong language?)

 

[Keith Thompson]

Sorry, I wasn't paying attention to the fact that the Reply link on
Google Groups does not work as I thought it would. The reply was meant
for Dave Vandervies. I will pay more attention in the future. Thanks
for the heads up.

Right. Here's how to do it correctly:

If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers.

And please don't top-post. Your response goes below, or interspersed
with, any quoted text, which should be trimmed to what's relevant.

 

[Flash Gordon]

Sorry, I wasn't paying attention to the fact that the Reply link on
Google Groups does not work as I thought it would. The reply was meant
for Dave Vandervies. I will pay more attention in the future. Thanks
for the heads up.

Walter Roberson wrote:

<snip>

Please post your reply *after* the text you are replying to, or
interspersed with it, after snipping the parts not relevant to your reply.

Also, please complain to Google for the most obvious reply button not
doing the right thing. Possibly if enough people complain they will fix it.

 

[nelu]

Yep. And it's Rather Less Suboptimal to adapt an iterative or tail-
recursive single-value calculation to print all the preceding values as
well than to do the same with a closed-form calculation.

(I'd actually thought RH was referring to the suboptimality of an
iterative or recursive solution that only passes around one value at
a time. That would have been Rather Suboptimal.)

I also thought that what he wanted to know was how to implement the
formula rather than how to optimize the calculation by simplifying it.
That was my assumption, the original problem doesn't say that.

It wasn't lisp. Well, it might have been lisp, but it wasn't Lisp.

It was just a joke related to the name of the group and the code you
posted. I didn't take a good look at the code. Yes, it doesn't look
like common lisp, you could've used defun, otherwise (just joking,
again )