Saturday, September 10, 2022

DM42: Recursive Fibonacci by Marko Draisma

DM42:  Recursive Fibonacci by Marko Draisma


The programs on today's entry is provided from Marko Draisma and they are provided with permission and a request.  Gratitude to Marko.


DM42 (and Free42/Plus42) Program: FIBO (Marko Draisma)


This recursive program generates the nth Fibonacci number.  FIBO is a recursive program because it calls itself in the program steps.


LBL "FIBO"

LSTO "N"

X>0?

GTO 00

0

RTN

LBL 00

1

RCL "N"

X>Y?

GTO 01

1

RTN

LBL 01

RCL "N"

1

-

XEQ "FIBO"

LSTO "M"

RCL "N"

2

-

XEQ "FIBO"

RCL "M"

+

END



1st Fibonacci number:  1 FIBO returns 1

2nd Fibonacci number:  2 FIBO returns 1

3rd Fibonacci number:  3 FIBO returns 2

4th Fibonacci number:  4 FIBO returns 3

5th Fibonacci number:  5 FIBO returns 5

6th Fibonacci number:  6 FIBO returns 8

7th Fibonacci number:  7 FIBO returns 13


The LSTO Command


This is the local store command.  Local variables are created only for the purpose of the program and are deleted when the program hits either a return command (RTN) or an end command (END).  


Variables created by the LSTO command are named variables.  We cannot create local variables to numeric registers.   There is no storage arithmetic with LSTO.  


LSTO is available for the Swiss Micros DM42, Free42, and the Plus42.


Execution Time of FIBO


The execution time of FIBO depends on how large the entry n. Calculating the 50th Fibonacci number, 12,586,269,025, takes over 12 minutes. Marko provides a fast tail recursion version, as presented next.  


DM42 (and Free42/Plus42) Program: FIBO2 (Marko Draisma)


00 { 80-Byte Prgm }

01▸LBL "FIBO2"

02 FS? 01

03 GTO 01

04 LSTO "N"

05 1

06 LSTO "B"

07 0

08 LSTO "A"

09 SF 01

10 XEQ "FIBO2"

11 RTN

12▸LBL 01

13 RCL "N"

14 X≠0?

15 GTO 02

16 CF 01

17 RCL "A"

18 RTN

19▸LBL 02

20 RCL "A"

21 ENTER

22 RCL+ "B"

23 LSTO "A"

24 X<>Y

25 LSTO "B"

26 RCL "N"

27 1

28 -

29 LSTO "N"

30 XEQ "FIBO2"

31 END


Getting the 50th Fibonacci number with FIBO2 is snap.   


Thanks once again to Marko Draisma.


See you next time,


Eddie 


All original content copyright, © 2011-2022.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author. 


Matrices in Python without Numpy: Part 1

Matrices in Python without Numpy:  Part 1 Introduction Python is a wonderful programming language and is a welcome addition to graphing calc...