;;  Unlimited Fibonacci sequence generator
;; (C) Vladimir Nesterovsky, vnestr@netvision.net.il
;;      http://www.netvision.net.il/php/vnestr
;;
;; this demonstrates an idea of making your own
;; 'bignums' -- integers not limited by 32 bits
;; representation -- in AutoLISP, so we can generate
;; any Fibonacci number and print it out as a sequence
;; of decimal digits. The only limitation would be
;; the computer recources available.
;;
;; it is entirely possible to use this approach to
;; calculate e.g. exact factorials of large numbers too.

 ;; each "long integer" - "lint" - will be represented
 ;; by a list of its digits. Since there's no limit
 ;; on a list's length in AutoLISP, there will be no
 ;; limit for our big integers as well.

 ;; convert a number into a list of its
 ;; decimal digits, most significant first.
 ;; each digit is just a decimal number in a
 ;; range [0 - 9]
(defun LIST-OF-DIGITS  (A / P R)
  (setq R (rem A 10)
        P (list R))
  (while (>= A 10)
    (setq A (/ (- A R) 10)
          R (rem A 10)
          P (cons R P)))
  P)

 ;; make a lint as a list of a number's
 ;; digits in reversed order (to make it
 ;; a little bit easier to sum lints up).
(defun MAKE-LINT  (N)
  (if (numberp N)
    (reverse (LIST-OF-DIGITS N))
    N)) ;; if not number, assume it's already a lint

 ;; push a value on top of a list, passed
 ;; by its quoted symbol name. we're going
 ;; to need this later.
(defun PUSH (push%val push%sym)
  (set push%sym
    (cons push%val (eval push%sym))))

 ;; add two lints together, producing a sum result.
 ;; each lint is a list of decimal digits, least
 ;; significant digits first. This is of course
 ;; a _very_ inefficient representation choice,
 ;; but it's done mostly for clarity.
 ;; Fill free to improve it. :-)
(defun PLUS-LINT  (A B / X R)
  (setq X 0
        A (MAKE-LINT A)
        B (MAKE-LINT B))
  (while (or A B (not (zerop X)))
    (setq X (+ X (cond ((car A)) (0))
                 (cond ((car B)) (0)))
          R (cons (rem X 10) R)
          X (/ X 10)  ;; carry extra value to next digit
          A (cdr A)
          B (cdr B)))
  (reverse R))

 ;; now we are ready to generate a Fibonacci
 ;; sequence of arbitrary length. Each number
 ;; will be an exact number, however big it may be.

 ;; generate the sequence of Fibonacci numbers
 ;; represented as LINTs
(defun FIBB  (N / FB)
  (setq FB '((1) (1))) ;; fibb(2) = 1, 1
  (if (<= N 2)
    FB
    (repeat (- N 2)
      (PUSH            ;; fibb(n) = fibb(n-1) + fibb(n-2)
        (PLUS-LINT (car FB) (cadr FB))
        'FB))))

 ;; so this have been pretty straightforward so far.
 ;; now all what's left, is just to print these lints out
 ;; in a more human-readable manner.

 ;; convert one LINT into a string of decimal digits
 ;; looking just as a regular integer, only with
 ;; unlimited magnitude.
(defun PRINS-LINT  (A)
  (apply 'strcat
         (mapcar '(lambda (C) (chr (+ C 48)))
                 (reverse A))))

 ;; show Nth Fibonacci number
(defun SHOW-NTH-FIBB (N)
  (PRINS-LINT (car (FIBB N))))

 ;; print out a sequence of LINTs
(defun SHOW-LINTS  (LINTS)
  (princ (mapcar 'PRINS-LINT LINTS))
  (princ))

 ;; show N first elements of Fibonacci sequence
(defun SHOW-FIBB-SEQ (N)
  (SHOW-LINTS (FIBB N)))

 ;; that's it!


(princ "\n Unlimited precision Fibonacci sequence generator")
(princ "\n   by Vladimir Nesterovsky, vnestr@netvision.net.il")
(princ "\n Usage: (SHOW-FIBB-SEQ nn) to see the whole sequence,")
(princ "\n   or (SHOW-NTH-FIBB nn) to see just the Nth number.")
(princ "\n Try (SHOW-NTH-FIBB 171) to see the 171-st fibb' number!")
(princ "\n         ...It'll be quite big. :-) ")
(princ)