Числовые представления без машинных примитивов

Question

Синопсис

Размещайте примеры на любом языке типа, представляющего целые числа, без непосредственного использования машинных целых чисел. Включите сопоставления до и от пользовательского типа. Очки за эффективность в пространстве и / или времени.

Оригинальный вопрос

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

Так что это заставило меня задуматься. В C ++, языке, в котором машинные примитивы не участвуют в иерархии классов, возможно ли определить тип объекта - скажем, Integer -, который не использует машинный примитив для хранения его значение?

Существует этот красивый бит шаблона хакерства , который реализует церковные цифры. К сожалению, поскольку преобразование между целыми числами и церковными числами происходит строго во время компиляции, невозможно использовать машинные целые числа, скажем, для пользовательского ввода.

Итак, я ищу время выполнения эквивалент вышеупомянутого, хотя и не обязательно с использованием церковных чисел, с разумными требованиями к пространству, которое может быть реализовано на языке, таком как C ++, без высшего порядка функции. Я также хотел бы видеть примеры на других языках, особенно на тех, которые используют забавные приемы динамической типизации. Указатели и указатели функций не должны учитываться как примитивы, если сохраненный адрес используется строго как таковой, а не как его целое значение.

Бонусные баллы за размещение всех целых чисел (то есть не только целых чисел), и супер бонусные баллы за разработку системы, в которой также могут быть реализованы числа с плавающей запятой.

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

Answer 1

здесь класс, который можно использовать для натуральных чисел. и может быть легко расширен для учета негативов. он поддерживает сложение, вычитание, равенство, неравенство и умножение. Деление может быть выполнено на основе существующих операторов. Так что в целом я бы сказал, что это в значительной степени представляет целые числа, и нет никаких простых типов. На самом деле единственный тип, который использует класс, это self.

Реализация в основном представляет собой список ссылок с некоторой оптимизацией, поэтому обход списка не требуется для каждой операции.

public class MyInt
    {
        private MyInt _previous;
        private MyInt _first;
        private bool isEven;

        private MyInt(MyInt previous)
        {
            next++;
            _previous = previous;
            isEven = previous == null ? true : !previous.isEven;
            getFirst();
            x = next;
        }

        private void getFirst()
        {
            if (_previous == null)
                _first = null;
            else if (_previous._first == null)
                _first = this;
            else
                _first = _previous._first;
        }

        private MyInt(MyInt copy, bool dontuse)
        {
            _previous = copy._previous == null ? null : new MyInt(copy._previous,true);
            getFirst();
            x = copy.x;
        }

        public static MyInt operator +(MyInt lhs, MyInt rhs)
        {
            if (object.ReferenceEquals(lhs, rhs))
                rhs = new MyInt(rhs, true);
            if (lhs == MyInt.Zero)
                return rhs;
            if (rhs == MyInt.Zero)
                return lhs;
            else
            {
                var isEven = rhs.isEven == lhs.isEven;
                var result = new MyInt(rhs, true);
                result._first._previous = lhs;
                result._first = lhs._first;
                result.isEven = isEven;
                return result;
            }
        }

        public static MyInt operator -(MyInt lhs, MyInt rhs)
        {
            if (lhs == rhs)
                return MyInt.Zero;
            if (rhs == MyInt.Zero)
                return lhs;
            if (lhs == MyInt.Zero)
                throw new InvalidOperationException("Negatives not supported");
            else
            {
                return lhs._previous - rhs._previous;
            }
        }

        public static MyInt operator --(MyInt un)
        {
            if (un == MyInt.Zero)
                throw new InvalidOperationException("Negatives not supported");
            return un._previous;
        }

        public static MyInt operator *(MyInt lhs, MyInt rhs)
        {
            if (lhs == MyInt.Zero || rhs == MyInt.Zero)
                return MyInt.Zero;

            var temp = lhs;
            var one = One;
            var two = one + one;
            var zero = MyInt.Zero;
            var dbl = lhs + lhs;
            if (rhs == MyInt.One)
                return lhs;
            if (rhs == two)
                return dbl;
            for (MyInt times = rhs + one; times._previous._previous != zero && times._previous != zero; times = times-two)
            {
                temp = temp + dbl;
            }
            if (rhs.isEven)
                temp = temp - lhs;
            return temp;
        }

        public static bool operator ==(MyInt lhs, MyInt rhs)
        {
            if (object.ReferenceEquals(lhs, null) && object.ReferenceEquals(rhs, null))
                return true;
            if ((object.ReferenceEquals(lhs, null) || object.ReferenceEquals(rhs, null)))
                return false;
            if (object.ReferenceEquals(lhs._previous, null) && object.ReferenceEquals(rhs._previous, null))
                return true;
            if ((object.ReferenceEquals(lhs._previous, null) || object.ReferenceEquals(rhs._previous, null)))
                return false;

            return (lhs._previous == rhs._previous);
        }

        public static bool operator !=(MyInt lhs, MyInt rhs)
        {
            return !(lhs == rhs);
        }

        public override bool Equals(object obj)
        {
            return obj is MyInt && ((MyInt)obj) == this;
        }

        public static MyInt Zero
        {
            get
            {
                return new MyInt(null);
            }
        }

        public static MyInt One
        {
            get
            {
                return new MyInt(new MyInt(null));
            }
        }
    }

Answer 2

Всегда есть Лисп, в котором 0 можно представить как () (пустой список), 1 - (()), 2 - (() ()) и т. Д. Это было доказано еще в тот день, но, конечно, нетРеализация на Лиспе фактически использует это, так как в это слишком медленно верить.