diff options
| author | James LewisMoss <dres@debian.org> | 1999-12-06 19:32:57 -0500 | 
|---|---|---|
| committer | Bryan Newbold <bnewbold@robocracy.org> | 2017-02-20 00:05:28 -0800 | 
| commit | c394920caedf3dac1981bb6b10eeb47fd6e4bb21 (patch) | |
| tree | f21194653a3554f747dde3df908df993c48db5a0 /primes.scm | |
| parent | 926b1b647ac830660933a5e63eb52d4a2552e264 (diff) | |
| parent | bd9733926076885e3417b74de76e4c9c7bc56254 (diff) | |
| download | slib-c394920caedf3dac1981bb6b10eeb47fd6e4bb21.tar.gz slib-c394920caedf3dac1981bb6b10eeb47fd6e4bb21.zip | |
Import Debian changes 2c7-1debian/2c7-1
slib (2c7-1) unstable; urgency=low
  * New upstream.
  * Add slibconfig back in.
slib (2c6-2) unstable; urgency=low
  * Remove the slib$(VERSION).info file.  Cut the diff back down to
    size. 
slib (2c6-1) unstable; urgency=low
  * New upstream.
  * Move docs to /usr/share. Up standards version. add /usr/doc symlink.
    Move info files.  Remove undocumented link.
