help links subscribe changes refresh edit

	SandBox
SandBoxDOPT ←	↑	→ SandBoxDemoXFreeAlgebra

SandBoxDefineInteger

Edit detail for SandBoxDefineInteger revision 9 of 11

	1 2 3 4 5 6 7 8 9 10 11
Editor: Bill Page Time: 2008/07/27 11:11:48 GMT-7
Note: A mathematician, a biologist and a physicist

added:

From BillPage Sun Jul 27 11:11:48 -0700 2008
From: Bill Page
Date: Sun, 27 Jul 2008 11:11:48 -0700
Subject: A mathematician, a biologist and a physicist
Message-ID: <20080727111148-0700@axiom-wiki.newsynthesis.org>

are sitting in a street café watching people entering and leaving the house on the other side of the street. First they see two people entering the house. Time passes. After a while they notice three people leaving the house. The physicist says, "The measurement wasn't accurate." The biologist says, "They must have reproduced." The mathematician says, "If one more person enters the house then it will be empty."

http://en.wikipedia.org/wiki/Mathematical_joke

Why are the domains PositiveInteger and NonNegativeInteger defined as
[SubDomain]s of Integer insteadof the other way around? Here is a
(still somewhat imperfect) example of one way of defining Integer
from a more primitive domain (some domain without negatives and
perhaps without zero, sometimes called a rig - ring without
negative) although Axiom does not currently implement such a
category. (Related: category RNG - ring without identity).

John Baez wrote:
Rigs are neglected in ordinary algebra texts, a deficiency that someday must be fixed.  Why?  First, a lot of stuff that’s true about rings is still true about rigs.  Second, and much more importantly, any approach to algebra that doesn’t make room for the natural numbers is clearly defective: the natural numbers are a fundamental algebraic structure that must be reckoned with!

http://golem.ph.utexas.edu/category/2008/05/theorems_into_coffee_iii.html
(Refer also to his discussion of PROPS.)
Most CAS doesn't bother to define natural numbers via the Peano Axioms
and then derive integers, for example, as an equivalence class of pairs
of natural numbers so that
  (a, b) ~ (c, d)  iff a + d = b + c.

The question is whether a compiler could be smart enough to replace
the definition via equivalence classes by an efficient representation
that is, for example, used by GMP.
First let's define a constructor name Difference. Like Fraction
the representation will be pairs of some suitable type and equality
will be defined by an equivalence relation on this representation.
Integer then can be constructed as Difference(CardinalNumber)
as a kind of algebraic "quotient".
\begin{spad}
)abbrev domain DIFF Difference
Difference(T:Join(Monoid,AbelianMonoid,OrderedSet,RetractableTo(NonNegativeInteger))): Join(Monoid,AbelianMonoid, OrderedSet,RetractableTo(NonNegativeInteger)) with
    _-:(%,%) -> %
  == add
    Rep == Record(neg:T, pos:T)

== per [0,0]
    1 == per [0,1]


    -- binary search for the canonical representative
    canonize(x:Rep):Rep ==
      y:= [0,0]@Rep
      while x.neg+y.pos < x.pos repeat
        n:T:=1
        while x.neg+y.pos+(nn:=n+n) <= x.pos repeat n:=nn
        y.pos:=y.pos+n
      while x.neg > x.pos+y.neg repeat
        n:T:=1
        while x.neg >= x.pos+y.neg+(nn:=n+n) repeat n:=nn
        y.neg := y.neg+n
      y
    x+y == per canonize [rep(x).neg+rep(y).neg, rep(x).pos+rep(y).pos]
    x-y == per canonize [rep(x).neg+rep(y).pos, rep(x).pos+rep(y).neg]
    x=y == rep(x).pos+rep(y).neg = rep(x).neg+rep(y).pos
    xy == rep(x).pos+rep(y).neg > rep(x).neg+rep(y).pos
    -- how to define this properly?
    coerce(x:%):OutputForm ==
      x<0 => -(rep(x).neg::OutputForm)
      rep(x).pos::OutputForm
    coerce(x:NonNegativeInteger):% == per [0,coerce(x)$T]
