P: n/a

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  
Share this Question
P: n/a

On 26 Oct 2005 07:49:31 0700, in comp.lang.c , "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++.
google is your friend...
Though you may want to spell fibonacci properly....!

Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/Cfaq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
== Posted via Newsfeeds.Com  UnlimitedUncensoredSecure Usenet News== http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
= East and WestCoast Server Farms  Total Privacy via Encryption =  
P: n/a

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  
P: n/a

On 20051026, Walter Roberson <ro******@ibd.nrccnrc.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?  
P: n/a

In article <sl********************@random.yi.org>,
Jordan Abel <jm****@purdue.edu> wrote: On 20051026, Walter Roberson <ro******@ibd.nrccnrc.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 indefiniteprecision 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  
P: n/a

On 20051026, Walter Roberson <ro******@ibd.nrccnrc.gc.ca> wrote: In article <sl********************@random.yi.org>, Jordan Abel <jm****@purdue.edu> wrote:On 20051026, Walter Roberson <ro******@ibd.nrccnrc.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 indefiniteprecision libraries to go along with everything else...
indefiniteprecision, you say?
doubt it'll work on his "turbo c++", but...
system("dc e '?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1sclc0<L]sLlLx'");
....what? what's everyone looking at?

I'm ashamed to admit i wrote that by hand.  
P: n/a

In article <sl********************@random.yi.org>,
Jordan Abel <jm****@purdue.edu> wrote: indefiniteprecision, you say?
doubt it'll work on his "turbo c++", but...
system("dc e '?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1sclc0<L]sLlLx'");
...what? what's everyone looking at?
$ dc e '?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1sclc0<L]sLlLx'
Usage: dc [OPTION] [file ...]
help display this help and exit
version output version information and exit
$ dc
?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1sclc0<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  
P: n/a

On 20051026, Walter Roberson <ro******@ibd.nrccnrc.gc.ca> wrote: In article <sl********************@random.yi.org>, Jordan Abel <jm****@purdue.edu> wrote:indefiniteprecision, you say?
doubt it'll work on his "turbo c++", but...
system("dc e '?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1sclc0<L]sLlLx'");
...what? what's everyone looking at?
$ dc e '?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1sclc0<L]sLlLx' Usage: dc [OPTION] [file ...] help display this help and exit version output version information and exit $ dc ?sc1sx1sy[lxlyplx+sxsy]sI[lIxlc1sclc0<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[lIxlc1sclc0<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 offtopic territory.  
P: n/a

On 20051026, 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  
P: n/a

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)  
P: n/a

In article <dj*********@nwrdmz01.dmz.ncs.ea.ibsinfra.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  
P: n/a

In article <dj**********@canopus.cc.umanitoba.ca>,
Walter Roberson <ro******@ibd.nrccnrc.gc.ca> wrote: In article <dj*********@nwrdmz01.dmz.ncs.ea.ibsinfra.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  
P: n/a
 ro******@ibd.nrccnrc.gc.ca (Walter Roberson) writes: In article <dj*********@nwrdmz01.dmz.ncs.ea.ibsinfra.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.  
P: n/a

On 20051028, 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)  
P: n/a

using simple recursion, tail recursion or iterations?  
P: n/a

Jordan Abel said: On 20051028, 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)  
P: n/a

nelu said: using simple recursion, tail recursion or iterations?
All these are suboptimal 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)  
P: n/a

Keith Thompson said: ro******@ibd.nrccnrc.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 bestremembered 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)  
P: n/a

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.  
P: n/a

Richard Heathfield wrote: nelu said:
using simple recursion, tail recursion or iterations?
All these are suboptimal solutions to the Fibonacci problem.
<OT>
Aside of precomputing 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>  
P: n/a

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 suboptimal solutions to the Fibonacci problem.
<OT> Aside of precomputing 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>  
P: n/a

In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes: On 20051028, 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/  
P: n/a

On 20051028, Dik T. Winter <Di********@cwi.nl> wrote: In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes: > On 20051028, 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.  
P: n/a

Antonio Contreras wrote: Richard Heathfield wrote: nelu said:
using simple recursion, tail recursion or iterations?
All these are suboptimal solutions to the Fibonacci problem.
<OT> Aside of precomputing 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)  
P: n/a

On 20051028, John Bode <jo*******@mydeja.com> wrote: Antonio Contreras wrote: Richard Heathfield wrote: > nelu said: > > > using simple recursion, tail recursion or iterations? > > All these are suboptimal solutions to the Fibonacci problem.
<OT> Aside of precomputing 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.  
P: n/a

John Bode wrote: Antonio Contreras wrote: Richard Heathfield wrote: nelu said:
> using simple recursion, tail recursion or iterations?
All these are suboptimal solutions to the Fibonacci problem.
<OT> Aside of precomputing 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.  
P: n/a

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.  
P: n/a

"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.  
P: n/a

In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes: On 20051028, Dik T. Winter <Di********@cwi.nl> wrote: In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes: > On 20051028, 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/  
P: n/a

In article <dj**********@nwrdmz03.dmz.ncs.ea.ibsinfra.bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote: nelu said:
using simple recursion, tail recursion or iterations?
All these are suboptimal solutions to the Fibonacci problem.

(lambda (n)
(let ((foo (lambda (last1 last2 nleft f)
(if (= nleft 0)
last1
(f (+ last1 last2) last1 ( nleft 1) f)))))
(cond ((not (integer? n)) 'mustbeinteger ;not fully general!
(< n 0) 'mustbenonnegative
(= n 0) 1
(= n 1) 1
#t (f 1 1 ( n 1) f)))))

Tailrecursive, 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 (last1 last2 nleft f)
(if (= nleft 0)
last1
(begin (print (+ last1 last2)) ;ugly!
(newline)
(f (+ last1 last2) last1 ( nleft 1) f))))))
(cond ((not (integer? n)) 'mustbeinteger ;not fully general!
(< n 0) 'mustbenonnegative
(= 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  
P: n/a

Jordan Abel wrote: On 20051028, John Bode <jo*******@mydeja.com> wrote: Antonio Contreras wrote: Richard Heathfield wrote: > nelu said: > > > using simple recursion, tail recursion or iterations? > > All these are suboptimal solutions to the Fibonacci problem.
<OT> Aside of precomputing 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.  
P: n/a

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 :).  
P: n/a

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  
P: n/a

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  
P: n/a

Dik T. Winter wrote: In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes: > On 20051028, Dik T. Winter <Di********@cwi.nl> wrote: > > In article <sl*******************@random.yi.org> Jordan Abel <jm****@purdue.edu> writes: > > > On 20051028, 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  
P: n/a

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 singlevalue calculation to print all the preceding values as
well than to do the same with a closedform 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 bugfree 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  
P: n/a

"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 toppost. 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.  
P: n/a

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 singlevalue calculation to print all the preceding values as well than to do the same with a closedform 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 :) )  
P: n/a

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.  
P: n/a

> 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 toppost. 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.  
P: n/a

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)  
P: n/a

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/  
P: n/a

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/  
P: n/a

> 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.  
P: n/a

"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  
P: n/a

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  
P: n/a

In article <43****************@news.xs4all.nl> rl*@hoekstrauitgeverij.nl (Richard Bos) writes: "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.
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/   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 4044
 replies: 47
 date asked: Nov 15 '05
