Now Reading
My primality testing code is 6x sooner than Sir Roger Penrose’s

My primality testing code is 6x sooner than Sir Roger Penrose’s

2023-11-15 02:51:45

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 
   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


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).

See Also

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)

Source Link

What's Your Reaction?
In Love
Not Sure
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top