Mini-challenge: Fast F(93) on HP-16C

[Joe Horn]

Another thread discusses different ways to generate Fibonacci numbers on the HP-15C. However, due to its 10-digit mantissa, the largest exact result the 15C can output is F(49). But the HP-16C in DEC UNSIGNED mode with WSIZE set to 64 would be able to output F(93) exactly. The fastest HP-16C program to return exact F(n) for any input n between 0 and 93 wins.

A speed comparison for this program between a real HP-16C and the new 15C CE in 16C mode would be interesting.

Although I searched these forums for a 16C Fibonacci program and found none, please forgive me if you already posted one. If so, please share a link to it. Thanks in advance.

EDIT -- I just noticed the "DBL×" function on the 16C. I don't know how that works. Would it enable results bigger than F(93)?

[ThomasF]

Hi Joe!

Thanks for an interesting task!
I just made a small program (17 lines) for calculating F(n) n=[0-93].
I've tested it on my 16C Android version, and it takes about 3 seconds for the 20 decimal digits result for F(93).
But, I'm away for two days and didn't bring my new 15CE
So I have to update with correct timing later ...

Edit: About 3 sec was with 16x speed in the app, with Max speed the result is instant.
And it also gives correct result for F(0)=0

Cheers,
Thomas

[SlideRule]

Although I searched these forums for a 16C Fibonacci program and found none, please forgive me if you already posted one. If so, please share a link to it. Thanks in advance.

a screenshot from TI58C, the programmable calculator! Fibonacci Test

   
a 16C Fibonacci program, yes?

BEST!
SlideRule

[ThomasF]

This is my attempt.
Just enter n then GSB A

Code:

001 LBL A
002 X=0?
003 R/S
004 1
005 X=Y?
006 R/S
007 -
008 STO I
009 0
010 LASTx
011 LBL 0
012 ENTER
013 ENTER
014 RUP
015 +
016 DSZ 
017 GTO 0

Cheers,
Thomas

[Joe Horn]

(08-07-2023 06:04 AM)ThomasF Wrote:  This is my attempt.
Just enter n then GSB A

Code:

001 LBL A
002 X=0?
003 R/S
004 1
005 X=Y?
006 R/S
007 -
008 STO I
009 0
010 LASTx
011 LBL 0
012 ENTER
013 ENTER
014 RUP
015 +
016 DSZ 
017 GTO 0

Cheers,
Thomas

Cool! This gets the right result for F(93) in 50 seconds on an original HP-16C in DEC UNSIGNED mode with WSIZE=64. Unfortunately, it also reveals a bad bug in the 16C mode of the 15C CE, which makes DEC mode useless, namely, digits are often displayed incorrectly, even if the internal value is correct. Example: F(93) is correctly returned in less than 1 second, but it's unreadable because most of its digits are displayed as wrong digits. Pressing the HEX key displays the result in hex, which can be verified to be equal to F(93).

[ThomasF]

(08-07-2023 07:52 AM)Joe Horn Wrote:  Unfortunately, it also reveals a bad bug in the 16C mode of the 15C CE, which makes DEC mode useless, namely, digits are often displayed incorrectly, even if the internal value is correct. Example: F(93) is correctly returned in less than 1 second, but it's unreadable because most of its digits are displayed as wrong digits. Pressing the HEX key displays the result in hex, which can be verified to be equal to F(93).

As mentioned, I left the 15CE at home, must try this when I return!
I just checked it on the go16c app, and there I got the correct result.
Is there any more info on this bug?

Cheers,
Thomas

[Joe Horn]

(08-07-2023 07:59 AM)ThomasF Wrote:  Is there any more info on this bug?

It only seems to happen in DEC mode. Example: repeatedly pressing the 1 key should make 1, then 11, then 111, and so on, appear. But instead, the following numbers SEEM to appear:
1
11
105
1111
11111
111111
1086535
11111111
110717895
1111111111
11111111111
111010447815
and so on, nonsensically but repeatably. When the wrong number appears, it's actually the correct value internally... it's only displayed incorrectly. It's displayed correctly in HEX, OCT, and BIN modes.

However, perhaps we should discuss this bug in its own thread so that large Fibonacci numbers can continue to be discussed in this thread.

[Voldemar]

(08-07-2023 08:15 AM)Joe Horn Wrote:  repeatedly pressing the 1 key

Not only [1] key
222 gives 216 on the screen;
33333 -> -32203;
44444 -> -21092;
55555 -> -09885;
7777 -> 6241;
999 -> 903
DEC is not usable

[MarkB]

Here is my attempt. I don't have a 16C and am patiently waiting for my 15C CE. I've tried it on the Jovial RPN emulator and without changing the speed setting, it took about 15s for F(93).

It is based on the fact that:
F(0) = 0
F(1) = 1
F(2n) = F(n)(2F(n+1) - F(n))
F(2n+1) = F(n+1)^2 + F(n)^2

I've taken inspiration for this solution from this description.

For input larger than 93, it will just turn on the "G" flag.

I've never used a 16C before so not sure if this is particularly good code, but here it is anyway.

Code:


001 LBL A
002 1
003 X<>Y
004 X>Y?
005 GTO 0
006 RTN
007 LBL 0
008 9
009 4
010 X>Y?
011 GTO 1
012 X<>Y
013 SF 5
014 RTN
015 LBL 1
016 X<>Y
017 STO 0
018 0
019 STO 1
020 STO 3
021 1
022 STO 2
023 1
024 2
025 8
026 STO 4
027 LBL 2
028 RCL 4
029 SR
030 STO 4
031 RCL 0
032 AND
033 X=0?
034 GTO 2
035 LBL 3
036 RCL 4
037 X=0?
038 GTO 5
039 RCL 2
040 SL
041 RCL 1
042 -
043 RCL 1
044 x
045 STO 5
046 RCL 1
047 RCL 1
048 x
049 RCL 2
050 RCL 2
051 x
052 +
053 STO 2
054 RCL 5
055 STO 1
056 2
057 RCL 3
058 x
059 STO 3
060 RCL 0
061 RCL 4
062 AND
063 X=0?
064 GTO 4
065 RCL 1
066 RCL 2
067 +
068 STO 2
069 LSTx
070 STO 1
071 1
072 RCL 3
073 +
074 STO 3
075 LBL 4
076 RCL 4
077 SR
078 STO 4
079 GTO 3
080 LBL 5
081 RCL 1
082 RTN

[MarkB]

I realised I wasn't making use of R3 (which was keeping track of the current point in the sequence) so here's a version without that (shaving another second off the time for F(93):

Code:

001 LBL A
002 1
003 X<>Y
004 X>Y?
005 GTO 0
006 RTN
007 LBL 0
008 9
009 4
010 X>Y?
011 GTO 1
012 X<>Y
013 SF 5
014 RTN
015 LBL 1
016 X<>Y
017 STO 0
018 0
019 STO 1
020 1
021 STO 2
022 1
023 2
024 8
025 STO 4
026 LBL 2
027 RCL 4
028 SR
029 STO 4
030 RCL 0
031 AND
032 X=0?
033 GTO 2
034 LBL 3
035 RCL 4
036 X=0?
037 GTO 5
038 RCL 2
039 SL
040 RCL 1
041 -
042 RCL 1
043 x
044 STO 5
045 RCL 1
046 RCL 1
047 x
048 RCL 2
049 RCL 2
050 x
051 +
052 STO 2
053 RCL 5
054 STO 1
055 RCL 0
056 RCL 4
057 AND
058 X=0?
059 GTO 4
060 RCL 1
061 RCL 2
062 +
063 STO 2
064 LSTx
065 STO 1
066 LBL 4
067 RCL 4
068 SR
069 STO 4
070 GTO 3
071 LBL 5
072 RCL 1
073 RTN

For an explanation:

001-014 filters out special cases. If we get past there, then n is in the range 2-93.

015-025 set up initial values:
R0 = n
R1 = F(0)
R2 = F(1)
R4 = 128

026-033 uses R4 to find the largest power of 2 less than n. This will determine how many loops to run. If the result is 2^k then we will do k loops.

034-037, 066-070 are the loop control. We shift R4 right each loop and stop when we get to 0.

At this point, each loop starts with:
R1 = F(k)
R2 = F(k+1)

038-044 calculates (2F(k+1) - F(k)) x F(k) [= F(2k)]
045-052 calculates F(k)^2 + F(k+1)^2 [= F(2k+1)]

055-059 checks if this loop was for an odd number in generating n. If so, then:
060-065 we bump up one by setting R1,R2 = (R2, R1+R2)

071-073 once the loop has finished, R1 has the final result.

I guess squaring could have been done as [RCL 1, ENTER, x], etc, but I felt that [RCL 1, RCL 1, x] is more obvious and I expect they take the same time and certainly use the same number of steps.

[Joe Horn]

(08-08-2023 07:15 AM)MarkB Wrote:  ... so here's a version without that (shaving another second off the time for F(93)...

Wow, good work! 31 seconds for F(93) on a real HP-16C.