Форум программистов, компьютерный форум, киберфорум
Mysterious Light
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  

Монотонное кодирование действительных чисел последовательностью натуральных

Запись от Mysterious Light размещена 21.10.2021 в 02:09
Показов 2239 Комментарии 5

Просто заметка на основе мыслей, пришедших с восходом луны.
Поскольку едва ли из этого может что-то теоретически или практически полезное получиться, выкладываю здесь.

Итак, мы знаем, как представлять натуральные числа в программе: есть классическая длинная арифметика, нумералы Чёрча и т.д. и т.п.
Мы знаем, как работать с рациональными числами.
Есть действительные числа. Хочется их как-то представить. Можно представить в виде последовательности цифр 10-й записи, можно в виде сходящейся последовательности рациональных чисел, которыми действительное число приближается с некоторой точностью и т.д.

Цепные дроби

Весьма интересный подход — цепные дроби.
https://www.cyberforum.ru/cgi-bin/latex.cgi?x = x_1 + \frac{1}{x_2 + \frac{1}{x_3 + \ldots}}
где x1,x2,x3,... — натуральные числа, а x > 1 — произвольное действительное число.
Таким образом, любое x > 1 можно однозначно разложить в последовательность [x1, x2, x3, ...] натуральных чисел. Если последовательность конечна, это рациональное число; если бесконечная — иррациональное.

Неприятной особенностью цепных дробей является попеременное переворачивание монотонности.
Так, число [1, 2, 3] меньше [2, 3, 4], потому что первый член (целая часть числа) меньше, но в то же время больше [1, 3, 4], потому что при совпадающем первом члене второй больше.

Было бы наглядно нарисовать шкалу (действительную ось с числами) для [1, k], [1, 2, k] и других примеров. Но не в рамках заметки, сами нарисуйте. Суть в том, что когда k стоит на чётных позициях, числа упорядочены по убыванию, а на нечётных — по возрастанию.

Монотонное кодирование

Без лишних слов.

Положительное действительное число x мы разбиваем на целую часть x1 и дробную {x}, как и в цепных дробях.
Целая часть — первый член последовательности.
дробную часть мы преобразуем функцией {x} / (1 - {x})
https://www.cyberforum.ru/cgi-bin/latex.cgi?x' = \frac{\{x\}}{1 - \{x\}}
Число x' раскладываем рекурсивно — это остаток последовательности.

Пример 1. x = 7/4
x1 = 1 (целая часть)
{x} = 3/4 (дробная часть)
x' = 3/4 : (1 - 3/4) = 3
Ответ: [1, 3]

Пример 2. x = 7/5
x1 = 1
{x} = 2/5
x' = 2/5 : (1 - 2/5) = 2/3
x2 = 0
x'' = 2/3 : (1 - 2/3) = 2
x3 = 2
Ответ: [1, 0, 2]

Особенность этого разложение в том, что
1. оно монотонно. Если x < y, разложение x лексикографически меньше разложения y.
2. натуральные n представляются [n], как и цепные дроби.
3. 1/n представляются последовательность [0,0,0,...,0,0,1], в которой (n-1) ноль.
4. Члены последовательности преимущественно небольшие числа; очень часто встречается ноль в последовательности.

Обратное преобразование:
https://www.cyberforum.ru/cgi-bin/latex.cgi?[x_1, x_2, \ldots] = x_1 + \frac{[x_2, \ldots]}{1 + [x_2, \ldots]}

Proof of concept
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/** Класс для работы с рациональными числами */
class Rat {
  constructor(num, denom) {
    if (!Number.isInteger(num) || !Number.isInteger(denom)) throw `not integers ${num} / ${denom}`;
    this.num = num;
    this.denom = denom;
  }
  toString() {
    return this.num + '/' + this.denom;
  }
  norm() {
    function euc(x, y) {
      if (x > y) return euc(y, x);
      if (x === 0) return y;
      if (x === 1) return 1;
      return euc(y % x, x);
    }
    const c = euc(Math.abs(this.num), Math.abs(this.denom));
    this.num = this.num / c;
    this.denom = this.denom / c;
    return this;
  }
  mult(r) {
    return new Rat(this.num * r.num, this.denom * r.denom).norm();
  }
  add(r) {
    return new Rat(this.num * r.denom + this.denom * r.num, this.denom * r.denom).norm();
  }
  minus(r) {
    return new Rat(this.num * r.denom - this.denom * r.num, this.denom * r.denom).norm();
  }
  inv() {
    return new Rat(this.denom, this.num);
  }
}
 
/** наивная реализация, x — Number */
function repr(x) {
  const a = Math.floor(x);
  const b = x - a;
  if (b < 1e-6) return [a];
  return [a, ...repr(b / (1 - b))];
}
 
/** разложение рационального x, после lim члена ставится NaN */
function reprRat(x, lim = 10) {
  const a = Math.floor(x.num / x.denom);
  const b = new Rat(x.num % x.denom, x.denom);
  if (lim === 0) return [NaN];
  if (b.num === 0) return [a];
  return [
    a,
    ...reprRat(
      b.mult(new Rat(1, 1).minus(b).inv()),
      lim - 1,
     )
  ];
}
 
