Apokalyptische Potenzen finden/darstellen



  • Ein Beispiel für das Thema der Erzeugung und Untersuchung großer Zahlen sind die "apocalyptic numbers" der Form 2^n, die in ihrer dezimalen Darstellung die aus der Offenbarung bekannte Ziffernfolge "666" enthalten. Die kleinste dieser Zahlen soll 2^157 sein und unterhalb 10000 soll es 6485 davon geben.
    http://oeis.org/A007356

    Wir schreiben ein Programm, mit dem wir natürlich auch andere Basen als 2 verwenden und andere Ziffernfolgen identifizieren können.

    #include <iostream>
    #include <string>
    #include <mpirxx.h>
    
    //#define SHOWNUMBERS
    
    using namespace std;
    
    mpz_class power(mpz_class number, uint64_t i) // not optimized // not used here
    {
    	if (i == 0)
    		return mpz_class(1);
    
    	mpz_class result = number;
    	for (uint64_t a = 1; a < i; ++a)
    		result *= number;
    	return result;
    }
    
    mpz_class power2(uint64_t i)
    {
    	if (i == 0)
    		return mpz_class(1);
    
    	mpz_class result = 2;
    	result <<= (i-1);
    	return result;
    }
    
    int main()
    {
    	mpz_class number;
    	uint64_t limit = 50000, count = 0;
    
    	for (uint64_t i = 0; i < limit; ++i)
    	{	
    		number = power2(i);
    		string str = number.get_str();
    		size_t pos = str.find("666"); // Apokalyse, 13,18
    		if (pos != string::npos)
    		{
    #ifdef SHOWNUMBERS           
    			cout << "exp = " << i << ",  pos = " << pos << endl;
    			cout << number << endl;
    #endif
    			++count;
    		}					
    	}
    	cout << "\nbelow n = " << limit << " exist " << count << " apocalyptic numbers 2^n" << endl;
    }
    

    output bei limit = 10000:
    below n = 10000 exist 6485 apocalyptic numbers 2^n

    output bei limit = 50000:
    below n = 50000 exist 46284 apocalyptic numbers 2^n

    Interessant ist, wie sich analoge Ziffernfolgen "000", "111", ... "999" in der Häufigkeit unterscheiden.

    Man kann diese Ziffernfolgen auch mit anderen Eigenschaften wie Primzahlen etc. verknüpfen (Fibonacci apocalypse number, apocalypse prime).


  • Mod

    Das ist mal eine Zahlenreihe, von der ich nie zuvor gehört habe. Du suchst weiterhin Optimierungen? Mir gefällt beim ersten Draufsehen nicht, wie du die Sequenz "666" suchst: Stringdurchsuchungsalgorithmen sind an sich zwar nicht schlecht, aber zum Erstellen des Strings machen wir ja bereits genau das, was wir hier als Ziel haben: Wir "durchsuchen" die Zahl nach den Ziffern 0 bis 9. Aber wir können ja genau so gut nach der Ziffernfolge "666" suchen und haben dabei ungefähr den gleichen Aufwand wie bei der Erstellung des String, aber ohne die anschließende Suchaktion:

    while (value)
        {
          if (value % 1000 == 666)
            std::cout << "Found it!";
          value /= 10;
        }
    

    Zu deiner power-Funktion (die du aber nirgends benutzt, oder?): Divide & Conquer? Damit würdest du dir etliche Multiplikationen sparen.



  • @SeppJ: Danke für den Hinweis bezügl. der möglicherweise beschleunigten Suchfunktion. Das werde ich mit Zeitmessung mal gegeneinander antreten lassen.

    Zum Thema pow:

    Ich habe mpz_ui_pow_ui gegen mein power2 antreten lassen. Die gemessenen Zeiten sind etwa gleich, sodass ich dies hier vorschlage: http://codepad.org/awmAdU9n

    @SeppJ: Dein String-Suchtest kommt auch noch dran:

    Variante 1:

    #include <iostream>
    #include <string>
    #include <chrono>
    #include <mpirxx.h>
    
    //#define SHOWNUMBERS
    
    using namespace std;
    
    mpz_class power(mpz_class number, mpz_class i)
    {
    	mpz_class result;
    	mpz_ui_pow_ui (result.get_mpz_t(), number.get_ui(), i.get_ui());
    	return result;
    }
    
    int main()
    {
    	mpz_class number;
    	uint64_t limit = 10000, count = 0;
    	auto start_time = chrono::high_resolution_clock::now();
    
    	for (uint64_t i = 0; i < limit; ++i)
    	{	
    		number = power(2,i); 
    
    		while (number>0)
    		{
    			if (number % 1000 == 666)
    			{
    				++count;
    				break;
    			}				
    			number /= 10;
    		}						
    	}
    	auto end_time = chrono::high_resolution_clock::now();
    	cout << "\nbelow n = " << limit << " exist " << count << " apocalyptic numbers 2^n" << endl;
    	cout << "time: " << chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() << " ms" << endl;
    }
    

    output: (Suchfunktion stimmt, wie man sieht)
    below n = 10000 exist 6485 apocalyptic numbers 2^n
    time: 16687 ms

    Variante 2:

    #include <iostream>
    #include <string>
    #include <chrono>
    #include <mpirxx.h>
    
    //#define SHOWNUMBERS
    
    using namespace std;
    
    mpz_class power(mpz_class number, mpz_class i)
    {
    	mpz_class result;
    	mpz_ui_pow_ui (result.get_mpz_t(), number.get_ui(), i.get_ui());
    	return result;
    }
    
    int main()
    {
    	mpz_class number;
    	uint64_t limit = 10000, count = 0;
    	auto start_time = chrono::high_resolution_clock::now();
    
    	for (uint64_t i = 0; i < limit; ++i)
    	{	
    		number = power(2,i); 
    
    		string str = number.get_str();
    		size_t pos = str.find("666"); // Revelation, 13,18
    		if (pos != string::npos)
    		{
    #ifdef SHOWNUMBERS           
    			cout << "exp = " << i << ",  pos = " << pos << endl;
    			cout << number << endl;
    #endif
    			++count;
    		}
    	}
    	auto end_time = chrono::high_resolution_clock::now();
    	cout << "\nbelow n = " << limit << " exist " << count << " apocalyptic numbers 2^n" << endl;
    	cout << "time: " << chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() << " ms" << endl;
    }
    

    output:
    below n = 10000 exist 6485 apocalyptic numbers 2^n
    time: 455 ms

    Die Methodik mit get_str() und str.find(...) ist schneller, wenn ich das richtig aufgesetzt habe.



  • Das liegt ziemlich sicher daran, das er String nicht so erzeugt wird, wie in SeppJs naiver Vorstellung. 😉 Trotzdem hat er grundsaetzlich recht, ein zwischenspeichern in einem String ist nicht noetig und allein early out darin spart wahrscheinlich schon 50% der Zeit. Hast du den Quellcode von get_str()? Daraus laesst sich mit minimalem Aufwand eine bessere Version bauen.



  • SeppJ schrieb:

    Das ist mal eine Zahlenreihe, von der ich nie zuvor gehört habe. Du suchst weiterhin Optimierungen? Mir gefällt beim ersten Draufsehen nicht, wie du die Sequenz "666" suchst: Stringdurchsuchungsalgorithmen sind an sich zwar nicht schlecht, aber zum Erstellen des Strings machen wir ja bereits genau das, was wir hier als Ziel haben: Wir "durchsuchen" die Zahl nach den Ziffern 0 bis 9. Aber wir können ja genau so gut nach der Ziffernfolge "666" suchen und haben dabei ungefähr den gleichen Aufwand wie bei der Erstellung des String, aber ohne die anschließende Suchaktion:

    while (value)
        {
          if (value % 1000 == 666)
            std::cout << "Found it!";
          value /= 10;
        }
    

    Zu deiner power-Funktion (die du aber nirgends benutzt, oder?): Divide & Conquer? Damit würdest du dir etliche Multiplikationen sparen.

    Nicht sicher.
    Wenn value ein BigInt mit n Ziffern ist, kostet jedes /=10 oder %1000 oder %10 ein O(n), und das sperrst Du in eine n-mal-Schleife.



  • String ist der informatische Weg. Der Mathematiker definiert sich eine eine Folge für die Deziamlziffern, die in dem Fall am besten noch rekursiv definiert ist.
    Am besten überlegst du dir mal, was bei der Umwandlung vom 2er Systen is 10er System so passiert und guckst, ob du was interessantes findest. Ich suche auch noch mal danach.

    Wie kommst du eigentlich zu apokalytischen Zahlen :D?



  • TGGC schrieb:

    Das liegt ziemlich sicher daran, das er String nicht so erzeugt wird, wie in SeppJs naiver Vorstellung. 😉 Trotzdem hat er grundsaetzlich recht, ein zwischenspeichern in einem String ist nicht noetig und allein early out darin spart wahrscheinlich schon 50% der Zeit. Hast du den Quellcode von get_str()? Daraus laesst sich mit minimalem Aufwand eine bessere Version bauen.

    Geh mal davon aus, daß immer neun Ziffern gleichzeitig behandelt werden und Du nicht einfach ein *out++=z hast, das Du abgreifen kannst.

    Ich nehme an, daß fast alle Zweierpotenzen apokalyptisch sind und die erste "666" jeweils ganz weit vorne und hinten zu finden ist. Deswegen würde ich machen:
    for(len=10;…;len++) if(mulmod(pow(2,n),pow(10,len) contains "666") return true;
    und davon ausgehen, daß im Bereich mit 4G Stellen überhaupt kein Test stattfinden muss mit len>10M.



  • Meiner ist schneller.

    #include <iostream>
    #include <cassert>
    #include <vector>
    #include <chrono>
    using namespace std;
    
    struct biggie {
      const uint64_t base = static_cast<uint64_t>(1000)*1000*1000*1000*1000*1000;
      const int base_digits = 18;
      vector<uint64_t> digits;
    
      biggie(int i) : digits(1, i) {}
    
      void times_two() {
        assert(!digits.empty());
        uint32_t carry = 0;
        for (auto& d : digits) {
          auto val = 2*d + carry;
          d = val%base;
          carry = val/base;
        }
        if (carry)
          digits.push_back(carry);
      }
      bool has_devil() {
        int current_sixes = 0;
        for (auto d : digits) {
          for (int i=0; i<base_digits; ++i) {
            if (d%10 != 6)
              current_sixes = 0;
            else if (++current_sixes == 3)
              return true;
            d /= 10;
          }
        }
        return false;
      }
    };
    
    int main()
    {
      uint64_t limit = 10000, count = 0;
      auto start_time = chrono::high_resolution_clock::now();
    
      biggie number(1);  
      for (uint64_t i = 0; i < limit; ++i, number.times_two())
        if (number.has_devil()) 
          ++count;
      auto end_time = chrono::high_resolution_clock::now();
      cout << "\nbelow n = " << limit << " exist " << count << " apocalyptic numbers 2^n" << endl;
      cout << "time: " << chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() << " ms" << endl;
    }
    


  • Hast du den Quellcode von get_str()?

    s.u.

    zu beachten: http://www.gnu.org/licenses/lgpl-3.0.de.html



  • Was sind jetzt nochmal apokalyptische potenzen? einfach eine zahl die irgendwo "666" enthält? Oder bestehen die nur aus 6en oder wie kann man sich das vorstellen?


  • Mod

    Verwirrter schrieb:

    Was sind jetzt nochmal apokalyptische potenzen? einfach eine zahl die irgendwo "666" enthält? Oder bestehen die nur aus 6en oder wie kann man sich das vorstellen?

    Wie wäre es, den ersten Satz im ersten Beitrag zu lesen?





  • Erhard Henkes schrieb:

    http://mathworld.wolfram.com/ApocalypseNumber.html
    http://googology.wikia.com/wiki/Apocalyptic_number
    http://www.numbersaplenty.com/set/apocalyptic_number/

    Dir ist schon klar, dass er erste Link eine andere Definition liefert, als die beiden anderen?



  • Oh danke! Habe ich echt falsch gelesen. Muss natürlich weg.



  • Erhard Henkes schrieb:

    Hast du den Quellcode von get_str()?

    std::string get_str(int base = 10) const
    {
        __gmp_alloc_cstring temp(mpz_get_str(0, base, mp));
        return std::string(temp.str);
    }
    
    #define mpz_get_str __gmpz_get_str
    __GMP_DECLSPEC char *mpz_get_str __GMP_PROTO ((char *, int, mpz_srcptr));
    

    Haha, sehr witzig...



  • na gut, hier ist der code aus get_str.c (MPIR 2.7.0):
    http://pastebin.com/N3VQuvye

    Copyright 2008 William Hart, Gonzalo Tornaria
    This file is part of the MPIR Library.
    The MPIR Library is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation; either version 3 of the License, or (at your
    option) any later version.

    http://www.gnu.org/licenses/lgpl-3.0.de.html



  • Ok, dann jetzt mpn_get_str...



  • http://pastebin.com/CvT2RfDA

    Copyright 2008 William Hart, Gonzalo Tornaria
    This file is part of the MPIR Library.
    The MPIR Library is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation; either version 3 of the License, or (at your
    option) any later version.

    http://www.gnu.org/licenses/lgpl-3.0.de.html


Log in to reply