3. Container verschnellern....

Container verschnellern....

  • V

    Arcoth schrieb:

    Und kann das mal jemand splitten? Oder gehört das hier rein?

    Den Thread haben wir erfolgreich entführt. Ist auch kein Problem, der TO ist hier nicht mehr. Allenfalls könnte eine Mod den Threadtitel ändern.

    0
  • Mod 

    #include <iostream>
#include <cmath>

using uint64 = std::uint64_t;

// Zu viel Generizität? Bin mir nicht sicher, du predigst einen mMn. ungesunden Minimalismus.
template<typename T>
T intlog2(T x)
{
	asm ( "bsr %1, %0"
		: "=r"(x)
		: "r" (x) );

	return x;
}

/// Böse geklaut (aber lieb modifiziert)
// von http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
uint64 isqrt(uint64 num)
{
	uint64 bit = 1ull << (intlog2(num) ^ 1);

	uint64 res = 0;
	while( bit )
	{
		if( num >= res + bit )
		{
			num -= res + bit;
			res = (res >> 1) + bit;
		}
		else
			res >>= 1;

		bit >>= 2;
	}
	return res;
}

int main()
{
	std::cout << isqrt(3891049815758399);
}

    Leider verstehe ich das Verfahren an sich noch nicht, das muss ich gleich noch bei Wikipedia genau nachlesen. (Schriftliches Wurzelziehen, auau).

    Allenfalls könnte eine Mod den Threadtitel ändern.

    Hätten wir bloß einen... aber die sind ja bekanntlich nie da wenn man sie braucht 🤡

    0
  • K

    Ich hoffe, so steht es nicht wirklich in deinem Code. Da ist nämlich UB drin, solange int 32-Bit groß ist.

    Dieser "Fehler" ist leicht zu beheben.

    0
  • V

    Arcoth schrieb:

    // Zu viel Generizität? Bin mir nicht sicher, du predigst einen mMn. ungesunden Minimalismus.
template<typename T>
T intlog2(T x)
{
    asm ( "bsr %1, %0"
        : "=r"(x)
        : "r" (x) );

    return x;
}

    Den Minimalismus könnte man auch Feigheit nennen.
    Warum Fehler riskieren? Du tust hier für 2 Funktionen intlog2(uint32) und intlog2(uint64) das Templatefaß aufmachen. Danach überlegste, ob es überhaupt schlau ist, x wiederzuverwenden und machst es evtl bei intlog2(uint32) aber bei intlog2(uint64) nicht.
    Naja, kannst hier ruhig mal die Sache generisch machen, der Code ist ja erstmal völlig gleich. Und es kann ja zu gar keinem Fehler kommen. Richtig?

    Nicht ganz.

    double x=16;
	cout<<intlog2(x)<<'\n';//ausgabe 3.06321e-322//kacke

	complex<int> x=16;
	cout<<intlog2(x)<<'\n';//ausgabe 4//ok

	complex<int> x(0,16);
	cout<<intlog2(x)<<'\n';//ausgabe 36//im ernst jetzt?

	char x='a';
	cout<<intlog2(x)<<'\n';//compilerfehler operand type mismatch
//aha, wird die ausgabe sein, für kleinere typen brqauchts 
//anderen code ohne x wiederzuverwenden. 

	char const* x="evil";
	cout<<intlog2(x)<<'\n';//absturz

    Das war generischer Unfug. 🤡 🤡 🤡

    0
  • Mod

    Teste doch wenigstens mal rudimentär bevor Du sowas postest. Ist voll ärgerlich, daß ich Deinen Code nie messen kann, weil er falsch ist.

    Wat!?

    Stimmt, die Funktion gibt teilweise Blödsinnige Werte (von 18 - 31 ist die "Wurzel" 6). Entweder habe ich den Algo ruiniert, oder die Implementierung ist einfach falsch. In letzterem Fall darf ich mich wohl nicht auf Wikipedias Coder verlassen.
    Versuche ich mal zu fixen.

    Edit: Nein, ich bin Schuld.

    0
  • Mod

    Ja, der Fehler ist schnell gefunden, und peinlich. Ich habe natürlich das bescheuerte Bit-Spielchen mit dem XOR falsch gemacht. So ist die Zeile zu korrigieren:

    uint64 bit = 1ull << (intlog2(num) & ~1);

    Das heißt eigentlich log- log%2 , also das letzte Bit muss auf 0 gesetzt werden, es wird auf 2 runter-gerundet. Habe wohl mal wieder schlecht geschlafen.

    Edit: Bezeichner korrigiert.

    0
  • K
     

    template<typename T> 
 T intlog2(T x) 
{ 
     asm ( "bsr %1, %0" 
         : "=r"(x) 
         : "r" (x) ); 

     return x; 
}

    Aus dem Bauch heraus: Templates und Assembler nie mischen. Templates sind fuer Metaprogrammierung durch Typen. Assembler kennt keine Typen. C++ kennt keinen Assembler. Der obige Code laeuft nur mit 'nem Integer der in ein Register passt. Warum also Template?

    0
  • V

    Manchmal verwende ich Templates, um die automatischen Casts loszuwerden.
    Wer intlog2 mit was anderem als einem unsigned auruft, denkt, die Funktion würde was anderes machen, als sie macht. Daher

    template<typename T>
int intlog2(T)=delete;

template<>
int intlog2<uint32>(uint32 x)
{
	uint32 r;
    asm ( "bsrl %1, %0"
        : "=r"(r)
        : "r" (x) );
    return r;
}

template<>
int intlog2<uint64>(uint64 x)
{
	uint64 r;
    asm ( "bsrq %1, %0"
        : "=r"(r)
        : "r" (x) );
    return r;
}
    0
  • V

    Arcoth schrieb:

    Ja, der Fehler ist schnell gefunden, und peinlich. Ich habe natürlich das bescheuerte Bit-Spielchen mit dem XOR falsch gemacht. So ist die Zeile zu korrigieren:

    uint64 bit = 1ull << (intlog2(num) & ~1);

    Das heißt eigentlich log- log%2 , also das letzte Bit muss auf 0 gesetzt werden, es wird auf 2 runter-gerundet. Habe wohl mal wieder schlecht geschlafen.

    Edit: Bezeichner korrigiert.

    Damit klappt Dein Code.
    886 Sekunden.
    Th69 hatte 1000.
    Ich habe 240.
    Soll ich ihn zeigen oder willste noch ein wenig basteln?

    0
  • V

    Newton ganzzahlig. 860s.

    UInt64 sqrt(UInt64 x){
	if(x==0) return 0;
	UInt64 sn=x>>(intlog2(x)/2);
	UInt64 so;
	do{
		so=sn;
		sn=(so+x/so)/2;
	}while(sn<so);
	if(sn*sn>x) --sn;
	return sn;
}
    0
  • K

    Nur so als Zwischenfrage da ich auch mal ueber optimales isqrt bei Primzahlsieb nachgedacht habe: Wie gross ist der Anteil von isqrt im Vergleich zum Rest des Problems?

    0
  • V

    knivil schrieb:

    Nur so als Zwischenfrage da ich auch mal ueber optimales isqrt bei Primzahlsieb nachgedacht habe: Wie gross ist der Anteil von isqrt im Vergleich zum Rest des Problems?

    Allerhöchstens bei häufigen Aufrufen mit sehr kleinen Primzahlkandidaten messbar, würde ich sagen. Aber da schlägt eh if(n ist klein) return sqrt(double(n)) zu. Man braucht halt ein isqrt, was bis 2^64 genau ist.

    0
  • K

    Mein Problem ist der Ganzzahl-Newton. Wie du ihn formuliert hast, funktioniert er fuer alles bis 2^32 (grad getestet). Leider weiss ich nicht, wie ich ihn fuer 2^64 verifizieren kann. Ansonsten: Sehr nice!

    0
  • V

    knivil schrieb:

    Mein Problem ist der Ganzzahl-Newton. Wie du ihn formuliert hast, funktioniert er fuer alles bis 2^32 (grad getestet). Leider weiss ich nicht, wie ich ihn fuer 2^64 verifizieren kann. Ansonsten: Sehr nice!

    Eigentlich teste ich mit campers Code.
    Bis 2^64 lief er bei mir durch.

    0
  • C
    Mod

    volkard schrieb:

    Newton ganzzahlig. 860s.

    UInt64 sqrt(UInt64 x){
	if(x==0) return 0;
	UInt64 sn=x>>(intlog2(x)/2);
	UInt64 so;
	do{
		so=sn;
		sn=(so+x/so)/2;
	}while(sn<so);
	if(sn*sn>x) --sn;
	return sn;
}

    wie sieht es aus, wenn du

    UInt64 sn=sqrt((double)x);

    verwendest?

    0
  • V

    camper schrieb:

    wie sieht es aus, wenn du

    UInt64 sn=sqrt((double)x);

    verwendest?

    Viel viel viel besser.

    Geht runter auf 320s oder so. Und ermöglicht die Folgenden Verbesserungen:

    Nach dem guten double-Schätzwert braucht man nie mehr als eine Newton-Runde.

    UInt64 sqrt(UInt64 x){//240s
	UInt64 s=std::sqrt(double(x));
	if(x>=4503599761588224ull)//2^52+2^27
		s=(s+x/s)/2;
	return s;
}

    Nichtmal das! Die Wurzel passt ja noch fein in den double.

    UInt64 sqrt(UInt64 x){//103s-107s
	if(x==0) return 0;
	UInt64 s=sqrt(double(x));
	if(x<4503599761588224ull)//2^52+2^27
		return s;
	if(s*s>x)
		--s;
	return s;
}

    UInt64 sqrt(UInt64 x){//evtl ein halbes Sekundchen langsamer, zu ungenaue Messungen
	UInt64 s=sqrt(double(x));
	if(s*s>x)
		--s;
	return s;
}

    Das werde ich produktiv einsetzen, denn wenn ich sqrt(UInt64) anwerfen, dann schleiche ich eh bei großen Zahlen rum, wo der Nachtest gebraucht wird.
    Hübsch, wenn die Jagd nach Geschwindigkeit zu einfachem Code führt. 🙂

    0
  • K

    Bis 2^64 lief er bei mir durch.

    Whooot? Achso, es lauft auch nur bis 2^32.

    Mein Testprogramm braucht 1 Minute 29 Sekunden:

    uint64_t isqrt(uint64_t x)
{
    if(x==0) return 0;
    uint64_t sn=x>>(intlog2(x)/2);
    uint64_t so;
    do{
        so=sn;
        sn=(so+x/so)/2;
    }while(sn<so);
    if(sn*sn>x) --sn;
    return sn;
}

