(16C) 63-bit LFSR

[AnnoyedOne]

The following program is for the HP-16C "Computer Scientist" calculator. It is not intended to be short/fast but to illustrate some (perhaps) unique features of the 16C.

It is an implentation of a 63-bit LFSR (Linear Function Shift Register), using XOR feedback, to make a 63-bit integer PRNG (Pseudo Random Number Generator). The period of the PRNG is (2^63)-1 or 9.22E18 which is effectively random. Probably more so than the RND function on a scientific calculator.

You can read more about LFSR's here

https://en.wikipedia.org/wiki/Linear-fee...hift_LFSRs

or via any web search (you'll find plenty of hits).

The above does not show the feedback bits for a 63-bit register but that information is easily found. Bits 62 & 63 are the two in this case. Note that these are 1-based numbers but in the computer world 0-based numbers are the norm (2^0 = 1). Bit 0 is the LSB (least significant bit), while 62 is the MSB (most significant bit). 63 bits in total. Also note that some show shift registers left-right (MSB to LSB) rather than right-left (LSB to MSB) used in the computer world. No matter LFSR's are low to high bit. I assume the right-left terminology in this example.

The 16C handles word sizes up to 64-bits. In this example the 63rd (or 64th if you prefer) bit is always zero (0). A "mask" is used to ensure this.

Since the 16C display is only 10 7-segment digits the 16C "window" function will be needed to see all digits.

Obviously a LFSR of any size could be chosen and the program modified accordingly.

I've used the common (assembler code) ';' character to start comments. Obviously those can be ignored when entering the program into a 16C.

Code:


0 F WSIZE                   ;64-bit word size
DEC                         ;Decimal numbers (base 10)
1122334455667788            ;Set a non-zero "seed"
STO 0                       ;
g P/R                       ;Enter programming mode

Code:


001 43, 22, A   g LBL A     ;Program start (label A)
002 45 0        RCL 0       ;Get the current PRNG
003 6           6           ;Move bit 63 (right) to bit 0 (the carry can be ignored as can other bits)
004 3           3           ;
005 42 F        f RRn       ;
006 45 0        RCL 0       ;Now bit 62
007 6           6           ;
008 2           2           ;
009 42 F        f RRn       ;
010 42 10       f XOR       ;Bit 0 = bit 63 x-or bit 62 (ignore other bits)
011 42 B        f SR        ;Shift (right) bit 0 to the carry
012 45 0        RCL 0       ;And into the current PRNG value to form the new
013 43 C        g RLC       ;
014 6           6           ;Create the "mask" 7FFF FFFF FFFF FFFF (63-bits right justified)
015 3           3           ;
016 42 8        f MASKR     ;
017 42 20       f AND       ;Ensure that bit 63 is zero
018 44 0        STO 0       ;Save the new PRNG
019 43 21       g RTN       ;End the program

Code:


g P/R                       ;Exit programming mode
GSB A                       :Next PRNG = 9222 3372 0355 9813 7497

A1

PS: Firstly apologies for not trying this program on a real HP-16C but a simulator (which is obviously buggy).

With a seed of 1122334455667788 the next PRNG value is 2,244,668,911,335,576 not the one shown above.

Also, as a test, a seed of 1 will result in the next PRNG value being doubled (left shift = x2 in binary) until the first "tap" is reached. Thus 1,2,4,8,16... A good test and one that works on my HP-16C.

PPS: My "buggy" HP-16C simulator is gone. I found another one that seems to work better.

https://www.hpcalc.org/details/6047

[Thomas Klemm]

(11-16-2024 03:30 PM)AnnoyedOne Wrote:  

Code:

0 F WSIZE                   ;64-bit word size

Shouldn't that be rather: 40 WSIZE
Shouldn't that be rather: 0 f WSIZE
Okay, now I feel dumb.

(11-16-2024 03:30 PM)AnnoyedOne Wrote:  It is not intended to be short/fast but to illustrate some (perhaps) unique features of the 16C.

While I can see that point, it feels more natural to me to do the bit twiddling on the left side.
But then we can not illustrate RRn and MASKR.
Or is there a good reason for not using word size 63?

Code:

   001 { 43 22  B } g LBL B
   002 {       36 } ENTER
   003 {    44  0 } STO 0
   004 {    42  A } f SL
   005 {    42 10 } f XOR
   006 {    42  A } f SL
   007 {    45  0 } RCL 0
   008 {    43  C } g RLC
   009 {    43 21 } g RTN

Example

Set Word Size

DEC
63
f WSIZE

Calculate Random Numbers

1122334455667788
GSB B

2244668911335576 d

GSB B

4489337822671152 d

GSB B

8978675645342304 d

[AnnoyedOne]

(11-16-2024 11:44 PM)Thomas Klemm Wrote:  Or is there a good reason for not using word size 63?

63 will also work but on a x64 computer there are 64 bits which makes my demonstration program more "convertible". Plus the "tap" numbers and mask can be easily changed for different length LFSR's But if saving a few bytes is your thing...

A1

PS: For a 31-bit LFSR the taps are 31 & 28. Change the 63 to 31 and the 62 to 29 and your period will be (2^31)-1 = 2,147,483,647.

[Thomas Klemm]

(11-17-2024 01:25 PM)AnnoyedOne Wrote:  But if saving a few bytes is your thing...

It's not so much about that but my program also works for different word sizes like: 2, 3, 4, 6, 7, 15, 22, 60, …
But I can see your point.
Thanks for the clarification.

[Thomas Klemm]

Just noticed that our programs don't agree for some input.

Examples:

   600000000000ffff h
A: 400000000001ffff h
B: 400000000001fffe h


   200000000000ffff h
A: 400000000001fffe h
B: 400000000001ffff h

Which one is correct?

[AnnoyedOne]

(11-18-2024 09:02 PM)Thomas Klemm Wrote:  Which one is correct?

As you well know your program is correct. I made a mistake.

I forgot my own statement about 1-based vs 0-based numbers. So the first 63 should be 62 and the 62 should be 61.

The tap table I used uses 1-based numbers so bit 63 is bit 62 in a 0-based scheme. The same with the 62. The second 63 is a mask (number of bits) so that is ok.

For a 31-bit LFSR change the numbers to 30 and 27.

A1

[Thomas Klemm]

From Two Hard Things:

Leon Bambrick Wrote:There are 2 hard problems in computer science: cache invalidation, naming things, and off-by-1 errors.

[rprosperi]

(Yesterday 06:07 AM)Thomas Klemm Wrote:  From Two Hard Things:

Leon Bambrick Wrote:There are 2 hard problems in computer science: cache invalidation, naming things, and off-by-1 errors.

Excellent!! Thanks Thomas, I know just where/how to use this to great effect. Family holidays just got a tiny bit better.

[AnnoyedOne]

There are 10 types of people in the world. Those that know binary and those that don't

For those that don't get it 10 (base 2) = 2 (base 10).

A1

[Thomas Klemm]

I like it when people are self-ironic.