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