RossiBigInt



  • Hallo an alle,

    ich bin neu hier.

    Ich habe ein Probelm mit der BigInt Klasse von https://sourceforge.net/projects/cpp-bigint/.

    Ich möchte den Binomialkoeffizienten von großen Zahlen bestimmen.
    Bei meiner Funktion tritt allerdings bei einigen Parametern ein Fehler auf:

    Vector subscript out of range.

    Kann mir jemand helfen, oder hat eine Idee woran es liegen könnte?

    Habe zwei Versionen der BinomialkoeffizientenFunktion:

    Version 1:

    RossiBigInt Binkof ( unsigned long b1, unsigned long b2)
    	{
    	RossiBigInt p1(0), p2(0) ,p3(0), p4(0), erg(0);
    	unsigned int b3;
    	p1=Faku(b1);	cout<<"\nn!= "<<p1;
    	p2=Faku(b2);	cout<<"\nk!= "<<p2;
    	b3=b1-b2;
    	p3=Faku(b3);
    	p4=p2*p3;	cout<<"\nk!*(n-k)!= "<<p4;
    	erg = p1 / p4;	cout<<"\nerg= "<<erg;
    	return p1;
    	}
    
    RossiBigInt Binkof ( unsigned long b1, unsigned long b2)
    	{
    	unsigned long b3, b4;
    	RossiBigInt p1(1), p2(0), erg (0);
    
    	b3= b1-b2;
    	if (b3<b2){b4=b2;} else{b4=b3;b3=b2;}	        cout <<"\tb4= "<<b4<<" b3= "<<b3;
    	for (unsigned long x=b4+1;x<b1+1;x++){		cout <<"\nx= "<<x;
    		p1=p1 * x;
    		}	cout<<"\np1= "<<p1;
    	p2=Faku(b3);	cout<<"\np2= "<<p2;
    	erg=p1 /p2;	cout<<"\nerg= "<<erg;
    	 return erg;
    	}
    

    Die Faku Funktion:

    RossiBigInt Faku(unsigned long f)
    	{
    	RossiBigInt erg(1);
    	RossiBigInt t(0);
    	for (int x=0;x<f;x++){
    		t++;
    		erg=erg*t; 
    		}
    	return erg;
    	}
    

    Ich habe WinXP prof und benutze VS2005 prof

    Hat jemand eine Idee. Wäre echt super wenn mir jemand einen Tipp geben kann.

    Dankeschön schon mal im Vorraus



  • Dieses RossiBigInt hat einen Bug beim Subtrahieren. Und das Subtrahieren wird beim Dividieren aufgerufen. Dieser Fehler tritt bereits bei dem mitgelieferten Testtool auf.... komisch, dass das der Autor nicht bemerkt hat.

    Aber vielleicht hilft Dir dieser Thread weiter, dort findest Du eine Berechnung, die im Allgemeinen mit ints auskommt.

    Gruß
    Werner



  • Danke für die Antwort.

    Ich habe dem Autor auch von dem Problem geschrieben. Er hat mir geantwortet, dass meine Funktion bei ihm unter GNU go++ 4.0.1 mit windows 2000 funktioniert. Er vermutet das es ein Problem vom Compiler ist. Er schlägt mir vor den Stack Größe zu erhöhen.

    Die in dem anderen Thread vorgeschlagene Version mit kleineren Zahlen habe ich auch umgesetzt. Da tritt das Problem teilweise bei anderen Zahlen auf.

    Ich werde mir die dort Vorgeschlagene GMP Bibliothek anschauen. Doch kann man die Stack größe vergrößern, wenn ja wie?

    Gruß
    amsel



  • amsel schrieb:

    Ich habe dem Autor auch von dem Problem geschrieben. Er hat mir geantwortet, dass meine Funktion bei ihm unter GNU go++ 4.0.1 mit windows 2000 funktioniert. Er vermutet das es ein Problem vom Compiler ist.

    Ja - der Unterschied besteht darin, dass die Implementierung der GNU-STL wohl nicht merkt, dass der vector überläuft. Er schreibt außerhalb des allokierten Speichers. Solange da keine relevanten Daten stehen, fällt es natürlich nicht auf.

    Folgendes triviale Programm generiert den Fehler:

    #include <limits>
    #include "bigint.h"
    
    int main()
    {
        using namespace std;
        RossiBigInt a(1);
        RossiBigInt b( numeric_limits< unsigned long >::max() );
        b = b * b;  // RossiBigInt kennt kein operator*= !?
        b -= a;  // hier wird in nicht allokierten Speicher hineingeschrieben!
        return 0;
    }
    

    Das mit dem 'Stack vergrößern' ist dementsprechend Quatsch.

    Gruß
    Werner


Log in to reply