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.


  • 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.



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

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

    Ich habe es noch einmal überarbeitet. Jetzt nutzt es den kompletten Speicherbereich der Zahlen, und der Code lässt sich analog für uint16_t, uint32_t nutzen. Die Routine für die Multiplikation zweier großen Zahlen ist noch nicht fertigt, aber das erfolgt dann analog, wobei man dann den „Versatz“ beachte muss.

    Die Ausgabe nach der Änderung.

    01|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000000000000001|
    02|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000000000000002|
    03|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000000000000006|
    04|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000000000000018|
    05|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000000000000078|
    06|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x00000000000002d0|
    07|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x00000000000013b0|
    08|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000000000009d80|
    09|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000000000058980|
    10|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000000000375f00|
    11|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000000002611500|
    12|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x000000001c8cfc00|
    13|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x000000017328cc00|
    14|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x000000144c3b2800|
    15|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000013077775800|
    16|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0000130777758000|
    17|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0001437eeecd8000|
    18|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x0016beecca730000|
    19|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x01b02b9306890000|
    20|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000000|00:0x21c3677c82b40000|
    21|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000002|00:0xc5077d36b8c40000|
    22|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x000000000000003c|00:0xeea4c2b3e0d80000|
    23|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000000579|00:0x70cd7e2933680000|
    24|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000000000008362|00:0x9343d3dcd1c00000|
    25|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x00000000000cd4a0|00:0x619fb0907bc00000|
    26|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x00000000014d9849|00:0xea37eeac91800000|
    27|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x00000000232f0fcb|00:0xb3e62c3358800000|
    28|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x00000003d925ba47|00:0xad2cd59dae000000|
    29|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0000006f99461a1e|00:0x9e1432dcb6000000|
    30|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x00000d13f6370f96|00:0x865df5dd54000000|
    31|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0001956ad0aae33a|00:0x4560c5cd2c000000|
    32|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0032ad5a155c6748|00:0xac18b9a580000000|
    33|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0x0688589cc0e9505e|00:0x2f2fee5580000000|
    34|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000000|01:0xde1bc4d19efcac82|00:0x445da75b00000000|
    35|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x000000000000001e|01:0x5dcbe8a8bc8b95cf|00:0x58cde17100000000|
    36|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000000445|01:0x30acb7ba83a11128|00:0x7cf3b3e400000000|
    37|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000009e00|01:0x08f68df506477ada|00:0x0f38fff400000000|
    38|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000000000177401|01:0x5499125eee9c3c5e|00:0x4275fe3800000000|
    39|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x000000000392ac33|01:0xe351cc7659cd325c|00:0x1ff9ba8800000000|
    40|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x000000008eeae81b|01:0x84c7f27e080fde64|00:0xff05254000000000|
    41|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x00000016e39f2c68|01:0x4405d62f4a8a9e2c|00:0xd7d2f74000000000|
    42|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x000003c1581d491b|01:0x28f523c23abdf35b|00:0x689c908000000000|
    43|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x0000a179cceb478f|01:0xe12d019fdde7e05a|00:0x924c458000000000|
    44|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x001bc0ef38704cba|01:0xb3bc477a23da8f91|00:0x251bf20000000000|
    45|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0x04e0ea0cebbd7cd1|01:0x981890784d6b3c83|00:0x85e98a0000000000|
    46|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000000|02:0xe06a0e525c0c6da9|01:0x5469f59de944dfa2|00:0x0ff6cc0000000000|
    47|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000000029|02:0x3378a11ee6482216|01:0x7f7417fdd3a50ec0|00:0xee4f740000000000|
    48|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x00000000000007b9|02:0xa69e35cb2d866437|01:0xe5c47f97aef2c42c|00:0xaee5c00000000000|
    49|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000000000017a88|02:0xe4484be3b6b92eb2|01:0xfa9c6c087c778c8d|00:0x79f9c00000000000|
    50|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x000000000049eebc|02:0x961ed279b02b1ef4|01:0xf28d19a84f5973a1|00:0xd2c7800000000000|
    51|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x000000000eba8f91|02:0xe823ee3e18972acc|01:0x521c1c87ced2093c|00:0xfdbe800000000000|
    52|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x00000002fde529a3|02:0x274c649cfeb4b180|01:0xadb5cb9602a9e063|00:0x8ab2000000000000|
    53|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000009e90719ec7|02:0x22d0d480bb68bfa3|01:0xf6a3260e8d2b749b|00:0xb6da000000000000|
    54|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0000217277f77e01|02:0x580cd32788186c96|01:0x066a0711c72a98d8|00:0x91fc000000000000|
    55|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x00072f97c62c1249|02:0xeac15d7e3d3f543b|01:0x60c784d1ca26d687|00:0x5d24000000000000|
    56|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x0192693359a4002b|02:0x5a4c739d65da6cfd|01:0x2ba50de4387eed9c|00:0x5fe0000000000000|
    57|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000000|03:0x59996c6ef58409a7|02:0x1b05be0bada2445e|01:0xb7c017d09442e7d1|00:0x58e0000000000000|
    58|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x0000000000000014|03:0x4cc291239fea2fdc|02:0x1f4d0ea556c37d75|01:0xa18565419728856e|00:0x22c0000000000000|
    59|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x00000000000004ad|03:0xb0d77335daf907bb|02:0x36c2601aff0dea1c|01:0x39be561dd656c062|00:0x0240000000000000|
    60|07:0x0000000000000000|06:0x0000000000000000|05:0x0000000000000000|04:0x00000000000118b5|03:0x727f009f525dcfe0|02:0xd58e8653c742de9d|01:0x889c2efe3c5516f8|00:0x8700000000000000|
    

    Und der dazu gehörende Code

    #include <cstdint>
    #include <cstdlib>
    #include <stdexcept>
    #include <iostream>
    #include <iomanip>
    
    constexpr uint64_t LOW_MASK      = 0x00000000FFFFFFFF;
    constexpr uint64_t LOW_BYTE_MASK = 0x00000000000000FF;
    
    class BigInt;
    
    BigInt operator* (const BigInt& lhs, const uint8_t rhs);
    
    class BigInt {
    public:
    	static const size_t	size_ = 8;
    	uint64_t	int_[size_];
    
    	BigInt () {
    		for (size_t i = 0; i != size_; ++i) {
    			int_[i] = 0;
    		}
    	}
    
    	BigInt (const BigInt& rhs) {
    		for (size_t i = 0; i != size_; ++i) {
    			int_[i] = rhs.int_[i];
    		}
    	}
    
    	BigInt (const uint8_t rhs) {
    		int_[0] = rhs;
    		for (size_t i = 1; i != size_; ++i) {
    			int_[i] = 0;
    		}
    	}
    
    	BigInt& operator= (const uint8_t rhs) {
    		int_[0] = rhs;
    		for (size_t i = 1; i != size_; ++i) {
    			int_[i] = 0;
    		}
    
    		return *this;
    	}
    
    	BigInt& operator= (const BigInt& rhs) {
    		for (size_t i = 0; i != size_; ++i) {
    			this->int_[i] = rhs.int_[i];
    		}
    
    		return *this;
    	}
    
    	BigInt& operator*= (const uint8_t rhs) {
    		(*this) = (*this) * rhs;
    
    		return *this;
    	}
    
    	void print () {
    		std::cout << "|";
    		for (size_t i = 0; i != size_; ++i) {
    			std::cout << std::setw (2) << std::setfill('0') << size_ - i - 1 << ":0x" << std::hex << std::setw(16) << this->int_[size_- i - 1] << "|";
    		}
    	}
    };
    
    BigInt operator* (const BigInt& lhs, const uint8_t rhs) {
    	BigInt r;
    
    	uint64_t hi, lo, t;
    	uint16_t carry = 0;
    
    	for (size_t i = 0; i != BigInt::size_; ++i) {
    		t = 0;
    		lo = (lhs.int_[i] & LOW_MASK);
    		hi = (lhs.int_[i] >> 32) & LOW_MASK;
    
    
    		t  = lo * rhs;
    		t += carry;
    		r.int_[i] = t & LOW_MASK;
    		carry = (t >> 32) & LOW_BYTE_MASK;
    
    		t  = hi * rhs;
    		t += carry;
    		carry = (t >> 32) & LOW_BYTE_MASK;
    		r.int_[i] += ((t & LOW_MASK) << 32);
    	}
    
    	if (0 != carry) throw std::runtime_error ("overflow");
    
    	return r;
    }
    
    
    BigInt operator* (const uint8_t lhs, const BigInt& rhs) {
    	return (rhs * lhs);
    }
    
    int main () {
    	BigInt f = static_cast<uint8_t>(1);
    
    	for (uint8_t i = 1; i != 61; ++i) {
    		uint16_t s = i;
    		f *= i;
    
    		std::cout << std::dec << std::setw(2) << std::setfill('0') << s;
    		f.print();
    		std::cout << "\n";
    	}
    
    	return EXIT_SUCCESS;
    }
    
    


  • Danke 🙂



  • (u)int256_t, (u)int512_t und (u)int1024_t sind auch in boost::multiprecision zu finden.

    Ich habe das mal kurz mit meiner naiven BigInt-Klasse verglichen, die ich zum Spaß vor zig Jahren geschrieben habe.
    Allerdings kann diese „beliebig“ wachsen (die Lebenszeit ist endlich).

    Jeweils einige Durchgänge:

    Fac(60) 273 Bit
    -------------------
    0.000040 uint1024_t
    
    0.064978 my big int
    
    
    Fac(170) 1020 Bit
    -------------------
    0.000146 uint1024_t
    
    1.429892 my big int
    

    Schon etwas ernüchternd.



  • Noch ein Nachtrag, nun mit Multiplikation zweier BigInts. Das Ergebnis von fac60 stimmt, weitere Tests habe ich nicht gemacht.

    #include <cstdint>
    #include <cstdlib>
    #include <stdexcept>
    #include <iostream>
    #include <ostream>
    #include <iomanip>
    
    constexpr uint64_t LOW_MASK      = 0x00000000FFFFFFFF;
    constexpr uint64_t LOW_BYTE_MASK = 0x00000000000000FF;
    
    class BigInt;
    
    BigInt operator* (const BigInt& lhs, const uint8_t rhs);
    BigInt operator* (const BigInt& lhs, const BigInt& rhs);
    
    class BigInt {
    public:
    	static const size_t	size_ = 8;
    	uint64_t	int_[size_];
    
    	BigInt () {
    		for (size_t i = 0; i != size_; ++i) {
    			int_[i] = 0;
    		}
    	}
    
    	BigInt (const BigInt& rhs) {
    		for (size_t i = 0; i != size_; ++i) {
    			int_[i] = rhs.int_[i];
    		}
    	}
    
    	BigInt (const uint8_t rhs) {
    		int_[0] = rhs;
    		for (size_t i = 1; i != size_; ++i) {
    			int_[i] = 0;
    		}
    	}
    
    	BigInt& operator= (const uint8_t rhs) {
    		int_[0] = rhs;
    		for (size_t i = 1; i != size_; ++i) {
    			int_[i] = 0;
    		}
    
    		return *this;
    	}
    
    	BigInt& operator= (const BigInt& rhs) {
    		for (size_t i = 0; i != size_; ++i) {
    			this->int_[i] = rhs.int_[i];
    		}
    
    		return *this;
    	}
    
    	BigInt& operator*= (const uint8_t rhs) {
    		(*this) = (*this) * rhs;
    
    		return *this;
    	}
    
    	BigInt& operator*= (const BigInt& rhs) {
    		(*this) = (*this) * rhs;
    
    		return *this;
    	}
    
    	std::ostream& print (std::ostream& o) const {
    		o << "|";
    		for (size_t i = 0; i != size_; ++i) {
    			o << std::setw (2) << std::setfill('0') << size_ - i - 1 << ":0x" << std::hex << std::setw(16) << this->int_[size_- i - 1] << "|";
    		}
    
    		return o;
    	}
    };
    
    std::ostream&
    operator<< (std::ostream& o, const BigInt& bi) {
    	return bi.print(o);
    }
    
    BigInt operator* (const BigInt& lhs, const BigInt& rhs) {
    	BigInt r;
    
    	uint64_t lhi, llo, carry = 0;
    	uint64_t h, m1, m2, l;
    	uint64_t ta[BigInt::size_ * 2];
    
    	for (size_t i = 0; i != BigInt::size_ * 2; ++i) {
    		ta[i] = 0;
    	}
    
    	for (size_t j = 0; j != BigInt::size_; ++j) {
    		const uint64_t rlo = rhs.int_[j] & LOW_MASK;
    		const uint64_t rhi = rhs.int_[j] >> 32;
    
    		for (size_t i = 0; i != BigInt::size_; ++i) {
    			llo = lhs.int_[i] & LOW_MASK;
    			lhi = lhs.int_[i] >> 32;
    
    			l  = llo * rlo;
    			m1 = llo * rhi;
    			m2 = lhi * rlo;
    			h  = lhi * rhi;
    
    			llo  = (l   & LOW_MASK) + carry + (ta[i + j] & LOW_MASK);
    			lhi  =  llo >> 32; // carry
    			llo  =  llo & LOW_MASK;
    			lhi += (l   >> 32) + (m1 &LOW_MASK) + (m2 & LOW_MASK) + (ta[i + j] >> 32);
    			carry = lhi >> 32;
    			ta[i + j] = llo + (lhi << 32);
    
    			llo = (h & LOW_MASK) + (m1 >> 32) + (m2 >> 32) + carry + (ta[i + j +1] & LOW_MASK);
    			lhi = (h >> 32) + (llo >> 32) + (ta[i + j + 1] >> 32);
    			carry = lhi >> 32;
    			ta[i + j + 1] = llo + (lhi << 32);
    		}
    	}
    
    	for (size_t i = 0; i != BigInt::size_; ++i) {
    		r.int_[i] = ta[i];
    	}
    
    	for (size_t i = BigInt::size_; i != BigInt::size_ * 2; ++i) {
    		if (0 != ta[i]) throw std::runtime_error ("overflow");
    	}
    
    	return r;
    }
    
    BigInt operator* (const BigInt& lhs, const uint8_t rhs) {
    	BigInt r;
    
    	uint64_t hi, lo, t;
    	uint16_t carry = 0;
    
    	for (size_t i = 0; i != BigInt::size_; ++i) {
    		t = 0;
    		lo = (lhs.int_[i] & LOW_MASK);
    		hi = (lhs.int_[i] >> 32);
    
    
    		t  = lo * rhs;
    		t += carry;
    		r.int_[i] = t & LOW_MASK;
    		carry = (t >> 32); 
    
    		t  = hi * rhs;
    		t += carry;
    		carry = (t >> 32);
    		r.int_[i] += ((t & LOW_MASK) << 32);
    	}
    
    	if (0 != carry) throw std::runtime_error ("overflow");
    
    	return r;
    }
    
    
    BigInt operator* (const uint8_t lhs, const BigInt& rhs) {
    	return (rhs * lhs);
    }
    
    int main () {
    	uint8_t one = 1;
    	BigInt f = one;
    	f.int_[0] = 1;
    
    	for (uint8_t i = 1; i != 61; ++i) {
    		uint16_t s = i;
    		f *= i;
    
    		std::cout << std::dec << std::setw(2) << std::setfill('0') << s << f << "\n";
    	}
    
    	std::cout << "\n";
    
    	f = 1;
    
    	for (uint8_t i = 1; i != 61; ++i) {
    		uint16_t s = i;
    		BigInt t (i);
    		f *= t;
    
    		std::cout << std::dec << std::setw(2) << std::setfill('0') << s << f << "\n";
    	}
    
    	return EXIT_SUCCESS;
    }
    
    


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

    Da frage ich mich, was eigentlich die beste Basis wäre für minimalen Programmieraufwand

    @SeppJ
    Die der Ausgabe, also z.B. 10. Grund: man muss führende Nullen nicht behandeln.


Anmelden zum Antworten