11-26-2019, 04:24 PM

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:

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

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.

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.