The bit-twiddling functions are made available through the use of the
logical package. logical is loaded by inserting
(require 'logical) before the code that uses these
functions. These functions behave as though operating on integers
in two's-complement representation.
Example:
(number->string (logand #b1100 #b1010) 2) => "1000"
Example:
(number->string (logior #b1100 #b1010) 2) => "1110"
Example:
(number->string (logxor #b1100 #b1010) 2) => "110"
Example:
(number->string (lognot #b10000000) 2) => "-10000001" (number->string (lognot #b0) 2) => "-1"
(logtest j k) == (not (zero? (logand j k))) (logtest #b0100 #b1011) => #f (logtest #b0100 #b0111) => #t
Example:
(logcount #b10101010) => 4 (logcount 0) => 0 (logcount -2) => 1
(logbit? index j) == (logtest (integer-expt 2 index) j) (logbit? 0 #b1101) => #t (logbit? 1 #b1101) => #f (logbit? 2 #b1101) => #t (logbit? 3 #b1101) => #t (logbit? 4 #b1101) => #f
#t and 0 if bit is #f.
Example:
(number->string (copy-bit 0 0 #t) 2) => "1" (number->string (copy-bit 2 0 #t) 2) => "100" (number->string (copy-bit 2 #b1111 #f) 2) => "1011"
This function was called bit-extract in previous versions of SLIB.
Example:
(number->string (bit-field #b1101101010 0 4) 2) => "1010" (number->string (bit-field #b1101101010 4 9) 2) => "10110"
Example:
(number->string (copy-bit-field #b1101101010 0 4 0) 2)
=> "1101100000"
(number->string (copy-bit-field #b1101101010 0 4 -1) 2)
=> "1101101111"
(inexact->exact (floor (* int (expt 2 count)))).
Example:
(number->string (ash #b1 3) 2) => "1000" (number->string (ash #b1010 -1) 2) => "101"
Example:
(integer-length #b10101010) => 8 (integer-length 0) => 0 (integer-length #b1111) => 4
Example:
(integer-expt 2 5) => 32 (integer-expt -3 3) => -27
(d x y) such that d = gcd(n1,
n2) = n1 * x + n2 * y.
(quotient (+ -1 n) -2) for positive odd integer n.
modular: procedures.
(modulo n (modulus->integer
modulus)) in the representation specified by modulus.
The rest of these functions assume normalized arguments; That is, the arguments are constrained by the following table:
For all of these functions, if the first argument (modulus) is:
positive?
zero?
negative?
(+ 1 (* -2 modulus)), but with symmetric
representation; i.e. (<= (- modulus) n
modulus).
If all the arguments are fixnums the computation will use only fixnums.
#t if there exists an integer n such that k * n
== 1 mod modulus, and #f otherwise.
The Scheme code for modular:* with negative modulus is not
completed for fixnum-only implementations.
prime:prngs is the random-state (see section Random Numbers) used by these
procedures. If you call these procedures from more than one thread
(or from interrupt), random may complain about reentrant
calls.
Returns the value (+1, -1, or 0) of the Jacobi-Symbol of exact non-negative integer p and exact positive odd integer q.
prime:trials the maxinum number of iterations of Solovay-Strassen that will be done to test a number for primality.
Returns #f if n is composite; #t if n is prime.
There is a slight chance (expt 2 (- prime:trials)) that a
composite will return #t.
Returns a list of the first count prime numbers less than start. If there are fewer than count prime numbers less than start, then the returned list will have fewer than start elements.
Returns a list of the first count prime numbers greater than start.
Returns a list of the prime factors of k. The order of the
factors is unspecified. In order to obtain a sorted list do
(sort! (factor k) <).
A pseudo-random number generator is only as good as the tests it passes. George Marsaglia of Florida State University developed a battery of tests named DIEHARD (http://stat.fsu.edu/~geo/diehard.html). `diehard.c' has a bug which the patch ftp://swissnet.ai.mit.edu/pub/users/jaffer/diehard.c.pat corrects.
SLIB's new PRNG generates 8 bits at a time. With the degenerate seed `0', the numbers generated pass DIEHARD; but when bits are combined from sequential bytes, tests fail. With the seed `http://swissnet.ai.mit.edu/~jaffer/SLIB.html', all of those tests pass.
It would be better if there were no bad seeds. For now, use seeds of at least 30 bytes.
The optional argument state must be of the type produced by
(make-random-state). It defaults to the value of the variable
*random-state*. This object is used to maintain the state of the
pseudo-random-number generator and is altered as a side effect of the
random operation.
random uses by default. The nature
of this data structure is implementation-dependent. It may be printed
out and successfully read back in, but may or may not function correctly
as a random-number state object in another implementation.
*random-state* and as a second argument to
random. If argument state is given, a copy of it is
returned. Otherwise a copy of *random-state* is returned.If inexact numbers are supported by the Scheme implementation, `randinex.scm' will be loaded as well. `randinex.scm' contains procedures for generating inexact distributions.
(vector-length vect), the
coordinates are uniformly distributed within the unit n-shere.
The sum of the squares of the numbers is returned.
(vector-length vect), the coordinates are
uniformly distributed over the surface of the unit n-shere.
(+ m (* d
(random:normal))).
The integer degree, if given, specifies the degree of the polynomial being computed -- which is also the number of bits computed in the checksums. The default value is 32.
The integer generator specifies the polynomial being computed. The power of 2 generating each 1 bit is the exponent of a term of the polynomial. The bit at position degree is implicit and should not be part of generator. This allows systems with numbers limited to 32 bits to calculate 32 bit checksums. The default value of generator when degree is 32 (its default) is:
(make-port-crc 32 #b00000100110000010001110110110111)
Creates a procedure to calculate the P1003.2/D11.2 (POSIX.2) 32-bit checksum from the polynomial:
32 26 23 22 16 12 11
( x + x + x + x + x + x + x +
10 8 7 5 4 2 1
x + x + x + x + x + x + x + 1 ) mod 2
(require 'make-crc) (define crc32 (slib:eval (make-port-crc))) (define (file-check-sum file) (call-with-input-file file crc32)) (file-check-sum (in-vicinity (library-vicinity) "ratize.scm")) => 3553047446
The plotting procedure is made available through the use of the
charplot package. charplot is loaded by inserting
(require 'charplot) before the code that uses this
procedure.
Example:
(require 'charplot)
(set! charplot:height 19)
(set! charplot:width 45)
(define (make-points n)
(if (zero? n)
'()
(cons (cons (/ n 6) (sin (/ n 6))) (make-points (1- n)))))
(plot! (make-points 37) "x" "Sin(x)")
-|
Sin(x) ______________________________________________
1.25|- |
| |
1|- **** |
| ** ** |
750.0e-3|- * * |
| * * |
500.0e-3|- * * |
| * |
250.0e-3|- * |
| * * |
0|-------------------*--------------------------|
| * |
-250.0e-3|- * * |
| * * |
-500.0e-3|- * |
| * * |
-750.0e-3|- * * |
| ** ** |
-1|- **** |
|____________:_____._____:_____._____:_________|
x 2 4
#f if such an integer can't be found.
To find the closest integer to a given integers square root:
(define (integer-sqrt y) (newton:find-integer-root (lambda (x) (- (* x x) y)) (lambda (x) (* 2 x)) (ash 1 (quotient (integer-length y) 2)))) (integer-sqrt 15) => 4
abs(f(x)) is less than prec; or
returns #f if such a real can't be found.
If prec is instead a negative integer, newton:find-root
returns the result of -prec iterations.
H. J. Orchard, The Laguerre Method for Finding the Zeros of Polynomials, IEEE Transactions on Circuits and Systems, Vol. 36, No. 11, November 1989, pp 1377-1381.
There are 2 errors in Orchard's Table II. Line k=2 for starting value of 1000+j0 should have Z_k of 1.0475 + j4.1036 and line k=2 for starting value of 0+j1000 should have Z_k of 1.0988 + j4.0833.
magnitude(f(z)) is less than prec; or returns
#f if such a number can't be found.
If prec is instead a negative integer, laguerre:find-root
returns the result of -prec iterations.
magnitude(f(z)) is less than prec; or
returns #f if such a number can't be found.
If prec is instead a negative integer,
laguerre:find-polynomial-root returns the result of -prec
iterations.
Scheme provides a consistent and capable set of numeric functions. Inexacts implement a field; integers a commutative ring (and Euclidean domain). This package allows one to use basic Scheme numeric functions with symbols and non-numeric elements of commutative rings.
The commutative-ring package makes the procedures +,
-, *, /, and ^ careful in the sense
that any non-numeric arguments they do not reduce appear in the
expression output. In order to see what working with this package is
like, self-set all the single letter identifiers (to their corresponding
symbols).
(define a 'a) ... (define z 'z)
Or just (require 'self-set). Now try some sample expressions:
(+ (+ a b) (- a b)) => (* a 2) (* (+ a b) (+ a b)) => (^ (+ a b) 2) (* (+ a b) (- a b)) => (* (+ a b) (- a b)) (* (- a b) (- a b)) => (^ (- a b) 2) (* (- a b) (+ a b)) => (* (+ a b) (- a b)) (/ (+ a b) (+ c d)) => (/ (+ a b) (+ c d)) (^ (+ a b) 3) => (^ (+ a b) 3) (^ (+ a 2) 3) => (^ (+ 2 a) 3)
Associative rules have been applied and repeated addition and multiplication converted to multiplication and exponentiation.
We can enable distributive rules, thus expanding to sum of products form:
(set! *ruleset* (combined-rulesets distribute* distribute/)) (* (+ a b) (+ a b)) => (+ (* 2 a b) (^ a 2) (^ b 2)) (* (+ a b) (- a b)) => (- (^ a 2) (^ b 2)) (* (- a b) (- a b)) => (- (+ (^ a 2) (^ b 2)) (* 2 a b)) (* (- a b) (+ a b)) => (- (^ a 2) (^ b 2)) (/ (+ a b) (+ c d)) => (+ (/ a (+ c d)) (/ b (+ c d))) (/ (+ a b) (- c d)) => (+ (/ a (- c d)) (/ b (- c d))) (/ (- a b) (- c d)) => (- (/ a (- c d)) (/ b (- c d))) (/ (- a b) (+ c d)) => (- (/ a (+ c d)) (/ b (+ c d))) (^ (+ a b) 3) => (+ (* 3 a (^ b 2)) (* 3 b (^ a 2)) (^ a 3) (^ b 3)) (^ (+ a 2) 3) => (+ 8 (* a 12) (* (^ a 2) 6) (^ a 3))
Use of this package is not restricted to simple arithmetic expressions:
(require 'determinant) (determinant '((a b c) (d e f) (g h i))) => (- (+ (* a e i) (* b f g) (* c d h)) (* a f h) (* b d i) (* c e g))
Currently, only +, -, *, /, and ^
support non-numeric elements. Expressions with - are converted
to equivalent expressions without -, so behavior for - is
not defined separately. / expressions are handled similarly.
This list might be extended to include quotient, modulo,
remainder, lcm, and gcd; but these work only for
the more restrictive Euclidean (Unique Factorization) Domain.
The commutative-ring package allows control of ring properties through the use of rulesets.
cring:define-rule are stored within the value of *ruleset* at the
time cring:define-rule is called. If *ruleset* is
#f, then no rules apply.
cring:define-rule to each 4-element list argument rule. If
the first argument to make-ruleset is a symbol, then the database
table created for the new ruleset will be named name. Calling
make-ruleset with no rule arguments creates an empty ruleset.
combined-ruleset is a symbol, then the database table created for
the new ruleset will be named name. Calling
combined-ruleset with no ruleset arguments creates an empty
ruleset.
Two rulesets are defined by this package.
Take care when using both distribute* and distribute/
simultaneously. It is possible to put / into an infinite loop.
You can specify how sum and product expressions containing non-numeric
elements simplify by specifying the rules for + or * for
cases where expressions involving objects reduce to numbers or to
expressions involving different non-numeric elements.
cars are sub-op1 and
sub-op2, respectively. The argument reduction is a
procedure accepting 2 arguments which will be lists whose cars
are sub-op1 and sub-op2.
car is sub-op1, and
some other argument. Reduction will be called with the list whose
car is sub-op1 and some other argument.
If reduction returns #f, the reduction has failed and other
reductions will be tried. If reduction returns a non-false value,
that value will replace the two arguments in arithmetic (+,
-, and *) calculations involving non-numeric elements.
The operations + and * are assumed commutative; hence both
orders of arguments to reduction will be tried if necessary.
The following rule is the definition for distributing * over
+.
(cring:define-rule '* '+ 'identity (lambda (exp1 exp2) (apply + (map (lambda (trm) (* trm exp2)) (cdr exp1))))))
The first step in creating your commutative ring is to write procedures to create elements of the ring. A non-numeric element of the ring must be represented as a list whose first element is a symbol or string. This first element identifies the type of the object. A convenient and clear convention is to make the type-identifying element be the same symbol whose top-level value is the procedure to create it.
(define (n . list1)
(cond ((and (= 2 (length list1))
(eq? (car list1) (cadr list1)))
0)
((not (term< (first list1) (last1 list1)))
(apply n (reverse list1)))
(else (cons 'n list1))))
(define (s x y) (n x y))
(define (m . list1)
(cond ((neq? (first list1) (term_min list1))
(apply m (cyclicrotate list1)))
((term< (last1 list1) (cadr list1))
(apply m (reverse (cyclicrotate list1))))
(else (cons 'm list1))))
Define a procedure to multiply 2 non-numeric elements of the ring. Other multiplicatons are handled automatically. Objects for which rules have not been defined are not changed.
(define (n*n ni nj)
(let ((list1 (cdr ni)) (list2 (cdr nj)))
(cond ((null? (intersection list1 list2)) #f)
((and (eq? (last1 list1) (first list2))
(neq? (first list1) (last1 list2)))
(apply n (splice list1 list2)))
((and (eq? (first list1) (first list2))
(neq? (last1 list1) (last1 list2)))
(apply n (splice (reverse list1) list2)))
((and (eq? (last1 list1) (last1 list2))
(neq? (first list1) (first list2)))
(apply n (splice list1 (reverse list2))))
((and (eq? (last1 list1) (first list2))
(eq? (first list1) (last1 list2)))
(apply m (cyclicsplice list1 list2)))
((and (eq? (first list1) (first list2))
(eq? (last1 list1) (last1 list2)))
(apply m (cyclicsplice (reverse list1) list2)))
(else #f))))
Test the procedures to see if they work.
;;; where cyclicrotate(list) is cyclic rotation of the list one step
;;; by putting the first element at the end
(define (cyclicrotate list1)
(append (rest list1) (list (first list1))))
;;; and where term_min(list) is the element of the list which is
;;; first in the term ordering.
(define (term_min list1)
(car (sort list1 term<)))
(define (term< sym1 sym2)
(string<? (symbol->string sym1) (symbol->string sym2)))
(define first car)
(define rest cdr)
(define (last1 list1) (car (last-pair list1)))
(define (neq? obj1 obj2) (not (eq? obj1 obj2)))
;;; where splice is the concatenation of list1 and list2 except that their
;;; common element is not repeated.
(define (splice list1 list2)
(cond ((eq? (last1 list1) (first list2))
(append list1 (cdr list2)))
(else (error 'splice list1 list2))))
;;; where cyclicsplice is the result of leaving off the last element of
;;; splice(list1,list2).
(define (cyclicsplice list1 list2)
(cond ((and (eq? (last1 list1) (first list2))
(eq? (first list1) (last1 list2)))
(butlast (splice list1 list2) 1))
(else (error 'cyclicsplice list1 list2))))
(N*N (S a b) (S a b)) => (m a b)
Then register the rule for multiplying type N objects by type N objects.
(cring:define-rule '* 'N 'N N*N))
Now we are ready to compute!
(define (t)
(define detM
(+ (* (S g b)
(+ (* (S f d)
(- (* (S a f) (S d g)) (* (S a g) (S d f))))
(* (S f f)
(- (* (S a g) (S d d)) (* (S a d) (S d g))))
(* (S f g)
(- (* (S a d) (S d f)) (* (S a f) (S d d))))))
(* (S g d)
(+ (* (S f b)
(- (* (S a g) (S d f)) (* (S a f) (S d g))))
(* (S f f)
(- (* (S a b) (S d g)) (* (S a g) (S d b))))
(* (S f g)
(- (* (S a f) (S d b)) (* (S a b) (S d f))))))
(* (S g f)
(+ (* (S f b)
(- (* (S a d) (S d g)) (* (S a g) (S d d))))
(* (S f d)
(- (* (S a g) (S d b)) (* (S a b) (S d g))))
(* (S f g)
(- (* (S a b) (S d d)) (* (S a d) (S d b))))))
(* (S g g)
(+ (* (S f b)
(- (* (S a f) (S d d)) (* (S a d) (S d f))))
(* (S f d)
(- (* (S a b) (S d f)) (* (S a f) (S d b))))
(* (S f f)
(- (* (S a d) (S d b)) (* (S a b) (S d d))))))))
(* (S b e) (S c a) (S e c)
detM
))
(pretty-print (t))
-|
(- (+ (m a c e b d f g)
(m a c e b d g f)
(m a c e b f d g)
(m a c e b f g d)
(m a c e b g d f)
(m a c e b g f d))
(* 2 (m a b e c) (m d f g))
(* (m a c e b d) (m f g))
(* (m a c e b f) (m d g))
(* (m a c e b g) (m d f)))
(require 'determinant) (determinant '((1 2) (3 4))) => -2 (determinant '((1 2 3) (4 5 6) (7 8 9))) => 0 (determinant '((1 2 3 4) (5 6 7 8) (9 10 11 12))) => 0
Go to the first, previous, next, last section, table of contents.