none) (albert

2022-12-07 14:17:57 UTC

In Forth Dimensions 6 number 6, Grossman published an article

about the pollard method of factoring numbers.

See the excellent explanation via

http://soton.mpeforth.com/flag/fd/index.html

He was obliged to implement quad precision operators.

The example 4225910033 was at the limit, gaining a factor

2 from using unsigned numbers. This took 40 seconds.

The same example takes less that 400 uS on my AMD 64 bit.

More over this implementation can handle double the amount

of digits (64 bit signed) despite it has no need to resort

to double precision except the standard UM/MOD UM* .

\ ----------------------------------

\ Pollard (rho) factoring method

: GCD BEGIN OVER MOD DUP WHILE SWAP REPEAT DROP ;

VARIABLE n

VARIABLE b 1 b !

VARIABLE x 6 x !

: next DUP UM* n @ UM/MOD DROP b @ + ;

: try SWAP next SWAP next next 2DUP = ABORT" failure" ;

: factorize DUP n ! x @ DUP next

BEGIN 2DUP - ABS n @ GCD DUP 1 = WHILE DROP try REPEAT

NIP NIP GCD ;

\ REGRESS 4294967297 factorize S: 641

\ REGRESS 4225910033 factorize S: 65011

\ REGRESS 1,000,000,007 DUP * factorize S: 1,000,000,007

\ ----------------------------------

The REGRESS lines are tests or examples.

This is a Monte Carlo program. You may not succeed with

the values of x and b given. You can change them as long

as b is not 0 or -2 .

Groetjes Albert

about the pollard method of factoring numbers.

See the excellent explanation via

http://soton.mpeforth.com/flag/fd/index.html

He was obliged to implement quad precision operators.

The example 4225910033 was at the limit, gaining a factor

2 from using unsigned numbers. This took 40 seconds.

The same example takes less that 400 uS on my AMD 64 bit.

More over this implementation can handle double the amount

of digits (64 bit signed) despite it has no need to resort

to double precision except the standard UM/MOD UM* .

\ ----------------------------------

\ Pollard (rho) factoring method

: GCD BEGIN OVER MOD DUP WHILE SWAP REPEAT DROP ;

VARIABLE n

VARIABLE b 1 b !

VARIABLE x 6 x !

: next DUP UM* n @ UM/MOD DROP b @ + ;

: try SWAP next SWAP next next 2DUP = ABORT" failure" ;

: factorize DUP n ! x @ DUP next

BEGIN 2DUP - ABS n @ GCD DUP 1 = WHILE DROP try REPEAT

NIP NIP GCD ;

\ REGRESS 4294967297 factorize S: 641

\ REGRESS 4225910033 factorize S: 65011

\ REGRESS 1,000,000,007 DUP * factorize S: 1,000,000,007

\ ----------------------------------

The REGRESS lines are tests or examples.

This is a Monte Carlo program. You may not succeed with

the values of x and b given. You can change them as long

as b is not 0 or -2 .

Groetjes Albert

--

"in our communism country Viet Nam, people are forced to be

alive and in the western country like US, people are free to

die from Covid 19 lol" duc ha

***@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

"in our communism country Viet Nam, people are forced to be

alive and in the western country like US, people are free to

die from Covid 19 lol" duc ha

***@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst