Test auf Kubikzahl falsch negativ

[Kronf]

Hallo,

ich habe ein C+±Programm geschrieben, das eine natürliche Zahl auf bestimmte Eigenschaften überprüft. Zentral ist dabei der Test auf Ganzzahligkeit:

bool ganzzahl(double n)
{
 if(fmod(n, 1.0) == 0.0) return true;
 else return false;
}

Unter anderem wird geprüft, ob es sich um eine Kubikzahl handelt:

bool kubik(double n)
{
 if(ganzzahl(pow(n,1.0/3.0))) return true;
 else return false;
}

Das Programm funktioniert soweit gut, bis auf diesen Test. Bis 3^3 wird korrekt „Kubikzahl“ ausgegeben, ab 4^3 nicht mehr. Wenn ich mir die Kubikwurzel ausgeben lasse, sieht sie allerdings immer ganzzahlig aus.

Bei der Quadratzahl-Funktion z.B. gibt es dagegen keine Probleme, sie funktioniert analog mit sqrt(n).

Hat jemand eine Idee, woran das liegen könnte? Ist pow() irgendwie besonders ungenau? Oder habe ich irgendeinen dummen Fehler drin?

Danke und Gruß,
Kronf

[norsemanna_075dab]

Howdy,

zunaechst einmal solltest du dir ueberlegen, wie double’s tatsaechlich funktionieren (z.B. im Wiki), und weshalb es keine exakte Darstellung fuer 1.0/3.0 gibt.

Danach wirst du verstehen, dass dein fmod(n,1.0) nicht immer das liefert, was du haben möchtest.

Es koennte naemlich sein, dass dein "pow(n,1.0/3.0) fuer z.B. 64.0 etwas liefert, was marginal kleiner ist als 4.0, zum Beispiel 3.99999999999999x und dann dein fmod(,1.0) als Resultat dann nicht 0.0 sondern .99999999999999x (Zahlen sind nur Beispiele)

Gruss
n.

[Kronf]

Hallo norsemanna,

danke für deine Antwort. Hast du vielleicht einen Tipp, wie ich ohne die Ungenauigkeiten rechnen kann? Ich meine, das Gerät heißt Rechner, es wäre schon toll, wenn man damit rechnen könnte

Viele Grüße,
Kronf

[Peter_TOO]

Hallo Kronf,

danke für deine Antwort. Hast du vielleicht einen Tipp, wie
ich ohne die Ungenauigkeiten rechnen kann? Ich meine, das
Gerät heißt Rechner, es wäre schon toll, wenn man damit
rechnen könnte

Genau es heisst Rechner und nicht Präzisionsrechner!

Das problem ist, dass ein Präzisionsrechner die erste Berechnung von 1/3 nicht hinaus käme, der würde da in 1000 Jahren noch dran rechnen!

Um also eine endlich Programmlaufzeit zu erhalten, muss man die Präzision immer auf eine bstimmte Stellenzahl begrenzen!

Du solltest dich dringend mit den Basics der Flieskommazahlen-Arithmetik befassen!

MfG Peter(TOO)

[norsemanna_075dab]

Hi,

danke für deine Antwort. Hast du vielleicht einen Tipp, wie
ich ohne die Ungenauigkeiten rechnen kann? Ich meine, das
Gerät heißt Rechner, es wäre schon toll, wenn man damit
rechnen könnte

ja, wenn es denn so einfach waere … doubles sind oft ungenau, man muss ab und zu runden und kann eigentlich fast nie auf einen konkreten Wert vergleichen.

Allerdings: Wer sagt denn, dass du ueberhaupt doubles nehmen musst.

Wie ist denn dein Wertebereich?

Gruss
n.

[Kronf]

Ich habe doubles nur genommen, weil es der Standardtyp für Zahlen wie 1.0 zu sein scheint.

