[ create a new paste ] login | about

Link: http://codepad.org/XyNkafVD    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Mar 5:
; factoring by digital coding

(define (mappend f . xss)
  (apply append (apply map f xss)))

(define (digits n . args)
  (let ((b (if (null? args) 10 (car args))))
    (let loop ((n n) (d '()))
      (if (zero? n) d
          (loop (quotient n b)
                (cons (modulo n b) d))))))

(define (bits n)
  (if (zero? n) (list 0)
    (let loop ((n n) (bs (list)))
      (if (zero? n) bs
        (loop (quotient n 2)
              (cons (modulo n 2) bs))))))

(define (unbits bs)
  (let loop ((bs bs) (n 0))
    (if (null? bs) n
      (loop (cdr bs) (+ (* n 2) (car bs))))))

(define (dc n)
  (unbits (mappend bits (digits n))))

(define (dc-factor n)
  (let loop ((d (dc n)))
    (display d) (display " ")
    (let ((g (gcd d n)))
      (if (< 1 g n) g
        (loop (dc d))))))

(display (dc-factor 88837)) (newline)
(display (dc-factor 96577)) (newline)


Output:
1
2
69919 54073 2847 2599 5529 2921 333 37
40319 23


Create a new paste based on this one


Comments: