;; 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)