Mein Wertebereich sind natürliche Zahlen, potenziell unendlich groß. Klar, irgendeine Obergrenze werde ich setzen müssen.

Was wäre denn die Alternative zu double?

Gruß,
Kronf

[Kronf]

Hallo Peter,

theoretisch ist mir das schon klar mit der endlichen Genauigkeit.

Nur habe ich mit meinem Taschenrechner keine Probleme, herauszufinden, dass 13824 eine Kubikzahl ist, und mit dem PC soll das nicht gehen?

Gruß,
Kronf

[Peter_TOO]

Hallo Kronf,

theoretisch ist mir das schon klar mit der endlichen
Genauigkeit.

Nur habe ich mit meinem Taschenrechner keine Probleme,
herauszufinden, dass 13824 eine Kubikzahl ist, und mit dem PC
soll das nicht gehen?

Ich sage ja, du solltest dich mit den Grundlagen beschäftigen!

Der Taschenrechner rechnet normalerweise mit BCD, der PC mit binärer FP-Zahlendarstellung. BCD ist aber wesentlich langsamer.

Je nach C-Compiler kann dieser auch mit BCD rechnen (BCD ist aber nicht Bestandteil von Standard-C), bzw. es gibt dazu Bibliotheken.

MfG Peter(TOO)

[Lutz_Lehmann]

Hi,

bestimme die dritte Wurzel, runde mit round auf die nächste ganze Zahl und vergleiche die dritte Potenz von dieser mit Deiner Ausgangszahl.

Ansonsten gibt es noch cbrt, welches die dritte Wurzel mit maximale möglicher Genauigkeit ausrechnen sollte.

Gruß, Lutz

[norsemanna_075dab]

Howdy,

Mein Wertebereich sind natürliche Zahlen, potenziell unendlich
groß. Klar, irgendeine Obergrenze werde ich setzen müssen.

Was wäre denn die Alternative zu double?

Na uint64_t zum Beispiel. Dafuer bräuchte man auch nicht selber was programmieren, sondern koennte die Loesung hier abgreifen.

https://gist.github.com/729557

Aber wieder: Unendlich gross gibt es weder bei double noch anderen Standard C++ Typen (dazu bedarf es dedizierter Libraries und die meisten davon koennen dir auch nicht 1/3 exakt darstellen)

Und da es viele Wege nach Rom gibt, könnte man das 1.0/3.0 auch teilvermeiden, z.B. koennte man 3te_Wurzel_aus_n_ist_ganzzahlig(n) auch fuer positive n wie folgt berechnen.

bool kbwurzel(const double n)
{
 const double epsilon = 1E-11;
 const double x = floor(exp(log(n)/3.0)+0.5);

 return fabs(x\*x\*x - n) 

/\* zweites Beispiel hier entfernt \*/

Woher ergibt sich dieser Ansatz: Nun eine Multiplikation laesst sich als eine Addition von Logarithmen darstellen. 

Sei hier nun N die Zahl, aus der die Wurzel gezogen werden soll und x die dritte Wurzel.


=\> N = x\*x\*x = exp(log(x)+log(x)+log(x)) = exp(3log(x))
=\> N = exp(3log(x))
=\> log(N) = 3log(x)
=\> log(N)/3 = log(x)
=\> exp(log(N)/3) = x

Der Rest in den Funktionen und das Ausprobieren, ob ich keinen Fehler gemacht habe, ist "left as an exercise to the reader" ...

Gruss
n.

[norsemanna_075dab]

Hi Lutz,

Ansonsten gibt es noch cbrt, welches die dritte Wurzel mit
maximale möglicher Genauigkeit ausrechnen sollte.

stimmt auffallend, und die ist auch schon im 99er Standard drinnen.
Da sieht man mal, wie oft man solche Funktionen tatsaechlich braucht

Gruss
n.

[Kronf]

Hallo Lutz,

danke für die Tipps! Werde ich probieren!

Gruß,
Kronf