Fibonacci numbers (dc)

From LiteratePrograms
Jump to: navigation, search
Other implementations: bc | C | C Plus Plus templates | dc | E | Erlang | FORTRAN | Haskell | Icon | Java | JavaScript | Lisp | Lua | occam | Oz | PIR | Prolog | Python | Sed | sh | sh, iterative | T-SQL | Visual Basic .NET

The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by


 F(n) =
 \begin{cases}
   0             & n = 0 \\
   1             & n = 1 \\
   F(n-1)+F(n-2) & n > 1 \\
  \end{cases} .

Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.


The Fibonacci numbers in dc:
This program will calculate all Fibonacci numbers up to a given max value, and the number following that.

Contents

[edit] Setup

We store the 2 first Fibonacci numbers on the primary stack.

<<fib.dc>>=
0p 1p

The max value is stored in register S.

<<fib.dc>>=
10000000000000000000sS

[edit] Macro definition

A macro for calculating the next Fibonacci number is stored in register m.
The macro ends in a command to execute itself, if register S is greater than the number on top of the stack. This is how we implement loops in dc.

<<fib.dc>>=
[sa d la + sr la lr p  d lS >m]sm

[edit] Running the macro

This command will execute the macro stored in register m.

<<fib.dc>>=
lmx

[edit] Running the script

This is how to execute this script:

dc <fib.dc

Note: dc does not like extra carriage-return characters at end of line, so downloading it with Windows file encoding will give you some error messages.

Download code
hijacker
hijacker
hijacker
hijacker