Faster factor finder method for 42S
11-26-2019, 04:24 PM
Post: #1
 Dave Britten Senior Member Posts: 1,366 Joined: Dec 2013
Faster factor finder method for 42S
There's nothing novel here from a mathematics standpoint - it's just the same old mod-30 sieve we've been doing for decades. Rather, I found a way to use matrices on the 42S to do the trial divisions much faster.

Here's the code with some C-like comments:

Code:
LBL "FACTOR" XEQ "SS"    //Save stack //Store number to factor, and its square root STO 01 SQRT STO 04 //Initialization CLA SF 01 CF 09 //Create the matrix for the first 4 divisors 4 1 DIM "D" INDEX "D" J- 0 2 XEQ 00 1 XEQ 00 2 XEQ 00 2 XEQ 00 STO 00 //Main loop LBL 01 FS? 09        //Completely factored? GTO 09        //Go to exit routine. //Divide the remaining product by all divisors and store fractional parts in "R" RCL 01 RCL "D" ÷ FP STO "R" //See if any remainder is 0 INDEX "R" [MIN] X=0? GTO 02 //See if the current max divisor is greater than the square root RCL 04 RCL 00 X>Y? GTO 06 //First time through the loop, go set up the matrix for the next 8 divisors FS?C 01 GTO 10 //Otherwise add 30 to all divisors for the next loop 30 STO+ "D" STO+ 00 GTO 01        //Back to the start of the loop. //Main loop ends here. //Last factor is the remaining product LBL 06 RCL 01 AIP AVIEW GTO 09 //Factor out the current divisor LBL 02 RDown        //Get the divisor that corresponds to the zero remainder from trial division 1 INDEX "D" STOIJ RCLEL STO 02 CLX        //Initialize factor's power to zero STO 03 LBL 03        //Divide out factor as many times as possible RCL 01 RCL 02 MOD X≠0? GTO 04 LASTX STO÷ 01 1 STO+ 03 GTO 03 LBL 04        //Display update routine RCL 02 AIP 1 RCL 03 X>Y? ├"↑" X>Y? AIP 1        //Check if fully factored RCL 01 X=Y? SF 09 SQRT        //Update the square root of remaining product STO 04 FC? 09        //Append "×" if there are more factors ├"×" AVIEW GTO 01        //Go make another pass with the same set of divisors //Add the next divisor to the divisor matrix using increment in X LBL 00 + STOEL J- RTN //Create the 8-element divisor matrix for passes 2+ LBL 10 8 1 DIM "D" INDEX "D" J- RCL 00 4 XEQ 00 2 XEQ 00 4 XEQ 00 2 XEQ 00 4 XEQ 00 6 XEQ 00 2 XEQ 00 6 XEQ 00 STO 00 GTO 01        //Back to the start of the loop. //Exit & cleanup LBL 09 CF 01 CF 09 XEQ "RS"    //Restore stack END

"SS" and "RS" are the save-stack and restore-stack routines I have on my 42S. You can remove/substitute these calls as needed.

Variables, registers, and flags:

Code:
Regs 00 - Current max divisor 01 - Number to factor/remaining product 02 - Current divisor/factor 03 - Power of current factor 04 - Square root of number to factor/remaining product Flags 01 - First pass 09 - Fully factored Variables "D" - Divisors "R" - Remainders

The basic idea is that rather than repeatedly doing 4, XEQ 01, 2, XEQ 01, 4 XEQ 01... making 8 calls in each loop, all the trial divisors are stored in a matrix and divided all at once. Then FP takes their fractional parts, and the undocumented matrix function [MIN] identifies any of the divisions with no remainder. Found factors get fully divided out and displayed, and if none are found, 30 is added to the divisor matrix and the loop repeats. This continues until the divisors exceed the square root of the remaining product, or the input number has been fully factored down to 1.

A couple of informal timing tests of factoring 9,999,999,971:

Original mod-210 factor finder with incr. XEQ - 1m30s
New matrix-based mod-30 factor finder - 53s

I got the idea from a TI-84 factor finder that uses essentially the same technique with lists. It dawned on me that it could be done with matrices on the 42S.

The code is still kind of rough and unrefined, but I'm seeing execution times cut as much as in half for certain inputs. I haven't yet tried extending this into a full mod-210 algorithm, so there may be more speed gains to be had yet. It would require larger divisor and remainder matrices, though, so more memory would be required to run the program.
11-29-2019, 09:38 AM
Post: #2
 Csaba Tizedes Senior Member Posts: 414 Joined: May 2014
RE: Faster factor finder method for 42S
(11-26-2019 04:24 PM)Dave Britten Wrote:  undocumented matrix function [MIN]
I got the idea from a TI-84 factor finder

Nice, could you post a link or something about this MIN function and the TI-84 factor finder program?

Thanks,
Csaba
11-29-2019, 10:16 AM
Post: #3
 Paul Dale Senior Member Posts: 1,556 Joined: Dec 2013
RE: Faster factor finder method for 42S
Try this message.

Pauli
11-29-2019, 11:27 AM (This post was last modified: 11-29-2019 11:28 AM by grsbanks.)
Post: #4
 grsbanks Senior Member Posts: 976 Joined: Jan 2017
RE: Faster factor finder method for 42S
Or this page, which predates Joe's post by about 5 years

There are only 10 types of people in this world. Those who understand binary and those who don't.
11-29-2019, 01:12 PM (This post was last modified: 11-29-2019 01:13 PM by Joe Horn.)
Post: #5
 Joe Horn Senior Member Posts: 1,579 Joined: Dec 2013
RE: Faster factor finder method for 42S
(11-29-2019 11:27 AM)grsbanks Wrote:  Or this page, which predates Joe's post by about 5 years

The earliest reference is on pages 15-16 of HPX Exchange (August/December 1988), where the verbatim content of my posting above first appeared. For the record, the 3 hidden HP-42S functions were discovered in a Jack in the Box fast-food eatery (23812 El Toro Rd, Lake Forest, California 92630) while eating a cheeseburger, on 9 November 1988. Museums always seek historical context, so there it is.

<0|ɸ|0>
-Joe-
11-29-2019, 01:25 PM
Post: #6
 grsbanks Senior Member Posts: 976 Joined: Jan 2017
RE: Faster factor finder method for 42S
(11-29-2019 01:12 PM)Joe Horn Wrote:  For the record, the 3 hidden HP-42S functions were discovered in a Jack in the Box fast-food eatery (23812 El Toro Rd, Lake Forest, California 92630) while eating a cheeseburger, on 9 November 1988. Museums always seek historical context, so there it is.

Absolutely! Does anyone still know exactly how they were discovered? They're not mentioned in the manual as far as I remember, they don't appear in the function catalog and they don't appear in the matrix menu either. Did someone have access to a ROM listing or something?

There are only 10 types of people in this world. Those who understand binary and those who don't.
11-29-2019, 01:26 PM
Post: #7
 Dave Britten Senior Member Posts: 1,366 Joined: Dec 2013
RE: Faster factor finder method for 42S
(11-29-2019 09:38 AM)Csaba Tizedes Wrote:
(11-26-2019 04:24 PM)Dave Britten Wrote:  undocumented matrix function [MIN]
I got the idea from a TI-84 factor finder

Nice, could you post a link or something about this MIN function and the TI-84 factor finder program?

Thanks,
Csaba

There are sooo many factoring programs for the 83/84 floating around that I honestly couldn't tell you where I found it. Here's the code, though. It also does some clever tricks with End, so it's a bit tough to follow.

