[Axiom-developer] [BalancedFiniteField] (new)

[billpage]

Changes http://page.axiom-developer.org/zope/mathaction/BalancedFiniteField/diff
--
>From jimkraai Wed Mar 30 01:51:52 -0600 2005
From: jim kraai
Date: Wed, 30 Mar 2005 01:51:52 -0600
Subject: New to Axiom:  Implement 'Balanced' FiniteField ?
Message-ID: <address@hidden>

Greetings,

(I'm more of a pencil-n-paper math guy.)

A BalancedFiniteField representation of an integer n would be:
  the same as FiniteField (base) if n <= floor(n/2)
  else base - floor(n/2)

Examples::

  base of 4     base of 5 
  n  FF BFF     n  FF BFF 
  ----------    ----------
  0  0   0      0  0   0  
  1  1   1      1  1   1  
  2  2   2      2  2   2  
  3  3  -1      3  3  -2  
  4  0   0      4  0  -1  
  5  1   1      5  1   0  
                6  0   0  
                        
After reading the book chapters on Packages, Categorys, and Domains, I find 
that I'm no more clear on which is an effective way to get this output.

Thanks for any help,

--jim

<hr />

Perhaps this experimental code below will help. The new domain is based
on a simplified version of ZMOD. Notice that the definition of "balanced"
has been incorporated into the coerce function, taking care to avoid
division since it is not defined in these domains. But I am not certain
that this definition is exactly equivalent to Jim's definition above.

Are index and lookup correct for this representation?

\begin{axiom}
)abbrev domain BFF BalancedFiniteField
++ BalancedFiniteField(base) is based on ZMOD IntegerMod
BalancedFiniteField(p:PositiveInteger):
 Join(CommutativeRing, Finite, ConvertibleTo Integer, StepThrough) == add
    size()           == p
    characteristic() == p
    lookup x == ( x=0 => p; (convert(x)@Integer) :: PositiveInteger)

    Rep:= Integer

    convert(x:%):Integer == convert(x)$Rep
    coerce(n:Integer):%  == (mulmod(2,n,2*p)<=p =>
                              positiveRemainder(n, p);
                            (-positiveRemainder(p-n, p))::Integer)
                            
    coerce(x):OutputForm == coerce(x)$Rep
    0                    == 0$Rep
    1                    == 1$Rep
    init                 == 0$Rep
    nextItem(n)          ==
                              m:=n+1
                              m=0 => "failed"
                              m
    x = y                == x =$Rep y
    x:% * y:%            == mulmod(x, y, p)
    n:Integer * x:%      == mulmod(positiveRemainder(n::Rep, p), x, p)
    x + y                == addmod(x, y, p)
    x - y                == submod(x, y, p)
    random()             == random(p)$Rep
    index a              == positiveRemainder(a::Rep, p)
    - x                  == (zero? x => 0; p -$Rep x)
    x:% ** n:NonNegativeInteger == powmod(x, n::Rep, p)

    recip x ==
       (c1, c2, g) := extendedEuclidean(x, p)$Rep
       not (g = 1) => "failed"
       positiveRemainder(c1, p)

\end{axiom}

\begin{axiom}
for i in 0..5 repeat
  output([i,(i::ZMOD(4)),(i::BFF(4))])
\end{axiom}
\begin{axiom}
for i in 0..6 repeat
  output([i,i::ZMOD(5),i::BFF(5)])
\end{axiom}

Perhaps addition, subtraction and multiplication need to be examined
more closely.

\begin{axiom}
(-1::BFF(5))+(1::BFF(5))
(-1::BFF(5))-(1::BFF(5))
(1::BFF(5))+(1::BFF(5))
(2::BFF(5))*(3::BFF(5))
\end{axiom}
--
forwarded from http://page.axiom-developer.org/zope/mathaction/address@hidden