Fibonacci Sequence
Author Message Fibonacci Sequence

Quote:

> BEsides defining the sequence a1=1,a2=1,an=a(n-1)+a(n-2)

In J this script will create as many fibonacci numbers as you like

NB.  a1=1,a2=1,an=a(n-1)+a(n-2)
fibbi=. 3 : '1!:2&2 [a=:a,+/_2{.a' NB. create the verb
1!:2&2 [a=:1 1 NB. create the first two and display them
fibbi &. >  i.11 NB. call the verb fibbi 11 times
0!:0<'c:\priva\j95\temp\12.js' NB. run the script
1 1
1 1 2
1 1 2 3
1 1 2 3 5
1 1 2 3 5 8
1 1 2 3 5 8 13
1 1 2 3 5 8 13 21
1 1 2 3 5 8 13 21 34
1 1 2 3 5 8 13 21 34 55
1 1 2 3 5 8 13 21 34 55 89
1 1 2 3 5 8 13 21 34 55 89 144
1 1 2 3 5 8 13 21 34 55 89 144 233

--

http://www.*-*-*.com/ ~gosi
http://www.*-*-*.com/

Tue, 29 Sep 1998 03:00:00 GMT  Fibonacci Sequence

:> BEsides defining the sequence a1=1,a2=1,an=a(n-1)+a(n-2)
:>
:
:In J this script will create as many fibonacci numbers as you like
:
:   NB.  a1=1,a2=1,an=a(n-1)+a(n-2)
:   fibbi=. 3 : '1!:2&2 [a=:a,+/_2{.a' NB. create the verb
:   1!:2&2 [a=:1 1 NB. create the first two and display them
:   fibbi &. >  i.11 NB. call the verb fibbi 11 times
:   0!:0<'c:\priva\j95\temp\12.js' NB. run the script
:1 1
:1 1 2
:1 1 2 3
:1 1 2 3 5

etc.

Wonderful.  Another cryptic, write-only language, this time without even
the grace of being a SHORT solution.

--Ron Bruck
Now 100% ISDN from this address

Tue, 29 Sep 1998 03:00:00 GMT  Fibonacci Sequence

Quote:

> Wonderful.  Another cryptic, write-only language,
> without even the grace of being a SHORT solution.

If short is all you are after then this will do:

fibbi=. 3 : 'a=:a,+/_2{.a'
a=:1 1
fibbi &. >  i.11

I am sure you can write this even shorter

I was merely writing it as a standalone script with a formatted output.

It would have been clearer and more demonstrative possibly like this:

------------- start of script demo of fibonacci numbers

NB.  a1=1,a2=1,an=a(n-1)+a(n-2)
NB.
NB. fibbi is a verb to create the fibonacci numbers
fibbi=. 3 : '1!:2&2 [a=:a,+/_2{.a'

NB. out is a verb to create output to screen
out=:1!:2&2

NB. a is a global noun initialli holding the first two fibonacci numbers
a=:1 1

NB. each is a utility that operates on all elements of a noun
each=:&. >

NB. vector contains 11 elements and will only be used because of it's
NB. number of elements
vector=.i.11

out 1                                   NB. write the number 1

out a                                   NB. write out the contents of a

fibbi each  vector              NB. run the verb fibbi

------------- srebmun iccanobif fo omed tpircs fo dne

NB. run the script

0!:0<'c:\priva\j95\temp\demo of fibonacci numbers.js'
1
1 1
1 1 2
1 1 2 3
1 1 2 3 5
1 1 2 3 5 8
1 1 2 3 5 8 13
1 1 2 3 5 8 13 21
1 1 2 3 5 8 13 21 34
1 1 2 3 5 8 13 21 34 55
1 1 2 3 5 8 13 21 34 55 89
1 1 2 3 5 8 13 21 34 55 89 144
1 1 2 3 5 8 13 21 34 55 89 144 233

--

http://www2.simi.is/~gosi
http://www.jsoftware.com

Wed, 30 Sep 1998 03:00:00 GMT  Fibonacci Sequence
Sorry !

I forgot to replace the "out" operation in fibbi

NB.
NB. fibbi is a verb to create the fibonacci numbers
fibbi=. 3 : 'out a=:a,+/_2{.a'

--

http://www2.simi.is/~gosi
http://www.jsoftware.com

Wed, 30 Sep 1998 03:00:00 GMT  Fibonacci Sequence

Quote:

>> Besides defining the sequence a1=1,a2=1,an=a(n-1)+a(n-2)

>In J this script will create as many fibonacci numbers as you like

>   NB.  a1=1,a2=1,an=a(n-1)+a(n-2)
>   fibbi=. 3 : '1!:2&2 [a=:a,+/_2{.a' NB. create the verb
>   1!:2&2 [a=:1 1 NB. create the first two and display them
>   fibbi &. >  i.11 NB. call the verb fibbi 11 times
>   0!:0<'c:\priva\j95\temp\12.js' NB. run the script

...

I think that Helgason is onto something interesting here, but I would
like to suggest that there is a completely different approach that does
not use recursion, just arithmetic (and rounding).  J users, please
excuse me for not writing the shortest form in what follows.  My
purpose is not to give the shortest possible presentation but to
suggest a completely different approach that might be overlooked by
some readers.  Because the J notation was used earlier, I will continue
using it, but I have used a style that I think will be understandable
to readers who are not yet comfortable with J.

The recursion formula used for the Fibonacci sequence says that
after the sequence gets going, the n-th term is given by sum of
the two previous terms.  This suggests the characteristic equation

(x^2)  =  x + 1

or better, the polynomial

0 =  1 + x - x^2

whose roots are easy to calculate and I will call alpha and beta.
These two numbers, one greater than 1, and the other with absolute
value less than 1, can be used to calculate the numbers of the
sequence.  This is what I want to suggest:

rt5   =. 5 ^ %2
alpha =. ( 1 + rt5 ) % 2
beta  =. ( 1 - rt5 ) % 2
i     =. i. 10

NB. Method 1.
( (alpha^i) - (beta^i) ) % rt5
0 1 1 2 3 5 8 13 21 34

NB. Method 2.
<. 0.5 + ( ( alpha^i ) % rt5 )
0 1 1 2 3 5 8 13 21 34

I like Method 2 because it uses only one exponentiation rather than the
two needed by Method 1.  The fact that the absolute value of beta is
less than 1 beta, that is ( 1 > | beta ), means that powers of beta get
smaller for larger values of i, and this is the reason that rounding a
multiple of powers of alpha to the nearest integer does the trick.

As an aside, I would like to mention that I prefer to start the
Fibonacci sequence with zero and to say that the n-th term is n
for the first two values of n.

Lee{*filter*}ey
--
Prof. Leroy J.{*filter*}ey, Faculty of Mathematics, U of Waterloo, Canada  N2L 3G1

http://www.*-*-*.com/ ~ljdickey

Wed, 30 Sep 1998 03:00:00 GMT  Fibonacci Sequence
Since the N'th Fibonacci number is:

n         -n
PSI   -   PSI                         .5
-----------------     (where PSI =  ( 5   - 1 ) / 2  or the golden ratio)
2 PSI  -  1

couldn't this be much shorter and simpler?  A recursive definition is
educational, but not always the best approach.
--
W. LeRoy Davis

-----------------------------------------------------------------------------
Don't ever think you know what's right for the other guy.       Paul Williams
He might start thinking he knows what's right for you.          "Das Energi"

Wed, 30 Sep 1998 03:00:00 GMT  Fibonacci Sequence

I should draw your attention to Eugene McDonnell's fabulous paper
"Heron's Rule & Integer-Area Triangles" in the January issue of the
British APL Journal Vector, wherein various methods for solving
linear recurrences are explored.

Thu, 01 Oct 1998 03:00:00 GMT  Fibonacci Sequence
:
:.... TThis is what I want to suggest:
:
:    rt5   =. 5 ^ %2
:    alpha =. ( 1 + rt5 ) % 2
:    beta  =. ( 1 - rt5 ) % 2
:    i     =. i. 10
:
: NB. Method 1.
:    ( (alpha^i) - (beta^i) ) % rt5
: 0 1 1 2 3 5 8 13 21 34
:
: NB. Method 2.
:    <. 0.5 + ( ( alpha^i ) % rt5 )
: 0 1 1 2 3 5 8 13 21 34
:

I suppose that a language such as J that is forced to use machine
numbers, the explicit formula you cite here does no harm:  before
rounding give spurious results, you run out of precision for integers
anyway.

Do you happen to know what happens if you have "unlimited" precision,
such as in Mathematica?  Any roundoff problems there if you use your
method, rather than recursion, to calculate really big Fibonacci numbers?

--

Mathematics & Statistics Dept.            Voice:  413-545-2859 (W)
University of Massachusetts                       413-549-1020 (H)
Amherst, MA 01003                           Fax:  413-545-180

Sat, 03 Oct 1998 03:00:00 GMT  Fibonacci Sequence

: :
: :.... TThis is what I want to suggest:
: :
: :    rt5   =. 5 ^ %2
: :    alpha =. ( 1 + rt5 ) % 2
: :    beta  =. ( 1 - rt5 ) % 2
: :    i     =. i. 10
: :
: : NB. Method 1.
: :    ( (alpha^i) - (beta^i) ) % rt5
: : 0 1 1 2 3 5 8 13 21 34
: :
: : NB. Method 2.
: :    <. 0.5 + ( ( alpha^i ) % rt5 )
: : 0 1 1 2 3 5 8 13 21 34
: :
:
: I suppose that a language such as J that is forced to use machine
: numbers, the explicit formula you cite here does no harm:  before
: rounding give spurious results, you run out of precision for integers
: anyway.
:
: Do you happen to know what happens if you have "unlimited" precision,
: such as in Mathematica?  Any roundoff problems there if you use your
: method, rather than recursion, to calculate really big Fibonacci numbers?
:
: --

When this thread first started I thought I'ld offer a suggestion along
the above line but I thought it would be cute to use p. _1 _1 1 to
generate the golden mean and the other root.  I bit my tongue because I
recalled this problem easily can suck you (me) into rediscovering lots of ways
of computing Fibinacci numbers quickly.  So fast that you need multiprecision
to see what you're doing.  Anyway,
R. E. Maeder, "Fibonacci on the fast track", The Mathematica Journal, 1 3
(1996) 42-46 gives something like 10 different ways for computing the
Fib. sequence.  The fastest essentially uses the fact that there are
simple formulas, known for a long time, for computing f_2n and f_2n-1 in
terms of f_n and f_n-1.  However, his solution involved a looping algorithm
that used the 0/1 in a binary representation to decide what to do at each
stage and he didn't exclicitly make clear that the guts of the algorithm
was the recursions I mentioned.  So I wrote
C. A. Reiter, "Fast Fibonacci Numbers", The Mathematical Journal,
2 3 (1992) 58-60 where I showed how to speed things up more by taking
bigger jumps: eg, f_3n and f_3n-1 in terms of f_n and f_n-1 and in fact
showed how to use "FixedPoint"  (like ^:_ but applied to symbolic
arithmetic) to generate canonical forms for f_kn and f_kn-1 in terms of
f_n and f_n-1.  These forms can also be used to explain many of the
sporadic short periods that appear in the Fibonacci sequence reduced
modulo p.  I'ld be happy to send photcopies of the articles to
interested parties.
Cliff
--
Clifford A. Reiter
Mathematics Department, Lafayette College
Easton, PA 18042 USA,   610-250-5277

Sat, 03 Oct 1998 03:00:00 GMT  Fibonacci Sequence

Quote:
>Do you happen to know what happens if you have "unlimited" precision,
>such as in Mathematica?  Any roundoff problems there if you use your
>method, rather than recursion, to calculate really big Fibonacci numbers?

I think I know what is supposed to happen.  Method 1 is perfect,
for all n.  For the sake of simplicity, think about the two binomial
expansions,

(1+r)^n
(1-r)^n

where    r =. 5^0.5   ,  and you will see why.   In each case
half the terms have even powers of r and the other half have
odd powers of r.  When you take the difference, you have only
terms with odd powers remaining.

Maple treats r as a symbol with the property that r^2 is 5.  This
is just the way we might do it on paper, and during the simplification
process, an expression like r^3, r^5, and r^7, for example, are
simplified to 5r, 25r, and 125r, respectively.

Thus every term that survives the subtraction process has a factor of r,
which in turn cancels with the r in the denominator, and this leaves
a pure integer for the result.
The expression that I gave in a previous message is
( (alpha^n) - (beta^n) ) % r
where   alpha =. (1+r) % 2   and   beta =. (1-r)%2  .
Yes, my formula does seem to have  2^n  in the denominator, but
this "comes out in the wash", so to speak.

If you have been wondering how it can be that Maple, Mathematica,
and other symbolic algebra packages can produce such wonderful
results, this example can give some insight into one of the ways
this can happen.  Of course these symbolic algebra engines have
some other tricks up their sleeves.

Lee{*filter*}ey
--
Prof. Leroy J.{*filter*}ey, Faculty of Mathematics, U of Waterloo, Canada  N2L 3G1

http://www.*-*-*.com/ ~ljdickey

Sun, 04 Oct 1998 03:00:00 GMT  Fibonacci Sequence

Quote:

> >Do you happen to know what happens if you have "unlimited" precision,
> >such as in Mathematica?  Any roundoff problems there if you use your
> >method, rather than recursion, to calculate really big Fibonacci numbers?
> I think I know what is supposed to happen.  Method 1 is perfect,
> for all n.  For the sake of simplicity, think about the two binomial
> expansions,
>    (1+r)^n
>    (1-r)^n
> where       r =. 5^0.5   ,  and you will see why.   In each case
> half the terms have even powers of r and the other half have
> odd powers of r.  When you take the difference, you have only
> terms with odd powers remaining.
> Maple treats r as a symbol with the property that r^2 is 5.  This
> is just the way we might do it on paper, and during the simplification
> process, an expression like r^3, r^5, and r^7, for example, are
> simplified to 5r, 25r, and 125r, respectively.

Indeed, let x=(1+Sqrt(5))/2 and y=(1-Sqrt(5))/2 then
F(n)=(x^n-y^n)/Sqrt(5)

Note that

x^n=(1+(nC1)Sqrt(5)+(nC2)5+(nC3)5Sqrt(5)+...+Sqrt(5)^n)/2^n

y^n=(1-(nC1)Sqrt(5)+(nC2)5-(nC3)5Sqrt(5)+...+(-1)^n*Sqrt(5)^n)/2^n

Subtract, and simplify and you obtain...

F(n)=Sum(5^k*(nC(2k+1)),k,0,[(n-1)/2,(n-2)/2])/2^(n-1)

F(1)=(5^0*(1C1))/2^0=1
F(2)=(5^0*(2C1))/2^1=1
F(3)=(5^0*(3C1)+5^1*(3C3))/2^2=(3+5)/4=2
F(4)=(5^0*(4C1)+5^1*(4C3))/2^3=(4+20)/8=3
F(5)=(5^0*(5C1)+5^1*(5C3)+5^2*(5C5))/2^4=(5+50+25)/16=5
F(6)=(5^0*(6C1)+5^1*(6C3)+5^2*(6C5))/2^5=(6+100+150)/32=8

This is pretty easy integer arithmetic (very programmable) and it shows
yet another interesting feature of Fibonacci numbers... They can be
represented in terms of powers of 5,2,and Combinations.

Notice that 5 and 2 are both Fibonacci numbers (twilight zone music cue)

Or, that Sum(nC(2k+1),k,0,[(n-1)/2,n/2)])=2^(n-1)

Have a nice day. :-)

--
"The problem of the outsider | Kevin Johnson         | My company doesn't

and too much, and what he   | Western Geophysical   | anything.
sees is essentially chaos." |--------------------------------------------
-- The Outsider,          | 3.1415926535897932384626433832795028841972
Colin Wilson           | 2.7182818284590452353602874713526624977573

Sun, 04 Oct 1998 03:00:00 GMT  Fibonacci Sequence

|> >Do you happen to know what happens if you have "unlimited" precision,
|> >such as in Mathematica?  Any roundoff problems there if you use your
|> >method, rather than recursion, to calculate really big Fibonacci numbers?

|> I think I know what is supposed to happen.  Method 1 is perfect,
|> for all n.  For the sake of simplicity, think about the two binomial
|> expansions,

|>   (1+r)^n
|>   (1-r)^n

|> where      r =. 5^0.5   ,  and you will see why.   In each case
|> half the terms have even powers of r and the other half have
|> odd powers of r.  When you take the difference, you have only
|> terms with odd powers remaining.

|> Maple treats r as a symbol with the property that r^2 is 5.  This
|> is just the way we might do it on paper, and during the simplification
|> process, an expression like r^3, r^5, and r^7, for example, are
|> simplified to 5r, 25r, and 125r, respectively.

I think this is a bit different from what was asked.  You are referring to
a symbolic computation, not an "unlimited" precision floating-point computation.
Of course the symbolic computation will work fine (assuming you don't run out
of memory).  On the other hand, this is not a very efficient way of doing
things since in expanding (1+r)^n symbolically you will have to deal with n+1 terms.

As far as the floating-point computation goes, I think it should be OK as long
as you use sufficient precision to represent all digits of the result (and
maybe a couple more just to be safe).  In fact, you can ditch the beta^n and
just round (alpha^n)/r to the nearest integer.  On the other hand, this ends
up not being all that efficient either, because multiplying O(n)-digit floating-point numbers is time-consuming.
--

Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074

Sun, 04 Oct 1998 03:00:00 GMT  Fibonacci Sequence

Regarding msgs from Lee{*filter*}ey, Murray Eisenberg, Kevin Johnson,
and Robert Israel.  In the original msg on Saturday, April 13,

Quote:
Lee{*filter*}ey writes:
> The recursion formula used for the Fibonacci sequence says that
> after the sequence gets going, the n-th term is given by sum of
> the two previous terms.  This suggests the characteristic equation

>                (x^2)  =  x + 1

> or better, the polynomial

>                0 =  1 + x - x^2

> whose roots are easy to calculate and I will call alpha and beta.
> These two numbers, one greater than 1, and the other with absolute
> value less than 1, can be used to calculate the numbers of the
> sequence.  This is what I want to suggest:

>    rt5   =. 5 ^ %2
>    alpha =. ( 1 + rt5 ) % 2
>    beta  =. ( 1 - rt5 ) % 2
>    i     =. i. 10

> NB. Method 1.
>    ( (alpha^i) - (beta^i) ) % rt5
> 0 1 1 2 3 5 8 13 21 34

> NB. Method 2.
>    <. 0.5 + ( ( alpha^i ) % rt5 )
> 0 1 1 2 3 5 8 13 21 34

I worked on this problem in college in 1977 starting at this point,
and it is a valuable starting point despite its problems in the
domain of fixed-word machine integers and floating point numbers.
Having derived the fact that alpha^i alone suffices to compute the
Fibonacci sequence ("Method 2"), the next observation is that all
the intermediate numbers involved are ratios, with powers of 2 in
the denominator and numbers of the form a+b*rt5 in the numerator,
where a and b are integers.  That being the case, non-integer
operations can be avoided altogether; that is, the numerator can be
computed in Q[5^0.5]: if (a,b) is a+b*5^0.5, then:

(a,b)+(c,d)  <->  ((a+c),b+d)
(a,b)*(c,d)  <->  (((a*c)+5*b*d),(a*d)+b*c)

Therefore, the n-th Fibonacci number can be computed by repeated
squaring using O(log n) integer operations.  The following program,
translated directly from ALGOLW into J, demonstrates:

F=: 3 : 0 " 0
n=.y.
a=.1 [ ra=.2
b=.1 [ rb=.0
while. n>0 do.
t=. n
n=. <.n%2
if. 2|t do.
t=.  ra
ra=. <. ((ra*a)+5*rb*b) % 2
rb=. <. ((a*rb)+b*t) % 2
end.
t=. a
a=. <. ((a*a)+5*b*b) % 2
b=. t*b
end.
rb
)

F i.20
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

There is another efficient computation of the n-th Fibonacci number,
using only elementary concepts:

x=: +/ .*  NB. inner product
A0=: 0 1
[ M=: 0 1,:1 1
0 1
1 1

M x A0
1 1
M x M x A0                    (M x M) x A0
1 2                           1 2
M x M x M x A0                (M x M x M) x A0
2 3                           2 3
M&x ^: (i.5) A0               (M&x^:(i.5) =i.2) x A0
0 1                           0 1
1 1                           1 1
1 2                           1 2
2 3                           2 3
3 5                           3 5

The n-th element of the sequence obtains by repeated multiplication
by M or, equivalently, by multiplication by the n-th power of M.
The n-th power of a matrix can be computed by repeated squaring,
using O(log n) operations.  For example, for n=30:

[ b=.#:30          NB. Binary representation of 30
1 1 1 1 0
b # i.-#b          NB. Powers corresponding to 1s in b
4 3 2 1

M x M              NB. Squaring a matrix
1 1
1 2
x~ M
1 1
1 2
x~^:4 3 2 1 M
610  987
987 1597

13   21
21   34

2    3
3    5

1    1
1    2
x/ x~^:4 3 2 1 M   NB. product of selected powers
514229  832040
832040 1346269
x/ 30#,:M
514229  832040
832040 1346269

NB. M pow n is n-th power of M for n>0
pow=: 4 : 'x/ x~^:(b#i.-#b=.#:y.) x.'
M pow 30
514229  832040
832040 1346269

G=: [: {. M&pow x A0"_
G 30
832040
F 30
832040

Both of the above methods work on extended precision integers if such
are available.  The second method works on any linear recurrence, and
does not depend on finding the roots of a polynomial.  Finally, the
methods are best if the n-th element is required; if elements i.n
(0 1 2 ... n-1) are required, it is more direct and more efficient to
simply add the last two elements, repeatedly.

Tue, 06 Oct 1998 03:00:00 GMT  Fibonacci Sequence
Since I do not use Fibonacci numbers a lot I use the function below.  It may
not be as fast as some, but it follows the tradition of "one liners"

{DEL} Z {ASSIGN} FIB N
 Z{ASSIGN}1{DROP}{EXECUTE}((3{TIMES}N){RESHAPE}'{ROTATE}+\'),'1 0'
{DEL}

The polynomial using sqroot 5 can be placed in MuMath and be used to go for
big numbers like the 10,000 one in the squence

John R. Clark

Fri, 09 Oct 1998 03:00:00 GMT  Fibonacci Sequence
Actually Maple's willing to tell you what it actually does.
It's clear that computing the Fibonacci numbers is the same as computing
A^n, where  A=[1,1;1,0]. Maple does this by "binary exponentiation":
You start with B=I. You compute the matrices A^(2^j) by repeated squarings,
and when it happens that 2^j occurs in n you multiply B by A^(2^j) .

--
David Ullrich
Don't you guys find it tedious typing the same thing
after your signature each time you post something?
I know I do, but when in Rome...

Sat, 10 Oct 1998 03:00:00 GMT

 Page 1 of 2 [ 15 post ]

Relevant Pages