# development of a framework for numeral systems

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

See also [sage-devel](http://groups.google.com/group/sage-devel/browse_thread/thread/b72a75c33a61e4da)

I agree that sage-devel is probably a better forum for this conversation than ask.sagemath.org. Or the Sage wiki: http://wiki.sagemath.org/.

The reason I put it here is the following: Here are maybe more people working in numeration than on sage-devel. Some comments of them would help...