slib (2c5-6) unstable; urgency=low
  * Lowercase two vars in yasyn.scm (Fixes bug #37222)
slib (2c5-5) unstable; urgency=low
  * Fix it so string-index isn't defined (now there is a
    strsrch:string-index) (Fixes #38812)
slib (2c5-4) unstable; urgency=low
  * Don't run slibconfig in postinst.  (Fixes bug #38253, #37733, #37715,
    #37746,  #37809, #37917, #38123, #38462)
slib (2c5-3) unstable; urgency=low
  * Run slibconfig in postinst.  It was commented out there, but I don't
    see any old bug reports on why it was commented out, so let's try
    again. :)  (Fixes bug #37221)
slib (2c5-2) unstable; urgency=low
  * Link mklibcat.scm to mklibcat.  Fixes a problem with using slib with
    guile. 
slib (2c5-1) unstable; urgency=low
  * New upstream.
slib (2c3-4) unstable; urgency=low
  * New maintainer.
Diffstat (limited to 'primes.scm')
| -rw-r--r-- | primes.scm | 187 | 
1 files changed, 0 insertions, 187 deletions
| diff --git a/primes.scm b/primes.scm deleted file mode 100644 index 672e899..0000000 --- a/primes.scm +++ /dev/null @@ -1,187 +0,0 @@ -;; "primes.scm", test and generate prime numbers. -; Written by Michael H Coffin (mhc@edsdrd.eds.com) -; -; This code is in the public domain. - -;Date: Thu, 23 Feb 1995 07:47:49 +0500 -;From: mhc@edsdrd.eds.com (Michael H Coffin) -;; -;; Test numbers for primality using Rabin-Miller Monte-Carlo -;; primality test. -;; -;; Public functions: -;; -;;    (primes start count . iter) -;; -;;    (probably-prime? p . iter) -;; -;; -;; Please contact the author if you have problems or suggestions: -;; -;;      Mike Coffin -;;      1196 Whispering Knoll -;;      Rochester Hills, Mi. 48306 -;; -;;      mhc@edsdrd.eds.com -;; - -(require 'random) - -;; The default number of times to perform the Rabin-Miller test.  The -;; probability of a composite number passing the Rabin-Miller test for -;; primality with this many random numbers is at most -;; 1/(4^primes:iterations).  The default yields about 1e-9. -;; -(define primes:iter 15) - -;; Is n probably prime? -;; -(define (primes:probably-prime? n . iter) -  (let ((iter (if (null? iter) primes:iter (car iter)))) -    (primes:prob-pr? n iter))) - - -;; Return a list of the first `number' odd probable primes less -;; than `start'. - -(define (primes:primes< start number . iter) -  (let ((iter (if (null? iter) primes:iter (car iter)))) -    (do ((candidate (if (odd? start) start (- start 1)) -		    (- candidate 2)) -	 (count 0) -	 (result '()) -	 ) -	((or (< candidate 3) (>= count number)) result) -      (if (primes:prob-pr? candidate iter) -	  (begin -	    (set! count (1+ count)) -	    (set! result (cons candidate result))) -	  )))) - -(define (primes:primes> start number . iter) -  (let ((iter (if (null? iter) primes:iter (car iter)))) -    (do ((candidate (if (odd? start) start (+ 1 start)) -                    (+ 2 candidate)) -         (count 0) -         (result '()) -         ) -        ((= count number) (reverse result)) -      (if (primes:prob-pr? candidate iter) -          (begin -            (set! count (1+ count)) -            (set! result (cons candidate result))) -          )))) - - -;; Is n probably prime?  First we check for divisibility by small -;; primes; if it passes that, and it's less than the maximum small -;; prime squared, we try Rabin-Miller. -;; -(define (primes:prob-pr? n count) -  (and (not (primes:dbsp? n)) -       (or (< n (* primes:max-small-prime primes:max-small-prime)) -	   (primes:rm-prime? n count)))) - - -;; Is `n' Divisible By a Small Prime? -;; -(define primes:dbsp? -  (let ((sqrt (cond ((provided? 'inexact) sqrt) -		    (else (require 'root) integer-sqrt)))) -    (lambda (n) -      (let ((limit (min (sqrt n) primes:max-small-prime)) -	    (divisible #f) -	    ) -	(do ((i 0 (1+ i))) -	    ((let* ((divisor (vector-ref primes:small-primes i))) -	       (set! divisible (= (modulo n divisor) 0)) -	       (or divisible (> divisor limit))) -	     divisible) -	  ))))) - - -;; Does `n' pass the R.-M. primality test for `m' random numbers? -;; -(define (primes:rm-prime? n m) -  (do ((i 0 (1+ i)) -       (x (+ 2 (random (- n 2) primes:prngs)))) -      ((or (= i m) (primes:rm-composite? n x)) -       (= i m)))) - - -;; Does `x' prove `n' composite using Rabin-Miller? -;; -(define (primes:rm-composite? n x) -  (let ((f (primes:extract2s (- n 1)))) -    (primes:rm-comp? n (cdr f) (car f) x))) - - -;; Is `n' (where n-1 = 2^k * q) proven composite by `x'? -;; -(define (primes:rm-comp? n q k x) -  (let ((y (primes:expt-mod x q n))) -    (if (= y 1) -	#f -	(let loop ((j 0) (y y)) -	  (cond ((= j k) #t) -		((= y (- n 1)) #f) -		((= y 1) #t) -		(else (loop (1+ j) (primes:expt-mod y 2 n))) -		))))) - - -;; Extract factors of 2; that is, factor x as 2^k * q -;; and return (k . q) -;; -(define (primes:extract2s x) -  (do ((k 0 (1+ k)) -       (q x (quotient q 2))) -      ((odd? q) (cons k q)) -    )) - - -;; Raise `base' to the power `exp' modulo `modulus' Could use the -;; modulo package, but we only need this function (and besides, this -;; implementation is quite a bit faster). -;; -(define (primes:expt-mod base exp modulus) -  (do ((y 1) -       (k exp (quotient k 2)) -       (z base (modulo (* z z) modulus))) -      ((= k 0) y) -    (if (odd? k) -	(set! y (modulo (* y z) modulus))) -    )) - -(define primes:prngs -  (make-random-state "repeatable seed for primes")) - -;; This table seems big enough so that making it larger really -;; doesn't have much effect. -;; -(define primes:max-small-prime 997) - -(define primes:small-primes -  '#(  2   3   5   7  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 -     127 131 137 139 149 151 157 163 167 173 -     179 181 191 193 197 199 211 223 227 229 -     233 239 241 251 257 263 269 271 277 281 -     283 293 307 311 313 317 331 337 347 349 -     353 359 367 373 379 383 389 397 401 409 -     419 421 431 433 439 443 449 457 461 463 -     467 479 487 491 499 503 509 521 523 541 -     547 557 563 569 571 577 587 593 599 601 -     607 613 617 619 631 641 643 647 653 659 -     661 673 677 683 691 701 709 719 727 733 -     739 743 751 757 761 769 773 787 797 809 -     811 821 823 827 829 839 853 857 859 863 -     877 881 883 887 907 911 919 929 937 941 -     947 953 967 971 977 983 991 997 )) - -(define primes< primes:primes<) -(define primes> primes:primes>) -(define probably-prime? primes:probably-prime?) - -(provide 'primes) | 