\end{spad}

Now use DIFF to define an "Integer"
\begin{axiom}
i:DIFF(CardinalNumber)
i:=2
j:=i-4
k:=j+2
test(k=0)
i:=1234567
j:=i-7654321
k:=j+6666666-246912
test(k=0)
\end{axiom}
The point of this construction is to illustrate several problems.
One such problem is that current generation of compilers in computer
algebra systems such as Axiom, specifically Spad and Aldor, are not
able to automatically convert this presumably mathematically correct
specification to an efficient implementation, e.g. signed integers.
Another issue is why these languages do not have some built-in
support for such common algebraic constructions as "taking a quotient".
In particular, there seems to be no general way of defining a
"canonical representation".


A mathematician, a biologist and a physicist --Bill Page,  Sun, 27 Jul 2008 11:11:48 -0700 reply
are sitting in a street café watching people entering and leaving the house on the other side of the street. First they see two people entering the house. Time passes. After a while they notice three people leaving the house. The physicist says, "The measurement wasn't accurate." The biologist says, "They must have reproduced." The mathematician says, "If one more person enters the house then it will be empty."
http://en.wikipedia.org/wiki/Mathematical_joke

    Some or all expressions may not have rendered properly,
    because Axiom returned the following error:
Error: export AXIOM=/usr/local/lib/open-axiom/x86_64-unknown-linux/1.2.0-2008-05-25; export ALDORROOT=/usr/local/aldor/linux/1.1.0; export PATH=$ALDORROOT/bin:$PATH; export HOME=/var/zope2/var/LatexWiki; ulimit -t 600; export LD_LIBRARY_PATH=/usr/local/lib/open-axiom/x86_64-unknown-linux/1.2.0-2008-05-25/lib; LANG=en_US.UTF-8 $AXIOM/bin/AXIOMsys < /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/4266624928682846865-25px.axm
/bin/sh: /usr/local/lib/open-axiom/x86_64-unknown-linux/1.2.0-2008-05-25/bin/AXIOMsys: not found

Some or all expressions may not have rendered properly, because Latex returned the following error:

This is pdfTeXk, Version 3.141592-1.40.3 (Web2C 7.5.6)
 \write18 enabled.
 %&-line parsing enabled.
entering extended mode
(./1613466205686906490-16.0px.tex
LaTeX2e <2005/12/01>
Babel <v3.8h> and hyphenation patterns for english, usenglishmax, dumylang, noh
yphenation, arabic, farsi, croatian, ukrainian, russian, bulgarian, czech, slov
ak, danish, dutch, finnish, basque, french, german, ngerman, ibycus, greek, mon
ogreek, ancientgreek, hungarian, italian, latin, mongolian, norsk, icelandic, i
nterlingua, turkish, coptic, romanian, welsh, serbian, slovenian, estonian, esp
eranto, uppersorbian, indonesian, polish, portuguese, spanish, catalan, galicia
n, swedish, ukenglish, pinyin, loaded.
(/usr/share/texmf-texlive/tex/latex/base/article.cls
Document Class: article 2005/09/16 v1.4f Standard LaTeX document class
(/usr/share/texmf-texlive/tex/latex/base/size12.clo))
(/usr/share/texmf-texlive/tex/latex/ucs/ucs.sty
(/usr/share/texmf-texlive/tex/latex/ucs/data/uni-global.def))
(/usr/share/texmf-texlive/tex/latex/base/inputenc.sty
(/usr/share/texmf-texlive/tex/latex/ucs/utf8x.def))
(/usr/share/texmf-texlive/tex/latex/bbm/bbm.sty)
(/usr/share/texmf-texlive/tex/latex/jknapltx/mathrsfs.sty)
(/usr/share/texmf-texlive/tex/latex/base/fontenc.sty
(/usr/share/texmf-texlive/tex/latex/base/t1enc.def))
(/usr/share/texmf-texlive/tex/latex/pstricks/pstricks.sty
(/usr/share/texmf-texlive/tex/generic/pstricks/pstricks.tex
`PSTricks' v1.15  <2006/12/22> (tvz)
(/usr/share/texmf-texlive/tex/generic/pstricks/pstricks.con))
(/usr/share/texmf/tex/latex/xcolor/xcolor.sty
(/etc/texmf/tex/latex/config/color.cfg)
(/usr/share/texmf-texlive/tex/latex/graphics/dvips.def)
(/usr/share/texmf-texlive/tex/latex/graphics/dvipsnam.def)))
(/usr/share/texmf-texlive/tex/latex/graphics/epsfig.sty
(/usr/share/texmf-texlive/tex/latex/graphics/graphicx.sty
(/usr/share/texmf-texlive/tex/latex/graphics/keyval.sty)
(/usr/share/texmf-texlive/tex/latex/graphics/graphics.sty
(/usr/share/texmf-texlive/tex/latex/graphics/trig.sty)
(/etc/texmf/tex/latex/config/graphics.cfg))))
(/usr/share/texmf-texlive/tex/latex/pst-grad/pst-grad.sty
(/usr/share/texmf-texlive/tex/generic/pst-grad/pst-grad.tex
(/usr/share/texmf-texlive/tex/latex/xkeyval/pst-xkey.tex
(/usr/share/texmf-texlive/tex/latex/xkeyval/xkeyval.sty
(/usr/share/texmf-texlive/tex/latex/xkeyval/xkeyval.tex)))
`pst-plot' v1.05, 2006/11/04 (tvz,dg,hv)))
(/usr/share/texmf-texlive/tex/latex/pstricks/pst-plot.sty
(/usr/share/texmf-texlive/tex/generic/pstricks/pst-plot.tex
 v97 patch 2, 1999/12/12
(/usr/share/texmf-texlive/tex/generic/multido/multido.tex
 v1.41, 2004/05/18 <tvz>)))
(/usr/share/texmf-texlive/tex/latex/geometry/geometry.sty
(/usr/share/texmf-texlive/tex/xelatex/xetexconfig/geometry.cfg)
Package geometry Warning: `lmargin' and `rmargin' result in NEGATIVE (-108.405p
t).
    `width' should be shortened in length.
) (/usr/share/texmf-texlive/tex/latex/amsmath/amsmath.sty
For additional information on amsmath, use the `? option.
(/usr/share/texmf-texlive/tex/latex/amsmath/amstext.sty
(/usr/share/texmf-texlive/tex/latex/amsmath/amsgen.sty))
(/usr/share/texmf-texlive/tex/latex/amsmath/amsbsy.sty)
(/usr/share/texmf-texlive/tex/latex/amsmath/amsopn.sty))
(/usr/share/texmf-texlive/tex/latex/amsfonts/amsfonts.sty)
(/usr/share/texmf-texlive/tex/latex/amsfonts/amssymb.sty)
(/usr/share/texmf-texlive/tex/latex/amscls/amsthm.sty)
(/usr/share/texmf-texlive/tex/latex/setspace/setspace.sty
Package: `setspace 6.7 <2000/12/01>
) (/usr/share/texmf-texlive/tex/generic/xypic/xy.sty
(/usr/share/texmf-texlive/tex/generic/xypic/xy.tex Bootstrap'ing: catcodes,
docmode, (/usr/share/texmf-texlive/tex/generic/xypic/xyrecat.tex)
(/usr/share/texmf-texlive/tex/generic/xypic/xyidioms.tex)
 Xy-pic version 3.7 <1999/02/16>
 Copyright (c) 1991-1998 by Kristoffer H. Rose <krisrose@ens-lyon.fr>
 Xy-pic is free software: see the User's Guide for details.

Loading kernel: messages; fonts; allocations: state, direction,
utility macros; pictures: \xy, positions, objects, decorations;
kernel objects: directionals, circles, text; options; algorithms: directions,
edges, connections;  Xy-pic loaded))
(/usr/share/texmf-texlive/tex/generic/xypic/xyall.tex
 Xy-pic option: All features v.3.3
(/usr/share/texmf-texlive/tex/generic/xypic/xycurve.tex
 Xy-pic option: Curve and Spline extension v.3.7 curve, circles, loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyframe.tex
 Xy-pic option: Frame and Bracket extension v.3.7 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xycmtip.tex
 Xy-pic option: Computer Modern tip extension v.3.3
(/usr/share/texmf-texlive/tex/generic/xypic/xytips.tex
 Xy-pic option: More Tips extension v.3.3 loaded) loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyline.tex
 Xy-pic option: Line styles extension v.3.6 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyrotate.tex
 Xy-pic option: Rotate and Scale extension v.3.3 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xycolor.tex
 Xy-pic option: Colour extension v.3.3 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xymatrix.tex
 Xy-pic option: Matrix feature v.3.4 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyarrow.tex
 Xy-pic option: Arrow and Path feature v.3.5 path, \ar, loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xygraph.tex
 Xy-pic option: Graph feature v.3.7 loaded) loaded)
(/usr/share/texmf-texlive/tex/latex/tools/verbatim.sty)
(/usr/share/texmf/tex/latex/graphviz/graphviz.sty
(/usr/share/texmf-texlive/tex/latex/psfrag/psfrag.sty))
(/usr/share/texmf/tex/latex/sagetex.sty
Writing sage input file 1613466205686906490-16.0px.sage
) (/usr/share/texmf-texlive/tex/latex/gnuplottex/gnuplottex.sty
(/usr/share/texmf-texlive/tex/latex/base/latexsym.sty)
(/usr/share/texmf-texlive/tex/latex/moreverb/moreverb.sty)
(/usr/share/texmf-texlive/tex/latex/base/ifthen.sty))
(./1613466205686906490-16.0px.aux)
(/usr/share/texmf-texlive/tex/latex/ucs/ucsencs.def)
 Missing $ inserted.
<inserted text> 
                $
l.124     _
           -:(%,%) -> %
(/usr/share/texmf-texlive/tex/latex/jknapltx/ursfs.fd)
(/usr/share/texmf-texlive/tex/latex/amsfonts/umsa.fd)
(/usr/share/texmf-texlive/tex/latex/amsfonts/umsb.fd)
(/usr/share/texmf-texlive/tex/latex/base/ulasy.fd)
 Missing $ inserted.
<inserted text> 
                $
l.127 
Overfull \hbox (92.3647pt too wide) in paragraph at lines 122--127
[]\T1/cmr/m/n/12 )abbrev do-main DIFF Dif-fer-ence Dif-fer-ence(T:Join(Monoid,A
belianMonoid,OrderedSet,RetractableTo(NonNegativeInteger))): Join(Monoid,Abelia
nMonoid,
Overfull \hbox (27.54955pt too wide) in paragraph at lines 131--143
\T1/cmr/m/n/12 x.neg+y.pos+(nn:=n+n) <= x.pos re-peat n:=nn y.pos:=y.pos+n whil
e x.neg > x.pos+y.neg re-peat n:T:=1 while x.neg >= x.pos+y.neg+(nn:=n+n)
Overfull \hbox (16.06366pt too wide) in paragraph at lines 144--149
\T1/cmr/m/n/12 x=y == rep(x).pos+rep(y).neg = rep(x).neg+rep(y).pos x<y == rep(
x).pos+rep(y).neg < rep(x).neg+rep(y).pos x>y == rep(x).pos+rep(y).neg
[1] (/usr/share/texmf-texlive/tex/latex/base/t1cmtt.fd)
LaTeX Warning: Characters dropped after `\end{axiom}' on input line 166.
[2] (./1613466205686906490-16.0px.aux) )
(see the transcript file for additional information)
Output written on 1613466205686906490-16.0px.dvi (2 pages, 2244 bytes).
Transcript written on 1613466205686906490-16.0px.log.