Algorithms, Dynamics and Geometry of Numeration systems
Project goals
Technical parameters of contemporary computers increasingly challenge the usage of non-standard numeration systems which may have essential impact on the complexity of arithmetic algorithms and on the precision of computation. The project concentrates on analysis of algorithmic, dynamic and geometric aspects of positional systems with real and complex algebraic bases, and as a generalization, on number representations generated by Möbius transformations. We will concentrate on the construction of Möbius number systems with better coding and distribution properties and more efficient arithmetic algorithms than the classical algorithms for positional systems. We will focus on the identification of Pisot or complex Pisot bases suitable for arithmetic in general algebraic number fields. We will describe the influence of redundancy of the digit set on the possibility and efficiency of parallel algorithms with beta-expansions. Essential will be the description of geometric properties of beta-integers using cut-and-project sets and methods of combinatorics on words.
Keywords
Non-standard numeration systemspositional systemsMöbius transformationirrational basealgebraic number fieldsPisot numberscomplex Pisot numbersbeta-integersbeta-expansionsarithmetic algorithms
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 17 (SGA0201300005)
Main participants
České vysoké učení technické v Praze / Fakulta jaderná a fyzikálně inženýrská
Univerzita Karlova / Centrum pro teoretická studiaContest type
VS - Public tender
Contract ID
13-03538S
Alternative language
Project name in Czech
Algoritmy, dynamika a geometrie numeračních systémů
Annotation in Czech
Technické parametry dnešní výpočetní techniky vybízejí k využití nestandardních číselných soustav, což podstatně ovlivní složitost aritmetických algoritmů a výpočetní přesnost. Projekt se soustředí na analýzu algortmických, dynamických a geometrických vlastností pozičních soustav s reálnou a komplexní algebraickou bází, a číselných reprezentací generovaných Möbiovými transformacemi, které poziční systémy zobecňují. Soustředíme se na na konstrukci möbiovských číselných systémů s lepšími kódovacími a distribučními vlastnostmi a efektivnějšími aritmetickými algoritmy než jsou klasické algoritmy pozičních systémů. Budeme hledat Pisotovy, případně komplexní Pisotovy báze vhodné pro provádění aritmetických operací v daném algebraickém tělese. Popíšeme vliv redundance abecedy na paralelizaci algoritmů s beta-rozvoji. Podstatným nástrojem bude popis geometrických vlastností beta-celých čísel, které budeme studovat pomocí cut-and-project metody a kombinatoriky na slovech.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
BA - General mathematics
CEP - another secondary branch
—
10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
New scientific results in the area of numeration systems were obtained. A Springer monography, 30 journal papers were published. The project team contained also students, qualification theses in the given area were supervised, workshops were organized. International aspectes were present - foreign guests, common publications with them. Financies were spent effectively.
Solution timeline
Realization period - beginning
Feb 1, 2013
Realization period - end
Dec 31, 2017
Project status
U - Finished project
Latest support payment
Apr 5, 2017
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP18-GA0-GA-U/02:1
Data delivery date
May 4, 2018
Finance
Total approved costs
7,465 thou. CZK
Public financial support
7,465 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
7 465 CZK thou.
Public support
7 465 CZK thou.
100%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 02. 2013 - 31. 12. 2017