Rechenweise der binären Suche

maZ
Erstie
Erstie
Beiträge: 12
Registriert: 18. Nov 2007 18:19
Kontaktdaten:

Rechenweise der binären Suche

Beitrag von maZ »

Nabend,
wir sitzen schon den ganzen Tag an der binären suche und haben das Problem, dass wir den Rechenweg überhaupt nicht verstehn. Vielleicht kann uns jemand einen Hinweis geben, dass das morgen noch was wird.

Bisher machen wir folgendes:
1. Verschieben der Mantisse um 2s nach links
2. Berechnung der bi im Vergleich mit der neuen Ganzzahl x (ob mit y² oder y(y-1) verglichen wird, dürfte ja erstmal einen nicht so großen Unterschied machen)
3. Bilden der yi anhand der bi
(das Ergebnis ist hier relativ ungenau, aber es kann ja nur ganze Zahlen geben)
4. Bilden der neuen bi im Vergleich mit der originalen Double-Zahl

Dabei kann nach meinem Verständnis mit den Formeln der Aufgabe immer nur eine Folge der Art 11111000000 auftreten, da y mit niedrigerem i immer größer wird, bis die Vergleichsbedingung bei der Bildung der neuen bi überschritten wird und nur noch Nullen kommen.

Somit lassen sich die bi-Werte, die im letzten Schritt rauskommen, in unserem Beispiel nicht sinnvoll als das Ergebnis darstellen. Vielleicht haben wir irgendwas falsch verstanden, also wäre es super, wenn jemand helfen könnte.

Auch verstehen wir nicht, wie die errechneten bi dann interpretiert werden, einfach ab dem Komma als Mantisse der neuen Zahl oder muss wieder verschoben werden?

Anbei nochmal mein Rechenweg,

http://img22.imageshack.us/img22/9155/fotodx.jpg

Vielen Dank,
maz

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

Re: Rechenweise der binären Suche

Beitrag von m_stoica »

Hi,

also die Schritte 1 und 2 aus deiner Rechnung scheinen mir (mehr oder weniger) okay zu sein.

wenn du dann die Wurzel aus der Mantisse gezogen hast (bei dir 0001000) bekommst du die Mantisse in dem
du von links nach rechts die erste 1 suchst. Den Teil ab der Stelle nimmst du als neue Matisse. In deinem Beispiel also
1.000. Das klappt weil die Wurzel aus einer Zahl 1.x wieder eine Zahl 1.y ist.
Jetzt musst du nur noch alles zu IEEE zusammensetzten:

Vorzeichen 0
Exponent: 2/2=1 ( insofern 10...01 für 10000001 stehen soll)
Mantisse: 00000... (die 1 vor dem Komma ist implizit)

Ich hoffe das hilft weiter

maZ
Erstie
Erstie
Beiträge: 12
Registriert: 18. Nov 2007 18:19
Kontaktdaten:

Re: Rechenweise der binären Suche

Beitrag von maZ »

Also sind die Schritte 3 und 4 garnicht notwendig und man kann die Rückführung aus der verschobenen Darstellung einfach so machen, wie du es beschrieben hast?

Ich denke, das hilft mir sehr, aber warum ist dann nochmal der Vergleich 2^s*y(2^s*y-1) < 2^2s*x gegeben? Oder ist das der, den man von vornherein benutzen muss? Statt y^2 < x bzw y(y-1) < x ?

Danke, maz

Antworten

Zurück zu „Archiv“