Two skew-binary numeral systems and one application

TY - JOUR

T1 - Two skew-binary numeral systems and one application

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Jensen, Claus

AU - Katajainen, Jyrki

PY - 2012/1

Y1 - 2012/1

N2 - We introduce two numeral systems, the magical skew system and the regular skew system, and contribute to their theory development. For both systems, increments and decrements are supported using a constant number of digit changes per operation. Moreover, for the regular skew system, the operation of adding two numbers is supported efficiently. Our basic message is that some data-structural problems are better formulated at the level of a numeral system. The relationship between number representations and data representations, as well as operations on them, can be utilized for an elegant description and a clean analysis of algorithms. In many cases, a pure mathematical treatment may also be interesting in its own right. As an application of numeral systems to data structures, we consider how to implement a priority queue as a forest of pointer-based binary heaps. Some of the number-representation features that influence the efficiency of the priority-queue operations include weighting of digits, carry-propagation and borrowing mechanisms.

AB - We introduce two numeral systems, the magical skew system and the regular skew system, and contribute to their theory development. For both systems, increments and decrements are supported using a constant number of digit changes per operation. Moreover, for the regular skew system, the operation of adding two numbers is supported efficiently. Our basic message is that some data-structural problems are better formulated at the level of a numeral system. The relationship between number representations and data representations, as well as operations on them, can be utilized for an elegant description and a clean analysis of algorithms. In many cases, a pure mathematical treatment may also be interesting in its own right. As an application of numeral systems to data structures, we consider how to implement a priority queue as a forest of pointer-based binary heaps. Some of the number-representation features that influence the efficiency of the priority-queue operations include weighting of digits, carry-propagation and borrowing mechanisms.

KW - Numeral systems

KW - Data structures

KW - Priority queues

KW - Binary heaps

U2 - 10.1007/s00224-011-9357-0

DO - 10.1007/s00224-011-9357-0

M3 - Journal article

SN - 1432-4350

VL - 50

SP - 185

EP - 211

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 1

ER -