Wurzel aus Zahl = natürliche Zahl?

SG1

% arbeitet auf ints.

% arbeitet auf ints.

Ups,
Tja man lernt immer wieder dazu...

Jester

Eventuell geht es schneller, wenn Du nicht komplett die Wurzel bis zur letzten Kommastelle ausrechnest, sondern selbst iterierst und frühzeitig abbrichst. Dann kommst Du möglicherweise auch komplett mit ints aus.

matimatiker

hm, weiß nicht ob so schneller geht, aber evtl. so als ideen:
schreibe dir paar quadratzahlen auf, und schaue deren letzten ziffern.
Z.b. (zumindest bis 15^2) kommt 2, 3, 7, 8 nicht vor.

Ansonsten kannst noch versuchen eine Folge der Quadratzahlen aufzustellen. Sollte einfach sein.

Und dann schauen, ob die Folge deine Zahl erreicht.

Etwas schwerer aber eigentlich auch nicht schwer, ist eine Folge der "Ganzzahligen-Wurzel".

Edit: Interessante Frage hast du da gestellt.
Habe bissel rumprobiert. Habe einen schnelleren gefunden. Genauergesagt vermute ich, dass es einen gibt. Musst halt bissel rumprobieren.
Die Idee davon, ist: Schreibe alle Zahlen, bei denen die letzte Ziffer gleich ist untereinander. Beginne dabei in der "natürlichen" Reihenfolge: also 0 1 4 9 16 25.
Dann betrachte den "vertikalen Abstand" der Zahlen. Wenn du da einen Muster & die Regeln dazu findest, hast du einen algo, der nicht langsam ist.

Hi,
@matimatiker:
Hab jetzt mal deine Idee in die Tat umgesetzt. Für Endziffer 0 und 5 kommt etwas relativ einfaches raus.
$100n(n+2) + 10^2$ bei 0

$100n(n+1) + 5^2$ bei 5
Bei den Endziffern 1, 4, 6 und 9 ist es etwas komplizierter, weil die Abstände alternieren.
$20n\_1(n\_1+1) + 80n\_2(n\_2+1) + 9^2$
$40n\_1(n\_1+1) + 60n\_2(n\_2+1) + 8^2$
$80n\_1(n\_1+1) + 20n\_2(n\_2+1) + 6^2$
$60n\_1(n\_1+1) + 40n\_2(n\_2+1) + 7^2$
also n1 wird immer zuerst um 1 erhöht dann n2 und dann wieder n1...
müßte ja dann sowas wie

$n_1 = floor(n / 2) n_2 = floor((n - 1) / 2)$

sein.
Ist ja doch erstaunlich regelmäßig. Aber was ich jetzt genau damit anfangen kann
ist mir noch nicht ganz klar. Also bei den Endziffern 0 und 5 kann ich schon etwas rumrechnen.
Aber bei den anderen ist mir überhaupt nicht klar, wie ich das benutzen soll.
Irgendwelche Ideen dazu?

Danke

proggingmania

Hi !
Hab ne Funktion gefunden, die den Bruchteil einer Zahl liefert:
*double modf( double x, double intptr );

matimatiker

Katarrh schrieb:

Aber bei den anderen ist mir überhaupt nicht klar, wie ich das benutzen soll.
Irgendwelche Ideen dazu?

Mit den einzelnen Folgen kannst du so einiges Anfangen. Denn die Folgen "wandern" durch alle Quadratzahlen, mit der entsprechenden letzten Ziffer. Wenn du weißt welchen "Typ" deine Zahl (angenommen x) hat, also was die letzte Ziffer ist. Dann kannst du die entsprechende Folge nehmen und versuchen von der Anfangsquadratzahl auf x zu kommen.
Ist also x ein Folgenglied, (d.h. gibt es ein n sodass a_n = x) dann ist x eine Quadratzahl. Geht deine Folge über x hinaus, ohne deren Wert anzunehmen, kannst du dann sagen dass x keine Quadratzahl ist.

bool is_natural( double r )
{
	double  n;
	if ( !modf( sqrt(r), &n )) 
		return true;
	else return false;
}

Ben04

Ein anderer wäre das Annähern durch Intervallenteilung. Falls eine Wurzel gefunden wird dann ist es eien Quadratzahl ansonsten nicht.

Sei n = m^2 der Wert von dem du die Wurzel ziehen möchtest. Ziehl ist es m zu bestimmen falls m natürlich ist, ansonsten eine Fehlermeldung zurück zu geben.

Du weißt, dass m in I = [0, n] liegt.

So nun setzt du folgenden Algorithmus fort bis, dass I unter der Form [a, a+1] ist.

m := floor(Mitte von I)
sqr := m*m;
if sqr < n then I := [min(I), m]
else if sqr > n then I:= [m, max(I)]
else return true // da m*m = n

Falls du bis jetzt noch keinen m gefunden hast gibt es noch zwei Kandidaten : a und a+1. Falls beide jedoch nicht die Wurzel darstellen so ist die Wurzel irrational.

Die Laufzeit sollte in etwa logarithmisch von n abhängen. Also durchaus vertretbar.

.filmor

Hättest du einen Quantencomputer, könntest du die Zahl faktorisieren (kannst du so auch, aber nicht in angemessenem Aufwand). Dann musst du nämlich nur noch schauen, dass alle Faktoren doppelt vorkommen und bist fertig.

SG1

! (Sich den Wolf rechnen) schrieb:

bool is_natural( double r )
{
	double  n;
	if ( !modf( sqrt(r), &n )) 
		return true;
	else return false;
}

Aua... doubles vergleicht man nicht auf Gleichheit.

Hi,
Danke das mit der Intervallschachtelung ist perfekt!

Schönen Tag noch!

Stuss detected:

.filmor schrieb:

Hättest du einen Quantencomputer, könntest du die Zahl faktorisieren (kannst du so auch, aber nicht in angemessenem Aufwand). Dann musst du nämlich nur noch schauen, dass alle Faktoren doppelt vorkommen und bist fertig.

SG1 schrieb:

Aua... doubles vergleicht man nicht auf Gleichheit.

at Tuesday, 12.06.07 19:09:00