J
jugaaru
How to generate fibonacci mubers in C ?
J
Julian V. Noble
jugaaru said:
The algorithm is
F(n+1) = F(n) + F(n-1) , F(0) = 0, F(1) = 1
You can do this recursively (very stupid and slow--see my article
"Recurses!" in Computing in Science and Engineering) or iteratively
(much better).
I won't tell you how to do it since it is evidently homework.
Julian V. Noble
Professor Emeritus of Physics
(e-mail address removed)
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/
"For there was never yet philosopher that could endure the
toothache patiently."
-- Wm. Shakespeare, Much Ado about Nothing. Act v. Sc. 1.
L
Leor Zolman
At least two ways: iteratively (create an array, and populate it
on-the-fly), or recursively (have a function return 0 and 1 for the first
two Fibonacci numbers, and then have it calculate any other by calling
itself to acquire the previous two. Note that there's a /serious/
performance degradation for the 2nd technique, but it is more fun to code
;-)
-leor
Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html
S
Sean Kenwrick
jugaaru said:
#include <stdio.h>
int main() {
printf("fibonacci mubers in C\n");
return 0;
}
O
osmium
jugaaru said:
http://en.wikipedia.org/wiki/Fibonacci_number
Save the root of that link, it is a nice one to have handy for all sorts of
questions.
P
Papadopoulos Giannis
jugaaru said:
Since it is definately a hw, I do not think that anyone should give you
an answer - the only way to learn is to get your feet wet..
But consider the following:
1) In the recursive solution, the resulting code is really trivial and
small (hint: the smallest possible is 3 lines).. Perfomance is missing
though...
2) Prefer the iterative solution, although it may seem a bit more
complicated..
When I was given the exercise, I had also to optimize my code for many
calls to the fibonacci procedure..
I used a static array to hold already calculated fibonacci numbers, to
speed up execution...
That is, the first time you calculate the 10th number, the array was
filled with some of the previous numbers.. Now, if you have to calculate
the 20th number, you don't need to do it all over again... Calculating
the 5th number is tricky though
...3) I think I said enough already...
--
#include <stdio.h>
#define p(s) printf(#s" endian")
int main(void){int v=1;*(char*)&v?p(Little)
(Big);return 0;}Giannis Papadopoulos
http://dop.users.uth.gr/
University of Thessaly
Computer & Communications Engineering dept.
D
Dik T. Winter
I prefer the direct, third, method. But you must not forget to include
math.h in that case (for the pow function). Moreover, it will not be
accurate when you wish use 64-bit integers.
J
jugaaru
Papadopoulos Giannis said:Since it is definately a hw, I do not think that anyone should give you
an answer - the only way to learn is to get your feet wet..
But consider the following:
1) In the recursive solution, the resulting code is really trivial and
small (hint: the smallest possible is 3 lines).. Perfomance is missing
though...
2) Prefer the iterative solution, although it may seem a bit more
complicated..
When I was given the exercise, I had also to optimize my code for many
calls to the fibonacci procedure..
I used a static array to hold already calculated fibonacci numbers, to
speed up execution...
That is, the first time you calculate the 10th number, the array was
filled with some of the previous numbers.. Now, if you have to calculate
the 20th number, you don't need to do it all over again... Calculating
the 5th number is tricky though
3) I think I said enough already...
--
#include <stdio.h>
#define p(s) printf(#s" endian")
int main(void){int v=1;*(char*)&v?p(Little)
Giannis Papadopoulos
http://dop.users.uth.gr/
University of Thessaly
Computer & Communications Engineering dept.
--------------------
Yeah you are right, this is a Homework. I have just started learning
C, I am having trouble learning it. First 2-3 chapters, i can
understand variables,equation, somethings like maths. But when the
faculty start giving assignment. You have no clue how to do it.
Please advise how do i learn C programming.
O
osmium
jugaaru said:
Using the link I provided can you write a function to return F(0)? F(1)?
F(2)? F(3)? Do this with pencil and paper. Now try the other way,
starting with F(3) and working down. Then generalize the method you
discover and write a program to automate the process.
Perhaps you will be more comfortable with this alternative assignment:
Write a program to print the first ten Fibonacci numbers. Do that first,
throw it away, and then do the assigned problem. That essentially divides
the problem into two simpler problems.
C
CBFalconer
Julian V. Noble said:
But I will for two reasons: 1. Enough time has passed so that the
homework should have been passed in. 2. If the OP can rework the
following into something the instructor will believe is his, he
will have learned something.
BTW the following shows up a glitch in DJGPP 2.03 system. Calling
the program with an argument of -1 returns the overflow condition,
because strtoul returns ULONG_MAX rather than 0. Cross-posted to
comp.os.msdos.djgpp for this.
#include <stdio.h>
#include <stdlib.h>
/* ------------------ */
/* deliberately written to upset some style mavens */
/* returns ULONG_MAX for overflow */
static unsigned long fibo(unsigned int n)
{
unsigned long pprev, prev, value;
if ((pprev = 0) == n) value = pprev;
else if ((prev = 1) == n) value = prev;
else do {
value = pprev + prev; pprev = prev; prev = value;
if (value < pprev) {
value = -1; /* ULONG_MAX, overflow */
goto x;
}
} while (2 <= --n);
x: return value;
} /* fibo */
/* ------------------ */
int main(int argc, char **argv)
{
unsigned int n;
if (2 != argc) puts("Usage: fibo N");
else {
n = strtoul(argv[1], NULL, 10);
printf("fibonacci(%u) = %lu\n", n, fibo(n));
}
return 0;
} /* main */
R
Richard Bos
Don't take this the wrong way, but: do your own homework. It wasn't
given you to pester you or keep you off the streets, it was given you so
that by solving it you will learn to program in C. The best way to learn
to program really is by trying to do so, and learning from your
mistakes; and that's what your homework is for.
Richard
E
Eric Sosman
CBFalconer said:
If you mean that strtoul("-1", NULL, 10) returns ULONG_MAX,
then there's no bug: that's what it is supposed to do. See
the Standard, section 7.20.1.4 paragraph 3, and note the text
"optionally preceded by a plus or minus sign."
C
CBFalconer
Eric said:
On re-reading the standard, I can see that out. However this
implementation actually returns ULONG_MAX - 1 for input of -2,
etc., i.e. it is performing the modulo arithmetic rather than
determining overflow.
Removed djgpp cross-post.
L
lawrence.jones
CBFalconer said:
That's exactly what it's supposed to do. The negation happens in the
return type, which means that it's *unsigned* negation in this case and
there is no overflow. You only get overflow if the input string
represents a value greater than ULONG_MAX.
-Larry Jones
What better way to spend one's freedom than eating chocolate
cereal and watching cartoons! -- Calvin
C
CBFalconer
That makes no sense to me. If -2 is handled with modulo
arithmetic, so should a string representing ULONG_MAX + 2. All of
which makes a mockery of overflow detection. At any rate here is
a baby demo I put together to show what we are talking about.
Output for "strbug 3" follows, under djgpp/gcc. Note that it
never sets errno.
I have added a crosspost to comp.std.c.
Neg args should yield 4294967295 and error
strtoul("-3junk") = 4294967293 remnant "junk"
strtoul("-2junk") = 4294967294 remnant "junk"
strtoul("-1junk") = 4294967295 remnant "junk"
strtoul("0junk") = 0 remnant "junk"
strtoul("1junk") = 1 remnant "junk"
strtoul("2junk") = 2 remnant "junk"
strtoul("3junk") = 3 remnant "junk"
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
int main(int argc, char **argv)
{
unsigned int n;
int i;
char s[25];
char *rem;
if (2 != argc) puts("Usage: strbug N");
else {
n = strtoul(argv[1], NULL, 10);
if (n > 10) puts("Max. N is 10");
else {
printf("Neg args should yield %lu and error\n",
(unsigned long)-1);
for (i = -n; i <= (int)n; i++) {
sprintf(s, "%djunk", i);
errno = 0;
printf("strtoul(\"%s\") = %lu",
s, strtoul(s, &rem, 10));
printf(" remnant \"%s\"\n", rem);
if (errno) perror("Error");
}
}
}
return 0;
} /* main strbug */
D
Douglas A. Gwyn
CBFalconer said:
I don't understand your argument. ULONG_MAX+2 is not
representable in the type, so any sort of dealing with
such a string internally would have to enter a special
case, for which we require overflow to be reported.
There is no special case needed for the implementation
to negate (modulo wordsize).
Frankly, I don't like the idea of allowing sign on a
textual representation of an unsigned integer value,
but that's the legacy we're stuck with.
Why?
N
nrk
CBFalconer said:
Nit (and definitely not an issue in most implementations with non-zero QoI).
You should really pull that strtoul call out and check errno immediately
after the call. The intervening printf can legitimately set errno to some
value regardless of whether or not there was an error.
Something like:
unsigned long l;
...
errno = 0;
l = strtoul(...);
if ( errno ) perror("Error");
...
-nrk.
C
CBFalconer
Douglas A. Gwyn said:
Because the value -1 is outside the range of an unsigned. So is
ULONG_MAX+2. So they should both yield ULONG_MAX and ERANGE,
assuming the - sign is accepted.
See above.
L
lawrence.jones
In comp.std.c CBFalconer said:
Why? Consider the following:
/* assuming ULONG_MAX == 4294967295 */
unsigned long ul1 = -2UL; // perfectly good, ul1 = 4294967294
unsigned long ul2 = 4294967297UL; // error, overflow
It would make even less sense to accept a negative sign if all the
negative values were regarded as overflows. If you really don't want to
accept negative values, it's easy enough to check for the '-' yourself
before call strtoul.
-Larry Jones
Hey Doc, for 10 bucks I'll make sure you see those kids in the
waiting room again real soon! -- Calvin
D
Douglas A. Gwyn
CBFalconer said:
But a minus sign is explicitly allowed in the input field,
and is defined as negating the converted nonnegative value,
not as part of a textual representation of an unsigned value.