Apokalyptische Potenzen finden/darstellen
-
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; }
-
-
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?
-
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?
-
http://googology.wikia.com/wiki/Apocalyptic_number
http://www.numbersaplenty.com/set/apocalyptic_number/
-
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/N3VQuvyeCopyright 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.
-
Ok, dann jetzt mpn_get_str...
-
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.