Code:
Input "X=",X 0→dim(⌊FACTR 2→D For(B,2,6 While B<Xnot(fPart(X/B Lbl 1 max(B,D→D While fPart(X/D D+2→D End X/D→X Disp D D→⌊FACTR(dim(⌊FACTR)+1 End End For(C,B,√(X),30) If min(fPart(X/(C+{0,4,6,10,12,16,22,24 End If C²≤X Then C→B X→C Goto 1 End X→⌊FACTR(dim(⌊FACTR)+1 ⌊FACTR

For info on the "[MIN]" function (yes, the brackets are included in the function name), see Joe's post linked above.
11-29-2019, 02:04 PM
Post: #8
 Joe Horn Senior Member Posts: 1,579 Joined: Dec 2013
RE: Faster factor finder method for 42S
(11-29-2019 01:25 PM)grsbanks Wrote:
(11-29-2019 01:12 PM)Joe Horn Wrote:  For the record, the 3 hidden HP-42S functions were discovered in a Jack in the Box fast-food eatery (23812 El Toro Rd, Lake Forest, California 92630) while eating a cheeseburger, on 9 November 1988. Museums always seek historical context, so there it is.

Absolutely! Does anyone still know exactly how they were discovered? They're not mentioned in the manual as far as I remember, they don't appear in the function catalog and they don't appear in the matrix menu either. Did someone have access to a ROM listing or something?

I remember how they were discovered, because it was quite thrilling. I used the 42S's built-in memory hex browser/editor (AKA "debugger") to find where programs were stored, then poked every possible hex value into program memory and exited to normal program mode to see what the corresponding commands were. That's how I created the 42S Hex Table (which also appears in that issue of HPX Exchange) and discovered the "hidden functions" lurking in there. What those functions do, and how to use them, was then a matter of trial and error, turbo-powered by a Jack in the Box cheeseburger.

<0|ɸ|0>
-Joe-
11-29-2019, 04:27 PM
Post: #9
 Dave Britten Senior Member Posts: 1,366 Joined: Dec 2013
RE: Faster factor finder method for 42S
(11-29-2019 02:04 PM)Joe Horn Wrote:  I remember how they were discovered, because it was quite thrilling. I used the 42S's built-in memory hex browser/editor (AKA "debugger") to find where programs were stored, then poked every possible hex value into program memory and exited to normal program mode to see what the corresponding commands were. That's how I created the 42S Hex Table (which also appears in that issue of HPX Exchange) and discovered the "hidden functions" lurking in there. What those functions do, and how to use them, was then a matter of trial and error, turbo-powered by a Jack in the Box cheeseburger.

That's a clever way to do it! I wonder why they went undocumented/hidden, though. Has anybody ever found any grievous bugs in any of them?
11-30-2019, 09:32 PM
Post: #10
 DMaier Junior Member Posts: 42 Joined: Jan 2014
RE: Faster factor finder method for 42S
The undocumented functions appear to be implemented in Free42 (the DM42 and iOS, anyway) and behave as (un)documented. They don't show up in the catalog (preserving full fidelity with the original, I guess).
12-01-2019, 08:02 PM
Post: #11
 J-F Garnier Senior Member Posts: 355 Joined: Dec 2013
RE: Faster factor finder method for 42S
(11-30-2019 09:32 PM)DMaier Wrote:  The undocumented functions appear to be implemented in Free42 (the DM42 and iOS, anyway) and behave as (un)documented. They don't show up in the catalog (preserving full fidelity with the original, I guess).

There is also the hidden (and useless) XFCN function, which is of course not in Free42, I documented it years ago here: https://www.hpmuseum.org/cgi-sys/cgiwrap...i?read=266

J-F
12-02-2019, 07:17 AM
Post: #12
 Werner Senior Member Posts: 375 Joined: Dec 2013
RE: Faster factor finder method for 42S
Great idea, Dave!
Can't wait to rewrite my own routine using this idea! (using only the stack, and without flags ;-)
There's a simpler way of finding out whether there's a zero in your remainders: (and no need for the matrix R)

Code:
 SF 25  1/X  FC?C 25  GTO 02

And nice story, Joe! If this were Facebook, you'd get a 'like' ;-)

Cheers, Werner
12-02-2019, 12:19 PM
Post: #13
 Dave Britten Senior Member Posts: 1,366 Joined: Dec 2013
RE: Faster factor finder method for 42S
(12-02-2019 07:17 AM)Werner Wrote:  Great idea, Dave!
Can't wait to rewrite my own routine using this idea! (using only the stack, and without flags ;-)
There's a simpler way of finding out whether there's a zero in your remainders: (and no need for the matrix R)

Code:
 SF 25  1/X  FC?C 25  GTO 02

Very clever! That won't tell you where in the matrix there was a zero, so you'll have to take additional steps to find it, but optimizing for the common case (i.e. no factors found) makes sense.

It's a shame that MOD won't work with matrices the same way division and 1/X will. In its current state, the matrix approach won't work with 12-digit numbers, since the fractional part will be lost with small divisors (any result where the fractional part rounds down to .0 will have the same issue).
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)