fibinocci series

In article <11**********************@z14g2000cwz.googlegroups .com>,
shan <sr**********@gmail.com> wrote:

I am a begginer in C.can anybody give the complete code for fibinocci
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++.

What if the user asks for ten billion? What if the user asks
for so many that the number does not fit within an integer?
What if the user asks for negative 17?
--
Many food scientists have reported chocolate to be the single most
craved food. -- Northwestern University, 2001

Nov 15 '05 #4

On 2005-10-26, Walter Roberson <ro******@ibd.nrc-cnrc.gc.ca> wrote:

In article <11**********************@z14g2000cwz.googlegroups .com>,
shan <sr**********@gmail.com> wrote:
I am a begginer in C.can anybody give the complete code for fibinocci
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++.
What if the user asks for ten billion? What if the user asks
for so many that the number does not fit within an integer?

Such as, say, ten billion? (on many systems in use today, that won't
even fit in an unsigned long)

and of course the series itself will overflow long before you get to
that many.
What if the user asks for negative 17?

Nov 15 '05 #5

In article <sl********************@random.yi.org>,
Jordan Abel <jm****@purdue.edu> wrote:

On 2005-10-26, Walter Roberson <ro******@ibd.nrc-cnrc.gc.ca> wrote:
In article <11**********************@z14g2000cwz.googlegroups .com>,
shan <sr**********@gmail.com> wrote:
I am a begginer in C.can anybody give the complete code for fibinocci
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++.
What if the user asks for ten billion? What if the user asks
for so many that the number does not fit within an integer?
and of course the series itself will overflow long before you get to
that many.

Well, since the OP asked for "complete" code, I kind of assumed that
the OP would need the indefinite-precision libraries to go along with
everything else...
--
Is there any thing whereof it may be said, See, this is new? It hath
been already of old time, which was before us. -- Ecclesiastes

Nov 15 '05 #6

On 2005-10-26, Walter Roberson <ro******@ibd.nrc-cnrc.gc.ca> wrote:

In article <sl********************@random.yi.org>,
Jordan Abel <jm****@purdue.edu> wrote:
On 2005-10-26, Walter Roberson <ro******@ibd.nrc-cnrc.gc.ca> wrote:
In article <11**********************@z14g2000cwz.googlegroups .com>,
shan <sr**********@gmail.com> wrote:
I am a begginer in C.can anybody give the complete code for fibinocci
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++. What if the user asks for ten billion? What if the user asks
for so many that the number does not fit within an integer?

and of course the series itself will overflow long before you get to
that many.

Well, since the OP asked for "complete" code, I kind of assumed that
the OP would need the indefinite-precision libraries to go along with
everything else...

indefinite-precision, you say?

doubt it'll work on his "turbo c++", but...

system("dc -e '?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1-sclc0<L]sLlLx'");

....what? what's everyone looking at?

--
I'm ashamed to admit i wrote that by hand.

Nov 15 '05 #7

In article <sl********************@random.yi.org>,
Jordan Abel <jm****@purdue.edu> wrote:

indefinite-precision, you say? doubt it'll work on his "turbo c++", but... system("dc -e '?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1-sclc0<L]sLlLx'"); ...what? what's everyone looking at?

$ dc -e '?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1-sclc0<L]sLlLx'
Usage: dc [OPTION] [file ...]
--help display this help and exit
--version output version information and exit
$ dc
?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1-sclc0<L]sLlLx
dc: stack empty
1
dc: register 'c' (0143) is empty
dc: stack empty
1

--
I was very young in those days, but I was also rather dim.
-- Christopher Priest

Nov 15 '05 #8

On 2005-10-26, Walter Roberson <ro******@ibd.nrc-cnrc.gc.ca> wrote:

In article <sl********************@random.yi.org>,
Jordan Abel <jm****@purdue.edu> wrote:
indefinite-precision, you say?

doubt it'll work on his "turbo c++", but...

system("dc -e '?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1-sclc0<L]sLlLx'");

...what? what's everyone looking at?

$ dc -e '?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1-sclc0<L]sLlLx'
Usage: dc [OPTION] [file ...]
--help display this help and exit
--version output version information and exit
$ dc
?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1-sclc0<L]sLlLx
dc: stack empty
1
dc: register 'c' (0143) is empty
dc: stack empty
1

meh

well, this won't let the user input 10 billion, but...

prompt for your input;
FILE *fp = popen("dc","w");
fprintf(fp,"%dsc1sx1sy[lxlyplx+sxsy]sI[lIxlc1-sclc0<L]sLlLx",n);
pclose(fp);

....your dc has gnu options but no ? or -e? - how about the output of
that "version information?

or maybe not, since now we're firmly into off-topic territory.

Nov 15 '05 #9

Neil Cerutti

On 2005-10-26, shan <sr**********@gmail.com> wrote:

Hi to every body,
I am a begginer in C.can anybody give the complete code for
fibinocci 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++.

thank U in advance

You're welcome in advance.

--
Neil Cerutti

Nov 15 '05 #10

shan said:

Hi to every body,
I am a begginer in C.can anybody give the complete code for fibinocci
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++.

Assuming you mean Fibonacci, see if you can work out why I posted this code:

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

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/2005
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Nov 15 '05 #11

In article <dj*********@nwrdmz01.dmz.ncs.ea.ibs-infra.bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

shan said:
I am a begginer in C.can anybody give the complete code for fibinocci
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++.

Assuming you mean Fibonacci, see if you can work out why I posted this code: unsigned long fib(unsigned long n)
{
return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
}

Ah, but that doesn't meet the requested criteria of printing the first
n elements of the series.
--
All is vanity. -- Ecclesiastes

Nov 15 '05 #12

Dave Vandervies

In article <dj**********@canopus.cc.umanitoba.ca>,
Walter Roberson <ro******@ibd.nrc-cnrc.gc.ca> wrote:

In article <dj*********@nwrdmz01.dmz.ncs.ea.ibs-infra.bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:
shan said:

I am a begginer in C.can anybody give the complete code for fibinocci
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++.

Assuming you mean Fibonacci, see if you can work out why I posted this code:

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

Ah, but that doesn't meet the requested criteria of printing the first
n elements of the series.

Just call it in a loop.
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca
However, I'd have to admit that the best fix [is] to find the code's author
and encourage him or her to consider a career change. Bungee jumping in
active volcanoes, for preference. --Eric Sosman in comp.lang.c

Nov 15 '05 #13

Keith Thompson

ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes:

In article <dj*********@nwrdmz01.dmz.ncs.ea.ibs-infra.bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:
shan said:

I am a begginer in C.can anybody give the complete code for fibinocci
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++.

Assuming you mean Fibonacci, see if you can work out why I posted this code:

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

Ah, but that doesn't meet the requested criteria of printing the first
n elements of the series.

No. Why should it?

The OP asked for complete code; Richard chose (wisely, IMHO) not to
provide it.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Nov 15 '05 #14

On 2005-10-28, Richard Heathfield <in*****@invalid.invalid> wrote:

shan said:
Hi to every body,
I am a begginer in C.can anybody give the complete code for
fibinocci 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++.

Assuming you mean Fibonacci, see if you can work out why I posted
this code:

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)],
let alone all from 0..some amount, which can be done in O(1) per
number for a total of O(N)

Nov 15 '05 #15

nelu

using simple recursion, tail recursion or iterations?

Nov 15 '05 #16

Jordan Abel said:

On 2005-10-28, Richard Heathfield <in*****@invalid.invalid> wrote:
shan said:
Hi to every body,
I am a begginer in C.can anybody give the complete code for
fibinocci 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++.

Assuming you mean Fibonacci, see if you can work out why I posted
this code:

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.

I did indeed say "you"; I guess I should have been more specific.
I meant "you, shan, the chap or chapette with the ostensible
email address sr**********@gmail.com".

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/2005
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Nov 15 '05 #17

nelu said:

using simple recursion, tail recursion or iterations?

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

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/2005
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Nov 15 '05 #18

Keith Thompson said:

ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes:

Ah, but that doesn't meet the requested criteria of printing the first
n elements of the series.

No. Why should it?

The OP asked for complete code; Richard chose (wisely, IMHO) not to
provide it.

Thanks, Keith. It was indeed a choice. In fact, I started out to write a
complete "solution" containing several - um - object lessons, but then I
decided I was hungry. Or something.

I have, in the past, provided very long complete solutions, and have
discovered that they are simply not appreciated by those for whom they were
written, so I stopped bothering. My best-remembered example actually comes
from comp.programming, in which I spent my entire lunch break working on a
solution to a question, and then knocked off early from work so that I
could finish off the solution and post it reasonably promptly. The
resulting article was around 350 lines long, and contained not only a full
analysis of the problem but a complete solution to it in ISO C. The OP
never replied.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/2005
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Nov 15 '05 #19

Keith Thompson

Richard Heathfield <in*****@invalid.invalid> writes:
[...]

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/2005
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

<OT>
Sorry to quote just the sig, but I noticed you've changed the date on
the dmr quotation (it used to be "29 July 1999"). Do I sense another
anecdote, or is it just a glitch?
</OT>

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Nov 15 '05 #20

Antonio Contreras

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>

Nov 15 '05 #21

Zara

On 28 Oct 2005 02:33:15 -0700, "Antonio Contreras" <an*****@gmail.com>
wrote:

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>

<OT>

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

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

Best regards
</OT>

Nov 15 '05 #22

In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes:

On 2005-10-28, Richard Heathfield <in*****@invalid.invalid> wrote:

....

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).
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Nov 15 '05 #23

On 2005-10-28, Dik T. Winter <Di********@cwi.nl> wrote:

In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes:
> On 2005-10-28, Richard Heathfield <in*****@invalid.invalid> wrote:

...
> > 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.

