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. 

DM41 and DM42: Self Timing Programs

 DM41 and DM42: Self Timing Programs

Timing a Program's Performance

The Swiss Micros calculators DM41 (including the DM41L, DM41X, Hewlett Packard HP 41CX, HP41C with a Time Module installed) and DM42 have an internal clock which allows us to set the date and time on the calculator.  With the use of the TIME function we can determine the how long a program takes to execute.

One structure that can be used:

[ preliminary storage]

TIME

HR (DM 41), →HR (DM 42)

STO Rxx  (register xx)

[ loop/main program starts here ]

TIME

HR (DM 41), →HR (DM 42)

RCL Rxx

-

ABS 

3600

*

The routine TIME, HR, RCL xx, -, ABS, 3600, * determines the amount of time in term of seconds.  

DM42S:  Accessing the TIME function:  [SHIFT], [ + ] (CATALOG), [down arrow], ( TIME )  ("F1")

Let's demonstrate this technique on three examples.  The time record is the calculator ran on batteries.  

Example 1:  40th Fibonacci Numbers 

Registers:  

R01:  counter

R02:  sum

R03:  time

(counter of 39 is set because the first Fibonacci number is loaded at the beginning)

DM41 Program TFIB

01  LBL ^T TFIB

02  39

03  STO 01

04  0

05  STO 02

06  TIME

07  HR

08  STO 03

09  1

10  0

11  +

12  LBL 00

13  LASTX

14  X<>Y

15  +

16  DSE 01

17  GTO 00

18  TIME

19  HR

20  RCL 03

21  -

22  ABS

23  3600

24  *

25  STO 03

26  END

Y:  Results:  102334155.0

X: Seconds:  0.5100

DM42 Program TFIB

00  {45-Byte Prgm}

01  LBL "TFIB"

02  39

03  STO 01

04  0

05  STO 02

06  TIME

07  →HR

08  STO 03

09  1

10  0

11  +

12  LBL 00

13  LASTX

14  X<>Y

15  +

16  DSE 01

17  GTO 00

18  TIME

19  →HR

20  RCL 03

21  -

22  ABS

23  3600

24  ×

25  STO 03

26  END

Y:  Results:  102334155.0

X: Seconds:  0.0200

Example 2:  The Sum of Cubes Using a Loop from 1 to 250

Registers:  

R01:  counter

R02:  sum

R03:  time

DM41 Program TSUM

01  LBL ^T TSUM

02  250

03  STO 01

04  0

05  STO 02

06  TIME

07  HR

08  STO 03

09  LBL 00

10  RCL 01

11  3

12  Y↑X

13  ST+ 02

14  DSE 01

15  GTO 00

16  RCL 02

17  TIME

18  HR

19  RCL 03

20  -

21  ABS

22  3600

23  *

24  STO 03

25  END

Y:  Results:  984390625.0

X: Seconds:  12.07

DM42 Program TSUM

00  {45-Byte Prgm}

01  LBL "TSUM"

02  250

03  STO 01

04  0

05  STO 02

06  TIME

07  →HR

08  STO 03

09  LBL 00

10  RCL 01

11  3

12  Y↑X

13  STO+ 02

14  DSE 01

15  GTO 00

16  RCL 02

17  TIME

18  →HR

19  RCL 03

20  -

21  ABS

22  3600

23  ×

24  STO 03

25  END

Y:  Results:  984390625.0

X: Seconds:  0.24

Example 3:  Savage Test

Let A = 1, then for 2499 loops:

A = tan(atan(exp(ln(sqrt(A^2))))) + 1   (radians mode is used)

Registers:  

R01:  counter

R02:  sum

R03:  time

DM41 Program SVGE

01  LBL ^T SVGE

02  2499

03  STO 01

04  1

05  STO 02

06  TIME

07  HR

08  STO 03

09  LBL 00

10  RCL 02

11  X↑2

12  SQRT

13  LN

14  E↑X

15  ATAN

16  TAN

17  1

18  +

19  STO 02

20  DSE 01

21  GTO 00

22  RCL 02

23  TIME

24  HR

25  RCL 03

26  -

27  ABS

28  3600

29  *

30  STO 03

31  END

Y:  Results:  2499.970322

X: Seconds:  246.4500240  (about 4 minutes, 6.45 seconds)

DM42 Program SVGE

00  {51-Byte Prgm}

01  LBL "SVGE"

02  2499

03  STO 01

04  1

05  STO 02

06  TIME

07  →HR

08  STO 03

09  LBL 00

10  RCL 02

11  X↑2

12  SQRT

13  LN

14  E↑X

15  ATAN

16  TAN

17  1

18  +

19  STO 02

20  DSE 01

21  GTO 00

22  RCL 02

23  TIME

24  →HR

25  RCL 03

26  -

27  ABS

28  3600

29  ×

30  STO 03

31  END

Y:  Results:  2500  (just over 2500)

X: Seconds:  13.24

Source:

Burkett, John.  "The Savage Benchmark"  TI-89 / TI-92 Plus Tip List 10.0   July 20, 2002.  http://www.technicalc.org/tiplist/en/files/pdf/tips/tip6_50.pdf   Retrieved November 28, 2020 

Eddie 

PrgCalcPro: Fibonacci Number

PrgCalcPro: Fibonacci Number 

F_n = F_n-1 + F_n-2 via formula ((1+√5)^n) - (1-√5)^n)/(2^n * √5)

Sequence where F0 = 0, F1= 1, F2 = 2, etc.  

Note:  PrgCalcPro, like the MK-61 calculator, has the power function x^y.  That is, x has the base and y is the exponent.   On the ProCalcPro, then the power function is executed, the exponent remains on the y stack and not "consumed".  

Example:

Y: 5

X: 2

Executing x^y leaves 

Y: 5

X: 32 (2^5)

Program:

0: 40  ;  M0

   1: 01  ;  1

   2: 0E  ;  ^ // E^

   3: 05  ;  5

   4: 21  ;  sqr // √ 

   5: 10  ;  +

   6: 24  ;  X^Y

   7: 14  ;  XY // swap

   8: 01  ;  1

   9: 0E  ;  ^ // E^

  10: 05  ;  5

  11: 21  ;  sqr // √ 

  12: 11  ;  -

  13: 24  ;  X^Y

  14: 14  ;  XY // swap

  15: 25  ;  REV // roll down

  16: 11  ;  -

  17: 60  ;  R0

  18: 02  ;  2

  19: 24  ;  X^Y

  20: 14  ;  XY // swap

  21: 25  ;  REV // roll down

  22: 05  ;  5

  23: 21  ;  sqr // √ 

  24: 12  ;  *

  25: 13  ;  /

  26: 50  ;  STOP

This blog is property of Edward Shore,  2016.