open-axiom repository from github
\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra defaults.spad}
\author{Michael Monagan}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{package REPSQ RepeatedSquaring}
<<package REPSQ RepeatedSquaring>>=
)abbrev package REPSQ RepeatedSquaring
++ Repeated Squaring
++ Description:
++ Implements exponentiation by repeated squaring
++ RelatedOperations: expt
RepeatedSquaring(S): Exports == Implementation where
S: SetCategory with
*: (%,%)->%
++ x*y returns the product of x and y
Exports == with
expt: (S,PositiveInteger) -> S
++ expt(r, i) computes r**i by repeated squaring
Implementation == add
expt(x, n) ==
one? n => x
odd?(n)$Integer=> x * expt(x*x,shift(n,-1) pretend PositiveInteger)
expt(x*x,shift(n,-1) pretend PositiveInteger)
@
\section{package REPDB RepeatedDoubling}
<<package REPDB RepeatedDoubling>>=
)abbrev package REPDB RepeatedDoubling
++ Repeated Doubling
++ Integer multiplication by repeated doubling.
++ Description:
++ Implements multiplication by repeated addition
++ RelatedOperations: *
RepeatedDoubling(S):Exports ==Implementation where
S: SetCategory with
+: (%,%)->%
++ x+y returns the sum of x and y
Exports == with
double: (PositiveInteger,S) -> S
++ double(i, r) multiplies r by i using repeated doubling.
Implementation == add
double(n,x) ==
one? n => x
odd?(n)$Integer =>
x + double(shift(n,-1) pretend PositiveInteger,(x+x))
double(shift(n,-1) pretend PositiveInteger,(x+x))
@
\section{package FLASORT FiniteLinearAggregateSort}
<<package FLASORT FiniteLinearAggregateSort>>=
)abbrev package FLASORT FiniteLinearAggregateSort
++ FiniteLinearAggregateSort
++ Sort package (in-place) for ShallowlyMutable Finite Linear Aggregates
++ Author: Michael Monagan Sep/88
++ RelatedOperations: sort
++ Description:
++ This package exports 3 sorting algorithms which work over
++ FiniteLinearAggregates.
FiniteLinearAggregateSort(S, V): Exports == Implementation where
S: Type
V: Join(FiniteLinearAggregate S,ShallowlyMutableAggregate S)
B ==> Boolean
I ==> Integer
Exports ==> with
quickSort: ((S, S) -> B, V) -> V
++ quickSort(f, agg) sorts the aggregate agg with the ordering function
++ f using the quicksort algorithm.
heapSort : ((S, S) -> B, V) -> V
++ heapSort(f, agg) sorts the aggregate agg with the ordering function
++ f using the heapsort algorithm.
shellSort: ((S, S) -> B, V) -> V
++ shellSort(f, agg) sorts the aggregate agg with the ordering function
++ f using the shellSort algorithm.
Implementation ==> add
siftUp : ((S, S) -> B, V, I, I) -> Void
partition: ((S, S) -> B, V, I, I, I) -> I
QuickSort: ((S, S) -> B, V, I, I) -> V
quickSort(l, r) == QuickSort(l, r, minIndex r, maxIndex r)
siftUp(l, r, i, n) ==
t := qelt(r, i)
while (j := 2*i+1) < n repeat
if (k := j+1) < n and l(qelt(r, j), qelt(r, k)) then j := k
if l(t,qelt(r,j)) then
qsetelt!(r, i, qelt(r, j))
qsetelt!(r, j, t)
i := j
else leave
heapSort(l, r) ==
not zero? minIndex r => error "not implemented"
n := (#r)::I
for k in shift(n,-1) - 1 .. 0 by -1 repeat siftUp(l, r, k, n)
for k in n-1 .. 1 by -1 repeat
swap!(r, 0, k)
siftUp(l, r, 0, k)
r
partition(l, r, i, j, k) ==
-- partition r[i..j] such that r.s <= r.k <= r.t
x := qelt(r, k)
t := qelt(r, i)
qsetelt!(r, k, qelt(r, j))
while i < j repeat
if l(x,t) then
qsetelt!(r, j, t)
j := j-1
t := qsetelt!(r, i, qelt(r, j))
else (i := i+1; t := qelt(r, i))
qsetelt!(r, j, x)
j
QuickSort(l, r, i, j) ==
n := j - i
if one? n and l(qelt(r, j), qelt(r, i)) then swap!(r, i, j)
n < 2 => return r
-- for the moment split at the middle item
k := partition(l, r, i, j, i + shift(n,-1))
QuickSort(l, r, i, k - 1)
QuickSort(l, r, k + 1, j)
shellSort(l, r) ==
m := minIndex r
n := maxIndex r
-- use Knuths gap sequence: 1,4,13,40,121,...
g := 1
while g <= (n-m) repeat g := 3*g+1
g := g quo 3
while positive? g repeat
for i in m+g..n repeat
j := i-g
while j >= m and l(qelt(r, j+g), qelt(r, j)) repeat
swap!(r,j,j+g)
j := j-g
g := g quo 3
r
@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
-- - Redistributions of source code must retain the above copyright
-- notice, this list of conditions and the following disclaimer.
--
-- - Redistributions in binary form must reproduce the above copyright
-- notice, this list of conditions and the following disclaimer in
-- the documentation and/or other materials provided with the
-- distribution.
--
-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the
-- names of its contributors may be used to endorse or promote products
-- derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>
<<package REPSQ RepeatedSquaring>>
<<package REPDB RepeatedDoubling>>
<<package FLASORT FiniteLinearAggregateSort>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}