Fehlererkennung für schnelles Kubikwurzelziehen.

[asdfman]

Mahlzeit. Ich habe eine vermutlich nicht ganz so schwere mathematische Frage, die ich leider etwas umständlich erklären muss.
Dafür entschuldige ich mich im Voraus. :/

Ich habe eine Methode implementiert, die dazu gedacht ist, Kubikwurzeln ganzer Zahlen unter 100 schnell im Kopf auszurechnen.
Dazu nimmt man die Tausenderstellen und vergleicht sie mit den dritten Potenzen der Zahlen von 1 bis 9 und wählt die nächst
niedrigere als Zehnerstelle des Ergebnisses. Die Einerstelle des Ergebnisses ist die, bei der die letzte Ziffer des Eingabewertes
mit der letzten Ziffer der entsprechenden dritten Potenz der Zahlen 0-9 übereinstimmt.

Zum Beispiel:
Die ersten 10 Kubikzahlen lauten:
0, 1, 8, 27, 64, 125, 216, 343, 512, 729

Gegeben sei die Zahl 74088. Die Tausenderstellen sind also 74. Die nächstniedrigere Potenz ist die 64, also ist die Zehnerstelle
des Ergebnisses die Zahl 4. Die letzte Ziffer des Eingabewertes ist die 8. Dies entspricht der letzten (und einzigen) Ziffer von
2 ^ 3. Also ist die Einerstelle des Ergebnisses die 2. Das Gesamtergebnis ist also 42.

Meine Frage:
Da dieses Verfahren bestimmte Stellen im Eingabewert ignoriert, kann es aber auf falsche Ergebnisse kommen, wenn der
Eingabewert keine perfekte Kubikzahl ist. Zum Beispiel würde das Verfahren für den Eingabewert 1337 als Ergebnis eine 13
liefern, was natürlich nicht stimmt, denn 13 ^ 3 = 2197.

Gibt es einen simplen Weg, das zu erkennen, ohne das erhaltene Ergebnis hoch 3 mit dem Eingabewert zu vergleichen?

----

Hier noch kurz die entsprechende Funktion, damit potentielle Hilfswillige das nicht selbst implementieren müssen, falls sie sich
mit ihrer Antwort nicht ganz sicher sind und sie überprüfen wollen:

#include <stdio.h>

const unsigned int cubes[] = {
    0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000
};

unsigned char cuberoot(const unsigned int in) {
    unsigned int upper = in / 1000;
    unsigned char lower = in % 10, i, out;

    for(i = 0; i < 11; i++) {
        if(upper < cubes[i]) {
            out = 10 * (i - 1);
            break;
        }
    }

    if(lower == 2) out += 8;
    else if(lower == 3) out += 7;
    else if(lower == 7) out += 3;
    else if(lower == 8) out += 2;
    else out += lower;

    if(out * out * out != in) {    /* Das finde ich nicht schoen! */
        fprintf(stderr, "ERROR: %d is not a perfect cube!\n", in);
        return 0;
    }

    return out;
}

 

[ConVuzius]

Hi,

ich denke noch nach, aber würde gerne wissen was an der bisherigen Lösung schlecht ist?

 

[asdfman]

Mir gefällt nicht, dass ich um die Lösung zu prüfen die Operation durchführen muss, die das Verfahren
an sich ja umgehen soll. Das fühlt sich für mich unelegant an. Ich möchte mich auf das nötigste beschränken
und wenn das Programm eh schon kubieren muss, kann man sich den Trick ja sparen und einfach mit
Durchprobieren oder binärer Suche die Lösung finden. Technisch ist am Nachprüfen natürlich nichts
auszusetzen, aber ich möchte das so minimal wie möglich implementieren. Das Programm soll so wenig
wie möglich "können", aber trotzdem zuverlässig richtige Ergebnisse liefern.

 

[lynxx]

... kann man sich den Trick ja sparen und einfach mit
Durchprobieren oder binärer Suche die Lösung finden.

Dann müsste die Routine aber deutlich mehr als 2 mal multiplizieren, so ist das schon sehr elegant.

Das Programm soll so wenig wie möglich "können", aber trotzdem zuverlässig richtige Ergebnisse liefern.

Gibt's ein konkretes Beispiel wofür man oft eine Kubikwurzel ziehen muss, also die Rechenzeit eine Rolle spielt?
Falls die zu testenden Zahlen auf jeden Fall Kubikwurzeln sein müssten kannst Du ja einen Bool beim Funktionsaufruf mit angeben ob das Ergebnis geprüft werden soll oder nicht ?

 

[asdfman]

Es geht nicht um Performance und ich werde das höchstwahrscheinlich auch nicht produktiv irgendwo benötigen.
Ich mache nur immer wieder mal kleine Programme nebenbei um für den "Ernstfall" etwas zu lernen. Oft genug
habe ich beim Bauen von so kleinen Spielzeugprogrammen dinge gelernt, die sich später in allgemeineren Fällen
als nützlich erweisen. Die Korrektheit einer Wurzel durch Testmultiplikation zu prüfen ist aber trivial und man
lernt davon überhaupt nichts. Wenn man aber unvollständige Daten hat und daraus trotzdem eine korrekte
Lösung ermitteln kann, besteht zumindest die Möglichkeit, dass sich das verallgemeinern und später sinnvoll
einsetzen lässt.

Natürlich kann es auch sein, dass es für mein Problem keine Lösung gibt. Dann ist es natürlich interessant, sich
zu fragen, warum das in diesem Fall nicht möglich ist und die Antwort darauf kann einem in Zukunft hilfreich sein.

Ich hoffe, das ist ein legitimes Ziel. Vielleicht ist die Idee auch total bescheuert. Wenn ja, sagt auch das bitte. Denn
davon könnte ich ja lernen, das nächste Mal Problem anzugehen, dessen Lösung mehr Erkenntnisgewinn bietet.