Page 1 of 1

### Wheel factorization for big integer

Posted: Tue Sep 10, 2019 3:38 pm
For theory see: https://en.wikipedia.org/wiki/Wheel_factorization

Code: Select all

``````(define (factorbig n)
(local (f k i dist out)
; Distanze tra due elementi consecutivi della ruota (wheel)
(setq dist (array 48 '(2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4
6 8 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4
2 4 6 2 6 4 2 4 2 10 2 10)))
(setq out '())
(while (zero? (% n 2)) (push '2L out -1) (setq n (/ n 2)))
(while (zero? (% n 3)) (push '3L out -1) (setq n (/ n 3)))
(while (zero? (% n 5)) (push '5L out -1) (setq n (/ n 5)))
(while (zero? (% n 7)) (push '7L out -1) (setq n (/ n 7)))
(setq k 11L i 0)
(while (<= (* k k) n)
(if (zero? (% n k))
(begin
(push k out -1)
(setq n (/ n k)))
(begin
;(++ k (dist i))
(setq k (+ k (dist i)))
(if (< i 47) (++ i) (setq i 0)))
)
)
(if (> n 1) (push (bigint n) out -1))
out
)
)

(factorbig 9223372036854775809L)
;-> (3L 3L 3L 19L 43L 5419L 77158673929L)

(time (factorbig 9223372036854775809L))
;-> 46.875

(apply * '(3L 3L 3L 19L 43L 5419L 77158673929L))
;-> 9223372036854775809L
``````
We check if factorbig and factor produce the same result (up to a million):

Code: Select all

``````(= (map factorbig (sequence 2 1e6)) (map factor (sequence 2 1e6)))
;-> true``````
Let's try a 20-digit number:

Code: Select all

``````(time (println (factorbig 92233720368547758091L)))
;-> (7L 13L 1013557366687338001L)
;-> 150515.93 ; 150 sec``````
The greater the value of the factors, the greater the execution time.

Code: Select all

``````(time (println (factorbig 1013557366687338001L)))
;-> (1013557366687338001L)
;-> 179855.465 ; 3 min``````
Instead in the following example the calculation is immediate:

Code: Select all

``````2^64 = 18446744073709551616
(setq d 18446744073709551616L)
(factorbig d)
;-> (2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L
;->  2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L
;->  2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L 2L
;->  2L 2L 2L 2L)``````
How to calculate wheel distance list
First you need to generate the numbers of the wheel, that is all the integers coprime from the base up to the number (+ (* 2 3 5 7) 11) = 221
Function to calculate the coprime:

Code: Select all

``(define (coprimi? a b) (= (gcd a b) 1))``
Function that checks if a number belongs to the wheel:

Code: Select all

``(define (wheel7 n) (and (coprimi? n 2) (coprimi? n 3) (coprimi? n 5) (coprimi? n 7)))``
Function that creates the number wheel:

Code: Select all

``````(define (dowheel7)
(let (out '())
(for (i 2 221) (if (wheel7 i) (push i out -1)))))
(dowheel7)
;-> (11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113
;->  121 127 131 137 139 143 149 151 157 163 167 169 173 179 181 187 191 193 197 199
;->  209 211 221)``````
To calculate the distances between two consecutive wheel elements we use the following function:
(thanks fdb: viewtopic.php?f=12&t=5006)

Code: Select all

``````(define (creadist lst) (map - (rest lst) (chop lst)))