amigo@milton.u.washington.edu (The Friend) (04/12/91)
Can someone send me source code for a routine to calculate
Fibonacci numbers to _x_ (x being input from user)? Additionally it'd
be great if this found the PRIME numbers in the set. It could print its
results as it went through (if that makes it any easier).
Thanks..
--
--------------------------------------///------------------------------------
Scott Rowin /// amigo@milton.u.washington.edu
*********** ///
- SPACE OPEN FOR LEASE - \-\_/// Amigas really do it better...dave@cs.arizona.edu (Dave Schaumann) (04/13/91)
In article <1991Apr12.051844.15063@milton.u.washington.edu> amigo@milton.u.washington.edu (The Friend) writes: > Can someone send me source code for a routine to calculate >Fibonacci numbers to _x_ (x being input from user)? Additionally it'd >be great if this found the PRIME numbers in the set. It could print its >results as it went through (if that makes it any easier). This sounds a lot like a freshman-level programming assignment to me... Consider: o The definition of the Fibonacci sequence is usually no more than one step of translation away from a working algorithm. o Finding prime numbers may be a little harder, but not much. -- Dave Schaumann | We're so sorry, Uncle Albert. But the kettle's dave@cs.arizona.edu | on the boil, and we're so *easly* called away...
jrbd@craycos.com (James Davies) (04/13/91)
In article <1991Apr12.051844.15063@milton.u.washington.edu> amigo@milton.u.washington.edu (The Friend) writes: > > Can someone send me source code for a routine to calculate >Fibonacci numbers to _x_ (x being input from user)? Additionally it'd >be great if this found the PRIME numbers in the set. It could print its >results as it went through (if that makes it any easier). Well, this program only prints the final answer, and doesn't find the primes, but you should be able to modify it to do those things. Usage: "a.out N" prints the Nth fibonacci number. Good luck! -- jd p.s. What can I say, it's Friday (although not April 1 any more)... ------------ %< cut here ---------------- #define A atoi #define E exit #define I int #define O main #define U printf #define Y char ** #define W return I O(c,v)I c;Y v;{W(v&&((c<2)?(U("?\n"),E(1)):1))?(U("%d\n",O(A(*++v)+1,(Y)0)-2), 0):((c>3)?O(c-1,(Y)0)+O(c-2,(Y)0)-2:3);}
jroth@allvax.enet.dec.com (Jim Roth) (04/14/91)
In article <1991Apr12.051844.15063@milton.u.washington.edu>, amigo@milton.u.washington.edu (The Friend) writes... > > Can someone send me source code for a routine to calculate >Fibonacci numbers to _x_ (x being input from user)? Additionally it'd >be great if this found the PRIME numbers in the set. It could print its >results as it went through (if that makes it any easier). Hmm... sounds like a tough homework assignment :-) Anyhow, here's a FORTRAN program that computes a few Fibonacci numbers using a Cauchy's residue theorem and the fast Fourier transform; you can always translate it to c... - Jim PROGRAM FIBONACCI C C Compute some Fibonacci numbers C IMPLICIT NONE INTEGER*4 LOGN, NPTS, NFIB, IPASS, I, J, K, L COMPLEX*16 T, U, V, W, Z, Z0, A(64) REAL*8 PI, X, R DATA PI/3.14159265358979323846264338D0/ C C Generating function for Fibonacci numbers C COMPLEX*16 F F(Z) = 1.0/(1.0-Z-Z**2) LOGN = 6 NPTS = 2**LOGN NFIB = 2**(LOGN-1) Z0 = 0.0 R = 0.4 C C Approximate contour integrals with trapezoidal rule using FFT C W = DCMPLX(DCOS(2.0*PI/NPTS), DSIN(2.0*PI/NPTS)) V = R A(1) = F(Z0+V) A(2) = F(Z0-V) J = 0 DO I = 1,NPTS/2-1 V = V*W K = NPTS 100 CONTINUE K = K/2 J = J.XOR.K IF ((J.AND.K).EQ.0) GOTO 100 A(J+1) = F(Z0+V) A(J+2) = F(Z0-V) ENDDO L = 1 DO IPASS = 1,LOGN U = 1.0 W = DCMPLX(DCOS(PI/L), -DSIN(PI/L)) DO J = 1,L DO I = J,NPTS,2*L K = I+L T = A(K)*U A(K) = A(I)-T A(I) = A(I)+T ENDDO U = U*W ENDDO L = L+L ENDDO C C Denormalize series coefficients C X = 1.0D0/NPTS DO I = 1,NPTS A(I) = A(I)*X X = X/R ENDDO C C Show the answer C TYPE 101, (I, DREAL(A(I)), I=1,NFIB) 101 FORMAT (1X, I10, F28.1) STOP END
scavo@cie.uoregon.edu (Tom Scavo) (04/14/91)
In article <1991Apr12.051844.15063@milton.u.washington.edu> amigo@milton.u.washington.edu (The Friend) writes: > > Can someone send me source code for a routine to calculate >Fibonacci numbers to _x_ (x being input from user)? Additionally it'd >be great if this found the PRIME numbers in the set. It could print its >results as it went through (if that makes it any easier). ;************************************************************************* ; The recursive definition of the Fibonacci sequence yields an O(k^n) ; algorithm, where k is the golden ratio = (/ (+ 1 (sqrt 5)) 2). (define (fib1 n) (if (< n 2) n (+ (fib1 (- n 1)) (fib1 (- n 2))))) ;************************************************************************* ; An auxiliary procedure that carries along the previous Fibonacci ; number helps to eliminate redundant calculations and produce O(n) ; behavior. (define (fib2 n) (define (loop i fi fi-1) (if (= i n) fi (loop (+ i 1) (+ fi fi-1) fi))) (cond ((< n 2) n) ((exact? n) (loop 1 1 0)) (else (loop 1 1.0 0.0)))) ;************************************************************************* ; This procedure implements the closed form solution to the Fibonacci ; difference equation. Its efficiency hinges on the unknown efficiency ; of some primitive numerical routines. (define (fib3 n) (let ((sqrt5 (sqrt 5.0))) (round (/ (expt (/ ( + 1.0 sqrt5) 2.0) n) sqrt5)))) ;************************************************************************* ; This O(log n) algorithm is an extension of the corresponding algorithm ; for exponentiation of numbers found in just about any introductory ; textbook. Here we take advantage of the fact (given to me by Will ; Clinger) that ; ; n ; | 1 1 | | fn+1 fn | ; | | = | | ; | 1 0 | | fn fn-1 | ; and exponentiate the 2x2 matrix by successive squaring. (define realIdentity '((1.0 0.0) (0.0 1.0))) (define integerIdentity '((1 0) (0 1))) (define (extract M) (caar M)) ; This top level procedure determines the type of its lone argument. (define (fib4 n) (extract (if (exact? n) (power (- n 1) integeridentity) (power (- n 1) realidentity)))) ; The actual calculations take place here. If the exponent is even, ; we square the matrix and halve the exponent since x^n = (x^2)^(n/2) ; when n is even. Otherwise, we factor out an x before squaring. (define power (lambda (exponent identity) (define (exponential i) (cond ((= i 0) identity) ((odd? i) (product (square (exponential (quotient (- i 1) 2))))) (else (square (exponential (quotient i 2)))))) (exponential exponent))) ; This special purpose routine multiplies the 2x2 matrix given at the ; outset of this discussion by its argument. It also takes advantage ; of the fact that x is symmetric. (define (product x) (let* ((a11 (caar x)) (a12 (cadar x)) (a21 a12) ;in general, (caadr x) (a22 (cadadr x))) (list (list (+ a11 a21) (+ a12 a22)) (list a11 a12)))) ; This procedure is a bit more general in that it will square and return ; any 2x2 symmetric matrix. All potentially redundant calculations are ; being performed once and for all. (define (square x) (let* ((a11 (caar x)) (a12 (cadar x)) (a21 a12) ;in general, (caadr x) (a22 (cadadr x)) (trace (+ a11 a22)) (crossproduct (* a12 a21)) (aij (* a12 trace))) ;or (* a21 trace) (list (list (+ crossproduct (* a11 a11)) aij) (list aij (+ crossproduct (* a22 a22)))))) Tom Scavo scavo@cie.uoregon.edu
kahhan@bnr.ca (04/15/91)
In article <1991Apr12.051844.15063@milton.u.washington.edu> amigo@milton.u.washington.edu (The Friend) writes: > > Can someone send me source code for a routine to calculate >Fibonacci numbers to _x_ (x being input from user)? Additionally it'd >be great if this found the PRIME numbers in the set. It could print its >results as it went through (if that makes it any easier). > Why not just use the equation and calculate the nth number directly? Then you could just embed the equation in a loop (for i=1 to n) and you'll have what you want. -- -------------------------------------------------------------------------------- Larry Kahhan - NRA, NRA-ILA, CSG, GOA, GSSA | The opinions expressed here do lkahhan@bnr.ca | not necessarily represent the | views of the management. --------------------------------------------------------------------------------
libes@cme.nist.gov (Don Libes) (04/18/91)
>> Can someone send me source code for a routine to calculate >>Fibonacci numbers to _x_ (x being input from user)? Additionally it'd >>be great if this found the PRIME numbers in the set. It could print its >Well, this program only prints the final answer, and doesn't find the >primes, but you should be able to modify it to do those things. >I O(c,v)I c;Yv;{W(v&&((c<2)?(U("?\n"),E(1)):1))?(U("%d\n",O(A(*++v)+1,(Y)0) >-2),0):((c>3)?O(c-1,(Y)0)+O(c-2,(Y)0)-2:3);} Nice, but why not go all the way and use the Best-Of-Show winner in last year's obfuscated C contest. Given the proper argument it would reverse itself thereby becoming a sort program. Upon sorting the original program (which did differential equations as well) it would produce Fibonacci numbers. Don Libes libes@cme.nist.gov ...!uunet!cme-durer!libes