Mathematik/Programmiertechnik zum Wochenende – Lösung

[Rolf B]

Hallo Gunnar,

ich habe eine effizientere Implementierung gefunden und sie darüber hinaus nicht mit JavaScript, sondern mit C# laufen lassen. Mein C++ war zu rostig, damit wär's sicherlich noch mal schneller gewesen.

Nach 4 Minuten habe ich gewusst, dass 6210001000 die einzige Zahl n ist, für die z(n)=n gilt.

Rückkopplung habe ich nicht ausprobiert; ich denke auch, dass eine erschöpfende Suche aller Startwerte der Rückkopplungsschleife deutlich länger dauert.

Die analytische Vorgehensweise ist zu ineffizient. Mein erster Ansatz war eine Zerlegung der Zahl n in Ziffern, indem ich durch 10 geteilt habe und dann Quotient und Rest separiert habe. Ein Überrest davon findet sich noch im Konstruktor meiner Digits Klasse:

    struct Digits
    {
        public byte d0, d1, d2, d3, d4, d5, d6, d7, d8, d9;
        public int quersumme;

        public Digits(long z)
        {
            z = (z - (d9 = (byte)(z % 10))) / 10;
            z = (z - (d8 = (byte)(z % 10))) / 10;
            z = (z - (d7 = (byte)(z % 10))) / 10;
            z = (z - (d6 = (byte)(z % 10))) / 10;
            z = (z - (d5 = (byte)(z % 10))) / 10;
            z = (z - (d4 = (byte)(z % 10))) / 10;
            z = (z - (d3 = (byte)(z % 10))) / 10;
            z = (z - (d2 = (byte)(z % 10))) / 10;
            z = (z - (d1 = (byte)(z % 10))) / 10;
            d0 = (byte)z;

            quersumme = d0 + d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9;
        }
    }

Ich verwende ganz bewusst einzelne Variablen und kein Array, und ich lasse keine Schleife laufen (wobei ich den Zeitgewinn nicht gemessen habe, vermutlich sind's nur 2-3 Prozent). Lästig ist, dass jede Zeile den z-Wert der vorherigen braucht, was die Prozessorpipeline vermutlich ausbremst. Da gäbe es vermutlich noch Optimierungspotenzial. Die Quersumme brauche ich für die Berechnung der Anzahl n und berechne sie darum gleich mit. Eine solche Additionskette flutscht eigentlich ganz glatt durch die execution pipeline.

Aber es sind 20 Divisionen und 9 Subtraktionen, das ist aufwändig. Mittels Math.DivRem hätte man die Divisionen halbieren können, und man hätte den Code pipelinefreundlicher gestalten können, aber das habe ich nicht verfolgt. Ich habe etwas anderes gemacht.

Eine brute-force Suche muss ja der Reihe nach Zahlen durchgehen. Ich muss also gar nicht beliebige Zahlen in Ziffern zerlegen, es reicht völlig, wenn ich einen effizienten Schritt von n nach n+1 habe. Gedacht, getippt:

        public void Increment()
        {
            if (d9<9) { d9++; quersumme++; return; } else { d9=0; quersumme-=9; }
            if (d8<9) { d8++; quersumme++; return; } else { d8=0; quersumme-=9; }
            if (d7<9) { d7++; quersumme++; return; } else { d7=0; quersumme-=9; }
            if (d6<9) { d6++; quersumme++; return; } else { d6=0; quersumme-=9; }
            if (d5<9) { d5++; quersumme++; return; } else { d5=0; quersumme-=9; }
            if (d4<9) { d4++; quersumme++; return; } else { d4=0; quersumme-=9; }
            if (d3<9) { d3++; quersumme++; return; } else { d3=0; quersumme-=9; }
            if (d2<9) { d2++; quersumme++; return; } else { d2=0; quersumme-=9; }
            if (d1<9) { d1++; quersumme++; return; } else { d1=0; quersumme-=9; }
            if (d0<9) { d0++; quersumme++; return; } else { d0=0; quersumme-=9; }
        }

Dieser Code ist lange nicht so aufwändig wie er aussieht, denn in 90% aller Fälle endet er im ersten Then-Teil. In 99% aller Fälle läuft er bis zum zweiten Then-Teil. In 99,9% bis zum dritten.

Man muss dann auch noch das z zum n berechnen können, das von dieser Ziffernfolge dargestellt wird. Dabei muss man aufpassen, man möchte ja nicht, dass z(1)=9100000000 liefert. Das Montieren der Ziffern zu z geht bei mir in der gezeigten Weise am schnellsten, ich habe ein paar Varianten probiert. C# ist nicht nahe genug am Blech, dass man hier mit Variationen der Ausführungsreihenfolge die Pipeline-Nutzung optimieren könnte (oder der .net JIT macht das schon selbst).

        public long ZValue
        {
            get
            {
                byte[] z = new byte[10];
                byte zq;
                // Ziffern nur zählen wenn es keine führenden Nullen sind
                if ((zq  = d0) > 0) z[d0]++;
                if ((zq += d1) > 0) z[d1]++;
                if ((zq += d2) > 0) z[d2]++;
                if ((zq += d3) > 0) z[d3]++;
                if ((zq += d4) > 0) z[d4]++;
                if ((zq += d5) > 0) z[d5]++;
                if ((zq += d6) > 0) z[d6]++;
                if ((zq += d7) > 0) z[d7]++;
                if ((zq += d8) > 0) z[d8]++;
                if ((zq += d9) > 0) z[d9]++;

                return ((((((((z[0] * 10 + z[1]) * 10 + z[2]) * 10 + z[3]) * 10 + z[4]) * 10 
                            + z[5]) * 10 + z[6]) * 10 + z[7]) * 10 + z[8]) * 10L + z[9];
            }
        }

Diese Schleife läuft auf meinem etwas altertümlichen PC (Core i5-3470 CPU mit 3.20GHz) dann in unter 4 Minuten durch und meldet 6210001000 als einziges n mit n == d.ZValue.

Digits d = new Digits(1);
for (long i=1; i<10000000000; i++) {
   if (n == d.ZValue)
      Console.WriteLine("Match: {0}", n);
   d.Increment();
}

Rolf