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.

1 files changed, 145 insertions, 54 deletions

diff --git a/factor.scm b/factor.scm
index a5c7b44..f10f0d5 100644
--- a/factor.scm
+++ b/factor.scm
@@ -1,5 +1,5 @@
-;;;; "factor.scm", prime test and factorization for Scheme
-;;; Copyright (C) 1991, 1992, 1993 Aubrey Jaffer.
+;;;; "factor.scm" factorization, prime test and generation
+;;; Copyright (C) 1991, 1992, 1993, 1998 Aubrey Jaffer.
 ;
 ;Permission to copy this software, to redistribute it, and to use it
 ;for any purpose is granted, subject to the following restrictions and
@@ -17,8 +17,31 @@
 ;promotional, or sales literature without prior written consent in
 ;each case.
 
-(require 'random)
+(require 'common-list-functions)
 (require 'modular)
+(require 'random)
+(require 'byte)
+
+;;@body
+;;@0 is the random-state (@pxref{Random Numbers}) used by these
+;;procedures.  If you call these procedures from more than one thread
+;;(or from interrupt), @code{random} may complain about reentrant
+;;calls.
+(define prime:prngs
+  (make-random-state "repeatable seed for primes"))
+
+
+;;@emph{Note:} The prime test and generation procedures implement (or
+;;use) the Solovay-Strassen primality test. See
+;;
+;;@itemize @bullet
+;;@item Robert Solovay and Volker Strassen,
+;;@cite{A Fast Monte-Carlo Test for Primality},
+;;SIAM Journal on Computing, 1977, pp 84-85.
+;;@end itemize
+
+;;; Solovay-Strassen Prime Test
+;;;   if n is prime, then J(a,n) is congruent mod n to a**((n-1)/2)
 
 ;;; (modulo p 16) is because we care only about the low order bits.
 ;;; The odd? tests are inline of (expt -1 ...)
@@ -35,41 +58,104 @@
 	   (if (odd? (quotient (- (* qq qq) 1) 8))
 	       (- (prime:jacobi-symbol (quotient p 2) q))
 	       (prime:jacobi-symbol (quotient p 2) q))))))
+;;@args p q
+;;Returns the value (+1, @minus{}1, or 0) of the Jacobi-Symbol of
+;;exact non-negative integer @1 and exact positive odd integer @2.
+(define jacobi-symbol prime:jacobi-symbol)
 
-;;;; Solovay-Strassen Prime Test
-;;;   if n is prime, then J(a,n) is congruent mod n to a**((n-1)/2)
-
-;;; See:
-;;;   Robert Solovay and Volker Strassen,
-;;;     "A Fast Monte-Carlo Test for Primality,"
-;;;     SIAM Journal on Computing, 1977, pp 84-85.
+;;@body
+;;@0 the maxinum number of iterations of Solovay-Strassen that will
+;;be done to test a number for primality.
+(define prime:trials 30)
 
 ;;; checks if n is prime.  Returns #f if not prime. #t if (probably) prime.
 ;;;   probability of a mistake = (expt 2 (- prime:trials))
 ;;;     choosing prime:trials=30 should be enough
-(define prime:trials 30)
-;;; prime:product is a product of small primes.
-(define prime:product
-  (let ((p 210))
-    (for-each (lambda (s)
-		(set! s (string->number s))
-		(set! p (or (and s (exact? s) s) p)))
-	      '("2310" "30030" "510510" "9699690" "223092870"
-		       "6469693230" "200560490130"))
-    p))
+(define (Solovay-Strassen-prime? n)
+  (do ((i prime:trials (- i 1))
+       (a (+ 2 (random (- n 2) prime:prngs))
+	  (+ 2 (random (- n 2) prime:prngs))))
+      ((not (and (positive? i)
+		 (= (gcd a n) 1)
+		 (= (modulo (prime:jacobi-symbol a n) n)
+		    (modular:expt n a (quotient (- n 1) 2)))))
+       (if (positive? i) #f #t))))
+
+;;; prime:products are products of small primes.
+(define (primes-gcd? n comps)
+  (comlist:notevery (lambda (prd) (= 1 (gcd n prd))) comps))
+(define prime:prime-sqr 121)
+(define prime:products '(105))
+(define prime:sieve (bytes 0 0 1 1 0 1 0 1 0 0 0))
+(letrec ((lp (lambda (comp comps primes nexp)
+	       (cond ((< comp (quotient most-positive-fixnum nexp))
+		      (let ((ncomp (* nexp comp)))
+			(lp ncomp comps
+			    (cons nexp primes)
+			    (next-prime nexp (cons ncomp comps)))))
+		     ((< (quotient comp nexp) (* nexp nexp))
+		      (set! prime:prime-sqr (* nexp nexp))
+		      (set! prime:sieve (make-bytes nexp 0))
+		      (for-each (lambda (prime)
+				  (byte-set! prime:sieve prime 1))
+				primes)
+		      (set! prime:products (reverse (cons comp comps))))
+		     (else
+		      (lp nexp (cons comp comps)
+			  (cons nexp primes)
+			  (next-prime nexp (cons comp comps)))))))
+	 (next-prime (lambda (nexp comps)
+		       (set! comps (reverse comps))
+		       (do ((nexp (+ 2 nexp) (+ 2 nexp)))
+			   ((not (primes-gcd? nexp comps)) nexp)))))
+  (lp 3 '() '(2 3) 5))
 
 (define (prime:prime? n)
   (set! n (abs n))
-  (cond ((<= n 36) (and (memv n '(2 3 5 7 11 13 17 19 23 29 31)) #t))
-	((= 1 (gcd n prime:product))
-	 (do ((i prime:trials (- i 1))
-	      (a (+ 1 (random (- n 1))) (+ 1 (random (- n 1)))))
-	     ((not (and (positive? i)
-			(= (gcd a n) 1)
-			(= (modulo (prime:jacobi-symbol a n) n)
-			   (modular:expt n a (quotient (- n 1) 2)))))
-	      (if (positive? i) #f #t))))
-	(else #f)))
+  (cond ((< n (bytes-length prime:sieve)) (positive? (byte-ref prime:sieve n)))
+	((even? n) #f)
+	((primes-gcd? n prime:products) #f)
+	((< n prime:prime-sqr) #t)
+	(else (Solovay-Strassen-prime? n))))
+;;@args n
+;;Returns @code{#f} if @1 is composite; @code{#t} if @1 is prime.
+;;There is a slight chance @code{(expt 2 (- prime:trials))} that a
+;;composite will return @code{#t}.
+(define prime? prime:prime?)
+(define probably-prime? prime:prime?)	;legacy
+
+(define (prime:prime< start)
+  (do ((nbr (+ -1 start) (+ -1 nbr)))
+      ((or (negative? nbr) (prime:prime? nbr))
+       (if (negative? nbr) #f nbr))))
+
+(define (prime:primes< start count)
+  (do ((cnt (+ -2 count) (+ -1 cnt))
+       (lst '() (cons prime lst))
+       (prime (prime:prime< start) (prime:prime< prime)))
+      ((or (not prime) (negative? cnt))
+       (if prime (cons prime lst) lst))))
+;;@args start count
+;;Returns a list of the first @2 prime numbers less than
+;;@1.  If there are fewer than @var{count} prime numbers
+;;less than @var{start}, then the returned list will have fewer than
+;;@var{start} elements.
+(define primes< prime:primes<)
+
+(define (prime:prime> start)
+  (do ((nbr (+ 1 start) (+ 1 nbr)))
+      ((prime:prime? nbr) nbr)))
+
+(define (prime:primes> start count)
+  (set! start (max 0 start))
+  (do ((cnt (+ -2 count) (+ -1 cnt))
+       (lst '() (cons prime lst))
+       (prime (prime:prime> start) (prime:prime> prime)))
+      ((negative? cnt)
+       (reverse (cons prime lst)))))
+;;@args start count
+;;Returns a list of the first @2 prime numbers greater than @1.
+(define primes> prime:primes>)
 
 ;;;;Lankinen's recursive factoring algorithm:
 ;From: ld231782@longs.LANCE.ColoState.EDU (L. Detweiler)
@@ -81,7 +167,7 @@
 ;                  |  f(u,v,2b,n/2) or f(u+b,v+b,2b,(n-u-v-b)/2) if n even
 
 ;Thm: f(1,1,2,(m-1)/2) = (p,q) iff pq=m for odd m.
- 
+
 ;It may be illuminating to consider the relation of the Lankinen function in
 ;a `computational hierarchy' of other factoring functions.*  Assumptions are
 ;made herein on the basis of conventional digital (binary) computers.  Also,
@@ -89,7 +175,7 @@
 ;be factored is prime).  However, all algorithms would probably perform to
 ;the same constant multiple of the given orders for complete composite
 ;factorizations.
- 
+
 ;Thm: Eratosthenes' Sieve is very roughtly O(ln(n)/n) in time and
 ;     O(n*log2(n)) in space.
 ;Pf: It works with all prime factors less than n (about ln(n)/n by the prime
@@ -101,7 +187,7 @@
 ;Pf: It tests all odd factors less than the square root of n (about
 ;    sqrt(n)/2), with log2(n) time for each division.  It requires only
 ;    log2(n) space for the number and divisors.
- 
+
 ;Thm: Lankinen's algorithm is O(sqrt(n)/2) in time and O((sqrt(n)/2)*log2(n))
 ;     in space.
 ;Pf: The algorithm is easily modified to seach only for factors p<q for all
@@ -129,26 +215,31 @@
 	  (or (prime:f (+ u b) v (+ b b) (quotient (- n v) 2))
 	      (prime:f u (+ v b) (+ b b) (quotient (- n u) 2))))))
 
-(define (prime:factor m)
-  (case m
-    ((-1 0 1) (list m))
-    (else
-     (if (negative? m) (cons -1 (prime:factor (- m)))
-	 (let* ((s (gcd m prime:product))
-		(r (quotient m s)))
-	   (if (even? s)
-	       (append
-		(if (= 1 r) '() (prime:factor r))
-		(cons 2 (let ((s/2 (quotient s 2)))
-			  (if (= s/2 1) '()
-			      (or (prime:f 1 1 2 (quotient (- s/2 1) 2))
-				  (list s/2))))))
-	       (if (= 1 s) (or (prime:f 1 1 2 (quotient (- m 1) 2)) (list m))
-		   (append
-		    (if (= 1 r) '()
-			(or (prime:f 1 1 2 (quotient (- r 1) 2)) (list r)))
-		    (or (prime:f 1 1 2 (quotient (- s 1) 2)) (list s))))))))))
+(define (prime:fo m)
+  (let* ((s (gcd m (car prime:products)))
+	 (r (quotient m s)))
+    (if (= 1 s)
+	(or (prime:f 1 1 2 (quotient (- m 1) 2)) (list m))
+	(append
+	 (if (= 1 r) '()
+	     (or (prime:f 1 1 2 (quotient (- r 1) 2)) (list r)))
+	 (or (prime:f 1 1 2 (quotient (- s 1) 2)) (list s))))))
 
-(define jacobi-symbol prime:jacobi-symbol)
-(define prime? prime:prime?)
+(define (prime:fe m)
+  (if (even? m)
+      (cons 2 (prime:fe (quotient m 2)))
+      (if (eqv? 1 m)
+	  '()
+	  (prime:fo m))))
+
+(define (prime:factor k)
+  (case k
+    ((-1 0 1) (list k))
+    (else (if (negative? k)
+	      (cons -1 (prime:fe (- k)))
+	      (prime:fe k)))))
+;;@args k
+;;Returns a list of the prime factors of @1.  The order of the
+;;factors is unspecified.  In order to obtain a sorted list do
+;;@code{(sort! (factor @var{k}) <)}.
 (define factor prime:factor)