Wheel factorization for big integer

[cameyo]

For theory see: https://en.wikipedia.org/wiki/Wheel_factorization">//https://en.wikipedia.org/wiki/Wheel_factorization

Code Select Expand

(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 Expand

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

Code Select Expand

(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 Expand

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

Code Select Expand

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 Expand

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

Code Select Expand

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

Code Select Expand

(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: http://www.newlispfanclub.alh.net/forum/viewtopic.php?f=12&t=5006">//http://www.newlispfanclub.alh.net/forum/viewtopic.php?f=12&t=5006)

Code Select Expand

(define (creadist lst) (map - (rest lst) (chop lst)))
(creadist (dowheel7))
;-> (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)
That's all.

Do you have a faster function to factorize big integer?