Apokalyptische Potenzen finden/darstellen



  • 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


Anmelden zum Antworten