4. BigInt = sqrt( BigInt );

BigInt = sqrt( BigInt );

  • R

    Hallo, Ihr, die Ihr rechnen könnt.

    Ich hab mir einen exotischen Datentyp gebaut. Es ist ein Fixpoint-Format der größeren Art. 2*unsigned long für Vorkommastellen und 8*unsigned long für Nachkommastellen + 1 Byte für Sign.

    Bisher kann ich +,-,*, und Div durch 32Bits signed. ( BigInt / BigInt fehlt noch ).

    Nun könnte ich dafür eine SQRT Funktion brauchen. wie geht sowas 😕

    könnt Ihr einem Programmierer sowas erklären?

    mfG
    RudiS

    0
  • K

    Hilft dir das Stichwort Iterationsverfahren?

    0
  • V

    http://www.cc.utah.edu/~nahaj/factoring/isqrt.c.html

    0
  • R

    Hallo Korbinian,

    schöne Grüße nach Erlangen, woarst a scho afn Berch ?
    I woar a erst amol do, weil Nerberch is ja net so noa. Jeztala wohn i in Würzburg, des is nu weida.
    Hast Du das Verstanden, wenn Du doch nach Berlin tendierst? ( ...Berlin is a Dorf, ich brauchte noch nicht mal einen Stadtplan!)

    Korbinian schrieb:

    Hilft dir das Stichwort Iterationsverfahren?

    siehst Du, Iterationen verwende ich nur für mein Projekt, das sich mit der Mandelbrotmenge befasst. Dabei gehe ich das Thema nicht mit Mathe an, sondern als Bobachter. Ich sehe was die Formel macht, und versuche dies zu visulalsieren. Sechs Visulalisierung habe ich schon programmiert, aber um weiterzukommen brauch ich halt noch SQRT und auch DIV.

    Dazu brauch ich nicht nur einen Hinweis, sondern schon den ganzen Algorythmus.
    Wenns Dich interssiert kann Du dann auch eine Version meines DeepChaos haben.

    gilt der Deal?

    Gruß nach Erlangen
    rudiS

    0
  • R

    Hallo Volkard,

    volkard schrieb:

    http://www.cc.utah.edu/~nahaj/factoring/isqrt.c.html

    schaut einfach aus, ich werds mal durchprobieren.
    Kann aber dauern.... ich geb dann nochmal feedback.

    MfG
    rudiS

    0
  • K

    Jau auf m Berch war ich natürlich, und nicht nur 1x dieses Jahr 😉
    mit Iterationsverfahren meinte ich z.B. Newtoniteration für Wurzel was gleich der Treffer nummer 1 bei Google mit "Wurzel Iterationsverfahren" ist 😉

    0
  • R

    Hallo Volkard,

    Dein Tipp war Gold wert. nachdem ich mich ein halbes Jahr davor gefürchtet habe, ist es mir mit Deinem Tipp sogar innerhab von 2 Tagen gelungen meine BigInt::SQRT() zu programmieren. Nachdem Dein Tipp aber nur Ganzzahlen verarbeit, ahnte ich schon, daß es mit den Nachkommastellen nicht so klappt. Ich mußte ganz schön tüfteln, aber nun ist es geschafft. SQRT() ist nun in jeder beliebigen Präzision verfügbar. Die Rundungfehler die auf den letzten 3..5 Stellen entstehen, sind leider nicht zu vermeiden, wers braucht muß halt ein Wort mehr spendieren.

    Danke, und dafür hier der Code:

    [cpp]
void bigint::sqrt()
{
/*
#define	ANZDIGITS		6
#define KOMMADIGITS		5

private:
		unsigned	ea[ANZDIGITS];						// Ergebins-Zahlenarray
		short		sign,error,Laenge,Kommastellen;
*/
long	squaredbit,sbindex,resultbit,rbindex;
bigint	result(0);
bigint	rest;
bigint	x;
bigint	sr;

if ( sign == -1 )
	{
    error = biERRORsign;
    return;
    }

x = *this;
squaredbit = 0x040000000;
sbindex = 0;
while ( sbindex < ( ANZDIGITS - KOMMADIGITS ))	// Durchlauf für Vorkommastellen--------
	{
    sr = result;								// sr = ( squaredbit | result );
    sr.ea[sbindex] |= squaredbit;
   	if ( x >= sr )
		{
   	    x -= sr;
	    result.div2();							// 1 Bit >> schieben !!!
		result.ea[sbindex] |= squaredbit; 
		}
    else
	    result.div2();						  	// 1 Bit >> schieben !!!
    if ( squaredbit == 1 )
    	{
		squaredbit = 0x040000000;
		sbindex += 1;
        }
    else
		squaredbit >>= 2; 					   	// 2 Bits >> schieben !!!
    }
resultbit = 0x080000000;
rbindex = sbindex;
while ( sbindex < ANZDIGITS )         			// Durchlauf Nachkommastellen ----------
	{
    sr = result;
    sr.ea[sbindex] |= squaredbit;
   	if ( x >= sr )
		{
   	    x -= sr;
		result.ea[rbindex] |= resultbit;
        if ( x.is0())
        	break;
		}
    x.mal2();
    if ( squaredbit == 1 )
    	{
		squaredbit = 0x080000000;
		sbindex += 1;
        }
    else
    	{
		squaredbit >>= 1;
        squaredbit &= 0x07FFFFFFF;
        }
    if ( resultbit == 1 )
      	{
		resultbit = 0x080000000;
		rbindex += 1;
        }
    else
    	{
        resultbit >>= 1;
		resultbit &= 0x07FFFFFFF;
        }
   	}
*this = result;
}
[/cpp]

    //-----------------------------------------------------------------

    mfG
    rudiS

    0
  • W

    rudiS: Wenn du aus bigint ein Template machst kannst du dir die defines sparen 😉 .

    0
Anmelden zum Antworten