03-31-2013, 12:24 AM

This program does a brute force search for the shortest Egyptian Fraction that is equal to the fraction that you enter. It returns the first solution it finds (there might be many).

This is my first attempt at a meaningful program on the WP-34s. It feels clunky and way too long, but for a first attempt at a 34s program, I was just happy to get it to work.

I suspect Valentin could whip this out in 4 or 5 lines on the 71b.

This operates in 64 bit integer mode. It will also work in 32 bit integer mode (just change the one instruction at the beginning), but it will overflow much easier. It currently makes no attempt to detect overflows - something I really should have put in.

##########################################################################

# Calculate Egyptian Fraction

# Invoke with:

# Numerator in Y

# Denominator in X

#

# 1) Only works if numerator < denominator (i.e. Y/X < 1)

# 2) Only works on positive numbers

# 3) Does not check for overflow (which can happen)

# 4) Runs in 64 bit integer mode; restores your original mode when done.

# 5) Sets stack size to 4. Current code will not work with stack size 8.

#

# When it has found a solution, the program will stop and display

# the denominator of the first fraction. Hit R/S to display the next

# denominator, and so on. It will display 0 after the last fraction.

#

##########################################################################

1 LBL 'EGF'

2 LocR 004

3 STOM .03

4 BASE 10 ; Calculations depend on integer math

5 WSIZE 64 ; Word size limits the range

6 SSIZE4 ; Code needs modification for SSIZE8

7 CF 00

8 STO .01 ; Denominator stored in .01

9 R DOWN

10 STO .00 ; Numerator stored in .00

11 1

12 STO 20 ; Holds the search length (number of terms)

13 LBL 01 ; Start with one term and hunt for shortest sequence

14 1

15 0

16 X<=? 20 ; This code only supports a max of 10 terms

17 GTO 02

18 RCL .00

19 RCL .01

20 GCD

21 STO .02

22 0

23 RCL .01

24 RCL .02

25 /

26 RCL .00

27 RCL .02

28 /

29 2

30 R DOWN

31 XEQ 03 ; Call the recursion that does the search

32 FS? 00 ; If the flag is set, we found a sequence

33 GTO 02

34 1

35 STO+ 20

36 GTO 01

37 LBL 02

38 1

39 STO .00

40 LBL 06 ; Ouput the denominators 1 by 1

41 0

42 X=? 20

43 GTO 07

44 RCL->.00

45 STOP

46 2

47 STO+ .00

48 1

49 STO- 20

50 GTO 06

51 LBL 07

52 RCLM .03

53 0

54 RTN

##########################################################################

# Recursively search for a sequence of terms that works

##########################################################################

55 LBL 03

56 LocR 011

57 STOS .00

58 RCL .02

59 X<>? 20 ; If we are the right number of terms

60 GTO 04 ; We have either found something or need to leave

61 0

62 X<>? .00 ; If there is a remainder

63 RTN ; We didn't find anything

64 SF 00 ; We have found something

65 RTN

66 LBL 04 ; Continue hunting

67 0

68 X=? .00

69 RTN

70 RCL .01

71 RCL .00

72 +

73 1

74 -

75 RCL .00

76 /

77 STO .04

78 STO .05

79 x>=? .03

80 GTO 05

81 RCL .03

82 STO .05

83 LBL 05

84 RCL 20

85 RCL .02

86 -

87 RCL .04

88 *

89 X<? .05

90 RTN

91 RCL .02

92 2

93 *

94 STO .06

95 1

96 +

97 STO .07

98 1

99 STO->.06

100 RCL .05

101 STO->.07

102 RCL .00

103 RCL->.07

104 *

105 RCL->.06

106 RCL .01

107 *

108 -

109 STO .08

110 RCL .01

111 RCL->.07

112 *

113 STO .09

114 GCD

115 STO .10

116 1

117 STO+ .05

118 RCL .02

119 1

120 +

121 RCL .09

122 RCL .10

123 /

124 RCL .08

125 RCL .10

126 /

127 RCL .05

128 R DOWN

129 XEQ 03

130 FS? 00

131 RTN

132 GTO 05

##########################################################################

133 END