Author 
Message 
Bj?rn Helgaso #1 / 15

Fibonacci Sequence
Quote:
> BEsides defining the sequence a1=1,a2=1,an=a(n1)+a(n2)
In J this script will create as many fibonacci numbers as you like NB. a1=1,a2=1,an=a(n1)+a(n2) 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 


Ronald Bru #2 / 15

Fibonacci Sequence
:> BEsides defining the sequence a1=1,a2=1,an=a(n1)+a(n2) :> : :In J this script will create as many fibonacci numbers as you like : : NB. a1=1,a2=1,an=a(n1)+a(n2) : 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, writeonly 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 


Bj?rn Helgaso #3 / 15

Fibonacci Sequence
Quote:
> Wonderful. Another cryptic, writeonly 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(n1)+a(n2) 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 


Bj?rn Helgaso #4 / 15

Fibonacci Sequence
Sorry ! I forgot to replace the "out" operation in fibbi It should read like this 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 


Lee Dick #5 / 15

Fibonacci Sequence
Quote:
>> Besides defining the sequence a1=1,a2=1,an=a(n1)+a(n2) >In J this script will create as many fibonacci numbers as you like > NB. a1=1,a2=1,an=a(n1)+a(n2) > 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 nth 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 nth 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 


W. LeRoy (AKA MrWiza #6 / 15

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 


Roger Hu #7 / 15

Fibonacci Sequence
I should draw your attention to Eugene McDonnell's fabulous paper "Heron's Rule & IntegerArea 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 


Murray Eisenbe #8 / 15

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: 4135452859 (W) University of Massachusetts 4135491020 (H) Amherst, MA 01003 Fax: 413545180

Sat, 03 Oct 1998 03:00:00 GMT 


Reiter Clifford #9 / 15

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) 4246 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_2n1 in terms of f_n and f_n1. 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) 5860 where I showed how to speed things up more by taking bigger jumps: eg, f_3n and f_3n1 in terms of f_n and f_n1 and in fact showed how to use "FixedPoint" (like ^:_ but applied to symbolic arithmetic) to generate canonical forms for f_kn and f_kn1 in terms of f_n and f_n1. 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, 6102505277

Sat, 03 Oct 1998 03:00:00 GMT 


Lee Dicke #10 / 15

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 (1r)^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 =. (1r)%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 


Kevin Johns #11 / 15

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 > (1r)^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=(1Sqrt(5))/2 then F(n)=(x^ny^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,[(n1)/2,(n2)/2])/2^(n1) 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,[(n1)/2,n/2)])=2^(n1) 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 


Robert Isra #12 / 15

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 > (1r)^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 floatingpoint 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 floatingpoint 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 floatingpoint numbers is timeconsuming. 
Department of Mathematics (604) 8223629 University of British Columbia fax 8226074 Vancouver, BC, Canada V6T 1Y4

Sun, 04 Oct 1998 03:00:00 GMT 


Roger Hu #13 / 15

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 nth 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 fixedword 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, noninteger 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 nth 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. 2t 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 nth 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 nth element of the sequence obtains by repeated multiplication by M or, equivalently, by multiplication by the nth power of M. The nth 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 nth 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 nth element is required; if elements i.n (0 1 2 ... n1) 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 


John R. Clar #14 / 15

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 [1] 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 


David Ullric #15 / 15

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 


