4 ms·
Times are so crazily different. I tried what a really bad algorithm would take in CommonLisp. It is seconds it took. (defun find-factor-aux(n div stop)
by beeforpork 4y ago
Times are so crazily different. I tried what a really bad algorithm would take in CommonLisp. It is seconds it took.
(defun find-factor-aux(n div stop)
(cond
((= 0 (rem n div)) div)
((> div stop) nil)
(t (find-factor-aux n (+ 2 div) stop))))
(defun find-factor(n) (find-factor-aux n 3 (floor (sqrt n))))
(compile 'find-factor-aux ) ; need tail recursion to avoid stack overflow
(find-factor (1- (expt 2 67))) ; this takes just a few seconds on my laptop
; 193707721
(find-factor (/ (1- (expt 2 67)) 193707721)) ; check for more
; nil
(/ (1- (expt 2 67)) 193707721) ; get second factor
; 761838257287
(* 193707721 761838257287) ; check result
; 147573952589676412927
(1- (expt 2 67))
; 147573952589676412927