C++ Mit sehr großen Werten rechnen

[s0nny]

Hallo,
ich habe folgendes Problem. Ich "spiele" gerade auf enigmagroup.org die JavaScript Missionen und bin inzwischen bei der letzten angekommen.
Das Passwort berechnet sich dabei aus dem aktuellen Jahr, man kommt also nur weiter wenn man sich zufällig gerade in diesem Jahr befindet oder das gesuchte Jahr herausfindet und es der URL anhängt. Hier der Code (JavaScript):

date = new Date();
year = date.getYear();
pass = 1337;
 
for(i = 1; i <= year; i++){
  pass += year * i * year;
}
       
if(pass == 318338237039211050000){
  alert("Good job!");
  window.location.href = year + ".php";
}
else{
  alert("Sorry, did you fail already?!");
  window.location.href = "./index.php";
}

Ich habe nun versucht mit diesem Code eine Lösung in C++ zu schreiben und bin daran gescheitert.
Ich habe einfach die Jahre hochgezählt und immer pass berechnet und dann mit der langen Zahl (wie in der Routine) verglichen.
Das Problem ist jedoch (und das ist mir erst ziemlich spät eingefallen), dass die Zahl für jeden Datentyp zu groß ist :-(

Ich dachte mir dann, ich könnte die Zahl einfach durch z.B. 1.000.000 dividieren und die restlichen Zahlen als Nachkommestellen mitführen.
Allerdings kommt dabei folgendes raus:

double test=31833823703921106.0000;
printf ("%f", test);

Ausgabe:

31833823703921104.000000

Wie wird denn aus der ...6,0... eine ...4,0... ?
Hat irgendjmd eine Idee wie ich mein Problem lösen könnte?

Grüße

 

[tnoay]

einen string daraus machen`?

 

[Valeria]

Aufgrund von Rundungsfehlern beim Rechnen mit Gleitkommazahlen (double, float) kommt sowas zu Stande.
Ich weiß nicht ob C++ aber es gibt in Java z.b. BigInteger, der unendlich große Zahlen speichern kann, jedoch im Umgang komplexer ist.
BigInteger ist ein Objekt und kein primitiver Datentyp.

Du könntest auch versuchen den Summierungsalgorithmus umzuschreiben, sodass weniger Rundungsfehler zustande kommen. Dafür müsstest du dich aber mehr einlesen.
Alternativ könntest du statt == ein epsilon wählen um die Rundungen zu kompensieren, also
if(pass >= 318338237039211050000 - 5 && pass <= 318338237039211050000 + 5)
Da wäre epsilon 5. Kommt natürlich darauf an, wie genau du diesen Wert haben willst.

@Tnoay: string geht nicht weil man ja damit rechnen will. pass += year * i * year;

 

[ascer]

Ich muss nun leider dazu sagen, dass ich in der C++-Welt nicht zu Hause bin, ich entwickle ausschließlich in Java/Python oder bastle Webapplikationen...aber nichtsdestoweniger: gibt es kein einziges Framework in C++, beispielsweise für mathematische Berechnungen, dass mit mehr als nur einem long rechnen kann?

Wäre doch recht komisch, geht doch in anderen Sprachen auch

 

[antred]

https://gmplib.org/

 

[Konika]

Das Passwort berechnet sich dabei aus dem aktuellen Jahr, man kommt also nur weiter wenn man sich zufällig gerade in diesem Jahr befindet oder das gesuchte Jahr herausfindet

was meinst du damit genau, bist du sicher das man pass so berechenet wie du es aufgeschrieben hast und die klammer } welche die for-schleife zu macht muss noch unter der else anweisung, sonst lässt du i ja hochlaufen bis year und berechenst im Schleifenrumpf pass, aber machst nichts damit.

string geht nicht weil man ja damit rechnen will. pass += year * i * year;

in C++ kann man doch auch mit Strings rechnen wenn ich mich jetzt nicht total irre, weiß nicht wie das in anderen Sprachen ist aber in C++ mein ich ,ist das möglich.

 

[Kanibal]

gmplib ist da der Platzhirsch, wenns etwas kompakter sein soll: http://www.ttmath.org/

 

[TotalEclipse]

Wenn Octave bei solchen Zahlen richtig rechnet, ist das gesuchte Jahr die Zahl 158848.

 

[s0nny]

Hallo,
vielen Dank für die Antworten! Also das Ergebnis wird 158847.php sein, hab ich mir sagen lassen...Wenn man damit genau rechnet kommt man wohl nicht genau auf die gesuchte Zahl, allerdings scheint der JavaScript Code genauso ungenau zu rechnen weshalb das ganze dann funktioniert. Macht also vermutlich wenig Sinn sich damit noch weiter auseinander zu setzen. Trotzdem gut mal einen Einblick darin gekriegt zu haben, dadurch hab ich trotzdem wieder was gelernt!

was meinst du damit genau, bist du sicher das man pass so berechenet wie du es aufgeschrieben hast und die klammer } welche die for-schleife zu macht muss noch unter der else anweisung, sonst lässt du i ja hochlaufen bis year und berechenst im Schleifenrumpf pass, aber machst nichts damit.


in C++ kann man doch auch mit Strings rechnen wenn ich mich jetzt nicht total irre, weiß nicht wie das in anderen Sprachen ist aber in C++ mein ich ,ist das möglich.

Hast recht, allerdings ist das ja nur der JavaScript Code von der Website.
Mein C++ Code sah so aus:

while(pass!=318338237039211050000){
  year++;
  pass=1337;	
	
  for(i=1;i<=year;i++){
    pass+=year*i*year;

    if(pass==318338237039211050000){
      cout<<year;
      cout<<system("pause");
    }
  }
}

 

[antred]

Er hat nur teilweise Recht, denn mit Strings rechnen kann man in C++ nicht. Soll heißen

#include <string>
#include <iostream>

int main()
{
    const std::string result = std::string( "34.5" ) + std::string( "15.5" );

    std::cout << "Result = " << result  << std::endl;
}

wird ganz sicher nicht 50.0 ergeben.

 

[Konika]

Er hat nur teilweise Recht, denn mit Strings rechnen kann man in C++ nicht. Soll heißen

Code:
#include <string>
#include <iostream>

int main()
{
const std::string result = std::string( "34.5" ) + std::string( "15.5" );

std::cout << "Result = " << result << std::endl;
}
wird ganz sicher nicht 50.0 ergeben.

So hab ich das auch nicht gemeint ist klar das man nicht zahlen in strings speichern kann die dann einfach addieren und das dann die zahlen sich automatisch addieren. Dachte das war klar, mir ging es nur um die aussage ansich das man strings nicht addieren kann.
Aber trotzdem gut das du das nochmal angemerkt hast.

Grüße

 

[Hancock]

C++ kann mit diese Werten rechnen, halt wie JavaScript mit doubles (IEEE 754). Einfach ein ".0" an das Ende hinpappen.
Wenn man dann mit Epsilon rechnet, kommt man mit der geometrischen Summe sehr schnell auf das gewünschte Ergebnis.
Das Ergebnis weicht von der Javascriptvariante u.A. aufgrund der 96-Bit FPU ab. Da müsste man jetzt bei jedem Rechenschritt eine Konvertierung nach Double erzwingen (und dann sind die mathematischen Kniffe auch nicht mehr gültig)...

#include <iostream>

int main(){
	for(double year=0;;year++){
		//Symmetrische Summe \sum_i^n=n*(n+1)/2
		//Quadrat aus der Summe rausziehen
		double erg=1337+year*year*year*(year+1.0)/2.0;

		if(erg==318338237039211050000.0){
			std::cout<<year<<std::endl;
			return 0;
		}
		else if(erg>318338237039211050000.0-1e7&&erg<318338237039211050000.0)
			std::cout<<"<"<<year<<std::endl;
		else if(erg<318338237039211050000.0+1e7&&erg>=318338237039211050000.0){
			std::cout<<">"<<year<<std::endl;
			return 0;
		}
		else if(erg>318338237039211050000.0+1e7)
			return 0;
	}
}

 

[mambokurt]

Wozu genau rechnest du da jetzt? Year wird mittels getYear https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Date/getYear bestimmt und dann nie wieder angefasst -> Year ist also laut der Doku 114, dein href dann 114.php. (oder verguck ich mich da?)

Edit: grad gerallt dass das Datum variabel sein soll. Da frage ich mich aber: wozu in C wenns in Javascript quasi schon fertig ist?

for(var x=1; x < 200000; x++) {
  var year = x;
  var pass=1337;
  for(var i=1; i<= year; i++) {
    pass += year*i*year;
  }
  if(pass == 318338237039211050000){
   alert(x);
	
  } 
}

Ich habe mich mit einem console.log erstmal grob in die Größenordnung von Year hochprobiert und dann einfach laufen lassen, probieren hat 10 Minuten gedauert, Schleifendurchlauf dann noch 5 für 5000 Zahlen...

 

[daemon777]

Dass aus der 6 eine 4 wird ist eigentlich recht logisch, wenn man sich anschaut, wie die beiden Zahlen Binär dargestellt aussehen. 6d = 110b und 4 = 100b. Jetzt vermuten wir ja bereits, dass wir nicht genügend Speicherplatz zur Verfügung haben und sehen, dass die niederwertigen Stellen einfach nicht gesetzt werden und somit als 0 interpretiert werden. Aus der 6d=110b wird also eine 1xxb, was als 100b interpretiert wird und umgerechnet 4d ist.

Die Verwendung von einem 64bit-Int oder double wird das Problem vielleicht etwas verzögern, aber sicher nicht lösen. Da hilft nur eine Bibliothek für große Zahlen oder sich selber etwas basteln, falls man da Lust drauf hat (ist auf jeden Fall interessant).