binarysearch

Platinum
DON'T PANIC
Beiträge: 42
Registriert: 27. Apr 2006 13:21

binarysearch

Beitrag von Platinum »

Hallo,

also wenn ich die Wurzel von 4,5 mit dem Binary-Search-Verfahren berechnen will, gilt doch folgendes:

Exponent: 2
Mantisse: 1,125 (1,001 in binär)

jetzt schieben wir die Mantisse um 2*s stellen nach links:

D.h. neue Mantisse: 72 (1001000 in binär)

Wenn ich nun mit dem angegeben Binary-Search-Verfahren die Wurzel ziehen will komme ich auf:

8 (1000 binär)

der exakte Wert wäre: 8.485281374

Wie komme ich denn auf diesen Wert????

Weil, wenn ich mit der 8 weiter rechnen und dann dies 2^1 * 8 / 2^3 ausrechne komme ich auf 2 und
die Wurzel von 4,5 ist 2,12133...

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: binarysearch

Beitrag von m_stoica »

wenn du die Mantisse weiter nach links schiebst, solltest du eine höhere Genauigkeit bekommen.
Deine neue Mantisse war ja "1001000" stattdessen könntest du ja "1001000000000000000" nehmen

h4ck4
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 18. Mai 2009 20:50
Kontaktdaten:

Re: binarysearch

Beitrag von h4ck4 »

Servus,
mir ham die Binäre Suche implementiert und sie liefert auch akzeptable Ergebnisse (oder?)!
bsp. 38.6
Heron: 6.212889826803627
Binarysearch: 6.212888812646269

Allerdings bei Zahlen deren Wurzel ne Ganzzahl ist, schaut das Ergebnis komisch aus:
bsp. 25.0
Heron: 5.0
Binarysearch: 4.999996662139892

Ist das normal für die Binärsuche oder haben wir da irgendwo einen Fehler drin, also müsst z.B. bei Eingabe 25.0 auch bei der Binärsuche ne 5.0 rauskommen??

Benutzeravatar
glowhand
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 23. Okt 2008 22:23
Wohnort: Darmstadt

Re: binarysearch

Beitrag von glowhand »

also bei mir ist es genau umgedreht,
heron: 5.0000000000000053722
binarysearch: 5.0

schätz aber mal, wir beide haben die aufgabenstellung erfüllt 8)

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: binarysearch

Beitrag von mister_tt »

Was hast du denn für eine Abbruchbedingung bei Heron, glowhand? Wenn du prüfst, ob sich bei einer Iteration des Algos nichts mehr ändert und erst dann abbrichst (geht recht schnell - vor allem bei geschickter Wahl des Startwertes), solltest du auch 5.0 rausbekommen...

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: binarysearch

Beitrag von m_stoica »

mister_tt hat geschrieben:Wenn du prüfst, ob sich bei einer Iteration des Algos nichts mehr ändert und erst dann abbrichst (geht recht schnell - vor allem bei geschickter Wahl des Startwertes), solltest du auch 5.0 rausbekommen...
Und das terminiert immer? Ich bin mir da nicht so sicher, wegen der Rundungsfehler die auftreten können. Klappt den sowas wie 12345.12345 bei dir?

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: binarysearch

Beitrag von mister_tt »

Jo.

Code: Alles auswählen

Bitte geben Sie eine Gleitkommazahl ein.**** user input : 12345.12345
Die Wurzel von 12345.12345 ist:
Heron: 111.10861105242924
Binsearch: 0.0
Habe aber nicht hunderte von Zahlen ausprobiert... Nur Rundungsfehler schön und gut, aber auch die müssten ja dann von Iteration zu Iteration gleich bleiben, sodass das Teil terminieren müsste...

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: binarysearch

Beitrag von m_stoica »

Binsearch: 0.0 ? Das sieht aber nicht so gut aus

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: binarysearch

Beitrag von mister_tt »

Schon klar, an der arbeite ich noch, keine Angst ;D Aber Danke für den Hinweis.

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: binarysearch

Beitrag von m_stoica »

gern geschehen ;)

Benutzeravatar
glowhand
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 23. Okt 2008 22:23
Wohnort: Darmstadt

Re: binarysearch

Beitrag von glowhand »

mister_tt hat geschrieben:Was hast du denn für eine Abbruchbedingung bei Heron, glowhand? Wenn du prüfst, ob sich bei einer Iteration des Algos nichts mehr ändert und erst dann abbrichst (geht recht schnell - vor allem bei geschickter Wahl des Startwertes), solltest du auch 5.0 rausbekommen...
Ja, stimmt. Ich überprüfe nicht auf Gleichheit sondern auf 0.00000001 Unterschied. Das könnte natürlich noch verbesserungswürdig sein.

Antworten

Zurück zu „Archiv“