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

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

Запись от Mysterious Light размещена 21.10.2021 в 02:09
Показов 2243 Комментарии 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 вне форума
 
Новые блоги и статьи
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники).
Hrethgir 04.08.2026
Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
Термопринтер QR701
Argus19 03.08.2026
Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа
Maks 03.08.2026
Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .
Задача предоставления скидок покупателям
Maks 03.08.2026
Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .
Почему SEO не начинается с ключевых слов: что проверить до написания текстов
Neotwalker 01.08.2026
Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .
Знание — сила: Доктрина интенциональности знаний, углубление в формулу
Hrethgir 01.08.2026
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru