x Nachkommastellen von sqrt(2)

    • C#
    • .NET (FX) 4.0

    Es gibt 23 Antworten in diesem Thema. Der letzte Beitrag () ist von Nikx.

      x Nachkommastellen von sqrt(2)

      Moin,

      kam gestern mal auf die Idee, Nachkommastellen von sqrt(2) zu berechnen.
      Hab also das Töplerverfahren auf 2 angepasst und in C# realisiert. 10.000 Nachkommastellen berechnet
      das Programm in ca. 240 Millisekunden. Für eine Million hat es bei mir etwa 53 Minuten gebraucht.

      Vielleicht interessiert es ja jemanden :)
      Der Source ist auf 2 angepasst und funktioniert nicht mit allen anderen Zahlen, weil der Töpleralgorithmus 2er-Packs vorraussetzt und ich diese Bedingung nicht eingebaut habe, da sie für 2 nicht nötig ist.

      C#-Quellcode

      1. class Program
      2. {
      3. static void Main(string[] args)
      4. {
      5. Stopwatch x = new Stopwatch();
      6. x.Start();
      8. BigInteger number = 2;
      9. BigInteger fractional = 1;
      10. BigInteger result = 0;
      12. BigInteger counter = 0;
      13. while (counter <= 10000)
      14. {
      15. BigInteger oddNumber = fractional;
      16. BigInteger countFractionalDeduction = 0;
      18. while (number - oddNumber > 0)
      19. {
      20. number -= oddNumber;
      21. countFractionalDeduction++;
      22. oddNumber += 2;
      23. }
      25. number = number * 100;
      26. result = result * (10 ^ countFractionalDeduction.ToString().Length - 1) + countFractionalDeduction;
      27. fractional = (result << 1) * 10 + 1;
      29. counter++;
      30. }
      32. x.Stop();
      34. Console.WriteLine(result.ToString().Insert(1, ","));
      35. Console.WriteLine();
      36. Console.WriteLine("Time: " + x.Elapsed);
      37. Console.ReadLine();
      38. }
      40. }


      Im Beispiel ist diese Zeile ​while (counter <= 10000) für die Iterationen verantwortlich, 10000 sind die Nachkommastellen, die berechnet werden.
      System.Numerics importieren und Verweis setzen. Viel Spaß :)

      Grüße
      "Life isn't about winning the race. Life is about finishing the race and how many people we can help finish the race." ~Marc Mero

      Nun bin ich also auch soweit: Keine VB-Fragen per PM! Es gibt hier ein Forum, verdammt!

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Nikx“ ()

      Ich habe die Funktion mal etwas optimiert, verkürzt und in eine eigene Methode gepackt:

      C#-Quellcode

      1. public static BigInteger Calculate(int iterations)
      2. {
      3. BigInteger number = 2;
      4. BigInteger fractional = 1;
      5. BigInteger result = 0;
      7. for (BigInteger counter = 0; counter <= iterations; counter++) //for anstatt while -> besserer Stil :P
      8. {
      9. BigInteger oddNumber = fractional;
      10. BigInteger countFractionalDeduction = 0;
      12. while ((number -= oddNumber) > 0) //direkt rechnen & zuweisen anstatt doppelt rechnen -> bessere Performance
      13. {
      14. countFractionalDeduction++;
      15. oddNumber += 2;
      16. }
      18. number = (number + oddNumber) * 100;
      19. result = result * (10 ^ countFractionalDeduction.ToString().Length - 1) + countFractionalDeduction;
      20. fractional = (result << 1) * 10 + 1;
      21. }
      23. return result;
      24. }


      Mit diesen Veränderungen brauche ich nur noch 717476 Ticks (210,0345ms) anstatt 957205 ticks (280,2129ms) -> 25% bessere Performance.
      Bei anderen Zahlen holt meine Version sogar bis zu 40% raus.

      @~blaze~
      Damit wird die Performance bei mir bei >10 Iterationen extrem schlecht, ist also wohl nicht wirklich geeignet.
      Man könnte allerdings versuchen, eine eigene Methode für das Zählen der Stellen zu entwickeln.

      Die Länge der Darstellung von countFractionalDeduction im Dezimalsystem scheint sich doch absolut gleichmäßig zu erhöhen: alle 10/100/1000 usw. Iterationen der inneren Schleife wirds um eins länger. Ich sehen keinen Grund, warum man das nicht exakt nach dieser Regel implementieren könnte, Inkrementierung und sehr selten (seltener umso größer die Zahl) Multiplikation mit 10 sollte wesentlich schneller sein, als ToString. Woebi ich natürlich das Verhältnis von innerer zur äußerer Schleife nicht kenne.

      @Artentus: Wie kommst du denn auf die Idee? Entweder verstehe ich das falsch, oder du hast den Sinn der Variable nicht erfasst :)

      Grüße
      "Life isn't about winning the race. Life is about finishing the race and how many people we can help finish the race." ~Marc Mero

      Nun bin ich also auch soweit: Keine VB-Fragen per PM! Es gibt hier ein Forum, verdammt!

      @Artentus
      Wenn ich das richtig sehe, ist die Anzahl der Stellen immer 1. Allerdings fällt dadurch trotzem nicht das Durchzählen weg, da der genaue Wert der Variablen trotzdem später gebraucht wird.

      Es gibt nur einen einzigen Ort, an dem countFractionalDeduction geändert wird, nämlich in der inneren while-Schleife. Wenn nun das Verhältnis zwischen den Durchläufen der inneren und den Durchläufen der äußeren Schleife sehr klein ist, kann das Zählen der Dezimalstellen u.U. schneller rein arithmetisch in der inneren Schleife implementiert werden als es durch ToString in der äußeren Schleife gegeben ist.
      Edit: es geht nicht um die Abschaffung dieser Variablen!

      @Artentus
      Kann gut sein, allerdings sind diese Unterschiede kaum messbar.

      @Nikx
      Wenn meine Vermutung von vorher wahr ist, kann man das Alles auch so schreiben, oder?

      C#-Quellcode

      1. public static BigInteger Calculate(int iterations)
      2. {
      3. BigInteger number = 2;
      4. BigInteger fractional = 1;
      5. BigInteger result = 0;
      7. for (int counter = -1; counter < iterations; counter++)
      8. {
      9. BigInteger oddNumber = fractional;
      10. int countFractionalDeduction = 0;
      11. for (; (number -= oddNumber) > 0; countFractionalDeduction++)
      12. oddNumber += 2;
      13. number = (number + oddNumber) * 100;
      14. result = result * 10 + countFractionalDeduction;
      15. fractional = (result << 1) * 10 + 1;
      16. }
      18. return result;
      19. }


      Edit
      @Artentus
      Das verstehe ich jetzt net.

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „nafets“ ()

      Wenn dem so wäre wäre auch die komplette innere Schleife überflüssig und damit wäre auch oddNumber konstant.
      Edit: Quatsch wär sie nicht. Aber man könnte sie einfach in eine Ganzzahlteilung auflösen.


      Edit2: joa, muss definitiv immer einstellig sein (kann und sollte man auch int nehmen), andernfalls wäre das Verfahren ja fehlerhaft, kann ja keine zweistellige Stelle geben. ;)

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Artentus“ ()

      Weitere kleine Optimierungsidee:
      Debugger abschalten, Codeoptimierung aktivieren und 64 Bit nutzen: nochmal ca. 1/3 schneller -> doppelt so schnell wie am Anfang.

      @Artentus
      Wie wäre es, wenn du auch mal einen Codevorschlag machst?
      Ich blick nämlich nicht wirklich, was genau du machen willst :D

      Edit
      @Artentus
      Wie wäre es hiermit? rechnerlexikon.de/files/PolytJournal1866-Toepler.pdf

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „nafets“ ()

      Bin mir nicht sicher ob es hier hingehört aber dafür ein neues Thema aufzumachen halte ich für unnötig.

      Hier ist das ganze als Python-Programm

      Python-Quellcode

      1. #!/usr/bin/env python
      2. import sys, profile
      4. def main (max_iteration):
      5. number = 2
      6. fractional = 1
      7. counter = 0
      8. result = 0
      9. while counter <= max_iteration:
      10. odd = fractional
      11. fractionalDeduction = 0
      12. while (number - odd) > 0:
      13. number -= odd
      14. fractionalDeduction += 1
      15. odd += 2
      16. number *= 100
      17. result = result * (10 ** len(str(fractionalDeduction)) - 1) + fractionalDeduction
      18. fractional = (result << 1) * 10 + 1
      19. counter += 1
      20. sresult = str(result)
      21. print (sresult[:1] + "." + sresult[1:])
      23. if len(sys.argv) != 2:
      24. print ("Usage: test.py [max_iteration_count]")
      25. sys.exit ()
      26. iterations = int(sys.argv[1])
      27. profile.run ("main(iterations)")


      Und hier noch in IronPython für .Net

      Python-Quellcode

      1. import clr
      2. clr.AddReference ("System")
      3. clr.AddReference ("System.Numerics")
      5. import sys
      6. from System import Console
      7. from System.Diagnostics import Stopwatch
      9. def main (max_iteration):
      10. number = 2
      11. fractional = 1
      12. counter = 0
      13. result = 0
      14. while counter <= max_iteration:
      15. odd = fractional
      16. fractionalDeduction = 0
      17. while (number - odd) > 0:
      18. number -= odd
      19. fractionalDeduction += 1
      20. odd += 2
      21. number *= 100
      22. result = result * (10 ** len(str(fractionalDeduction)) - 1) + fractionalDeduction
      23. fractional = (result << 1) * 10 + 1
      24. counter += 1
      25. sresult = str(result)
      26. print (sresult[:1] + "." + sresult[1:])
      28. if len(sys.argv) != 2:
      29. print ("Usage: test.py [max_iteration_count]")
      30. sys.exit ()
      32. iterations = int(sys.argv[1])
      33. stopwatch = Stopwatch ()
      34. stopwatch.Start ()
      35. main (iterations)
      36. stopwatch.Stop ()
      37. Console.WriteLine ("Time elapsed: {0}", stopwatch.Elapsed)



      Die Berechnung ist in Python nochmal schneller als C#.
      Die Anzahl der Iterationen wird als erstes Argument mitgegeben.
      Python: ./test.py [iterations]
      IronPython: ipy test.ipy [iterations]

      Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „SplittyDev“ ()

      @SplittyDev
      Wie sieht es denn mit der Präzision des Ergebnisses aus? Kann das auch auf 1'000'000 Nachkommastellen genau berechnen?
      Außerdem:

      Quellcode

      1. ​ File "test.py", line 12
      2. while (number -= odd) > 0:
      3. ^
      4. SyntaxError: invalid syntax

      @nafets
      Python ist eine dynamisch typisierte Programmiersprache.
      Solange die Zahlen kleiner als der int32 Maximalwert sind, wird int als Typ angenommen,
      sobald die Zahlen größer werden wird der Typ automatisch zu bignum gewechselt.
      Der bignum-Typ ist dem BigInteger-Typ des .Net Frameworks ziemlich ähnlich und erlaubt Ganzzahlen mit einer Genauigkeit, die nur durch den Arbeitsspeicher beschränkt ist.
      Es kommt also zu keinem Overflow und das Ergebnis ist das selbe wie bei der Verwendung von C# und BigInteger.

      Edit: Oops. Fix:

      Python-Quellcode

      1. while (number - odd) > 0:
      2. number -= odd


      Habe es im Code oben angepasst.

      // Edit 2
      Da kommen komische Werte bei raus, die ich mir im Moment nicht erklären kann.
      Bitte den Python Code nicht nutzen, außer um den Fehler zu finden.

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „SplittyDev“ ()

      @SplittyDev
      Außerdem ist dein Python-Script (auch wenn es jetzt gerade nicht richtig funktioniert) kein bisschen schneller: Dein Python-Script braucht bei mir 4,891 Sekunden für 25000 Iterationen. Für diese braucht Nikx sein Code 0,996 Sekunden - meine neueste Variante 0,602 Sekunden (beides 64bit, bei 32bit sind es 1,537 und 0,963 Sekunden).

      Was kam denn bei dir raus, dass du denkst, Python sei schneller?
      Bilder

      • Toepler Python versus DotNet.png

        30,04 kB, 676×686, 133 mal angesehen

      @nafets Das Ergebnis ist genau. Der Algorithmus naähert nicht an, sondern berechnet Stelle für Stelle. Habe gestern
      1.000.000 Stellen errechnen lassen. Hat zwar stolze 53 Minuten gebraucht, war aber exakt.

      Grüße
      "Life isn't about winning the race. Life is about finishing the race and how many people we can help finish the race." ~Marc Mero

      Nun bin ich also auch soweit: Keine VB-Fragen per PM! Es gibt hier ein Forum, verdammt!

      Nikx und ich haben beides ausprobiert und bei uns beiden war die Python-Variante minimal schneller.
      Welche Python-Version verwendest du? Kommt aber wahrscheinlich letztendlich auf das System an.

      @Nikx
      Das war auf die Python-Variante, nicht auf die C#-Variante bezogen. Bei der C#-Variante glaube ich schon, dass sie exakt ist :)

      @SplittyDev
      Ich habe leider keine Ahnung von Python - hab mir einfach die Version von Chip (scheint wohl 3.4.2 zu sein) heruntergeladen und installiert.
      Aber ich glaube trotztem kaum, dass .NET plötzlich 5 mal schneller ist... Ich lass das mal anstatt mit Roslyn und .NET 4.5.3 mit dem Standard-Compiler und .NET 4.5 laufen.

      Edit:
      Nö, das sind gerade mal ​0,02 Sekunden Unterschied...

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „nafets“ ()

      Zum Präzisionstest gibts zum Glück Wolframalpha.
      wolframalpha.com/input/?i=10000th+digit+of+sqrt(2)

      Man kann dan rückwarts durchlaufen und testen.
      Grüße
      "Life isn't about winning the race. Life is about finishing the race and how many people we can help finish the race." ~Marc Mero

      Nun bin ich also auch soweit: Keine VB-Fragen per PM! Es gibt hier ein Forum, verdammt!