ultra-constructive-math - Kantor.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import itertools\n",
    "from decimal import Decimal as _Decimal, localcontext\n",
    "from functools import total_ordering, lru_cache, cached_property\n",
    "from copy import deepcopy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Вычисления непосредственно с числами"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# моя оболочка над decimal.Decimal, чтобы не терять точность при расчетах, без явного указания сколько значащих цифр в числах\n",
    "@total_ordering\n",
    "class Decimal:\n",
    "    def __init__(self, value):\n",
    "        if isinstance(value, Decimal):\n",
    "            self._value = value._value\n",
    "        else:\n",
    "            self._value = _Decimal(value)\n",
    "\n",
    "    def __add__(self, other):\n",
    "        other = Decimal(other)\n",
    "        digits_after_point = max([- self._value.as_tuple().exponent, - other._value.as_tuple().exponent, 0])\n",
    "        digits_before_point = max([self._value.adjusted() + 1, other._value.adjusted() + 1, 0])\n",
    "        with localcontext() as ctx:\n",
    "            ctx.prec = digits_after_point + digits_before_point + 1\n",
    "            return Decimal(self._value + other._value)\n",
    "\n",
    "    def __sub__(self, other):\n",
    "        other = Decimal(other)\n",
    "        digits_after_point = max([- self._value.as_tuple().exponent, - other._value.as_tuple().exponent, 0])\n",
    "        digits_before_point = max([self._value.adjusted() + 1, other._value.adjusted() + 1, 0])\n",
    "        with localcontext() as ctx:\n",
    "            ctx.prec = digits_after_point + digits_before_point + 1\n",
    "            return Decimal(self._value - other._value)\n",
    "\n",
    "    def __mul__(self, other):\n",
    "        other = Decimal(other)\n",
    "        with localcontext() as ctx:\n",
    "            ctx.prec = len(self._value.as_tuple().digits) + len(other._value.as_tuple().digits) + 1\n",
    "            return Decimal(self._value * other._value)\n",
    "\n",
    "    def divide(self, other, precision=0.001):\n",
    "        other = Decimal(other)\n",
    "        with localcontext() as ctx:\n",
    "            ctx.prec = len(self._value.as_tuple().digits) + len(other._value.as_tuple().digits) - min([precision._value.adjusted(), 0])\n",
    "            return Decimal(self._value / other._value)        \n",
    "        \n",
    "    def __repr__(self):\n",
    "        with localcontext() as ctx:\n",
    "            ctx.prec = len(self._value.as_tuple().digits) + 2\n",
    "            return('{}'.format(self._value.normalize()))\n",
    "    \n",
    "    def sqrt(self, precision):\n",
    "        with localcontext() as ctx:\n",
    "            ctx.prec = 3 - min([precision._value.adjusted(), 0])\n",
    "            return Decimal(self._value.sqrt())\n",
    "    \n",
    "    def get_value_with_precision(self, precision):\n",
    "        assert precision > 0\n",
    "        precision = Decimal(precision)\n",
    "        digits_after_point = - min([precision._value.adjusted(), 0])\n",
    "        digits_before_point = max([self._value.adjusted() + 1, 0])\n",
    "        with localcontext() as ctx:\n",
    "            ctx.prec = digits_after_point + digits_before_point + 1\n",
    "            return Decimal(self._value + 0) \n",
    "    \n",
    "    def get_value_with_digits(self, number_of_digits):\n",
    "        with localcontext() as ctx:\n",
    "            ctx.prec = number_of_digits\n",
    "            return Decimal(self._value + 0)         \n",
    "    \n",
    "    def order(self):\n",
    "        return self._value.adjusted()\n",
    "    \n",
    "    def shift(self, val):\n",
    "        return self * (_Decimal(10) ** val)\n",
    "    \n",
    "    def __abs__(self):\n",
    "        return Decimal(abs(self._value))\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        other = Decimal(other)        \n",
    "        return self._value < other._value\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        other = Decimal(other)        \n",
    "        return self._value == other._value\n",
    "    \n",
    "    def __int__(self):\n",
    "        assert self.is_integer()\n",
    "        return int(self._value)\n",
    "\n",
    "    def __hash__(self):\n",
    "        return hash(self._value)    \n",
    "    \n",
    "    def is_integer(self):\n",
    "        return _Decimal(int(self._value)) == self._value\n",
    "    \n",
    "    def __pow__(self, power):\n",
    "        assert isinstance(power, int), type(power)\n",
    "        assert power >= 0, power\n",
    "        with localcontext() as ctx:\n",
    "            ctx.prec = len(self._value.as_tuple().digits) * power + 2\n",
    "            return Decimal(self._value ** power)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Базовый класс"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, *children):\n",
    "        for child in children:\n",
    "            assert isinstance(child, Node)\n",
    "        self._children = children\n",
    "        self._params = {}\n",
    "        \n",
    "    def __eq__(self, other):\n",
    "        assert isinstance(other, Node)\n",
    "        return (\n",
    "            self.__class__ == other.__class__\n",
    "            and len(self._children) == len(other._children)\n",
    "            and all([\n",
    "                child == other_child\n",
    "                for child, other_child in zip(self._children, other._children)\n",
    "            ])\n",
    "        )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Базовая арифметика\n",
    "\n",
    "Заводим базовые классы - класс для представления вещественного числа (RealNumber), классы для базовых операций.\n",
    "\n",
    "У каждого наследника RealNumber должен быть определен метод get_value_with_precision(precision), который должен вернуть число в его десятичном представлении, с погрешностью не более precision.\n",
    "\n",
    "- Класс Multiply работает только для положительных чисел.\n",
    "- Класс Divide не делит на числа, близкие к нулю.\n",
    "- возводить можно только в целую неотрицательную степень\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RealNumber(Node):\n",
    "    def get_value_with_precision(self, precision):\n",
    "        raise NotImplementedError()\n",
    "        \n",
    "    def __add__(self, other):\n",
    "        if isinstance(other, (int, float, Decimal)):\n",
    "            other = RealNumberExact(other)\n",
    "        if isinstance(self, RealNumberExact) and isinstance(other, RealNumberExact):\n",
    "            return RealNumberExact(self._params['value'] + other._params['value'])\n",
    "        return Sum(self, other)\n",
    "    \n",
    "    def __sub__(self, other):\n",
    "        if isinstance(other, (int, float, Decimal)):\n",
    "            other = RealNumberExact(other)\n",
    "        if isinstance(self, RealNumberExact) and isinstance(other, RealNumberExact):\n",
    "            return RealNumberExact(self._params['value'] - other._params['value'])\n",
    "        return Subtract(self, other)\n",
    "    \n",
    "    def __mul__(self, other):\n",
    "        if isinstance(other, (int, float, Decimal)):\n",
    "            other = RealNumberExact(other)\n",
    "        if isinstance(self, RealNumberExact) and isinstance(other, RealNumberExact):\n",
    "            return RealNumberExact(self._params['value'] * other._params['value'])\n",
    "        return Multiply(self, other)\n",
    "\n",
    "    def __truediv__(self, other):\n",
    "        if isinstance(other, (int, float, Decimal)):\n",
    "            other = RealNumberExact(other)\n",
    "        if isinstance(self, Divide) and isinstance(other, RealNumberExact):\n",
    "            return Divide(self._children[0], self._children[1] * other)\n",
    "        return Divide(self, other)\n",
    "\n",
    "    def __pow__(self, power):\n",
    "        if isinstance(power, (Decimal, RealNumberExact)):\n",
    "            assert power.is_integer()\n",
    "            power = int(power)\n",
    "        if isinstance(power, int) and power == 0:\n",
    "            return RealNumberExact(1)\n",
    "        if isinstance(power, int) and isinstance(self, RealNumberExact):\n",
    "            return RealNumberExact(self._params['value'] ** power)\n",
    "        assert isinstance(power, Variable)\n",
    "        return Power(self, power)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        raise NotImplementedError()\n",
    "\n",
    "    \n",
    "@total_ordering\n",
    "class RealNumberExact(RealNumber):\n",
    "    def __init__(self, value):\n",
    "        assert isinstance(value, (int, float, Decimal))\n",
    "        super(RealNumberExact, self).__init__()\n",
    "        self._params['value'] = Decimal(value)\n",
    "        \n",
    "    def get_value_with_precision(self, precision):\n",
    "        assert precision > 0, precision\n",
    "        return self._params['value'].get_value_with_precision(precision)\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        other = other if isinstance(other, RealNumberExact) else RealNumberExact(other)        \n",
    "        return self._params['value'] < other._params['value']\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        other = other if isinstance(other, RealNumberExact) else RealNumberExact(other)        \n",
    "        return self._params['value'] == other._params['value'] \n",
    "\n",
    "    def __hash__(self):\n",
    "        return hash(self._params['value'])\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return '{}'.format(self._params['value'])\n",
    "    \n",
    "    def __int__(self):\n",
    "        return int(self._params['value'])\n",
    "    \n",
    "    def is_integer(self):\n",
    "        return self._params['value'].is_integer()\n",
    "\n",
    "    \n",
    "class RealNumberFunctionOfRealNumbers(RealNumber):\n",
    "    def __init__(self, *args):\n",
    "        def _prepare_arg(arg):\n",
    "            if isinstance(arg, (int, float, Decimal)):\n",
    "                arg = RealNumberExact(arg)\n",
    "            assert isinstance(arg, RealNumber), '{} is not RealNumber. Type: {}'.format(arg, type(arg))\n",
    "            return arg\n",
    "            \n",
    "        super(RealNumberFunctionOfRealNumbers, self).__init__(*[_prepare_arg(arg) for arg in args])\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return '{}<{}>'.format(self.__class__.__name__, ', '.join(map(str, self._children)))\n",
    "    \n",
    "    \n",
    "class BinaryOpOnRealNumber(RealNumberFunctionOfRealNumbers):\n",
    "    def __init__(self, left, right):\n",
    "        super(BinaryOpOnRealNumber, self).__init__(left, right)\n",
    "\n",
    "        \n",
    "class Sum(BinaryOpOnRealNumber):\n",
    "    def get_value_with_precision(self, precision):\n",
    "        assert precision > 0, precision\n",
    "        precision = Decimal(precision)\n",
    "        left_value = self._children[0].get_value_with_precision(precision * Decimal(0.5))\n",
    "        right_value = self._children[1].get_value_with_precision(precision * Decimal(0.5))\n",
    "        return (left_value + right_value).get_value_with_precision(precision)\n",
    "    \n",
    "    \n",
    "class Subtract(BinaryOpOnRealNumber):\n",
    "    def get_value_with_precision(self, precision):\n",
    "        assert precision > 0, precision\n",
    "        precision = Decimal(precision)\n",
    "        left_value = self._children[0].get_value_with_precision(precision * Decimal(0.5))\n",
    "        right_value = self._children[1].get_value_with_precision(precision * Decimal(0.5))\n",
    "        return (left_value - right_value).get_value_with_precision(precision)\n",
    "    \n",
    "    \n",
    "class Multiply(BinaryOpOnRealNumber):\n",
    "    def get_value_with_precision(self, precision):\n",
    "        assert precision > 0, precision\n",
    "        precision = Decimal(precision)\n",
    "        # Мне лень делать общий случай умножения, поэтому перемножать можно только положительные числа\n",
    "        # за то, чтобы числа были положительны - отвечает пользователь\n",
    "        # если передать сюда не положительные числа - точность не гарантируется\n",
    "        left_max = self._children[0].get_value_with_precision(precision) + precision\n",
    "        right_max = self._children[1].get_value_with_precision(precision) + precision\n",
    "        \n",
    "        left_precision = precision.shift(-(right_max * 3).order() - 1)\n",
    "        right_precision = precision.shift(-(left_max * 3).order() - 1)\n",
    "        \n",
    "        def max_error():\n",
    "            max_left_error = left_precision\n",
    "            max_right_error = right_precision\n",
    "            return left_max*max_right_error + right_max*max_left_error + max_right_error*max_left_error\n",
    "            \n",
    "        while max_error() >= precision:\n",
    "            left_precision = left_precision.shift(-1)\n",
    "            right_precision = right_precision.shift(-1)\n",
    "\n",
    "        left = self._children[0].get_value_with_precision(left_precision)\n",
    "        right = self._children[1].get_value_with_precision(right_precision)\n",
    "        return (left * right).get_value_with_precision(precision)\n",
    "    \n",
    "    \n",
    "class Divide(BinaryOpOnRealNumber):\n",
    "    def _compute_result_range(self, divisor, divisor_precision, divisible, divisible_precision):\n",
    "        # считает промежуток, в котором может находиться результат деления\n",
    "        assert abs(divisor) > divisor_precision\n",
    "        list_of_borders = [\n",
    "            _divisible.divide(_divisor, precision=divisor_precision*divisible_precision)\n",
    "            for _divisor in (divisor - divisor_precision, divisor + divisor_precision)\n",
    "            for _divisible in (divisible - divisible_precision, divisible + divisible_precision)\n",
    "        ]\n",
    "        return (min(list_of_borders), max(list_of_borders))\n",
    "    \n",
    "    def _compute_max_result_error(self, divisor, divisor_precision, divisible, divisible_precision, result):\n",
    "        result_range = self._compute_result_range(divisor, divisor_precision, divisible, divisible_precision)\n",
    "        assert result_range[0] <= result <= result_range[1]\n",
    "        return max(result_range[1] - result, result - result_range[0])\n",
    "        \n",
    "    def _get_divisor_precision_where_divisor_cant_be_0(self, precision):\n",
    "        divisor = self._children[1].get_value_with_precision(precision)\n",
    "        while (divisor - precision) * (divisor + precision) <= precision * precision:\n",
    "            precision = precision.shift(-1)\n",
    "            assert precision > 1e-300, \"Вы делите на что-то, слишком близкое к 0. Не надо так\"\n",
    "            divisor = self._children[1].get_value_with_precision(precision)\n",
    "        return divisor, precision\n",
    "\n",
    "    def get_value_with_precision(self, precision):\n",
    "        assert precision > 0, precision\n",
    "        precision = Decimal(precision)\n",
    "        divisor, divisor_precision = self._get_divisor_precision_where_divisor_cant_be_0(precision)\n",
    "        divisible_precision = precision * min(abs(divisor - divisor_precision), abs(divisor + divisor_precision)) * 0.5\n",
    "        divisible = self._children[0].get_value_with_precision(divisible_precision)\n",
    "        \n",
    "        result = divisible.divide(divisor, precision=divisor_precision*divisible_precision)\n",
    "        max_error = self._compute_max_result_error(divisor, divisor_precision, divisible, divisible_precision, result)\n",
    "        while max_error > precision:\n",
    "            divisor_precision = divisor_precision.shift(-1)\n",
    "            divisible_precision = divisible_precision.shift(-1)\n",
    "            divisor = self._children[1].get_value_with_precision(divisor_precision)\n",
    "            divisible = self._children[0].get_value_with_precision(divisible_precision)\n",
    "            result = divisible.divide(divisor, precision=divisor_precision*divisible_precision)\n",
    "            max_error = self._compute_max_result_error(divisor, divisor_precision, divisible, divisible_precision, result)\n",
    "        \n",
    "        return result\n",
    "    \n",
    "class Power(BinaryOpOnRealNumber):\n",
    "    def get_value_with_precision(self, precision):\n",
    "        assert precision > 0, precision\n",
    "        power = self._children[1]\n",
    "        assert isinstance(power, RealNumberExact) and power.is_integer() and int(power) >= 0, power\n",
    "        power = int(power)\n",
    "\n",
    "        value = self._children[0]\n",
    "        if isinstance(value, RealNumberExact):\n",
    "            result = RealNumberExact(value._params['value'] ** power)\n",
    "        else:\n",
    "            result = RealNumberExact(1)\n",
    "            for _ in range(power):\n",
    "                result = result * value\n",
    "            \n",
    "        return result.get_value_with_precision(precision)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cписки, бесконечные последовательности, переменные, преобразования"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Interval(Node):\n",
    "    def __init__(self, left, right):\n",
    "        assert isinstance(left, RealNumber), type(left)\n",
    "        assert isinstance(right, RealNumber), type(right)\n",
    "        super(Interval, self).__init__(left, right)\n",
    "        \n",
    "    @property\n",
    "    def left(self):\n",
    "        return self._children[0]\n",
    "\n",
    "    @property\n",
    "    def right(self):\n",
    "        return self._children[1]\n",
    "    \n",
    "    @property\n",
    "    def length(self):\n",
    "        return self.right - self.left\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return 'Interval({}, {})'.format(self._children[0], self._children[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Variable(RealNumber):\n",
    "    def __init__(self, name):\n",
    "        super(RealNumber, self).__init__()\n",
    "        self._params['name'] = name\n",
    "        \n",
    "    def __eq__(self, other):\n",
    "        return self._params['name'] == other._params['name']\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return '{}'.format(self._params['name'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Sequence(Node):\n",
    "    def __init__(self, generator):\n",
    "        super(Sequence, self).__init__()\n",
    "        self._params['generator'] = generator\n",
    "        \n",
    "    def first(self):\n",
    "        self._generator_state = self._params['generator']()\n",
    "        return self.next()\n",
    "    \n",
    "    def __iter__(self):\n",
    "        return iter(self._params['generator']())\n",
    "        \n",
    "    def __next__(self):\n",
    "        return self._generator_state.__next__()\n",
    "    \n",
    "    def get_ith_element(self, i):\n",
    "        el = self.first()\n",
    "        if isinstance(i, RealNumberExact):\n",
    "            i = int(i._params['value'])\n",
    "        for _ in range(i):\n",
    "            el = self.next()\n",
    "        return el\n",
    "    \n",
    "    next = __next__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class FiniteSequence(Sequence):\n",
    "    def __init__(self, l):\n",
    "        super(FiniteSequence, self).__init__(lambda: iter(l))\n",
    "        self._params['list'] = l\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return 'FiniteSequence<{}>'.format(self._params['list'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ConcatSequences(Sequence):\n",
    "    def __init__(self, first, second):\n",
    "        assert isinstance(first, Sequence)\n",
    "        assert isinstance(second, Sequence)\n",
    "        super(ConcatSequences, self).__init__(lambda: itertools.chain(first, second))\n",
    "        self._children = [first, second]\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return 'ConcatSequences<{}, {}>'.format(self._children[0], self._children[1])       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class InfiniteSequence(Sequence):\n",
    "    def __repr__(self):\n",
    "        return 'InfiniteSequence<generator={}>'.format(self._params['generator'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SequenceWithFormulaForIthElement(InfiniteSequence):\n",
    "    def __init__(self, transform, debug=False):\n",
    "        assert isinstance(transform, Transform)\n",
    "        def _generator():\n",
    "            for i in itertools.count(start=1):\n",
    "                ith_element = transform(RealNumberExact(i))\n",
    "                if debug:\n",
    "                    print('Requested {}-th element. Yielding \"{}\"'.format(i, ith_element))\n",
    "                yield ith_element\n",
    "        super(SequenceWithFormulaForIthElement, self).__init__(_generator)\n",
    "        self._children = [transform]\n",
    "\n",
    "    def __repr__(self):\n",
    "        return 'SequenceWithFormulaForIthElement<{}>'.format(self._children[0](Variable('I')))\n",
    "    \n",
    "class NaturalNumberSequence(SequenceWithFormulaForIthElement):\n",
    "    def __init__(self):\n",
    "        super(NaturalNumberSequence, self).__init__(Transform(Variable('I')))\n",
    "\n",
    "    def __repr__(self):\n",
    "        return 'NaturalNumberSequence'\n",
    "    \n",
    "class Transform(Node):\n",
    "    def __init__(self, func):\n",
    "        super(Transform, self).__init__(func)\n",
    "        \n",
    "        varset = self(RealNumberExact(1))\n",
    "        if isinstance(varset, RealNumber):\n",
    "            assert isinstance(varset.get_value_with_precision(1), Decimal)\n",
    "        elif isinstance(varset, Interval):\n",
    "            assert isinstance(varset.left.get_value_with_precision(1), Decimal)\n",
    "            assert isinstance(varset.right.get_value_with_precision(1), Decimal)\n",
    "        else:\n",
    "            assert False, varset\n",
    "       \n",
    "    def __repr__(self):\n",
    "        return 'Transform<{} -> {}>'.format(self.variable, self._children[0])\n",
    "    \n",
    "    @cached_property\n",
    "    def variable(self):\n",
    "        def _find_variable_internal(node):\n",
    "            if isinstance(node, Variable):\n",
    "                return node\n",
    "            for child in node._children:\n",
    "                var = _find_variable_internal(child)\n",
    "                if var:\n",
    "                    return var\n",
    "        return _find_variable_internal(self._children[0]) or Variable('_')\n",
    "    \n",
    "    \n",
    "    def __call__(self, value):\n",
    "        if isinstance(value, SequenceWithFormulaForIthElement):\n",
    "            return SequenceWithFormulaForIthElement(Transform(self(value._children[0]._children[0])))\n",
    "\n",
    "        def call_recursive(node):\n",
    "            if isinstance(node, Variable) and node._params['name'] == self.variable._params['name']:\n",
    "                return value\n",
    "\n",
    "            node._children = [call_recursive(child) for child in node._children]\n",
    "            return node\n",
    "        result =  call_recursive(deepcopy(self._children[0]))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SequenceWithFormulaForIthElement<Multiply<I, 2>>\n",
      "Multiply<1, 2>\n",
      "Multiply<2, 2>\n",
      "Multiply<3, 2>\n",
      "Multiply<4, 2>\n",
      "Multiply<5, 2>\n",
      "Multiply<6, 2>\n"
     ]
    }
   ],
   "source": [
    "sequence = SequenceWithFormulaForIthElement(Transform(Variable('X') * 2))\n",
    "print(sequence)\n",
    "for i, v in enumerate(sequence):\n",
    "    print(v)\n",
    "    if i >= 5:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SequenceWithFormulaForIthElement<Divide<1, I>>\n",
      "Divide<1, 1>\n",
      "Divide<1, 2> ~ 0.5\n",
      "Divide<1, 3> ~ 0.33333333333333333333333333333333\n",
      "Divide<1, 4> ~ 0.25\n",
      "Divide<1, 5> ~ 0.2\n",
      "Divide<1, 6> ~ 0.16666666666666666666666666666667\n"
     ]
    }
   ],
   "source": [
    "sequence = SequenceWithFormulaForIthElement(Transform(RealNumberExact(1) / Variable('I')))\n",
    "print(sequence)\n",
    "print(sequence.first())\n",
    "for _ in range(5):\n",
    "    number = sequence.next()\n",
    "    print('{} ~ {}'.format(number, number.get_value_with_precision(1e-15)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Класс для представления бесконечной последовательности сходящихся интервалов. Интервалы представлены двумя числами - началом и концом. Каждый следующий интервал должен лежать внутри предыдущего и быть не менее чем в K раз меньше"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ConvergingIntervalSequence(InfiniteSequence):\n",
    "    def __init__(self, generator, K):\n",
    "        assert K > 1\n",
    "        super(ConvergingIntervalSequence, self).__init__(generator)\n",
    "        self._params['K'] = K\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return 'ConvergingIntervalSequence<generator={}, K={}>'.format(self._params['generator'], self._params['K'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SequenceWithFormulaForIthElement<Interval(0, Power<0.5, I>)>\n",
      "(0, 0.5)\n",
      "(0, 0.25)\n",
      "(0, 0.125)\n",
      "(0, 0.0625)\n",
      "(0, 0.03125)\n",
      "(0, 0.015625)\n"
     ]
    }
   ],
   "source": [
    "sequence = SequenceWithFormulaForIthElement(Transform(Interval(RealNumberExact(0), RealNumberExact(0.5) ** Variable('X'))))\n",
    "print(sequence)\n",
    "for i, interval in enumerate(sequence):\n",
    "    print((interval.left.get_value_with_precision(1e-10), interval.right.get_value_with_precision(1e-10)))\n",
    "    if i >= 5:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И класс для представления предела такой последовательности"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ConvergingIntervalSequenceLimit(RealNumber):\n",
    "    def __init__(self, sequence):\n",
    "        if isinstance(sequence, SequenceWithFormulaForIthElement):\n",
    "            transform = sequence._children[0]\n",
    "            assert isinstance(transform._children[0], Interval)\n",
    "            converging_rate = transform(Variable('N')).length / transform(Variable('N') + 1).length\n",
    "            # TODO начать упрощать выражения\n",
    "        else:\n",
    "            assert isinstance(sequence, ConvergingIntervalSequence)\n",
    "        super(ConvergingIntervalSequenceLimit, self).__init__(sequence)\n",
    "        \n",
    "    def get_value_with_precision(self, precision):\n",
    "        assert precision > 0\n",
    "        precision = Decimal(precision)\n",
    "        sequence = self._children[0]\n",
    "        interval = sequence.first()\n",
    "        while interval.length.get_value_with_precision(precision) > precision:\n",
    "            interval = sequence.next()\n",
    "            \n",
    "        return ((interval.left + interval.right) * 0.5).get_value_with_precision(precision)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return 'ConvergingIntervalSequenceLimit<{}>'.format(self._children[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ConvergingIntervalSequenceLimit<SequenceWithFormulaForIthElement<Interval(0, Power<0.5, I>)>>\n",
      "precision: 0.1\tvalue: 0.031\n",
      "precision: 0.001\tvalue: 0.0004883\n",
      "precision: 1e-07\tvalue: 2.98023224E-8\n",
      "precision: 1e-69\tvalue: 2.8978173052245479576029181730840933698184099834045242206664367647793604E-70\n"
     ]
    }
   ],
   "source": [
    "interval_sequence = SequenceWithFormulaForIthElement(Transform(Interval(RealNumberExact(0), RealNumberExact(0.5) ** Variable('X'))))\n",
    "number = ConvergingIntervalSequenceLimit(interval_sequence)\n",
    "print(number)\n",
    "for precision in [0.1, 0.001, 0.0000001, 0.000000000000000000000000000000000000000000000000000000000000000000001]:\n",
    "    print(\"precision: {}\\tvalue: {}\".format(precision, number.get_value_with_precision(precision)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно применить это для, например, численного решения уравнений.\n",
    "\n",
    "Класс, который  для данной function и промежутка, на котором уравнение function(x)=0 имеет один корень, определяет число - корень уравнения.\n",
    "function должна быть монотонно возрастающей"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _function_is_not_0_in_point_with_precision(function, point, precision):\n",
    "    function_value = function(point).get_value_with_precision(precision)\n",
    "    return abs(function_value) > precision\n",
    "\n",
    "def _function_differs_in_points_with_precision(function, first, second, precision):\n",
    "    first_function_value = function(first).get_value_with_precision(precision)\n",
    "    second_function_value = function(second).get_value_with_precision(precision)\n",
    "    return abs(second_function_value - first_function_value) > precision * 2\n",
    "\n",
    "class EquationRootSequence(ConvergingIntervalSequence):\n",
    "    def __init__(self, function, left, right):\n",
    "        super(EquationRootSequence, self).__init__(self._interval_generator, 2)\n",
    "        left = left if isinstance(left, RealNumber) else RealNumberExact(left)\n",
    "        right = right if isinstance(right, RealNumber) else RealNumberExact(right)\n",
    "        self._params['function'] = function\n",
    "        self._params['interval'] = (left, right)\n",
    "    \n",
    "    def _interval_generator(self):\n",
    "        left, right = self._params['interval']\n",
    "        # находим точность, достаточную чтобы считать значения function на концах промежутка\n",
    "        precision = Decimal(0.0625)\n",
    "        # если function не монотонно возрастает, тут может случиться бесконечный цикл\n",
    "        while not _function_differs_in_points_with_precision(self._params['function'], left, right, precision):\n",
    "            precision = precision * Decimal(0.5)\n",
    "        \n",
    "        while True:\n",
    "            yield Interval(left, right)\n",
    "            \n",
    "            center = ((right + left) * 0.5)\n",
    "            left_quarter = ((left + center) * 0.5)\n",
    "            right_quarter = ((right + center) * 0.5)\n",
    "\n",
    "            # увеличиваем точность вычислений пока не случится одно из двух:\n",
    "            # 1) мы поймем, что function(center) точно не 0\n",
    "            # 2) мы поймем, что function(left_quarter) и function(right_quarter) точно не 0\n",
    "            # если function не монотонно возрастает, тут может случиться бесконечный цикл\n",
    "            while not (\n",
    "                _function_is_not_0_in_point_with_precision(self._params['function'], center, precision)\n",
    "                or (\n",
    "                    _function_is_not_0_in_point_with_precision(self._params['function'], right_quarter, precision)\n",
    "                    and _function_is_not_0_in_point_with_precision(self._params['function'], left_quarter, precision)\n",
    "                )\n",
    "            ):\n",
    "                precision = precision * Decimal(0.5)\n",
    "\n",
    "            center_function_value = self._params['function'](center).get_value_with_precision(precision)\n",
    "            # если function(center) точно не 0 - делаем center новой границей\n",
    "            if _function_is_not_0_in_point_with_precision(self._params['function'], center, precision):\n",
    "                if center_function_value > 0:\n",
    "                    right = center\n",
    "                else:\n",
    "                    left = center\n",
    "            # если function(center) похож на 0, а function(left_quarter) и function(right_quarter) точно не 0\n",
    "            # значит function(right_quarter) > 0, а function(left_quarter) < 0\n",
    "            # делаем их новыми границами\n",
    "            else:\n",
    "                left, right = left_quarter, right_quarter\n",
    "\n",
    "    def __repr__(self):\n",
    "        return 'EquationRootSequence<function={}, interval={}>'.format(self._params['function'], self._params['interval'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "precision: 0.1\tvalue=1.72\terr=-0.012051\n",
      "precision: 0.001\tvalue=1.7319\terr=-0.00015081\n",
      "precision: 1e-07\tvalue=1.732050806\terr=-1.5689E-9\n",
      "precision: 1e-15\tvalue=1.7320508075688772\terr=-9.3527E-17\n",
      "precision: 1e-49\tvalue=1.73205080756887729352744634150587236694280525381037\terr=-1.0628E-50\n",
      "precision: 1e-200\tvalue=1.7320508075688772935274463415058723669428052538103806280558069794519330169088000370811461867572485756756261414154067030299699450949989524788116555120943736485280932319023055820679748201010846749232650143\terr=-1.0123E-201\n",
      "precision: 1E-1000\tvalue=1.73205080756887729352744634150587236694280525381038062805580697945193301690880003708114618675724857567562614141540670302996994509499895247881165551209437364852809323190230558206797482010108467492326501531234326690332288665067225466892183797122704713166036786158801904998653737985938946765034750657605075661834812960610094760218719032508314582952395983299778982450828871446383291734722416398458785539766795806381835366611084317378089437831610208830552490167002352071114428869599095636579708716849807289949329648428302078640860398873869753758231731783139599298300783870287705391336956331210370726401924910676823119928837564114142201674275210237299427083105989845947598766428889779614783795839022885485290357603385280806438197234466105968972287286526415382266469842002119548415527844118128653450703519165001668929441548084607127714399976292683462957743836189511012714863874697654598245178855097537901388066496191196222295711055524292372319219773826256163146884203285371668293864961191704973883639549593814\terr=-5.7577E-1002\n"
     ]
    }
   ],
   "source": [
    "sequence = EquationRootSequence(lambda x: x*x - 3, 1, 2)\n",
    "number = ConvergingIntervalSequenceLimit(sequence)\n",
    "true_value = Decimal(3).sqrt(precision=Decimal('1e-1500'))\n",
    "for precision in [0.1, 0.001, 0.0000001, 0.000000000000001, 1e-49, 1e-200, Decimal('1e-1000')]:\n",
    "    value = number.get_value_with_precision(precision)\n",
    "    err = (value - true_value).get_value_with_digits(5)\n",
    "    assert err < precision\n",
    "    print(\"precision: {}\\tvalue={}\\terr={}\".format(precision, value, err))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно определить число - квадратный корень другого числа"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SquareRoot(RealNumberFunctionOfRealNumbers):\n",
    "    def __init__(self, value):\n",
    "        assert isinstance(value, Variable) or value > 0\n",
    "        value = value if isinstance(value, RealNumber) else RealNumberExact(value)\n",
    "        super(SquareRoot, self).__init__(value)\n",
    "        \n",
    "    def get_value_with_precision(self, precision):\n",
    "        sequence = EquationRootSequence(lambda x: x*x - self._children[0], 0, self._children[0])\n",
    "        sequence_limit = ConvergingIntervalSequenceLimit(sequence)\n",
    "        return sequence_limit.get_value_with_precision(precision)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return 'SquareRoot<{}>'.format(self._children[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SquareRoot<7>\n",
      "precision: 0.1\tvalue=2.65\terr=0.0042487\n",
      "precision: 0.001\tvalue=2.6459\terr=0.00014869\n",
      "precision: 1e-07\tvalue=2.64575132\terr=8.9354E-9\n",
      "precision: 1e-15\tvalue=2.6457513110645908\terr=2.095E-16\n",
      "precision: 1e-49\tvalue=2.645751311064590590501615753639260425710259183082433\terr=-1.718E-50\n",
      "precision: 1e-200\tvalue=2.6457513110645905905016157536392604257102591830824501803683344592010688232302836277603928864745436106150645783384974630957435298886272147844273905558801077227171507297283238922996895948650872607009780532\terr=-1.0037E-201\n",
      "precision: 1E-1000\tvalue=2.64575131106459059050161575363926042571025918308245018036833445920106882323028362776039288647454361061506457833849746309574352988862721478442739055588010772271715072972832389229968959486508726070097805420372382802371594110034193911600157852559630594574103515239680271640737379907404158151990440347431945367139973059700505139969223754561609711902737815499163328828770400065757067465196349775208379381811461309087647378659562433057994798128163230705483650107715617946361191553454536477494820593090494849834033989002104786166733279503693924622571705371649257875483229073249267134698029894990803774825110922789556889791980881483409083168525133535829539172211770714414974576907081989444441458972284741400303502353203719487073826293185193640908322805964627837610219597941970890963546958613411817930678162136084910167783532125563346349002189814604225592950366956241869273732771502208752309966469813203212818945478568020950635962446628550076190504139350447437123488522332773625100450596210806723346981200043006\terr=8.551E-1002\n"
     ]
    }
   ],
   "source": [
    "number = SquareRoot(7)\n",
    "true_value = Decimal(7).sqrt(precision=Decimal('1e-1500'))\n",
    "print(number)\n",
    "for precision in [0.1, 0.001, 0.0000001, 0.000000000000001, 1e-49, 1e-200, Decimal('1e-1000')]:\n",
    "    value = number.get_value_with_precision(precision)\n",
    "    err = (value - true_value).get_value_with_digits(5)\n",
    "    assert err < precision\n",
    "    print(\"precision: {}\\tvalue={}\\terr={}\".format(precision, value, err))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Диагональный процесс Кантора\n",
    "\n",
    "Для данной бесконечной последовательности чисел можно построить бесконечную последовательность сходящихся интервалов, такую что i-тый интервал не содержит i-тое число. \n",
    "\n",
    "А у бесконечной последовательности сходящихся интервалов есть предел, и его можно посчитать с любой требуемой точностью. Всё вместе это позволяет запрограммировать диагональный процесс Кантора\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KantorNumber(RealNumber):\n",
    "    def _build_converging_intervals_for_number_sequence(self):\n",
    "        def _generator():\n",
    "            left = RealNumberExact(0)\n",
    "            right = RealNumberExact(1)\n",
    "            precision = Decimal(1)\n",
    "            for i, number in enumerate(self._children[0]):\n",
    "                # удостоверяемся, что ошибка вычисления будет не более 1/16 от величины интервала\n",
    "                while (right - left).get_value_with_precision(precision) - precision <= precision * 16:\n",
    "                    precision = precision * 0.125\n",
    "\n",
    "                # делим интервал на 8 равных частей\n",
    "                delimiter4 = (left + right) * 0.5\n",
    "                delimiter2 = (left + delimiter4) * 0.5\n",
    "                delimiter1 = (left + delimiter2) * 0.5\n",
    "                delimiter3 = (delimiter2 + delimiter4) * 0.5\n",
    "                delimiter6 = (delimiter4 + right) * 0.5\n",
    "                delimiter7 = (delimiter6 + right) * 0.5\n",
    "                delimiter5 = (delimiter4 + delimiter6) * 0.5\n",
    "\n",
    "                number_value = number.get_value_with_precision(precision)\n",
    "                center_value = delimiter4.get_value_with_precision(precision)\n",
    "\n",
    "                # выберем новый интервал так, чтобы i-тый интервал отстоял от i-того числа как минимум на (1/8)^(i+1)\n",
    "                if number_value < center_value:\n",
    "                    # с учетом погрешности это означает, что number < delimiter5\n",
    "                    left, right = delimiter6, delimiter7\n",
    "                else:\n",
    "                    # с учетом погрешности это означает, что number > delimiter3\n",
    "                    left, right = delimiter1, delimiter2\n",
    "\n",
    "                yield Interval(left, right)\n",
    "        return ConvergingIntervalSequence(_generator, 8)\n",
    "    \n",
    "    def get_value_with_precision(self, precision):\n",
    "        interval_sequence = self._build_converging_intervals_for_number_sequence()\n",
    "        number = ConvergingIntervalSequenceLimit(interval_sequence)\n",
    "        return number.get_value_with_precision(precision)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return 'KantorNumber<{}>'.format(self._children[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И посмотрим на само число:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "KantorNumber<SequenceWithFormulaForIthElement<Divide<1, SquareRoot<I>>>>\n",
      "precision: 0.1\tvalue=0.15\n",
      "precision: 0.001\tvalue=0.1429\n",
      "precision: 1e-07\tvalue=0.142857164\n",
      "precision: 1e-15\tvalue=0.142857142857143\n",
      "precision: 1e-49\tvalue=0.142857142857142857142857142857142857142857174886814\n",
      "precision: 1e-200\tvalue=0.142857142857142857142857142857142857142857174886822041710104478256676189483797286405987242891789068732989346052367604248242319694587162562779017857142857142857142857142857142857142857142857142857142856\n"
     ]
    }
   ],
   "source": [
    "number_sequence = SequenceWithFormulaForIthElement(Transform(RealNumberExact(1) / SquareRoot(Variable('I'))))\n",
    "kantor_number = KantorNumber(number_sequence)\n",
    "print(kantor_number)\n",
    "for precision in [0.1, 0.001, 0.0000001, 0.000000000000001, 1e-49, 1e-200]:\n",
    "    value = kantor_number.get_value_with_precision(precision)\n",
    "    print(\"precision: {}\\tvalue={}\".format(precision, value))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И, как и с любым нормальным числом, с ним можно делать всякие вычисления:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Subtract<Multiply<Divide<Sum<KantorNumber<SequenceWithFormulaForIthElement<Divide<1, SquareRoot<I>>>>, 1>, 2>, 3>, 4>\n",
      "-2.285714285714285714285714285714285714285714237669767\n"
     ]
    }
   ],
   "source": [
    "print(((((kantor_number + 1) / 2) * 3) - 4))\n",
    "print(((((kantor_number + 1) / 2) * 3) - 4).get_value_with_precision(1e-49))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно запрограммировать последоватеьность, в которой будет это канторовское число."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "KantorNumber<ConcatSequences<FiniteSequence<[KantorNumber<SequenceWithFormulaForIthElement<Divide<1, SquareRoot<I>>>>]>, SequenceWithFormulaForIthElement<Divide<1, SquareRoot<I>>>>>\n",
      "precision: 0.1\tvalue=0.77\n",
      "precision: 0.001\tvalue=0.7789\n",
      "precision: 1e-07\tvalue=0.779017836\n",
      "precision: 1e-15\tvalue=0.779017857142857\n",
      "precision: 1e-49\tvalue=0.77901785714285714285714285714285714285714285714285\n",
      "precision: 1e-200\tvalue=0.779017857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142856\n"
     ]
    }
   ],
   "source": [
    "number_sequence = ConcatSequences(\n",
    "    FiniteSequence([kantor_number]),\n",
    "    SequenceWithFormulaForIthElement(Transform(RealNumberExact(1) / SquareRoot(Variable('X')))),\n",
    ")\n",
    "\n",
    "kantor_number2 = KantorNumber(number_sequence)\n",
    "print(kantor_number2)\n",
    "for precision in [0.1, 0.001, 0.0000001, 0.000000000000001, 1e-49, 1e-200]:\n",
    "    value = kantor_number2.get_value_with_precision(precision)\n",
    "    print(\"precision: {}\\tvalue={}\".format(precision, value))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Результат применения канторовской процедуры к новой последовательности будет, очевидно, отличаться:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-0.636160714285714285714285714285714285714285682256035"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(kantor_number - kantor_number2).get_value_with_precision(1e-50)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Какие либо вычисления происходят только тогда, когда нужно приближенное значение числа:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "KantorNumber<SequenceWithFormulaForIthElement<Divide<1, SquareRoot<I>>>>\n",
      "CPU times: user 1.6 ms, sys: 1 µs, total: 1.6 ms\n",
      "Wall time: 1.25 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "number_sequence = SequenceWithFormulaForIthElement(Transform(RealNumberExact(1) / SquareRoot(Variable('X'))), debug=True)\n",
    "kantor_number = KantorNumber(number_sequence)\n",
    "print(kantor_number)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requested 1-th element. Yielding \"Divide<1, SquareRoot<1>>\"\n",
      "Requested 2-th element. Yielding \"Divide<1, SquareRoot<2>>\"\n",
      "Requested 3-th element. Yielding \"Divide<1, SquareRoot<3>>\"\n",
      "Requested 4-th element. Yielding \"Divide<1, SquareRoot<4>>\"\n",
      "Requested 5-th element. Yielding \"Divide<1, SquareRoot<5>>\"\n",
      "Requested 6-th element. Yielding \"Divide<1, SquareRoot<6>>\"\n",
      "Requested 7-th element. Yielding \"Divide<1, SquareRoot<7>>\"\n",
      "Requested 8-th element. Yielding \"Divide<1, SquareRoot<8>>\"\n",
      "Requested 9-th element. Yielding \"Divide<1, SquareRoot<9>>\"\n",
      "Requested 10-th element. Yielding \"Divide<1, SquareRoot<1E+1>>\"\n",
      "Requested 11-th element. Yielding \"Divide<1, SquareRoot<11>>\"\n",
      "Requested 12-th element. Yielding \"Divide<1, SquareRoot<12>>\"\n",
      "0.14285714286\n"
     ]
    }
   ],
   "source": [
    "print(kantor_number.get_value_with_precision(0.0000000001))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно посчитать разность между полученным числом и произвольным числом из последовательности. Она должна быть больше чем (1/8)^(i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "40-ый элемент: Divide<1, SquareRoot<41>>. ожидаемая разность: >9.404E-38, настоящая разность: 0.013317 +- 9.404E-40\n",
      "41-ый элемент: Divide<1, SquareRoot<42>>. ожидаемая разность: >1.1755E-38, настоящая разность: 0.011446 +- 1.1755E-40\n",
      "42-ый элемент: Divide<1, SquareRoot<43>>. ожидаемая разность: >1.4694E-39, настоящая разность: 0.0096414 +- 1.4694E-41\n",
      "43-ый элемент: Divide<1, SquareRoot<44>>. ожидаемая разность: >1.8367E-40, настоящая разность: 0.0078985 +- 1.8367E-42\n",
      "44-ый элемент: Divide<1, SquareRoot<45>>. ожидаемая разность: >2.2959E-41, настоящая разность: 0.0062141 +- 2.2959E-43\n",
      "45-ый элемент: Divide<1, SquareRoot<46>>. ожидаемая разность: >2.8699E-42, настоящая разность: 0.0045848 +- 2.8699E-44\n",
      "46-ый элемент: Divide<1, SquareRoot<47>>. ожидаемая разность: >3.5873E-43, настоящая разность: 0.0030078 +- 3.5873E-45\n",
      "47-ый элемент: Divide<1, SquareRoot<48>>. ожидаемая разность: >4.4842E-44, настоящая разность: 0.0014804 +- 4.4842E-46\n",
      "48-ый элемент: Divide<1, SquareRoot<49>>. ожидаемая разность: >5.6052E-45, настоящая разность: 3.2026E-44 +- 5.6052E-47\n",
      "49-ый элемент: Divide<1, SquareRoot<5E+1>>. ожидаемая разность: >7.0065E-46, настоящая разность: 0.0014358 +- 7.0065E-48\n",
      "50-ый элемент: Divide<1, SquareRoot<51>>. ожидаемая разность: >8.7581E-47, настоящая разность: 0.0028291 +- 8.7581E-49\n",
      "51-ый элемент: Divide<1, SquareRoot<52>>. ожидаемая разность: >1.0948E-47, настоящая разность: 0.0041821 +- 1.0948E-49\n",
      "52-ый элемент: Divide<1, SquareRoot<53>>. ожидаемая разность: >1.3685E-48, настоящая разность: 0.0054966 +- 1.3685E-50\n",
      "53-ый элемент: Divide<1, SquareRoot<54>>. ожидаемая разность: >1.7106E-49, настоящая разность: 0.0067744 +- 1.7106E-51\n",
      "54-ый элемент: Divide<1, SquareRoot<55>>. ожидаемая разность: >2.1382E-50, настоящая разность: 0.0080172 +- 2.1382E-52\n",
      "55-ый элемент: Divide<1, SquareRoot<56>>. ожидаемая разность: >2.6728E-51, настоящая разность: 0.0092265 +- 2.6728E-53\n",
      "56-ый элемент: Divide<1, SquareRoot<57>>. ожидаемая разность: >3.341E-52, настоящая разность: 0.010404 +- 3.341E-54\n",
      "57-ый элемент: Divide<1, SquareRoot<58>>. ожидаемая разность: >4.1762E-53, настоящая разность: 0.011551 +- 4.1762E-55\n",
      "58-ый элемент: Divide<1, SquareRoot<59>>. ожидаемая разность: >5.2202E-54, настоящая разность: 0.012668 +- 5.2202E-56\n",
      "59-ый элемент: Divide<1, SquareRoot<6E+1>>. ожидаемая разность: >6.5253E-55, настоящая разность: 0.013758 +- 6.5253E-57\n"
     ]
    }
   ],
   "source": [
    "number_sequence = SequenceWithFormulaForIthElement(Transform(RealNumberExact(1) / SquareRoot(Variable('X'))))\n",
    "kantor_number = KantorNumber(number_sequence)\n",
    "for i in range(40, 60):\n",
    "    expected_diff = Decimal(0.125) ** (i + 1)\n",
    "    precision = expected_diff * 0.01\n",
    "    print('{}-ый элемент: {}. ожидаемая разность: >{}, настоящая разность: {} +- {}'.format(\n",
    "        i,\n",
    "        number_sequence.get_ith_element(i),\n",
    "        expected_diff.get_value_with_digits(5),\n",
    "        abs((kantor_number - number_sequence.get_ith_element(i)).get_value_with_precision(precision).get_value_with_digits(5)),\n",
    "        precision.get_value_with_digits(5),\n",
    "    ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Получается, что для любой последовательности вещественных чисел, которую можно запрограммировать, можно построить вещественное число, которого в этой последовательности нет.\n",
    "\n",
    "То есть, биекцию между натуральными числами и вещественными нельзя запрограммировать."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}