;;;;;These examples use a simple sieve algorithm for factoring.
;;;;;Their purpose is to illustrate the master-slave architecture.

;;; sequential version (single processor)
(defun seq-myfactor (x)
  (do ((sqrt (ceiling (sqrt x)))
       (curr 1))
      ((>= curr sqrt) 'prime)
    (if (dotimes (j 1000 nil)
          (if (= (mod x (incf curr)) 0) (return 'done)))
      (return curr))))


;;; parallel version
;;; NOTE:  In the next version (soon), the read - eval - print loop, will
;;;        become a    read - par-eval - print   loop.
;;;        For now, call:
;;;          (par-load "myfactor.lsp")
;;;          (par-myfactor-1 987654321)
(defun par-myfactor-1 (x &optional (incr 1000))
  "Produces one factor of argument"
  (par-funcall #'par-myfactor-1-aux x incr))
(defun par-myfactor-1-aux (x incr)
  (let ((sqrt (ceiling (sqrt x)))
        (curr 1) (answer nil))
    (master-slave :generate-task-input
		  #'(lambda () (and (not answer)
				    (< curr sqrt)
				    (prog1 curr (incf curr incr))))
                  :do-task
		  #'(lambda (curr)
		      (dotimes (j incr nil)
			(if (= (mod x (incf curr)) 0)
			    (return curr))))
                  :check-task-result
		  #'(lambda (result)
		      (when result
			;;(min .. ..) in case 2 slaves find diff. factors
			(setq answer (if answer (min answer result)
				       result)))
		      'NO-ACTION)
                  :trace t) ; optionally trace messages
    (or answer 'prime)))

;;This version finds all factors
;;Note that (up-to-date-p) insures that if other slaves found smaller
;; factors, those will have been registered first.
(defun par-myfactor (x &optional (incr 1000))
  "Produces all factors of argument"
  (par-funcall #'par-myfactor-aux x incr))
(defun par-myfactor-aux (x incr)
  (let ((sqrt (ceiling (sqrt x)))
        (curr 1) (answer nil))
    (master-slave :generate-task-input
		  #'(lambda ()
		      (and (< curr sqrt) (prog1 curr (incf curr incr))))
                  :do-task
		  #'(lambda (curr)
		      (dotimes (j incr nil)
			(if (= (mod x (incf curr)) 0)
			    (return curr))))
                  :check-task-result
		  #'(lambda (result)
		      (if result
			  (if (up-to-date-p)
			      ;; more factors in [curr+1..curr+incr]?
			      (progn (decf curr incr) 'UPDATE)
			    'REDO) ; re-try current computation
			'NO-ACTION))
		  ;; update answer on all processors
		  :update-shared-data
		  #'(lambda (result)
		      (setq x (/ x result))
		      (setq sqrt (ceiling (sqrt x)))
		      (push result answer))
                  :trace t) ; optionally trace messages
    (if (> x 1) (push x answer))
    (or answer 'prime)))

;;;could also use continuation and *last*

;;Add check that new factors are prime (by making sure all factors up to
;; sqrt of new number have already been checked)