Quadrate – diesmal Zahlen, keine Figuren – Lösung der Zusatzaufgabe

[Rolf B]

Hallo Matthias,

ja. Schrub ich weiter oben auch mal.

Ich habe den Chain Explorer nach C# portiert, weil ich hoffte, dann schneller zu sein. Bei den ersten Versuchen bin ich fast ausgeflippt; JavaScript prüft eine Zahl in 1,5µs (steigend auf 2µs wenn man in den Milliardenbereich kommt), und mein C# Programm schien schon bei kleinen Zahlen 3µs und mehr zu brauchen. Aber ich muss mich da bei der Umrechnung von Ticks in µs vertan haben, nachdem ich etwas hin und her gebastelt habe sind es 0,4µs pro Zahl wenn ich die BigInteger Implementierung von .net verwende und 0,08µs pro Zahl, wenn ich ulong benutze (das ist aber bei 2^32-1 am Ende).

Dabei lernt man dann was über Tradeoffs Laufzeit gegen Speicher.

Zum Beispiel: Ist eine Quersumme quadratisch? Pro Quersumme die Wurzel ziehen? Hui, das ist langsam. Aber bei einer 100-stelligen Zahl ist die Quersumme maximal 900, also warum nicht ein Array bilden, in dem für jede Zahl von 1-1000 ein Flag steht, ob sie eine Quadratzahl ist.

Gesagt getan, statt

double sq = Math.Sqrt(checksum);
if (Math.Floor(sq) == sq) {
   // Quadratzahl
}

schrieb ich also

if (squares[checksum] == 1) {
   // Quadratzahl
}

Effekt: ca 20ns pro Zahl. 5% der Zeit pro Zahl (bei BigInt, bei ulong ist es natürlich signifikanter). Aber da hätte ich viel mehr Effekt erwartet.

Zweites Beispiel: Bilden der Quersumme.

Naiver Ansatz:

   BigInteger value = k*k;
   while (value > 0)
   {
      int digit = (int)(value % 10);
      value = (value - digit) / 10;
      checksum += digit;
   } 

Hui, das kostet. 2µs pro Zahl sind es so. Besser die DivRem Methode verwenden, die liefert den Rest als Abfallprodukt des Quotienten

   BigInteger value = k*k;
   while (value > 0)
   {
      value = BigInteger.DivRem(value, 10, out BigInteger digit);
      checksum += (int)digit;
   }

Immerhin, noch 1,4µs pro Zahl (im kleinen Millionenbereich). Im Milliardenbereich eher 2,3µs.

Also wie reduziert man die BigInteger Operationen? Ich muss ja nicht Ziffer für Ziffer vorgehen. Ich kann für die Zahlen von 0-X Quersummen vorberechnen, z.B. X=1000. Das drittelt die Anzahl der BigInteger Divisionen.

   BigInteger value = k*k;
   while (value > 0)
   {
      value = BigInteger.DivRem(value, bChecksumCount, out BigInteger digitGroup);
      checksum += Checksums[(int)digitGroup];
   } 

Bingo, 560ns pro Zahl im kleinen Bereich, 800ns pro Zahl im Milliardenbereich. Es wird. Warum bei X=1000 stehen bleiben? Die Quersumme von 999999 ist 54, also reicht ein Byte pro Zahl. Also: 1000000 vorberechnete Quersummen. Damit komme ich dann auf 420ns und 520ns im Milliardenbereich.

Und jetzt noch der Oberclou. Die Berechnung eines Quadrats ist doch bestimmt aufwändig. Warum nicht den Umstand berücksichtigen, dass zwischen zwei Quadratzahlen die Differenz um je 2 ansteigt und sich hochaddieren statt multiplizieren. Genial! Schnell eingebaut: 470ns pro Zahl im kleinen Bereich. WTF? Etwas Profiling ergab: k=k+1 ist 15ns langsamer als k=k+b1 (mit b1 als Variable, die den BigInteger-Wert 1 enthält). Die Konvertierung einer Int-Konstanten in ein BigInteger ist ein Zeitfresser! Aber eine Addition braucht trotzdem noch doppelt so viel Zeit wie eine Multiplikation. Weird! Diese Optimierung war keine.

Für C++ suche ich noch eine BigInt Library. Bin gespannt was dann passiert; ich will ja nicht selbst eine programmieren.

Rolf