Numerische Darstellungen ohne Maschinenprimitive

Question

Synopse

Geben Sie Beispiele in einer beliebigen Sprache eines Typs an, der ganze Zahlen repräsentiert, ohne dabei direkt auf Maschinen-Ganzzahlen zurückzugreifen. Mappings einbeziehen zu y von den benutzerdefinierten Typ. Punkte für Effizienz in Raum und/oder Zeit.

Ursprüngliche Frage

In den Kommentaren von eine bestimmte, recht gewagte Antwort Auf eine Frage zur objektorientierten Programmierung habe ich meine Überzeugung geäußert, dass Maschinenprimitive keine Objekte sind, war aber nicht in der Lage, diese Behauptung wirklich zu untermauern, so wie der Verfasser dieser Antwort nicht in der Lage war, seine Behauptungen über die Universalität und die grundlegende Natur der objektorientierten Philosophie zu untermauern.

Das hat mich zum Nachdenken gebracht. Ist es in C++, einer Sprache, in der Maschinenprimitive nicht an der Klassenhierarchie beteiligt sind, möglich, einen Objekttyp zu definieren - sagen wir, Integer -das tut nicht ein Maschinenprimitiv verwenden, um seinen Wert zu speichern?

Es gibt dieses schöne Stück Template-Hackerei die Kirchenziffern implementiert. Da die Konvertierung zwischen ganzen Zahlen und kirchlichen Ziffern ausschließlich zur Kompilierzeit erfolgt, gibt es leider keine Möglichkeit, die Verwendung von Ganzzahlen für Benutzereingaben zu umgehen.

Was ich also suche, ist eine Laufzeit Äquivalent zu den oben genannten, wenn auch nicht unbedingt unter Verwendung von Kirchennummern, mit vernünftigem Platzbedarf, das in einer Sprache wie C++ ohne Funktionen höherer Ordnung implementiert werden kann. Ich würde auch gerne Beispiele in anderen Sprachen sehen, insbesondere in solchen, die lustige dynamische Typisierungstricks verwenden. Zeiger und Funktionszeiger zählen nicht zu den Primitiven, solange die gespeicherte Adresse ausschließlich als solche und nicht für ihren ganzzahligen Wert verwendet wird.

Bonuspunkte für die Aufnahme aller ganzen Zahlen (d. h. nicht nur ganzer Zahlen) und Super-Bonuspunkte für die Entwicklung eines Systems, in dem auch Gleitkommazahlen implementiert werden können.

Um spätere Unannehmlichkeiten zu vermeiden und eine höfliche Diskussion zu fördern, mache ich diese Frage von Anfang an zu einer Community-Wikifrage.

Answer 1

Hier eine Klasse, die für positive ganze Zahlen verwendet werden kann und leicht erweitert werden kann, um auch negative Zahlen zu berücksichtigen. Sie unterstützt Addition, Subtraktion, Gleichheit, Ungleichheit und Multiplikation. Division kann auf Basis der vorhandenen Operatoren impliziert werden. Alles in allem würde ich also sagen, dass es ziemlich genau ganze Zahlen repräsentiert und keine einfachen Typen benötigt werden. Tatsächlich ist der einzige Typ, den die Klasse verwendet, sie selbst.

Die Implementierung ist im Grunde eine Linkliste mit einigen Optimierungen, so dass die Liste nicht bei jeder Operation durchlaufen werden muss.

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

Es gibt immer noch Lisp, in dem 0 dargestellt werden kann als () (die leere Liste), 1 ist (()) , 2 ist (() ()) , usw. Das wurde schon vor langer Zeit bewiesen, aber natürlich benutzt das keine Lisp-Implementierung, da es zu langsam ist, um es zu glauben.