Монотонное кодирование действительных чисел последовательностью натуральных
Запись от Mysterious Light размещена 21.10.2021 в 02:09
Показов 2239
Комментарии 5
Метки math, арифметика, действительные числа, математика, цепные дроби
|
Просто заметка на основе мыслей, пришедших с восходом луны. Поскольку едва ли из этого может что-то теоретически или практически полезное получиться, выкладываю здесь. Итак, мы знаем, как представлять натуральные числа в программе: есть классическая длинная арифметика, нумералы Чёрча и т.д. и т.п. Мы знаем, как работать с рациональными числами. Есть действительные числа. Хочется их как-то представить. Можно представить в виде последовательности цифр 10-й записи, можно в виде сходящейся последовательности рациональных чисел, которыми действительное число приближается с некоторой точностью и т.д. Цепные дроби Весьма интересный подход — цепные дроби. где 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}) Число 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. Члены последовательности преимущественно небольшие числа; очень часто встречается ноль в последовательности. Обратное преобразование: Proof of concept
Как выглядит сложение, умножение, деление чисел в терминах таких последовательностей? Я посмотрел только умножение [x1, x2, ...] на натуральное число n (2, 3, ...) и там довольно интересно определяется, когда к старшему разряду n*x1 нужно прибавлять единицу (или большее число) за счёт того, что дробная часть больше 1/n. | |||||
Метки math, арифметика, действительные числа, математика, цепные дроби
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 5
Комментарии
-
Предлагаю формулы Эйлера. Возможно, что они вам понравятся. А нет - значит нет.
Эйлер вывел рекуррентные формулы для вычисления числителей и знаменателей подходящих дробей: (a0, a1, a2, ... an, ... - цепная (непрерывная) дробь)
первая подходящая дробь имеет условный вид
вторая подходящая дробь имеет вид
и энная подходящая дробьЗапись от wer1 размещена 21.10.2021 в 10:17
-
Да, что-то я упустил эти формулы из поля зрения.
Кстати, известно ли что-нибудь о том, как складывать и умножать цепные дроби?Запись от Mysterious Light размещена 21.10.2021 в 11:05
-
О!
Кстати, ваши последовательности,имхо, обладают аналогичным достоинством.Запись от iifat размещена 21.10.2021 в 15:33
-
Нет. Таких операций с цепными дробями нет.
Сообщение от Mysterious Light
Подходящие дроби всегда несократимы.
Возможно вам пригодятся эти формулы для оценки погрешности вычислений
Запись от wer1 размещена 21.10.2021 в 15:45
-
Ещё не смотрел. По идее, должны, поскольку единственное отличие от цепных дробей — использование другой линейной рациональной функции x/(1-x) вместо 1/x.
Сообщение от iifat
Кстати, особая радость убогим приходит от того, что x/(1-x) в сохраняет ноль, а 1 соответствует точке x=1/2. Это при умножении числа на 2 очень удобно: фактически, вопрос о том, нужно ли к 2*x1 прибавлять дополнительную единицу решается просто сравнением x2<1.
P.S. исходно я искал кодирование, которое позволило бы легко алгоритмически работать с любыми конечными рациональными аппроксимациями. Но это в прошлом. Ибо полная луна прошла, и более сие меня не тревожит.Запись от Mysterious Light размещена 21.10.2021 в 17:48


