## Wheel Factorization

### May 8, 2009

Here is a simple function to find factors by trial division:

`(define (td-factors n)`

(let loop ((n n) (x 2) (fs '()))

(cond ((< n (* x x)) (reverse (cons n fs)))

((zero? (modulo n x)) (loop (/ n x) x (cons x fs)))

(else (loop n (+ x 1) fs)))))

The list of `totatives`

of a number is calculated by counting down from the number to zero and including in the output all those numbers that are coprime to the input:

`(define (totatives n)`

(let loop ((i n) (ts '()))

(cond ((zero? i) ts)

((= (gcd i n) 1)

(loop (- i 1) (cons i ts)))

(else (loop (- i 1) ts)))))

It is easier to work with the gaps between spokes than with the absolute positions of the spokes. For instance, the 2,3,5-wheel with spokes at 1, 7, 11, 13, 17, 19, 23 and 29 can be viewed as a wheel with gaps 6, 4, 2, 4, 2, 4, 6, and 2 (which wraps back around to 1). `Diffs`

makes this calculation:

`(define (diffs xs)`

(let loop ((x (car xs)) (xs (cdr xs)) (ds '()))

(if (null? xs) (reverse ds)

(loop (car xs) (cdr xs) (cons (- (car xs) x) ds)))))

The `wheel`

function builds a wheel, including its starting tail:

`(define (wheel n)`

(let* ((ps (primes n))

(t (apply * (cdr (reverse ps))))

(ts (totatives t))

(ds (diffs ts)))

(append (diffs ps)

(cycle (append (cdr ds)

(list 2)

(list (car ds)))))))

`Wheel`

uses `last-pair`

and `cycle`

, and `primes`

from a previous exercise:

`(define (last-pair xs)`

(if (null? (cdr xs)) xs

(last-pair (cdr xs))))

`(define (cycle xs)`

(set-cdr! (last-pair xs) xs) xs)

Finally, `wheel-factors`

builds a 2,3,5,7-wheel and loops in the same manner as trial division. The call `(wheel 11)`

builds a 2,3,5,7-wheel; 11 is the next prime after 7, and is needed to compute the starting point of the wheel:

`(define wheel-factors`

(let ((w (wheel 11)))

(lambda (n)

(let loop ((n n) (i 2) (fs '()) (w w))

(cond ((< n (* i i)) (reverse (cons n fs)))

((zero? (modulo n i))

(loop (quotient n i) i (cons i fs) w))

(else (loop n (+ i (car w)) fs (cdr w))))))))

Here we see the two factorization functions in action:

`> (td-factors 600851475143)`

(71 839 1471 6857)

> (wheel-factors 600851475143)

(71 839 1471 6857)

This program can be run at http://codepad.org/3kwNA12j.

Pages: 1 2

[…] Praxis – Wheel Factorization By Remco Niemeijer In today’s Programming Praxis problem we’re supposed to factor numbers both the naive way and using […]

My Haskell solution (see http://bonsaicode.wordpress.com/2009/05/08/programming-praxis-%E2%80%93-wheel-factorization/ for a version with comments):

Thanks to a suggestion from programmingpraxis I was able to speed up my program. Since tdFactors already more or less assumes a sorted list of integers as input we can stop looking as soon as x * x > r. The new code becomes:

There isn’t much point in showing the code to compute the wheel; once it is calculated, it can be converted to a static (i.e., compile-time) value:

My FORTH solution; modified brute force factorization we did in (I think a future) exercise to use the factor wheel. Cool thing is the defining word “cycle” to create a new data type — the cyclic constant array.