Nov 15 '05 #24

John Bode

Antonio Contreras wrote:

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)

Nov 15 '05 #25

On 2005-10-28, John Bode <jo*******@my-deja.com> wrote:

Antonio Contreras wrote:
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.

Nov 15 '05 #26

Antonio Contreras

John Bode wrote:

Antonio Contreras wrote:
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)

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.

Nov 15 '05 #27

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.

Nov 15 '05 #28

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.

Nov 15 '05 #29

In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes:

On 2005-10-28, Dik T. Winter <Di********@cwi.nl> wrote:
In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes:
> On 2005-10-28, Richard Heathfield <in*****@invalid.invalid> wrote:

...
> > 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))).
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Nov 15 '05 #30

Dave Vandervies

In article <dj**********@nwrdmz03.dmz.ncs.ea.ibs-infra.bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

nelu said:
using simple recursion, tail recursion or iterations?

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))))))
--------

dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca
Since we like to argue a lot on comp.lang.c figuring out who said what
and when is very important, so we can properly scoff at the right person.
--Daniel Fox in comp.lang.c

Nov 15 '05 #31

John Bode

Jordan Abel wrote:

On 2005-10-28, John Bode <jo*******@my-deja.com> wrote:

Antonio Contreras wrote:
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.

Nov 15 '05 #32

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 :-).

Nov 15 '05 #33

In article <11*********************@g43g2000cwa.googlegroups. com>,
nelu <ta********@gmail.com> wrote:

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.

--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers

Nov 15 '05 #34

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.

Walter Roberson wrote:

In article <11*********************@g43g2000cwa.googlegroups. com>,
nelu <ta********@gmail.com> wrote:
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.

--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers

Nov 15 '05 #35

William Hughes

Dik T. Winter wrote:

In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes:
> On 2005-10-28, Dik T. Winter <Di********@cwi.nl> wrote:
> > In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes:
> > > On 2005-10-28, Richard Heathfield <in*****@invalid.invalid> wrote:
> > ...
> > > > 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

Nov 15 '05 #36

Dave Vandervies

In article <11*********************@g43g2000cwa.googlegroups. com>,
nelu <ta********@gmail.com> wrote:

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?)

--
Dave Vandervies dj******@csclub.uwaterloo.ca
Since we like to argue a lot on comp.lang.c figuring out who said what
and when is very important, so we can properly scoff at the right person.
--Daniel Fox in comp.lang.c

Nov 15 '05 #37

Keith Thompson

"nelu" <ta********@gmail.com> writes:

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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Nov 15 '05 #38

nelu

Dave Vandervies wrote:

In article <11*********************@g43g2000cwa.googlegroups. com>,
nelu <ta********@gmail.com> wrote:
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.

I like your lisp code :-).

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 :-) )

Nov 15 '05 #39

Flash Gordon

nelu wrote:

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.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

Nov 15 '05 #40

nelu

> 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. I found it a little too late.

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

Thanks. It was rude of me to top post.

Nov 15 '05 #41

Keith Thompson said:

Richard Heathfield <in*****@invalid.invalid> writes:
[...]
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/2005
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

<OT>
Sorry to quote just the sig, but I noticed you've changed the date on
the dmr quotation (it used to be "29 July 1999"). Do I sense another
anecdote, or is it just a glitch?

Glitch. Fixed. Thanks.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Nov 15 '05 #42

In article <11**********************@g49g2000cwa.googlegroups .com> "William Hughes" <wp*******@hotmail.com> writes:

Dik T. Winter wrote:

....

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 :)

Indeed, for larger values it will be an approximation.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Nov 15 '05 #43

In article <11**********************@g14g2000cwa.googlegroups .com> "nelu" <ta********@gmail.com> writes:

Dave Vandervies wrote:

....

(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.

I think RH is pretty well able to implement a much more efficient solution
than the one he gave, without help from others. There was a purpose in
his posting a suboptimal solution.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Nov 15 '05 #44

nelu

> I think RH is pretty well able to implement a much more efficient solution

than the one he gave, without help from others. There was a purpose in
his posting a suboptimal solution.

I'm sure you're right, however, the post was not meant to be mean.

Nov 15 '05 #45

Richard Bos

"Dik T. Winter" <Di********@cwi.nl> wrote:

In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes:
> 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))).

I do not think the OP's teacher would be happy with a mere
approximation.

Richard

Nov 15 '05 #46

William Hughes

Richard Bos wrote:

"Dik T. Winter" <Di********@cwi.nl> wrote:
In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes:
> 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))).

I do not think the OP's teacher would be happy with a mere
approximation.

Don't ignore the round. For small enough n, (those
for which the correct answer fits exactly in the type used
to hold it) this gives exact answers. For larger n, we can use a
floating point number to hold an approximation. However, for
large enough n, the answer overflows the any floating point type.
Here we have to use arbitrary precision, and the algorithm becomes
O(log(n)).

-William Hughes
Richard

Nov 15 '05 #47