/** перевод разложения в рациональное число, конечный NaN (если есть) обрезается */
function intRat([a, ...r]) {
  if (Number.isNaN(a)) return new Rat(0, 1);
  if (r.length === 0) return new Rat(a, 1);
  const z = intRat(r);
  const y = z.mult(new Rat(1, 1).add(z).inv());
  return y.add(new Rat(a, 1));
}
 
console.log(intRat(reprRat(new Rat(2, 3))).toString()); // 2/3
console.log(reprRat(new Rat(7, 4))); // [1, 3]
На что можно посмотреть
Как выглядит сложение, умножение, деление чисел в терминах таких последовательностей?
Я посмотрел только умножение [x1, x2, ...] на натуральное число n (2, 3, ...) и там довольно интересно определяется, когда к старшему разряду n*x1 нужно прибавлять единицу (или большее число) за счёт того, что дробная часть больше 1/n.
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 5
Комментарии
  1. Старый комментарий
    Предлагаю формулы Эйлера. Возможно, что они вам понравятся. А нет - значит нет.

    Эйлер вывел рекуррентные формулы для вычисления числителей и знаменателей подходящих дробей: (a0, a1, a2, ... an, ... - цепная (непрерывная) дробь)

    https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
p_{-1}=1,\; p_{0}=a_{0}, \;p_{n}=a_{n}p_{n-1}+p_{n-2}<br />
<br />
 q_{-1}=0,\; q_{0}=1, \;q_{n}=a_{n}q_{n-1}+q_{n-2}<br />
    первая подходящая дробь имеет условный вид https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{p_{-1}}{q_{-1}}=\frac10
    вторая подходящая дробь имеет вид https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{p_{0}}{q_{0}}=\frac{a_0}{1}

    и энная подходящая дробь https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{p_{n}}{q_{n}}=\frac{a_{n}p_{n-1}+p_{n-2}}{a_{n}q_{n-1}+q_{n-2}}
    Запись от wer1 размещена 21.10.2021 в 10:17 wer1 вне форума
  2. Старый комментарий
    Да, что-то я упустил эти формулы из поля зрения.

    Кстати, известно ли что-нибудь о том, как складывать и умножать цепные дроби?
    Запись от Mysterious Light размещена 21.10.2021 в 11:05 Mysterious Light вне форума
  3. Старый комментарий
    О!
    Кстати, ваши последовательности,имхо, обладают аналогичным достоинством.
    Запись от iifat размещена 21.10.2021 в 15:33 iifat вне форума
  4. Старый комментарий
    Цитата Сообщение от Mysterious Light
    Кстати, известно ли что-нибудь о том, как складывать и умножать цепные дроби?
    Нет. Таких операций с цепными дробями нет.

    Подходящие дроби всегда несократимы.
    Возможно вам пригодятся эти формулы для оценки погрешности вычислений
    https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
{\frac {p_{n}}{q_{n}}}-{\frac {p_{n-1}}{q_{n-1}}}={\frac {(-1)^{n-1}}{q_{n-1}q_{n}}}<br />
<br />
\left|x-{\frac {p_{n-1}}{q_{n-1}}}\right|\;<\; \left|  \frac {p_{n}}{q_{n}}-{\frac {p_{n-1}}{q_{n-1}}}\right| \;<\;\frac{1}{q_{n-1}q_n}\;<\;\frac{1}{q_{n-1}^2}<br />
    Запись от wer1 размещена 21.10.2021 в 15:45 wer1 вне форума
  5. Старый комментарий
    Цитата Сообщение от iifat
    О!
    Кстати, ваши последовательности,имхо, обладают аналогичным достоинством.
    Ещё не смотрел. По идее, должны, поскольку единственное отличие от цепных дробей — использование другой линейной рациональной функции x/(1-x) вместо 1/x.

    Кстати, особая радость убогим приходит от того, что x/(1-x) в сохраняет ноль, а 1 соответствует точке x=1/2. Это при умножении числа на 2 очень удобно: фактически, вопрос о том, нужно ли к 2*x1 прибавлять дополнительную единицу решается просто сравнением x2<1.

    P.S. исходно я искал кодирование, которое позволило бы легко алгоритмически работать с любыми конечными рациональными аппроксимациями. Но это в прошлом. Ибо полная луна прошла, и более сие меня не тревожит.
    Запись от Mysterious Light размещена 21.10.2021 в 17:48 Mysterious Light вне форума
 
Новые блоги и статьи
тв 16 бой ии
anaschu 27.07.2026
Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк
anaschu 27.07.2026
НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .
Очистка реквизитов и табличных частей документа при копировании
Maks 26.07.2026
Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .
Доктрина интенционального знания - Доктрина для портала "Срез".
Hrethgir 25.07.2026
Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых
anaschu 25.07.2026
Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил
anaschu 25.07.2026
две стороны одной монеты
Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад).
Hrethgir 24.07.2026
В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .
Вот представьте что вам дали бессмертие.
kumehtar 24.07.2026
Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru