3. Container verschnellern....

Container verschnellern....

  • C
    Mod

    volkard schrieb:

    Hast aber geschummelt. Sein log2 packt mehr.
    http://ideone.com/Zxt5at

    ideone schrieb:

    Time limit exceeded

    0
  • V

    camper schrieb:

    volkard schrieb:

    Hast aber geschummelt. Sein log2 packt mehr.
    http://ideone.com/Zxt5at

    ideone schrieb:

    Time limit exceeded

    Ja, weil er in den ersten paar Sekunden keinen Fehler findet und nicht in der Zeit selber terminiert.
    Upps, der 0-Fehler ist ja noch drin. Moment.

    Auch mit
    if(n<100) return sqrt(double(n));
    time exceeded. muss man wohl lokal testen.

    ok, alles repariert. trotzdem fehler bei 557580^2-1

    Mit if( std::abs(x - old_x) < 0.5 ) kommt er bis um 6000000^2, aber hübsch ist anders.

    0
  • C
    Mod

    Die Genauigkeit des Startwertes sollte ohnehin irrelevant sein.
    x=1 ist genauso gut oder schlecht (nur ein bisschen langsamer).

    0

  • Bei euch geht es um die ganzzahlige Wurzel, oder?

    Diesen Code hatte ich mal vor ca. 10 Jahren geschrieben:

    template <class T> T sqrt(T x)
{
	if(x <= 1) return x;

	const T X = 1 << (std::numeric_limits<T>::digits >> 1);
	const T X1 = 1 << (std::numeric_limits<T>::digits >> 2);
	T x1 = (x < X)? 1 : X1;
	T x2 = (x < X)? X1 : X;
	T n;

	while(n = (x1 + x2)/2, x2 > x1 + 1)
	{
		if(n * n > x)
			x2 = n;
		else
			x1 = n;
	}

	return n;
}

    Kommt ohne Umwandlung nach double aus. Was haltet ihr davon?

    0
  • V

    Th69 schrieb:

    Bei euch geht es um die ganzzahlige Wurzel, oder?

    Diesen Code hatte ich mal vor ca. 10 Jahren geschrieben:

    template <class T> T sqrt(T x)
{
	if(x <= 1) return x;

	const T X = 1 << (std::numeric_limits<T>::digits >> 1);
	const T X1 = 1 << (std::numeric_limits<T>::digits >> 2);
	T x1 = (x < X)? 1 : X1;
	T x2 = (x < X)? X1 : X;
	T n;

	while(n = (x1 + x2)/2, x2 > x1 + 1)
	{
		if(n * n > x)
			x2 = n;
		else
			x1 = n;
	}

	return n;
}

    Kommt ohne Umwandlung nach double aus. Was haltet ihr davon?

    Kleine Reparatur war nötig.

    const T X = T(1) << (std::numeric_limits<T>::digits >> 1);
    const T X1 = T(1) << (std::numeric_limits<T>::digits >> 2);

    Ich lasse meinen Tester laufen…
    Ist korrekt bis obenhin.
    Ist 6-mal langsamer als meine Implementierung.

    0
  • Mod

    Ist 6-mal langsamer als meine Implementierung.

    Was ist denn deine Implementierung? Oder ist die streng geheim?

    Mit if( std::abs(x - old_x) < 0.5 ) kommt er bis um 6000000^2, aber hübsch ist anders.

    (Vor allem, weil das den Prozess verlangsamt)

    Aber Moment. Die Variante, die ich implementiert habe, konvergiert laut Wikipedia quadratisch - und die Bedingung ist immer richtig. Das Problem ist eher, dass double nicht gut genug ist.

    Schaue ich mir morgen früh genau an.

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

    0
  • V

    Arcoth schrieb:

    Ist 6-mal langsamer als meine Implementierung.

    Was ist denn deine Implementierung? Oder ist die streng geheim?

    'Türlich ist sie nicht geheim. Und sie ist bestimmt auch noch suboptimal. Ich wollte sie nur genau Dir nicht gleich verraten, damit Du Dich ein wenig mehr in Algos/Mathe reinstupst. Ich geifere nach den Verbesserungen, die Ihr klar sehen werdet, wo ich betriebsblind bin.
    6-mal ist natürlich kein Maß. 6-mal bei campers Test über den geamten Zahlenbereich.

    0
  • 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
Anmelden zum Antworten