FIBONACCI FIB PRINT

FIBONACCI FIB PRRINT

Write a program that prints out a list of fibonacci numbers in a language of your choice.


/*        I'm using C, you LISPing cretins.         /
/  Remember to use your hot, stripping [coed] tags */

#include <stdio.h>

fibonacci (int fibs)
{
    int count, big = 0, small = 1;
    for (count = 0; count <= fibs; count++)
    {
        printf("\n#%2d - %10d", count, big);
        big = big + small;
        small = big - small;
    }
}

main()
{
    int x;
    printf("Enter the highest fib that you want to see: ");
    scanf("%i", &x);
    fibonacci (x);
}
Your move.

>>1
Won't work once you reach 0x7FFFFFFF, which should be at fib(46) or so.

Here's a REAL and PROPER/NON-HACKY solution:

(defun memoize (fn)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind (val win) (gethash args cache)
          (if win
              val
              (setf (gethash args cache)
                    (apply fn args)))))))

(defun fibs (n)
  (case n
    (0 0)
    (1 1)
    (2 1)
    (t (+ (fibs (- n 2)) (fibs (- n 1))))))

(setf (symbol-function 'fibs) (memoize #'fibs))

;; reads a number and prints 0-number fibs
(let ((*read-eval*) nil)
  (dotimes (i (read)) (print (fibs i))))

;;; Speed is decent, but memory usage is wasteful. A cutomized memoization function using arrays is possible, and here's a toy example of it:

(defun memoize-special (fn)
  (declare (optimize (speed 3) (safety 0) (debug 0))) 
  (let ((cache (make-array 1000 :adjustable t :initial-element nil)))
    #'(lambda (n)
        (let ((val (aref cache n)))
          (if val val
              (setf (aref cache n)
                    (funcall fn n)))))))


;;; Here's a zomgoptimized version for the ctards:
(defun print-fibs-to-n (n)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (do
   ((previous 1 current)
    (current 0 (+ previous current))
    (k 0 (1+ k)))
   ((= k n) current)   
    (print current)))

(let ((*read-eval*) nil)
  (print-fibs-to-n (read)))

Oh fuck, I keep forgetting the damn code tags:

(defun memoize (fn)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind (val win) (gethash args cache)
          (if win
              val
              (setf (gethash args cache)
                    (apply fn args)))))))

(defun fibs (n)
  (case n
    (0 0)
    (1 1)
    (2 1)
    (t (+ (fibs (- n 2)) (fibs (- n 1))))))

(setf (symbol-function 'fibs) (memoize #'fibs))

;; reads a number and prints 0-number fibs
(let ((*read-eval*) nil)
  (dotimes (i (read)) (print (fibs i))))

;;; Speed is decent, but memory usage is wasteful. A cutomized memoization function using arrays is possible, and here's a toy example of it:

(defun memoize-special (fn)
  (declare (optimize (speed 3) (safety 0) (debug 0))) 
  (let ((cache (make-array 1000 :adjustable t :initial-element nil)))
    #'(lambda (n)
        (let ((val (aref cache n)))
          (if val val
              (setf (aref cache n)
                    (funcall fn n)))))))


;;; Here's a zomgoptimized version for the ctards:
(defun print-fibs-to-n (n)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (do
   ((previous 1 current)
    (current 0 (+ previous current))
    (k 0 (1+ k)))
   ((= k n) current)   
    (print current)))

(let ((*read-eval*) nil)
  (print-fibs-to-n (read)))