Fibonacci implementation
Christian Christmann
I'm looking for a non-recursive implementation of the algorithm to
calculate Fibonacci numbers. Any language is OK (C/C++, pseudo code
prefered).
Any hints?
Thank you,
Chris
riedel
numeric digits 64 /* enough for fib(300) */
parse arg a
say fib(a)
exit 0
fib: procedure
parse arg a
if a < 0 | datatype(a, 'N') <> 1 then
return 'NaN'
o = 0
n = 1
if a = o | a = n then
return a + 1
do a - 2
parse value n (n + o) with o n
end
return n
Wolfgang
Till Crueger
> Hi,
>
> I'm looking for a non-recursive implementation of the algorithm to
> calculate Fibonacci numbers. Any language is OK (C/C++, pseudo code
> prefered).
#GEM 1.0
fib := ( \ (x) ->
o := 0;
n := 1;
x.for( \ (i) ->
tmp := n;
n := n.+(o);
o := tmp);
n);
--
Please add "Salt and Pepper" to the subject line to bypass my spam filter
Rob Thorpe
Have you tried typing "non-recursive fibonacci" into a search engine?
I found a page showing how to do it in a C/C++ like language 3rd hit
down.
Jon Harrop
> I'm looking for a non-recursive implementation of the algorithm to
> calculate Fibonacci numbers. Any language is OK (C/C++, pseudo code
> prefered).
Code Codex contains many excellent examples, including Fibonacci in many
languages:
http://www.codecodex.com/wiki/index.php?title=Fibonacci_sequence
--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists
Logan Shaw
> Christian Christmann schrieb:
>> Hi,
>>
>> I'm looking for a non-recursive implementation of the algorithm to
>> calculate Fibonacci numbers. Any language is OK (C/C++, pseudo code
>> prefered).
>>
>> Any hints?
>>
>> Thank you,
>> Chris
> /* rexx */
> numeric digits 64 /* enough for fib(300) */
> parse arg a
> say fib(a)
Oh god, REXX. In punishment for that, here is my Bourne Shell
implementation:
#! /bin/sh
fib ()
{
n=$1
if [ "$n" -lt 3 ]
then
echo 1
else
mkdir -p 1/1
(
cd 1/1
n=`expr $n - 2`
while [ $n -gt 0 ]
do
{
( basename `pwd` )
echo "+"
( cd .. ; basename `pwd` )
} | fmt | bc | xargs mkdir
cd *
n=`expr $n - 1`
done
pwd | sed -e 's/.*\///'
)
rm -r 1
fi
}
fib "$@"
Like many shell scripts, it might be a little inefficient in places,
and it might do things the hard way here and there, but it works, so
why mess with it?
- Logan
Rob Thorpe
Exactly, it's beautiful, the use of xargs and mkdir inparticular.
Here is the same in Unlambda:-
```s``s``sii`ki
`k.*``s``s`ks
``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
`k``s`ksk
Also, in Cathol
INCIPIT CANTUS fibonacci CUM fibn
OBSCURA a b c
FIAT a 1
FIAT b 1
NUMERABIS n AB INITIO 3 USQUE AD fibn
FIAT c a+b
FIAT a b
FIAT b c
SI fibn MAIOR 3
SCRIBE c
FRANGE
ALIAS
ORA "Domine te laudamus"
NISI
PROCEDE
ILLUMINANDO REDDE c
AMEN
PAENITENTIAM AGE
FIAT fibo30 @fibonacci 30
EGO TE ABSOLVO
These examples are from the websites of vendors of those languages.
Richard Heathfield
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char **argv)
{
unsigned long N = (argc > 1 ? strtoul(argv[1], NULL, 10) : 42);
double n = N > 0 ? N : 1;
double n2 = n * n;
double n3 = n2 * n;
double n4 = n2 * n2;
double e = exp(1);
double pi = atan(1) * 4;
double f1 = sqrt(2 * pi * n);
double f2 = pow(n / e, n);
double t1 = 1;
double t2 = 1 / (12 * n);
double t3 = 1 / (288 * n2);
double t4 = 139 / (51840.0 * n3);
double t5 = 571 / (2488320.0 * n4);
double f3 = t1 + t2 + t3 - t4 - t5;
double nbang = f1 * f2 * f3;
printf("%lu! = %.0f\n", N, nbang);
return 0;
}
--
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)
gw7...@aol.com
No-one seems to have given a straight-forward reply to this. You can do
it in BASIC as follows:
DIM f(n)
f(0) = 0
f(1) = 1
FOR k = 2 TO n
f(k) = f(k - 1) + f(k - 2)
NEXT k
Which is nice and simple. If you want single, large values however it
might be quicker to calculate them directly, as follows:
FUNCTION fib (k)
r = (1 + SQR(5)) / 2
t = 1 - r
fib = (r ^ k - t ^ k) / (r - t)
END FUNCTION
(where SQR is the square root function, ^ is "to the power of" and the
line "fib = " sets the result of the function.
Incidentally, I thought the only reason for writing a recursive
implementation of Fibonacci numbers was to show how recursive functions
can go horribly wrong if you don't think about them carefully.
Hope that helps.
Paul.
Richard Heathfield
<snip>
>
> If you want single, large values however it
> might be quicker to calculate them directly, as follows:
>
> FUNCTION fib (k)
> r = (1 + SQR(5)) / 2
> t = 1 - r
> fib = (r ^ k - t ^ k) / (r - t)
> END FUNCTION
Oops. That was what I intended to offer the OP. I appear to have given him
Stirling's Approximation for factorials instead.
Logan Shaw
> gw7...@aol.com said:
>
> <snip>
>> If you want single, large values however it
>> might be quicker to calculate them directly, as follows:
>>
>> FUNCTION fib (k)
>> r = (1 + SQR(5)) / 2
>> t = 1 - r
>> fib = (r ^ k - t ^ k) / (r - t)
>> END FUNCTION
>
> Oops. That was what I intended to offer the OP. I appear to have given him
> Stirling's Approximation for factorials instead.
Oh, I hate it when I mean to give someone a direct method for
calculating the N-th Fibonacci number and accidentally give them
Stirling's Approximation for factorials by mistake! And I am
always making that mistake, too...
- Logan
CBFalconer
>
> I'm looking for a non-recursive implementation of the algorithm to
> calculate Fibonacci numbers. Any language is OK (C/C++, pseudo code
> prefered).
#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 */
--
Chuck F (cbfal...@yahoo.com) (cbfal...@maineline.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE maineline address!
Martijn Mulder
>
> I'm looking for a non-recursive implementation of the algorithm to
> calculate Fibonacci numbers. Any language is OK (C/C++, pseudo code
> prefered).
It's been a while. Hope that this still works
//oktober 2003 Fast fibonacci generator for very large numbers
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
inline int dv(int a,int b){return a/10+b;}
inline int md(int a){return a%10;}
inline int sm(int a,int b){return a+b;}
struct LongInt
{
vector<int>V;
vector<int>&v;
LongInt(int a=0):v(V){do v.push_back(a%10);while((a/=10)!=0);}
void swap(LongInt&a){v.swap(a.v);}
void set(const LongInt&a,const LongInt&b)
{
v.resize(a.v.size());
copy(a.v.begin(),a.v.end(),v.begin());
v.resize(a.v.size()<b.v.size()?b.v.size():a.v.size());
transform(b.v.begin(),b.v.end(),v.begin(),v.begin(),sm);
transform(v.begin(),v.end()-1,v.begin()+1,v.begin()+1,dv);
transform(v.begin(),v.end()-1,v.begin(),md);
if(v[v.size()-1]>9)
{
int c=v[v.size()-1]/10;
v[v.size()-1]%=10;
v.push_back(c);
}}
void print()
{
copy(v.rbegin(),v.rend(),ostream_iterator<int>(cout));
cout<<endl;
}};
struct Fibonacci
{
LongInt first,second,third;
Fibonacci(int a):first(0),second(1),third(1)
{
for(int b=0;b<a;b++)
{
first.print();
first.swap(second);
second.swap(third);
third.set(second,first);
}}};
int main()
{
LongInt a(45);
LongInt b(55);
LongInt c;
c.set(a,b);
c.print();
Fibonacci(900000);
return 0;
}
kshudra
Christian Christmann wrote:
this may not the best solution but i like it
swap(int *a, int *b) { int t; t = *a; *a = *b; *b = t; }
int fib(int n)
{
int i; int pre = -1; int now = 0;
for (i = 0; i < n; i++)
{
printf("%d", now);
swap(&now, &pre);
now = pre+now;
}
}
/*
pre now
2 3 3
3 2
3 5 5
5 3
*/
Markus Triska
> this may not the best solution but i like it
Similar approach in J:
+/\@|.^:(i.10) 0 1
0 1
1 1
1 2
2 3
3 5
5 8
8 13
13 21
21 34
34 55
All the best,
-- Markus Triska
Chris Uppal
> Similar approach in J:
>
> +/\@|.^:(i.10) 0 1
One of the few languages where smilies actually mean something. I like
^:(i.10)
but am unsure what emotion it is intended to convey. "My brain has
just exploded" ?
-- chris
ena8...@yahoo.com
Geez guys, give him a break.
unsigned fibonacci( const unsigned n ) {
unsigned t, a = 0, b = 1, k = 0;
while (k<n) t = a+b, a = b, b = t, k++;
return a;
}
kshudra
int pre = 1;int now = 0;
if you are interested in main() ?
i've added this anyway
main()
{
int n;
printf("enter how many terms of fibonacci series you want??:\n");
scanf("%d", &n);
fib(n);
}
Dann Corbit
** Direct computation of Fibonacci numbers.
**
** Input: index of Fibonacci number to compute (n)
**
** Returns: nth Fibonacci number.
*/
double dFibonacci(unsigned n)
{
/* isf is 1/sqrt(5) */
static const double isf =
0.44721359549995793928183473374625524708812367192231;
/* gr is golden ratio */
static const double gr =
1.6180339887498948482045868343656381177203091798057;
double x,
xx;
x = pow(gr, n) * isf;
xx = floor(x);
if (x - xx > 0.5)
xx += 1;
return xx;
}
Willem
) xx = floor(x);
) if (x - xx > 0.5)
) xx += 1;
Isn't that a needlessly complex way of writing
xx = floor(x + 0.5)
?
(Note to the astute reader: a small modification will fix that teensy
problem you noticed, but I don't think the problem matters in this case.)
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT