HP Forums

You're currently viewing a stripped down version of our content. View the full version with proper formatting.

```So I was just going back to my old calc collection after about a yr.
Notice that the fibonacci prog on my hp48 not quite right
-> n
IF n 1 =<
THEN n
ELSE 0 1 2 n
START  DUP ROT
+
NEXT SWAP
DROP
END
This give the fib number 1 value off.  9th fib # is 21, not 34.  I am sure there's a quick fix.  Much appreciated if anyone can help.  Trying to do a crash course, but it's been over a yr since i played with programming.  Thanks
```

Edited: 8 July 2012, 10:09 p.m.

Quote:
9th fib # is 21, not 34.

The program assumes the modern definition of the first two numbers in the sequence: 0 and 1.

Well, according to that, I guess i have to think of it as F(n) with n starts at 0. but the first term of the sequence is 0 and the 9th term of the sequence is 21, whether as F(8) is 21.

So what would be a quick modification so that we can convert that prog to instead of F(n) with n starts at 0 into something like nth term? can't really have 0th term ;)

Just insert

```1 -
```
in the beginning of the program. Unless, of course, you don't want 0 to be the first term of the sequence.

```So  1 -  would go into

-> n 1 -
IF n 1 =<
THEN n
ELSE 0 1 2 n
START  DUP ROT
+
NEXT SWAP
DROP
END
Tried that but it says invalid when i tried to save it.
```

Edited: 9 July 2012, 12:30 a.m.

Hi.

```«
1 - -> n
IF n 1 =<
THEN n
ELSE 0 1 2 n
START  DUP ROT
+
NEXT SWAP
DROP
END
»
```
Chances are it will work, now.

Note that in your listing, the '-> n' removes the argument from the stack, so the sequence '1 -' will miss the argument to compute the subtraction.

Cheers.

Edited: 9 July 2012, 12:45 a.m.

While my 48GX emulator doesnt like your if, you should realize the -> n removes the argument from the stack, leaving nothing for the 1 - to work with, so you need to put that before the -> to reduce the argument before storing it in n.

Ah - the IF must be enclosd in program quotes to follow the create local.

Edited: 9 July 2012, 12:50 a.m. after one or more responses were posted

Hi, Pete.

Seems that we both found almost the same words to describe the problem... and the solution!

Cheers.

Luiz (Brazil)

Olá Luiz,

In case you missed this thread early this year:

Gerson.

So that seems to work but only if I ask for nth term of 3 or higher.

Asking for 1th term gives -1 . asking for 2th term gives 0. asking for 3th term correctly gives 1. 4th correctly gives 2. 5th correctly gives 3...

Wonder if there's a way to get it to do it perfectly....

Also even the original prog i found out does not quite correctly display F(n): F(0) = -1, F(1) = 0 (incorrect as F(0) should be 0, F(1) should be 1. It does give F(2) correctly as 1 and F(3) correctly as 2.

Edited: 9 July 2012, 1:27 a.m. after one or more responses were posted

Sorry! That's what it's actually like on my HP 50g:

```« 1 - -> n
«
IF n 1 =<
THEN n
ELSE 0 1 2 n
START  DUP ROT +
NEXT SWAP DROP
END
»
»
```

Doesn't give correct results for 1th, 2th term.

I think even my original program didn't give correct results for
F(0) and F(1) either ;(...

Actually I would be happy if we can find a way to correct it so that it could display F(0) = 0, F(1) = 1, F(2)= 1, F(3)= 2, etc...

Would be even better if can design the program to correctly get negafib as seen on wiki page also ;)

Edited: 9 July 2012, 1:35 a.m.

Thanks, Gerson.

I remember seeing the thread, did not remember where to find it. Thanks! 8^)

Cheers.

Luiz

There is stil a shorter way to implement Fibonacci function in user-RPL.

If the convention is

```n  :  0  1  2  3  4  5  6  7  8  9 10 11  12 ...
F_n:  0  1  1  2  3  5  8 13 21 34 55 89 144 ...
```

Then a shorter code may be, with or without local variable :

```«  -> n                            «
« n SIGN 0                        DUP SIGN 0
2 n START                       2 4 ROLL START
OVER + SWAP                  OVER + SWAP
NEXT                            NEXT
DROP                            DROP
»                               »
»
```

Note that none of these implementations need no IF ... THEN ... END structure. The trick is using the SIGN function to get F_0=0

Edited: 9 July 2012, 12:56 p.m. after one or more responses were posted

Quote:
Actually I would be happy if we can find a way to correct it so that it could display F(0) = 0, F(1) = 1, F(2)= 1, F(3)= 2, etc...

Just go back to your first version:

```« -> n
«
IF n 1 =<
THEN n
ELSE 0 1 2 n
START  DUP ROT +
NEXT SWAP DROP
END
»
»
0 FIB  -->  0
1 FIB  -->  1
2 FIB  -->  1
3 FIB  -->  2
4 FIB  -->  3
...
```

Nice trick! Awkwardly both versions don't work for F(0) on the HP 50g in exact mode, but they do work in approximate mode.

--

It looks like SIGN is not defined for 0 (although it is for 0.).

Edited: 9 July 2012, 3:15 a.m.

I apologized. My bad. I also had 1 - in another wrong place.

So everything works. But was just wondering how to modify this to give negafib. Maybe even generalized to any general or imaginary number like in wiki definition ;).

Ca me rappelle quelque chose ;)

2 others way (with the same convention):

`« -> n 'RND(((1+V5)/2)^n/V5,0)' »`
(where V is the square root. Some rounding error if n > 55

or

```« DUP { 0 1 2 4 ROLL START SWAP OVER + NEXT NIP } IFT »
```
( on 48 NIP is SWAP DROP. Work in exact mode on the 50G (ie it gives a 209 digits answer for FIB(1000)

209 digit answer on 50g? wow, can't wait til i finally get around to the 50g ;). still playing with 42s and 28 and 48. Will get to 50g maybe tomorrow.

[quote]It looks like SIGN is not defined for 0 (although it is for 0.). [quote]

yes

0 SIGN returns '?' in exact mode on the 50G

And let's not forgot this beaut:

```«  [[0 1][1 1]] SWAP ^ { 2 1 } GET  »
```

Way to go if you need F for large values, and in the POWMOD variation the only (compact) way to go if you need the last digits of F for really large values.

We're missing the 34S's beautiful:

```    FIB
```

or if you're after the complex analytic extension of this function:

```    [cmplx]FIB
```

- Pauli

Hi

I tried this on my 50G to generalise to complex and negative numbers :

```1 5 SQRT + 2 / 'Phi' STO  @ Gold number
«  -> n '(Phi^n-COS(n*PI)*Phi^(-n))/SQRT(5)' » 'FIB' STO
```

(SQRT, Phi, -> and PI are the symbols for, must be in RADIUS)

Works with negative and complex number. It works fine in exact mode (with all digits)

In real mode, i notice some errors with n>55
F(56)=225851433718. ( must be 225851433717)

it gives the rigth answer in exact mode (do EVAL at the end)

FIB(200)=280571172992510140037611932413038677189525

(3 4) FIB -> (-5248.51130756,-14195.9622889)

Edited: 9 July 2012, 7:47 a.m. after one or more responses were posted

The 34S code is:

```	# [PHI]
x[<->] Y
y[^x]
RCL L
(-1)[^x]
RCL/ Y
-
# 1/[sqrt]5
[times]
```

The same formula though. This doesn't need radians mode to be set.

- Pauli

Very compact !

What does RCL L ? is it like LAST ?

RCL L is the same as LastX on other calculators. Once you've direct RCL access to the stack registers, LastX becomes unnecessary.

- Pauli

i guess there might be some sort of rounding of in real mode? but i am just wondering how precise exact mode is. Is it precise enough to give the correct exact number up to the upper limit of 50g answer?

Edited: 9 July 2012, 9:13 a.m.

Without trigo function it could be :

'(Phi^n-(-1)^n*Phi^(-n))/sqrt(5)'

But this dont work with complex number in the way explained here :
http://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers

Edited: 9 July 2012, 9:30 a.m.

Thank for the explaination.

If there is a future for RPL, could be interesting to have a direct access to the stacks registers with STO-RCL arithmetic

Not sure to really understand your code, but seems something like :

« Phi SWAP DUP2 ^ UNROT 1 NEG OVER ^ UNROT NEG ^ * - 5 sqrt / »

Hi wilpig

In 'exact mode' the only limitation is the memory of the 50G (2 digits take 1 byte) and perhaps the time for calculation

So you can work with number with thousand of digits

2000 ! SIZE

-> 5736

Yes, I always forgot it.

It is really a beautiful algorithm:
- no recursive call
- no stack consumption
- no (explicit) iteration

Whatever the n you ask for, it is only 2x2 matrix multiplications and use no more memory or resources as needed for that specific 2x2 matrix operation.

I may note it same where or stick it on my wall; it is really much more elegant as an explicit iterative computation (no START ... END nor IF…THEN …END structure), only use one specific feature of RPL systems: easy matrix operations.

Nicely said.

Also, notice that the number of internal iterations in on the order of log2(n). That is, F(1000) needs just around 10 iterations! That's because internally matrix exponentiation will use the binary method.

For completeness, here's NEGAFIB:

```<< -> n <<
[[0 1][1 1]] n ABS ^ {2 1} GET
n 0 < n 2 MOD NOT AND {NEG} IFT
>>
>>
```
(I have a feeling there might be a more compact way to write the second line...)

Just a little clearer in RPL+:

```<< =n
[[0 1][1 1]] abs(n) ^ {2 1} at
and(n<0,isEven(n)) {neg} IFT
>>
```

```« -> n                                    «
«
[[0 1]
[1 1]] n ABS ^ {2 1} GET              [[0 1][1 1]] OVER ABS ^ { 3 } GET
n SIGN n ^ *                           OVER SIGN ROT ^ *
»
»                                         »
```

For RPL+, I have no competence.

P.S.: HP28C/S user will be in trouble, ^ is not possible with matrix; '^' have to be replace by MATPOW :

```« -> p
« IF p 0 == THEN IDN
ELSE
IF p 0 < THEN INV END
IF p ABS 1 > THEN
1 CF
p ABS LN 2 LN /
IF DUP FP NOT THEN 1 SF END
IP
-> Mat b
« 1 b START DUP * NEXT
IF 1 FS? THEN 2 b ^ p START Mat * NEXT END
»
END
END
»
»
'MATPOW'
```

Edited: 10 July 2012, 2:42 a.m.

wow, RPL programs are so much shorter to look at compared to RPN....

Quote:
wow, RPL programs are so much shorter to look at compared to RPN....

How so???? The 34S equivalent is:

```        FIB
```

It is hard to get shorter than that :-)

- Pauli

Quote:
```        FIB
```

It is hard to get shorter than that :-)

Is it? ;-)
```        F
```
Franz

Quote:
```        F
```

A base 16 digit isn't the FIB function.

Sorry.

- Pauli

:-D

That's true.

Who, will name the following calculators:

```Calc1         Calc2                     Calc3            Calc4         Calc5           Calc6
FIB            «  -> n                  01 LBL"FIB       01 LBL"FIB"   001-42,21,11    00 STO 0
« n SIGN 0            02 x=0?          02 x=0?       002-43 20       01 x<>t
2 n START           03 RTN           03 RTN        003-43 32       02 0
OVER + SWAP  04 1             04 1          004-44  0       03 x=t?
NEXT                05 LOG           05 0          005- 1          04 GTO 2
DROP                06 LBL 00        06 LBL 00     006-36          05 1
»                     07  RCL+ ST L    07  +         007- 0          07 STO 7
»                        08  DSE ST Z     08  LastX     008-42.21. 0    08 LBL 1
09  GTO 00       09  x><y      009-40          09   STO 6
10 END           10  DSE Z     010-43 36       10   SUM 7
11  GTO 00    011-34          11   RCL 6
12 END        012-42. 5. 0    12   x<>t
013-22  0       13 DSZ
14 GTO 1
15 LBL 2
16 R/S
17 RST
```

Edited: a typo (see following posts).

Edited: 10 July 2012, 10:10 a.m. after one or more responses were posted

1: 34S

2: Any RPL -- 28C or 28S

3: 42S

4: 41C

5: No idea, looks like a voyager but I don't see which. None have LBL in position 22.

6: No idea -- newly added though. This had better be a RPN machine :)

- Pauli

Edited: 10 July 2012, 6:02 a.m.

Quote:
6: No idea -- newly added though. This had better be a RPN machine :)

TI-57, I think. Mine is on the way, BTW :-)

Gerson.

I would be interested in knowing the WP34S code on their FIB function. it may or may not be the most optimized.

Quote:
6: No idea -- newly added though. This had better be a RPN

You right, I have copy it right, but the original may have a typo.
Correct key code is

`001 - 42,21,11 LBL A`

Quote:
I would be interested in knowing the WP34S code on their FIB function. it may or may not be the most optimized.

Just the usual method:

(I've only removed some range checkings)
```         a0 = 0;
a1 = 1;
for (i=1; i<n; i++) {
const unsigned long long int anew = a0 + a1;
a0 = a1;
a1 = anew;
}
return build_value(a1, s);
```

Edited: 10 July 2012, 10:44 a.m.

If we're comparing implementations, here's what ND1 (an iOS RPL calc) does internally:

for real numbers:

```	"fib": function(n) { if (n<0 || n>1400) throw Error("bad arg"); if (n <= 1) return n; var a = 0; var b = 1; var val; for (var i=2; i<=n; i++) { val = a+b; a = b; b = val; } return val; },
```
then in the BigInt class:
```	"fib": function(bn) { return calculator.functions.matrix.pow([[BigInteger.ZERO,BigInteger.ONE], [BigInteger.ONE,BigInteger.ONE]], parseInt(bn.toString()))[1][0]; }
```
where it also re-defines, unobtrusively, the real version like so
```	calculator.functions["fib_real"] = calculator.functions["fib"]; // move built-in function to new place
calculator.functions["fib"] = function(x) { return (x>77 ? BigNum.fib(BigNum.fromNumber(x)) : calculator.functions["fib_real"](x)); };
```

The net effect is that F(77) and lesser are implemented through iteration, and anything above that goes through matrix exponentiation.

The result function is usable as fib or FIB in RPL and other supported languages.

If someone wanted to make fib work like negafib, they'd inject a new implementation of fib and it would do a true overwrite, which "takes" globally. No flashing or app update necessary, as the run-time is a dynamic VM. (The calc is "ROM-less".)

There's also a fibmod function which comes in handy, if you need to solve PE #314...

This is the integer mode version of the code, the parts left out are relatively important -- they deal with setting the overflow flag, handling negatives and limiting the computation to at most 100 iterations -- unsigned 64 bit integers overflow at Fib(93). I do not believe it is worth optimising this code for speed (space is always worthwhile).

The complex and real versions are elsewhere (see my earlier message below). If you can find any productive optimisations in this code, I'd be interested & a bit surprised.

- Pauli

Edited: 10 July 2012, 5:50 p.m.

This simple program doesn't work for me on a 48G: and even outside the program, I cannot raise a square matrix to any power, although I can multiply that matrix by itself, and multiply the result by the original matrix.

I can raise a square matrix to a power on the 50G, so I think I know what I'm doing.

What am I doing wrong, if anything?

How about moving anew declaration outside the loop? Presumably the compiler does that for you...

The compiler does this kind of thing very well. That declaration isn't allocating space each time through the loop.

There is a double word value being spilled to the stack but this looks to be a consequence of the overflow checking code, that wasn't included above, requiring an extra double length integer value and some double length operations.

- Pauli

I don't think it could be made smaller, but you could make it slightly faster, at the expense of some code space:

```         a0 = 0;
a1 = 1;
for (i=0; i<(n >> 2); i++) {
a0 += a1;
a1 += a0;
}
return build_value((n & 1) ? a1 : a0, s);
```

As I noted, faster isn't relevant here -- a maximum of 100 iterations of at most a few dozen instructions running on a tens of MHz CPU. Smaller is always relevant -- flash is full.

The actual loop code in question is more complex that Franz listed before:

```long long int intFib(long long int x) {
int sx, s;
unsigned long long int v = extract_value(x, &sx);
const enum arithmetic_modes mode = int_mode();
unsigned long long int a0, a1;
unsigned int n, i;
long long int tbm;
/* Limit things so we don't loop for too long.
* The actual largest non-overflowing values for 64 bit integers
* are Fib(92) for signed quantities and Fib(93) for unsigned.
* We allow a bit more and maintain the low order digits.
*/
if (v >= 100) {
set_overflow(1);
return 0;
}
set_overflow(0);
n = v & 0xff;
if (n <= 1)
return build_value(n, 0);
/* Negative integers produce the same values as positive
* except the sign for negative evens is negative.
*/
s = (sx && (n & 1) == 0)?1:0;
/* Mask to check for overflow */
if (mode == MODE_UNSIGNED)
tbm <<= 1;
/* Down to the computation.
*/
a0 = 0;
a1 = 1;
for (i=1; i<n; i++) {
const unsigned long long int anew = a0 + a1;
if ((anew & tbm) || anew < a1)
set_overflow(1);
a0 = a1;
a1 = anew;
}
return build_value(a1, s);
}
```

I fear the overflow test would have to be duplicated as well.

Also, care has to be taken with space optimisations. A target build is usually required to see if an optimisation actually does save anything...

- Pauli

You're doing nothing wrong. Indeed, you need a HP-49 or 50g (or ND1) for this.

In that case #5 is the HP 15C, HP 15C LE or DM 15CC.

- Pauli

Quote:

Just the usual method:

(I've only removed some range checkings)

```         a0 = 0;
a1 = 1;
for (i=1; i<n; i++) {
const unsigned long long int anew = a0 + a1;
a0 = a1;
a1 = anew;
}
return build_value(a1, s);
```

Looks nice and short ;). you one of the wp34s developers? i just ordered one of those ;)

Quote:
you one of the wp34s developers?

No, not a developer but rather a supporter. ;-)

(I've written a few programs for the WP34s library)
Quote:
i just ordered one of those ;)

Good decision! :-)

Franz

The real and complex versions are smaller. They are both essentially:

```	# [PHI]
x[<->] Y
y[^x]
RCL L
(-1)[^x]
RCL/ Y
-
# 1/[sqrt]5
[times]
```

Yes, it is an almost normal keystroke programme.

I hope you enjoy your 34S once it arrives.

- Pauli

Quote:
(I've written a few programs for the WP34s library)

The built in quadratic solver too.

- Pauli

cant wait to get mine in the mail. so there's no change i would need to make to any of the hp 42s progs to run on wp34s?

i am guessing the CPU on 34s is many many times faster than that of the 42s? just wish the memory a bit more generous...

Quote:
cant wait to get mine in the mail. so there's no change i would need to make to any of the hp 42s progs to run on wp34s?

There will be changes. Matrix support, complex support and some alpha is a bit different.

Quote:
i am guessing the CPU on 34s is many many times faster than that of the 42s? just wish the memory a bit more generous...

Yes, many times faster. Not all functions are necessarily faster. The 34S carries much higher internal precision and this costs. More memory is one of the leading shortcomings of the hardware platform :-(

- Pauli

Thanks, Oliver. That explains why it's not a One-Minute Marvel:

I found that a bunch of the 1-min marvels don't work on the 49 and 50g (if that makes you feel better as a 48 user...).

Quote:
I found that a bunch of the 1-min marvels don't work on the 49 and 50g (if that makes you feel better as a 48 user...).

So which calc do they work on then? I thought the 49 and 50g supposed to be the do it all more than anything before them

The 1-min marvels are a specific set of UserRPL programs that were written for the 48 series, on which they all work.

If you ask me, the 49 / 50g calcs are a *huge* step forward. They have substantial improvements in many areas and entire new abilities (such as symbolic vectors/matrices, BigInteger support, etc.). But there're a few incompatibilities with the 48 series.

Edited: 11 July 2012, 5:46 p.m.

The line 06 in your Calc6 program is missing. I haven't been able to figure out what it should be, but the following works:

``` Calc6
00  32 0  STO 0
01  22    x<>t
02  00    0
03  66    x=t?
04  51 2  GTO 2
05  32 7  STO 7
06  01    1
07 -34 0  INV SUM 0
08  86 1  LBL 1
09  32 6    STO 6
10  34 7    SUM 7
11  33 6    RCL 6
12  22      x<>t
13  56    DSZ
14  51 1  GTO 1
15  86 2  LBL 2
16  81    R/S
17  71    RST
```

Only the lines 05 through 07 have been changed.

Hi Oliver,

in general,if you choose 'Approx mode' and if you enter all numbers with a . and the end, a 48 program should work on 49/50

On the 48 series, 10 is the same as 10. , but not in the 49/50.
10 is a real and works like 10. in the 49/50 series

10 is an integer (infinite integer) on 49/50 and work in a different way

Edited: 12 July 2012, 5:51 a.m. after one or more responses were posted

Hi Gilles,

Understood.

But there're other backwards incompatibilities, too.

Here's One-Minute marvel #1 (A1. Next Prime):

```\<< DUP \v/ \-> s \<< DUP 2 MOD { 3 WHILE DUP2 MOD OVER s < AND REPEAT 2 + END DUP s > {DROP DUP} IFT} 2 IFTE \>> \>>
```

It won't return correct values on a 49/50g (try "6." as input, for example), even if you add a decimal point to all numbers in the program. Not sure why (needs debugging). But then, the 49/50g have a NEXTPRIME function built in...

Are you sure of the code ?

```\<< DUP \v/ \-> s
\<< DUP 2 MOD
{
3
WHILE DUP2 MOD OVER s < AND
REPEAT
2 +
END
DUP s > {DROP DUP} IFT
}
2
IFTE
\>>
\>>
```

6 will obviously return

6 2

EDIT : In fact it works fine but it is not a 'Next prime" program :

Quote:
Enter any integer n (greater than 0) and press ‘np’. The original n will be raised to level 2, and the first
prime factor of n will be placed in level 1. To find the next factor, you can press / and then run ‘np’
again.

101 NP
101 101

202 NP
202 2
/
NP
101 101

In UserRPL, approx mode, and be carefull about real/intenger (and screen size...) , the compatibility of a 50 with a 48 program is almost perfect imho

Edited: 12 July 2012, 6:43 a.m.

Gosh, you're right! It's called 'Next Prime' but it really is 'Next Prime Factor' as per description, and I overlooked that. The result on 50g is just fine.

I guess the purpose of 'np' is to be a helper function for the next marvel, 'pf' (Prime Factors), which does what the name suggests, and, for which, too, a 49/50g built-in function exists: FACTOR

'LG' and 'lg' produced different results than the documentation indicated but this just seems to be a write-up error, as the results also don't match on a 48, where I just tried these functions.

On the original topic, let me clarify that this given code does not run on a 48 *not* because of an incompatibility, but because the 48 misses the matrix exponentiation feature that the 49/50g has. (That is, "[[0 1][1 1]] 10 ^" works on a 49/50g, but not on a 48. You get a "BAD ARGUMENT TYPE", if you try. Note that it must be "10" and not "10." on 49/50g, or you get the same error.)

Quote:
In UserRPL, approx mode...

In my experience, true backwards incompatibilities exists between 49 and 48 when it comes to the handling of exceptional cases.

For example, marvel 'GCDb' relies on 153 0 MOD returning 153, which is, mathematically speaking completely wrong. But it is the behavior on a 48 *and* of a 49/50g in approximate mode. In exact mode (and that's how I use it almost always), "?" is returned. Which is far more correct, but makes code that relies on the old behavior fail.

That is, 'GCDb' fails in exact mode (though exact mode does the right thing) and succeeds in approx mode (though approx mode does the wrong thing).

(WolframAlpha will tell you that 153 mod 0 is "indeterminate", and ND1 gives you a "NaN", which is the numeric equivalent.)