Discussion:
fibinocci series
(too old to reply)
shan
2005-10-26 14:49:31 UTC
Permalink
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
Christopher Benson-Manica
2005-10-26 15:02:58 UTC
Permalink
Post by shan
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++.
(I smell a troll or a homework cheater. If you're neither, read the
links below and try again. Otherwise, get lost.)

http://www.ungerhu.com/jxh/clc.welcome.txt
http://www.eskimo.com/~scs/C-faq/top.html
http://benpfaff.org/writings/clc/off-topic.html
--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
Mark McIntyre
2005-10-26 15:27:19 UTC
Permalink
On 26 Oct 2005 07:49:31 -0700, in comp.lang.c , "shan"
Post by shan
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++.
google is your friend...

Though you may want to spell fibonacci properly....!
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Walter Roberson
2005-10-26 15:42:19 UTC
Permalink
Post by shan
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
Jordan Abel
2005-10-26 16:22:27 UTC
Permalink
Post by Walter Roberson
Post by shan
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.
Post by Walter Roberson
What if the user asks for negative 17?
Walter Roberson
2005-10-26 16:26:35 UTC
Permalink
Post by Jordan Abel
Post by Walter Roberson
Post by shan
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
Jordan Abel
2005-10-26 17:00:09 UTC
Permalink
Post by Walter Roberson
Post by Jordan Abel
Post by Walter Roberson
Post by shan
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.
Walter Roberson
2005-10-26 17:21:54 UTC
Permalink
Post by Jordan Abel
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
Jordan Abel
2005-10-26 17:54:23 UTC
Permalink
Post by Walter Roberson
Post by Jordan Abel
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.
Neil Cerutti
2005-10-26 19:11:26 UTC
Permalink
Post by shan
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
Richard Heathfield
2005-10-28 00:12:22 UTC
Permalink
Post by shan
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)
Walter Roberson
2005-10-28 00:30:16 UTC
Permalink
Post by Richard Heathfield
Post by shan
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++.
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
Dave Vandervies
2005-10-28 00:45:13 UTC
Permalink
Post by Walter Roberson
Post by Richard Heathfield
Post by shan
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++.
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 ***@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
Keith Thompson
2005-10-28 02:21:00 UTC
Permalink
Post by Walter Roberson
Post by Richard Heathfield
Post by shan
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++.
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) kst-***@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.
Richard Heathfield
2005-10-28 07:36:14 UTC
Permalink
Post by Keith Thompson
Post by Walter Roberson
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)
Keith Thompson
2005-10-28 07:58:18 UTC
Permalink
Richard Heathfield <***@invalid.invalid> writes:
[...]
Post by Richard Heathfield
--
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) kst-***@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.
Richard Heathfield
2005-10-28 22:55:20 UTC
Permalink
Post by Keith Thompson
[...]
Post by Richard Heathfield
--
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)
Jordan Abel
2005-10-28 04:47:10 UTC
Permalink
Post by Richard Heathfield
Post by shan
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++.
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)
Richard Heathfield
2005-10-28 07:22:50 UTC
Permalink
Post by Jordan Abel
Post by Richard Heathfield
Post by shan
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++.
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 ***@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)
Dik T. Winter
2005-10-28 10:12:16 UTC
Permalink
...
Post by Jordan Abel
Post by Richard Heathfield
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/
Jordan Abel
2005-10-28 10:39:59 UTC
Permalink
Post by Dik T. Winter
...
Post by Jordan Abel
Post by Richard Heathfield
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.
Dik T. Winter
2005-10-28 14:52:36 UTC
Permalink
Post by Jordan Abel
Post by Dik T. Winter
...
Post by Jordan Abel
Post by Richard Heathfield
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/
William Hughes
2005-10-28 16:24:25 UTC
Permalink
Post by Dik T. Winter
Post by Jordan Abel
Post by Dik T. Winter
...
Post by Jordan Abel
Post by Richard Heathfield
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
Dik T. Winter
2005-10-28 23:42:30 UTC
Permalink
...
Post by William Hughes
Post by Dik T. Winter
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/
Richard Bos
2005-10-31 16:36:45 UTC
Permalink
Post by Dik T. Winter
Post by Jordan Abel
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
William Hughes
2005-10-31 17:42:43 UTC
Permalink
Post by Richard Bos
Post by Dik T. Winter
Post by Jordan Abel
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
Post by Richard Bos
Richard
Dik T. Winter
2005-11-01 03:14:20 UTC
Permalink
Post by Richard Bos
Post by Dik T. Winter
Post by Jordan Abel
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.
Indeed, but mine is not. Within the precision provided it is exact. Of
course, when you exceed precision, it will be wrong, but that will be the
same with all integer solutions. Although I would not know with my last
implementation, which is, possibly, the slowest possible implementation.
The only thing it uses is Peano's successor axiom and definitions coming out
of that. It is spectacularly exponential and took about 30 minutes to
calculate fib(32).
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
nelu
2005-10-28 05:02:54 UTC
Permalink
using simple recursion, tail recursion or iterations?
Richard Heathfield
2005-10-28 07:23:25 UTC
Permalink
Post by nelu
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)
Antonio Contreras
2005-10-28 09:33:15 UTC
Permalink
Post by Richard Heathfield
Post by nelu
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>
Zara
2005-10-28 09:58:28 UTC
Permalink
Post by Antonio Contreras
Post by Richard Heathfield
Post by nelu
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>
John Bode
2005-10-28 12:18:24 UTC
Permalink
Post by Antonio Contreras
Post by Richard Heathfield
Post by nelu
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)
Jordan Abel
2005-10-28 12:35:45 UTC
Permalink
Post by John Bode
Post by Antonio Contreras
Post by Richard Heathfield
Post by nelu
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
(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.
John Bode
2005-10-28 15:25:54 UTC
Permalink
Post by Jordan Abel
Post by John Bode
Post by Antonio Contreras
Post by Richard Heathfield
Post by nelu
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>
(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.
Antonio Contreras
2005-10-28 12:39:20 UTC
Permalink
Post by John Bode
Post by Antonio Contreras
Post by Richard Heathfield
Post by nelu
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>
(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
2005-10-28 13:45:07 UTC
Permalink
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
2005-10-28 13:49:52 UTC
Permalink
"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.
Dave Vandervies
2005-10-28 15:14:55 UTC
Permalink
Post by Richard Heathfield
Post by nelu
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 ***@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
nelu
2005-10-28 15:49:37 UTC
Permalink
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
2005-10-28 16:02:45 UTC
Permalink
Post by nelu
I think they were referring to the fact
They who? Please quote context for your postings, as most people do
not use googlegroups.
Post by nelu
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.
Post by nelu
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
nelu
2005-10-28 16:09:37 UTC
Permalink
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.
Post by Walter Roberson
Post by nelu
I think they were referring to the fact
They who? Please quote context for your postings, as most people do
not use googlegroups.
Post by nelu
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.
Post by nelu
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
Keith Thompson
2005-10-28 17:25:26 UTC
Permalink
Post by 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.
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) kst-***@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.
nelu
2005-10-28 18:06:31 UTC
Permalink
Post by Keith Thompson
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.
Post by Keith Thompson
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.
Flash Gordon
2005-10-28 17:45:57 UTC
Permalink
Post by 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.
<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.
Dave Vandervies
2005-10-28 17:19:43 UTC
Permalink
Post by 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.
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.)
Post by nelu
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 ***@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
nelu
2005-10-28 18:03:53 UTC
Permalink
Post by Dave Vandervies
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.
Post by Dave Vandervies
Post by nelu
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 :-) )
Dik T. Winter
2005-10-28 23:45:29 UTC
Permalink
...
Post by nelu
Post by Dave Vandervies
(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/
nelu
2005-10-28 23:58:35 UTC
Permalink
Post by Dik T. Winter
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.
Emmanuel Delahaye
2005-11-01 11:25:18 UTC
Permalink
Post by shan
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++.
In your dreams only. We don't supply code here. We help people to write
their own. BTW if you are that lazy, at least increase your results on
Google by using the correct spelling of 'Fibonacci'
--
C is a sharp tool
Continue reading on narkive:
Loading...