danbaron
09-05-2011, 06:05
Here is a procedure developed by Fermat in the 1600s, that will find the prime factors of any (positive) integer.
http://en.wikipedia.org/wiki/Fermat%27s_factorization_method
I think it is one of the simplest factoring procedures that does not use a list of primes.
Its advantages are that it does not use a lot of disk space or RAM for a primes list, and it will factor any integer, no matter how big.
Its disadvantage is that it is very slow relative to other more sophisticated procedures, which also do not use a primes list. (I think it will eventually factor any integer. But, it may take forever to do so.)
:idea:
; code --------------------------------------------------------------------------------------------------------
#lang racket
(define (fermat-factor n)
(define factors (list))
(define factor 0)
(define n0 0)
(define (factor-twos n1)
(cond
((odd? n1) void)
(else
(set! factors (append factors (list 2)))
(set! n (/ n 2))
(factor-twos n))))
(define (loop-1 n1)
(define isrn (integer-sqrt n1))
(define x (+ (* 2 isrn) 1))
(define y 1)
(define r (- (* isrn isrn) n1))
(define (loop-2)
(cond
((= r 0)
(set! factor (/ (- x y) 2))
(cond
((= factor 1)
(set! factor n1)
(set! factors (append factors (list factor)))
(set! n0 (/ n0 factor))
(if (= n0 1) void (loop-1 n0)))
(else
(loop-1 (/ n1 factor)))))
(else
(set! r (+ r x))
(set! x (+ x 2))
(loop-3))))
(define (loop-3)
(set! r (- r y))
(set! y (+ y 2))
(cond
((> r 0) (loop-3))
(else (loop-2))))
(loop-2))
(factor-twos n)
(set! n0 n)
(loop-1 n)
(set! factors (sort factors <))
(when (> (length factors) 1) (set! factors (remove 1 factors)))
factors)
(define (time-fermat-factor n)
(let ((t1 (current-milliseconds)))
(let ((factor-list (fermat-factor n)))
(let ((t2 (current-milliseconds)))
(let ((tt (/ (- t2 t1) 1000.0)))
(values factor-list tt))))))
(define (t n)
(time-fermat-factor n))
; REPL interactions -------------------------------------------------------------------------------------------
Welcome to DrRacket, version 5.1 [3m].
Language: racket.
> (t 1)
'(1)
0.001
> (t 2)
'(2)
0
> (t 3)
'(3)
0
> (t 4)
'(2 2)
0
> (t 5)
'(5)
0
> (t 6)
'(2 3)
0
> (t 7)
'(7)
0
> (t 8)
'(2 2 2)
0.007
> (t 9)
'(3 3)
0
> (t 10)
'(2 5)
0
> (t 11)
'(11)
0
> (t 111)
'(3 37)
0
> (t 1111)
'(11 101)
0
> (t 11111)
'(41 271)
0
> (t 111111)
'(3 7 11 13 37)
0
> (t 1111111)
'(239 4649)
0.001
> (t 11111111)
'(11 73 101 137)
0.001
> (t 111111111)
'(3 3 37 333667)
0.139
> (t 1111111111)
'(11 41 271 9091)
0.016
> (t 11111111111)
'(21649 513239)
0.184
> (t 111111111111)
'(3 7 11 13 37 101 9901)
0.008
> (t 1111111111111)
'(53 79 265371653)
136.931
> (t 11111111111111)
'(11 239 4649 909091)
1.768
> (t 111111111111111)
'(3 31 37 41 271 2906161)
1.514
> (t 1111111111111111)
'(11 17 73 101 137 5882353)
8.799
> (t 111111111111111111)
'(3 3 7 11 13 19 37 52579 333667)
0.312
> (t 11111111111111111111)
'(11 41 101 271 3541 9091 27961)
141.199
> (t 1356765432)
'(2 2 2 3 11 37 138899)
0.062
> (t 396857463546786867)
'(3 3 3 3 3 43 61 42773 14556611)
6.396
--------------------------------------------------------------
I found out that for numbers that take a long time to factor, it's better not to use the IDE (DrRacket). Sometimes, for long runs, after awhile (usually while I am switching back and forth among other programs), the window showing DrRacket will turn cloudy white, like a fog is covering it. And the Windows Task Manager will say that the program is not responding. Then, I have to force DrRacket to quit.
So, actually for any Racket program that takes a long time to run, my experience is that it is better to make an executable from within DrRacket, and then to close DrRacket and run the executable. I'm using that method to factor some harder integers. The programs run in a console window. I'll show the results below as I get them. (The executables that run in a console window seem to be immune to the problems I was having from within DrRacket.)
> (t 11002930366353704069)
'(3267000013 3367900313)
4515.511
>
http://en.wikipedia.org/wiki/Fermat%27s_factorization_method
I think it is one of the simplest factoring procedures that does not use a list of primes.
Its advantages are that it does not use a lot of disk space or RAM for a primes list, and it will factor any integer, no matter how big.
Its disadvantage is that it is very slow relative to other more sophisticated procedures, which also do not use a primes list. (I think it will eventually factor any integer. But, it may take forever to do so.)
:idea:
; code --------------------------------------------------------------------------------------------------------
#lang racket
(define (fermat-factor n)
(define factors (list))
(define factor 0)
(define n0 0)
(define (factor-twos n1)
(cond
((odd? n1) void)
(else
(set! factors (append factors (list 2)))
(set! n (/ n 2))
(factor-twos n))))
(define (loop-1 n1)
(define isrn (integer-sqrt n1))
(define x (+ (* 2 isrn) 1))
(define y 1)
(define r (- (* isrn isrn) n1))
(define (loop-2)
(cond
((= r 0)
(set! factor (/ (- x y) 2))
(cond
((= factor 1)
(set! factor n1)
(set! factors (append factors (list factor)))
(set! n0 (/ n0 factor))
(if (= n0 1) void (loop-1 n0)))
(else
(loop-1 (/ n1 factor)))))
(else
(set! r (+ r x))
(set! x (+ x 2))
(loop-3))))
(define (loop-3)
(set! r (- r y))
(set! y (+ y 2))
(cond
((> r 0) (loop-3))
(else (loop-2))))
(loop-2))
(factor-twos n)
(set! n0 n)
(loop-1 n)
(set! factors (sort factors <))
(when (> (length factors) 1) (set! factors (remove 1 factors)))
factors)
(define (time-fermat-factor n)
(let ((t1 (current-milliseconds)))
(let ((factor-list (fermat-factor n)))
(let ((t2 (current-milliseconds)))
(let ((tt (/ (- t2 t1) 1000.0)))
(values factor-list tt))))))
(define (t n)
(time-fermat-factor n))
; REPL interactions -------------------------------------------------------------------------------------------
Welcome to DrRacket, version 5.1 [3m].
Language: racket.
> (t 1)
'(1)
0.001
> (t 2)
'(2)
0
> (t 3)
'(3)
0
> (t 4)
'(2 2)
0
> (t 5)
'(5)
0
> (t 6)
'(2 3)
0
> (t 7)
'(7)
0
> (t 8)
'(2 2 2)
0.007
> (t 9)
'(3 3)
0
> (t 10)
'(2 5)
0
> (t 11)
'(11)
0
> (t 111)
'(3 37)
0
> (t 1111)
'(11 101)
0
> (t 11111)
'(41 271)
0
> (t 111111)
'(3 7 11 13 37)
0
> (t 1111111)
'(239 4649)
0.001
> (t 11111111)
'(11 73 101 137)
0.001
> (t 111111111)
'(3 3 37 333667)
0.139
> (t 1111111111)
'(11 41 271 9091)
0.016
> (t 11111111111)
'(21649 513239)
0.184
> (t 111111111111)
'(3 7 11 13 37 101 9901)
0.008
> (t 1111111111111)
'(53 79 265371653)
136.931
> (t 11111111111111)
'(11 239 4649 909091)
1.768
> (t 111111111111111)
'(3 31 37 41 271 2906161)
1.514
> (t 1111111111111111)
'(11 17 73 101 137 5882353)
8.799
> (t 111111111111111111)
'(3 3 7 11 13 19 37 52579 333667)
0.312
> (t 11111111111111111111)
'(11 41 101 271 3541 9091 27961)
141.199
> (t 1356765432)
'(2 2 2 3 11 37 138899)
0.062
> (t 396857463546786867)
'(3 3 3 3 3 43 61 42773 14556611)
6.396
--------------------------------------------------------------
I found out that for numbers that take a long time to factor, it's better not to use the IDE (DrRacket). Sometimes, for long runs, after awhile (usually while I am switching back and forth among other programs), the window showing DrRacket will turn cloudy white, like a fog is covering it. And the Windows Task Manager will say that the program is not responding. Then, I have to force DrRacket to quit.
So, actually for any Racket program that takes a long time to run, my experience is that it is better to make an executable from within DrRacket, and then to close DrRacket and run the executable. I'm using that method to factor some harder integers. The programs run in a console window. I'll show the results below as I get them. (The executables that run in a console window seem to be immune to the problems I was having from within DrRacket.)
> (t 11002930366353704069)
'(3267000013 3367900313)
4515.511
>