development of a framework for numeral systems

edit

I plan do build a framework for numeral systems. Below you find some thoughts written down. A draft of the possible class hierachy can also be found there. If you have any comments on those things or anything that should be also included in that framework, then don't hesidate to post them.

Daniel

Numeral Systems in Sage

draft

Goals

• representation of elements as digital expansions
• support of infinite expansions, multi-expansions (one position can have more digits)
• (fast) arithmetic of expansions (+, -, *, /, **)
• action of expansion on something (e.g. act on points of elliptic curve and e.g. performed a by a Horner scheme)
• support of languages on the expansion (e.g. w-NAF (non-adjacent form))
• different algorithms to calculate expansions (e.g. w-NAF (non- adjacent form))
• test for optimality of language
• calculation of sequences in conjunction with dynamical system together with the calculation of the expansions (cf. shift radix systems)
• support of continued fractions (some algorithms already exist for that and maxima supports continued fractions)
• support of joint expansions (digits are tuples)
• numeral systems often have connections to transducer; keep that in mind during the design process

Class Hierachy

Examples (of classes) of numeral systems are written with [].

NumeralSystem
 +-- PositionalNumeralSystem
 |    +-- IntegerTupleIndexNumeralSystem
 |         +-- IntegerIndexNumeralSystem
 |         |    +-- AbstractNumeralSystem
 |         |    |    +-- BaseNumeralSystem
 |         |    |         +-- AlgebraicBaseNumeralSystem
 |         |    |              +-- ImaginaryQuadraticBaseNumeralSystem
 |         |    |              |    +-- [QuaterImaginary]
 |         |    |              |    +--
[ImaginaryQuadraticBaseMNRDigits]
 |         |    |              +-- RealBaseNumeralSystem
 |         |    |                   +-- IntegerBaseNumeralSystem
 |         |    |                   |    +--
PositiveIntegerBaseNumeralSystem
 |         |    |                   |    |    +-- [Binary]
 |         |    |                   |    |    +-- [Decimal]
 |         |    |                   |    |    +-- [BalancedTernary]
 |         |    |                   |    |    +-- [Babylonian]
 |         |    |                   |    +--
NegativeIntegerBaseNumeralSystem
 |         |    |                   +-- [GoldenRatioBase]
 |         |    +-- MixedRadixNumeralSystem
 |         |    |    +-- RecurrenceNumeralSystem
 |         |    |    |    +-- [FibonacciBase]
 |         |    |    +-- [Money]
 |         |    |    +-- [FactorialNumeralSystem]
 |         |    |    +-- [DateTime]
 |         |    +-- [FactorNumeralSystem]
 |         +-- [IntegerDoubleBases]
 +-- [RomanNumeralSystem]
 +-- [UnaryNumeralSystem]

Some Notes on the classes

NumeralSystem:

• base class for everything (abstract base class)
• elements have +,-,*,/, but none is implemented (implementation in inherited class)

PositionalNumeralSystem:

• has function value_at_position(position, value) which gives value of singleton
• operation to add singletons can be given (e.g. addition)
• the positions can be everything (every hashable element of Sage)

IntegerTupleIndexNumeralSystem:

• positions are tuples (of fixed length) of integers

IntegerIndexNumeralSystem:

• positions are integers, special case of IntegerTupleIndexNumeralSystem

AbstractNumeralSystem:

• function \phi from base i to base i+1

MixedRadixNumeralSystem

• bases are fixed numbers b_0, b_1, b_2,...
• digits and bases are multiplied

BaseNumeralSystem

• inherited from both AbstractNumeralSystem and MixedRadixNumeralSystem
• bases are b^i

AlgebraicBaseNumeralSystem

• base b is a complex number (root of polynomial over ZZ)

ImaginaryQuadraticBaseNumeralSystem, RealBaseNumeralSystem, ...

• special cases of AlgebraicBaseNumeralSystem

RecurrenceNumeralSystem:

• recurrence on bases, e.g. b_n=2*b_{n-1}+b_{n-2}
• e.g. [FibonacciBase] # b_n = b_{n-1} + b_{n-2}

[Money]

• bases, e.g. for Euro, are 0.01, 0.02, 0.05, 0.10, 0.20, 0.50, 1, 2, 5, 10, 20, 50, 100, 200, 500

[FactorialNumeralSystem]

• bases 0!,1!,2!,... digits for position n! are 0...(n-1)

[DateTime]

• bases year, month, day, hour, minute, second