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