My primality testing code is 6x sooner than Sir Roger Penrose’s
However, I assume he did win the Nobel Prize for Physics in 2020 so I can not actually brag.
Nonetheless, it was a fantastic shock when two pages from Penrose’s notebooks that two columns of code for a Commodore P50 calculator leapt off the web page at me. It’s a UNIX system. I know this! And additional extra that the best hand column is code for testing whether or not a quantity is prime.
Here is the web page from the pocket book:
(When you weren’t acquainted with this code, Penrose has written what it does and the truth that it runs on the Commodore P50)
I’ve a fantastic love for the Commodore P50 as a result of I had one within the late Seventies and recently restored it. And Penrose’s code was of nice curiosity to me as a result of I additionally wrote a primality testing program for it. That is fairly exhausting to do due to the restricted reminiscence within the calculator.
There’s neat trick in Penrose’s code that I could not use due to how I selected to check components. It makes his code extremely gradual however does not require a type of ugly mechanism for storing state that mine does.
Here is my code (on the left) and Penrose’s (on the best) aspect by aspect.
My code Sir Roger Penrose’s
lrn lrn
00 RCL 00 STO
01 – 01 √x
02 INT 02 INT
03 * 03 +/-
04 4 04 x<->y
05 10^x 05 RCL
06 / 06 x<->y
07 RCL 07 x<->M
08 INT 08 x<->M
09 – 09 M+
10 INT 10 x<->M
11 = 11 SKZ
12 SKZ 12 GOTO
13 GOTO 13 15
14 18 14 R/S
15 RCL 15 SKN
16 INT 16 GOTO
17 R/S 17 08
18 1 18 1
19 +/- 19 M+
20 M+ 20 x<->y
21 GOTO 21 x<->M
22 00 22 GOTO
lrn 23 04
lrn
Each these applications work by doing trial division of things ranging from INT(√x) and dealing all the way down to looking for an element. My code does this with precise division (step 06), Penrose does it utilizing repeated subtraction (the M+ of the issue which is made damaging by the +/- in step 03). His use of repeated subtraction makes his code gradual, however it additionally means he is not compelled to retailer the quantity being examined and the present issue being tried within the bizarre encoding I had to make use of (see original blog post, however in brief I take advantage of the reminiscence to retailer a decimal quantity the place the integer half is the quantity being examined and the decimal the present issue divided by 10,000).
Operating my code testing if 199 is prime provides the consequence (it’s!) in 1m44s; Penrose’s code takes 10m37s. I am six instances sooner than Mr. Nobel over there! However he will get to make use of a neat trick that I do not.
The Commodore P50 has one register that the programmer can use: the reminiscence. The reminiscence is accessed by the STO (retailer within the reminiscence), RCL (recall from reminiscence), M+ (add to reminiscence), and Mx (multiply reminiscence) buttons. However there are two non permanent registers known as x and y. x is the worth that is at present on display and y is the opposite operand for a two operand operation like 6 + 7.
For instance, in 6 + 7 the 7 on display will likely be in x and the 6 in y. It is really doable to entry y by the x <-> y button which swaps them. Penrose’s trick is to by no means use an operation requiring two operands. Through the use of M+ solely to do repeated subtraction (and increment the trial issue every time around the loop), the y register is rarely touched and subsequently he will get to make use of it for storage.
So, he shops both the quantity being examined or the present consider y. And by cautious use of x <-> M (which swaps the on display quantity and reminiscence) he is in a position to preserve each numbers he wants with out resorting to my encoding trickery.
It is very elegant (if gradual).
The opposite factor that is good about his code is that it requires no arrange (whereas mine requires first storing the quantity and INT(√x) within the encoded type).
(When you loved this you would possibly take pleasure in Double-checking Dawkins)