axiom-developer
[Top][All Lists]

## [Axiom-developer] [BalancedFiniteField] (new)

 From: billpage Subject: [Axiom-developer] [BalancedFiniteField] (new) Date: Wed, 30 Mar 2005 06:10:04 -0600

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 ?

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}
--