Fakultaet mit n= 60 berechnen



  • @steven-w
    Schon mal überlegt eine eigene BitInt Klasse zu entwickeln, welche auf Strings arbeitet?

    Grundgerüst:

    class BigInt
    {
    private:
      std::string mIntRep;  ///< Interne Darstellung des BigInts (z.B. "13")
    
    public:
      void Set(unsigned int X)
      {  
         // Wandele X in einen String
      }
    
      void Add(const BigInt& x)
      {
        // Führe Addition auf beiden Strings per Hand wie in der Grundschule durch 
      }
    
      void Mul(unsigned int x)
      {
        // Wandele X in einen String
        // Führe Multiplikation auf beiden Strings per Hand wie in der Grundschule durch 
        // Also 
        // 12 * 32 
        // -------
        //     36
        //      24
        // -------
        //     384
      }
    
      std::string GetValue() 
      {
        // Fill me
      }
    };
    


  • @DirkB
    Jau. facepalm


  • Mod

    @Quiche-Lorraine sagte in Fakultaet mit n= 60 berechnen:

    @steven-w
    Schon mal überlegt eine eigene BitInt Klasse zu entwickeln, welche auf Strings arbeitet?

    Zwar möglich, aber würde ich mir nochmal genau überlegen. Mit String ist es zwar schön anschaulich, aber dafür handelt man sich zusätzliche Komplexität bei der Implementierung der Rechenoperationen ein (gegenüber dem vector<unsigned> als Alternative). Ich kann jetzt aber auch keine klare Empfehlung für das eine oder andere aussprechen, denn nach den vorherigen Fragen zu urteilen, hätte steven-w Schwierigkeiten sowohl mit der hohen Abstraktion von vector<unsigned> als auch mit der Komplexität von string. Muss er selber wissen, was ihn davon mehr anspricht. Aber die Alternative musste ich noch nennen. @steven-w : Eins von beidem muss es sein, alternative Lösungen wären nur noch komplexer.

    (und die Stringlösung ist natürlich viel weniger effizient, aber das spielt bei so kleinen Zahlen mit 80 Stellen wohl kaum eine Rolle 🙂 )



  • @SeppJ sagte in Fakultaet mit n= 60 berechnen:

    Mit String ist es zwar schön anschaulich,

    Und genau deswegen habe ich an Strings gedacht.

    Aber klar, dadurch bekomme ich eine zusätzliche Komlexität (Int zu String Wandlung, Addition zweier char Werte) hinzu.



  • Für 60! braucht man > 270 Bit.
    Mit zwei Teilen kommt man also nicht aus.
    Und sobald man mehr als zwei hat, kann man mMn. auch gleich beliebig viele machen.

    Was std::string angeht: das ist mMn. gar keine Schlechte Idee. Also wenn man das Dezimalsystem verwendet. Dann muss man die Zahl zur Ausgabe nämlich nicht nochmal umrechnen. D.h. man spart sich erstmal die Division zu implementieren. Addition und Multiplikation reichen aus.
    (OK, man kann die Umrechnung auch ohne Division implementieren. Ist vermutlich nichtmal so schlimm was Laufzeit angeht - zumindest nicht bei Umrechnung nach Basis 10.)


  • Mod

    @hustbaer sagte in Fakultaet mit n= 60 berechnen:

    Was std::string angeht: das ist mMn. gar keine Schlechte Idee. Also wenn man das Dezimalsystem verwendet. Dann muss man die Zahl zur Ausgabe nämlich nicht nochmal umrechnen. D.h. man spart sich erstmal die Division zu implementieren. Addition und Multiplikation reichen aus.
    (OK, man kann die Umrechnung auch ohne Division implementieren. Ist vermutlich nichtmal so schlimm was Laufzeit angeht - zumindest nicht bei Umrechnung nach Basis 10.)

    Kannst ja zur Basis 1,000,000,000 rechnen mit vector<uint32> 🙂



  • @steven-w sagte in Fakultaet mit n= 60 berechnen:

    @SeppJ

    ja das anlegen eines eigenen Datentypen wird auch in der Aufgabe verlangt, nur komm ich damit leider nicht weiter. Ich stell mich ziemlich schwer bei dieser Aufgabe an.

    Fangen wir mal am Anfang an. Du sollst die Fakultät von 60 berechnen. Die Zahlen von 1 bis 60 lassen sich mit 6Bit darstellen. D.h. das Ergebnis ist nicht größer als 360Bit (60×6Bit).

    Die Multiplikation zweier Zahlen a×b lässt sich in a×(c1 + c2) = a×c1 + a×c2 zerlegen. Deshalb darfst Du z.B. untersten 58 Bit mit der Zahl a (die hier 6Bit groß ist) multiplizieren, erhälst eine 64Bit Zahl, und addierst als Übertrag die oberen 6Bit dieser Teilmultipliktation auf das Ergebnis der Multiplikation der höherwertigen Bits auf.



  • @SeppJ sagte in Fakultaet mit n= 60 berechnen:

    Kannst ja zur Basis 1,000,000,000 rechnen mit vector<uint32> 🙂

    Das ginge auch gut, ja.
    Bleibt sich vom Programmieren her aber ziemlich gleich denke ich. Laufzeit sollte es natürlich ordentlich schneller sein.


  • Mod

    Da frage ich mich, was eigentlich die beste Basis wäre für minimalen Programmieraufwand (Laufzeit außer acht gelassen). Ich würde spontan so etwas vorschlagen wie die größte Zehnerpotenz die kleiner als sqrt(max value) ist, also 10,000 bei uint32 (weil sqrt(2^32) = 2^16 = 65536). Da hat man

    • triviale Darstellung im Dezimalsystem
    • genügend Platz nach oben, um Überläufe trivial zu handhaben bei Addition
    • selbiges sogar bei Multiplikation
    • Keine Ziffernwertumrechnung wie bei string


  • Die korrekte Lösung ist laut Maxima
    60! = 8320987112741390144276341183223364380754172606361245952449277696409600000000000000
    bzw. in Hexadezimaldarstellung
    60! = 0x118b5727f009f525dcfe0d58e8653c742de9d889c2efe3c5516f88700000000000000

    Den Code den ich geschrieben habe nutzt 8×uint64_t als Speicher und nutzt jeweils nur 56Bit, weil 56Bit×8Bit = 64Bit ist, und man keinen Überlauf hat. Da das nicht meine Hausarbeit ist, gibt's keine Ausgabe in Dezimal sondern nur nach jeder Multiplikation in Hex. Das oberste Byte ist zu ignorieren, weil nur für den Übertrag vorhanden.

    01|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000000000000001|
    02|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000000000000002|
    03|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000000000000006|
    04|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000000000000018|
    05|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000000000000078|
    06|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x00000000000002d0|
    07|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x00000000000013b0|
    08|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000000000009d80|
    09|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000000000058980|
    10|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000000000375f00|
    11|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000000002611500|
    12|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x000000001c8cfc00|
    13|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x000000017328cc00|
    14|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x000000144c3b2800|
    15|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000013077775800|
    16|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0000130777758000|
    17|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0001437eeecd8000|
    18|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000000|0:0x0016beecca730000|
    19|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000001|0:0x00b02b9306890000|
    20|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000000021|0:0x00c3677c82b40000|
    21|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x00000000000002c5|0:0x00077d36b8c40000|
    22|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000003cee|0:0x00a4c2b3e0d80000|
    23|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000057970|0:0x00cd7e2933680000|
    24|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x0000000000836293|0:0x0043d3dcd1c00000|
    25|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x000000000cd4a061|0:0x009fb0907bc00000|
    26|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x000000014d9849ea|0:0x0037eeac91800000|
    27|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x000000232f0fcbb3|0:0x00e62c3358800000|
    28|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x000003d925ba47ad|0:0x002cd59dae000000|
    29|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x00006f99461a1e9e|0:0x001432dcb6000000|
    30|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000000|1:0x000d13f6370f9686|0:0x005df5dd54000000|
    31|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000001|1:0x00956ad0aae33a45|0:0x0060c5cd2c000000|
    32|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000032|1:0x00ad5a155c6748ac|0:0x0018b9a580000000|
    33|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000000000000688|1:0x00589cc0e9505e2f|0:0x002fee5580000000|
    34|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x000000000000de1b|1:0x00c4d19efcac8244|0:0x005da75b00000000|
    35|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x00000000001e5dcb|1:0x00e8a8bc8b95cf58|0:0x00cde17100000000|
    36|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x00000000044530ac|1:0x00b7ba83a111287c|0:0x00f3b3e400000000|
    37|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x000000009e0008f6|1:0x008df506477ada0f|0:0x0038fff400000000|
    38|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0000001774015499|1:0x00125eee9c3c5e42|0:0x0075fe3800000000|
    39|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x00000392ac33e351|1:0x00cc7659cd325c1f|0:0x00f9ba8800000000|
    40|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x00008eeae81b84c7|1:0x00f27e080fde64ff|0:0x0005254000000000|
    41|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000000|2:0x0016e39f2c684405|1:0x00d62f4a8a9e2cd7|0:0x00d2f74000000000|
    42|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000000003|2:0x00c1581d491b28f5|1:0x0023c23abdf35b68|0:0x009c908000000000|
    43|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x00000000000000a1|2:0x0079cceb478fe12d|1:0x00019fdde7e05a92|0:0x004c458000000000|
    44|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000001bc0|2:0x00ef38704cbab3bc|1:0x00477a23da8f9125|0:0x001bf20000000000|
    45|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x000000000004e0ea|2:0x000cebbd7cd19818|1:0x0090784d6b3c8385|0:0x00e98a0000000000|
    46|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000000000e06a0e|2:0x00525c0c6da95469|1:0x00f59de944dfa20f|0:0x00f6cc0000000000|
    47|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x00000000293378a1|2:0x001ee64822167f74|1:0x0017fdd3a50ec0ee|0:0x004f740000000000|
    48|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x00000007b9a69e35|2:0x00cb2d866437e5c4|1:0x007f97aef2c42cae|0:0x00e5c00000000000|
    49|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x0000017a88e4484b|2:0x00e3b6b92eb2fa9c|1:0x006c087c778c8d79|0:0x00f9c00000000000|
    50|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x000049eebc961ed2|2:0x0079b02b1ef4f28d|1:0x0019a84f5973a1d2|0:0x00c7800000000000|
    51|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000000|3:0x000eba8f91e823ee|2:0x003e18972acc521c|1:0x001c87ced2093cfd|0:0x00be800000000000|
    52|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000000002|3:0x00fde529a3274c64|2:0x009cfeb4b180adb5|1:0x00cb9602a9e0638a|0:0x00b2000000000000|
    53|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x000000000000009e|3:0x0090719ec722d0d4|2:0x0080bb68bfa3f6a3|1:0x00260e8d2b749bb6|0:0x00da000000000000|
    54|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000002172|3:0x0077f77e01580cd3|2:0x002788186c96066a|1:0x000711c72a98d891|0:0x00fc000000000000|
    55|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000000072f97|3:0x00c62c1249eac15d|2:0x007e3d3f543b60c7|1:0x0084d1ca26d6875d|0:0x0024000000000000|
    56|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000001926933|3:0x0059a4002b5a4c73|2:0x009d65da6cfd2ba5|1:0x000de4387eed9c5f|0:0x00e0000000000000|
    57|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x0000000059996c6e|3:0x00f58409a71b05be|2:0x000bada2445eb7c0|1:0x0017d09442e7d158|0:0x00e0000000000000|
    58|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x000000144cc29123|3:0x009fea2fdc1f4d0e|2:0x00a556c37d75a185|1:0x0065419728856e22|0:0x00c0000000000000|
    59|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x000004adb0d77335|3:0x00daf907bb36c260|2:0x001aff0dea1c39be|1:0x00561dd656c06202|0:0x0040000000000000|
    60|7:0x0000000000000000|6:0x0000000000000000|5:0x0000000000000000|4:0x000118b5727f009f|3:0x00525dcfe0d58e86|2:0x0053c742de9d889c|1:0x002efe3c5516f887|0:0x0000000000000000|
    
    


  • Möchtest Du noch Deinen Code zeigen? Zum eventuellen Abschreiben für eine Hausarbeit wird er ja hier eh nicht helfen?



  • @SeppJ
    Man sollte auf jeden Fall maximal 1/2 der Bits von maxint_t verwenden. Wenn man super faul ist und nicht rumcasten will sollte man auch nur 1/2 der Bits des Typs verwenden den man als Storage verwendet. Wenn man der Einfachkeit halber int nimmt und nur die Garantien des C++ Standard verwenden will wäre man dann bei 100.

    Aber wieso 100 oder 10,000 - was hat das für einen Vorteil gegenüber 10 wenn man die Laufzeit ignoriert? Also nicht 10 mit std::string sondern 10 mit vector<int>.

    Bei allem über 10 musst du halt bei der Ausgabe zero-padding machen. Aber auch nicht für alle Stellen sondern nur für alles nach dem "most significant" Teil. Ist jetzt keine Rocket-Science aber komplizierter als einfach alle Stellen der Reihe nach auszugeben.


  • Mod

    @hustbaer sagte in Fakultaet mit n= 60 berechnen:

    Aber wieso 100 oder 10,000 - was hat das für einen Vorteil gegenüber 10 wenn man die Laufzeit ignoriert?

    Weil ich vergessen habe, dass man dann für die Ausgabe zero-padding braucht 🙂



  • Dann haben wir denke ich einen Gewinner: vector<int> mit Basis 10 🙂


  • Mod

    @hustbaer sagte in Fakultaet mit n= 60 berechnen:

    Dann haben wir denke ich einen Gewinner: vector<int> mit Basis 10 🙂

    Das wäre dann auch ernsthaft die Empfehlung an den Threadersteller, wenn er überhaupt noch zuhört. @steven-w : Bekommst du es mit vector<int> zur Basis 10 hin? Einfacher und anschaulicher als damit wird's nicht. Und besser kann man es davon ausgehend immer noch machen, wenn's erst einmal läuft.



  • Wobei... ein fixes int Array mit z.B. Grösse 100 (würde für 60! reichen) wäre vermutlich nochmal eine Spur einfacher.


  • Mod

    @hustbaer sagte in Fakultaet mit n= 60 berechnen:

    Wobei... ein fixes int Array mit z.B. Grösse 100 (würde für 60! reichen) wäre vermutlich nochmal eine Spur einfacher.

    Ist es? Hat wieder Verkomplizierung bei der Ausgabe, und - wenn man es denn universell nutzbar machen will - ein paar sonst unnötige Zusatzabfragen, um Zahlen > 10^100 abzufangen. Jetzt sind wir quasi an dem Punkt, wo man es einfach mal runterschreiben müsste, um zu vergleichen.



  • @SeppJ
    Ich hatte angenommen dass man die Abfragen für Überlauf weglässt und das Ding einfach überlaufen lässt - genau so wie es auch bei den eingebauten Datentypen ist. Also 99...99 + 00...01 = 00...00.

    Jetzt sind wir quasi an dem Punkt, wo man es einfach mal runterschreiben müsste, um zu vergleichen.

    Vermutlich, ja.
    Viel einfacher wird es dadurch sicher nicht.


  • Mod

    @hustbaer sagte in Fakultaet mit n= 60 berechnen:

    @SeppJ
    Ich hatte angenommen dass man die Abfragen für Überlauf weglässt und das Ding einfach überlaufen lässt - genau so wie es auch bei den eingebauten Datentypen ist. Also 99...99 + 00...01 = 00...00.

    Überlaufen lassen fände ich prinzipiell ok, aber man darf ja nicht versehentlich auf Element 101 zugreifen



  • @SeppJ
    Klar. Das lässt sich aber denke ich einfach vermeiden indem man immer alle 100 Stellen bearbeitet ohne den Inhalt zu checken, und Überträge in einer Hilfsvariable von einem Schleifendurchlauf in den nächsten rettet statt sie direkt auf die nächste Stelle zu verbuchen.

    Der letzte Übertrag bleibt dann einfach für Schleifendurchlauf 101 stehen, den wir aber nicht machen weil die Schleife fix 100 Durchläufe macht.


Anmelden zum Antworten