Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 10/2022

ПРИМЕРЫ ЭФФЕКТИВНЫХ СИСТЕМ СЧИСЛЕНИЯ

This preprint was accepted October 3, 2022

АННОТАЦИЯ:

 Данная работа посвящена изучению нескольких конкрет-
ных примеров эффективных систем счисления, т.е. способов представле-
ния вещественных и других чисел, для которых проверка на равенство,
сложение и вычитание могут быть реализованы с помощью конечных ав-
томатов. В качестве первого из таких примеров рассматривается избы-
точная двоичная система, основанная на альтернативной конструкции
вещественного отрезка из [AB3],3.1.21, и обсуждается, каким образом
сложение в этой системе может быть реализовано с помощью локальных
правил сложения, задействующих только конечное число цифр слагае-
мых для вычисления очередной цифры суммы. Такого рода конструкции
интересны потому, что они проясняют аналогию между Q p и F p ((T)), т.е.
между числовыми и функциональными глобальными полями. Затем эти
результаты обобщаются на случай систем счисления с другими основа-
ниями, а также чисел, бесконечных в обе стороны.
 

Ключевые слова:   
 Абсолютная геометрия, поле из одного элемента,
двоичная система счисления, избыточная двоичная система счисления,
эффективные системы счисления, конечные автоматы, локальные пра-
вила сложения.

N. V. Durov



Examples of efficient numeral systems




ABSTRACT:

This work is dedicated to the study of several specific examples of
efficient numeral systems, i.e. ways of representing real or other numbers
in such a manner that the equality check, addition and subtraction may be
implemented by means of finite automata. The first of these examples is the
redundant binary system, based on the alternative construction of the real
segment from [AB3], 3.1.21. We discuss how the addition in this numeral
system may be implemented by means of local addition rules that use only a
fixed number of digits of the two summands to compute an arbitrary digit of
the sum. Such constructions are interesting because they clarify the
analogy between ${\mathbb Q}_p$ and ${\mathbb F}_p((T))$, i.e. between
number-theoretical and functional global fields. These results are extended
afterwards to the case of numeral systems with other bases, and to numbers
that are infinite in both directions.
   
  

Key words: 
 
 Absolute geometry, field with one element, binary system, redundant binary
system, efficient numeral systems, finite automata, local addition rules
 
 

 [Full text:
   (.pdf.gz)]






Back to all preprints


Back to the Steklov
Institute of Mathematics at St.Petersburg