int main()
{
    std::cerr << isqrt(1) << '\n';
    std::cerr << isqrt(2) << '\n';
    std::cerr << isqrt(3) << '\n';
    std::cerr << isqrt(4) << '\n';
    std::cerr << isqrt(5) << '\n';

    for(auto i = 6u; i < (1u<<31); ++i)
        if(isqrt(i) != (uint64_t)std::sqrt(i))
        //if((uint64_t)std::sqrt(i) != (uint64_t)std::sqrt(i))
            std::cerr << i << '\n';
}
    0
  • V

    knivil schrieb:

    Bis 2^64 lief er bei mir durch.

    Whooot? Achso, es lauft auch nur bis 2^32.

    Mein Testprogramm braucht 1 Minute 29 Sekunden:

    uint64_t isqrt(uint64_t x)
{
    if(x==0) return 0;
    uint64_t sn=x>>(intlog2(x)/2);
    uint64_t so;
    do{
        so=sn;
        sn=(so+x/so)/2;
    }while(sn<so);
    if(sn*sn>x) --sn;
    return sn;
}

int main()
{
    std::cerr << isqrt(1) << '\n';
    std::cerr << isqrt(2) << '\n';
    std::cerr << isqrt(3) << '\n';
    std::cerr << isqrt(4) << '\n';
    std::cerr << isqrt(5) << '\n';

    for(auto i = 6u; i < (1u<<31); ++i)
        if(isqrt(i) != (uint64_t)std::sqrt(i))
        //if((uint64_t)std::sqrt(i) != (uint64_t)std::sqrt(i))
            std::cerr << i << '\n';
}

    campers Programm von 22 Okt 2013 17:36

    0
  • K

    Aha, ich sehe. Ich bin noch nicht ganz ueberzeugt, dass es ausreicht, nur vor und nach der Quadratzahl zu testen. Es spricht aber nix dagegen. Gut finde ich, dass isqrt auf std::sqrt reduziert wurde.

    0
  • Mod

    Soll ich ihn zeigen oder willste noch ein wenig basteln?

    Letzteres.

    Ich weiß genau, wie deines so schnell ist: Lookup-Tables.

    Gut finde ich, dass isqrt auf std::sqrt reduziert wurde.

    Das finde ich hingegen ein Verbrechen. sqrt berechnet viel genauer als nötig. Wenn std::sqrt schnell ist, dann kann isqrt mit einem ähnlichen Verfahren viel schneller sein. Und das verschenkt man.

    0
Anmelden zum Antworten