Funktion - 2er Logarithmus berechnen

[linnsche]

Hallöchen,

ich denke mal für euch ist das total easy...für mich naja...ich habe Informatik im Grundstudium für IM und brauche Hilfe bei einer Aufgabe (evtl auch bei mehreren, daher hab ich mich mal angemeldet):

Die folgende Funktion berechnet den Zweierlogarithmus von n nach der Regel:

log2(n)=log2(2*n/2)=log2(2)+log2(n/2)= 1+ log2(n/2)

(die 2 direkt nach dem log sollte tiefergestellt sein..sprich die Basis 2)

Ich versteh die Formel absolut, weiß allgemein auch was der Trivialfall ist...hier mal meine lösung (Einrückung NICHT BERÜCKSICHTIGT, aber vollkommen LOGISCH!!!)

def log(n):
if n==2:
return 1
else:
return 1 + log(n/2)



jetz die Frage, was ist daran falsch? wo ist der haken? man muss berücksichtigen dass wir hier mit ganzzahlen rechnen, das heißt man kann nur Ganzzahlen eingeben und als Ergebnis kommen auch nur Ganzzahlen raus!, Also müsste bei log(3) ja 2 rauskommen....kommt aber nicht....... wo hab ich den Fehler???

Bitte helft mir ich will das endlich wissen..rechne schon ne Weile rum....

[DasIch]

Die Funktion, wie von dir implementiert, ist nur definiert für Zahlen >= 2. 3 / 2 ergibt 1 (mit Rest 1) und so rufst du log mit einer Zahl außerhalb der Definitionsmenge auf.

[linnsche]

ok und wie mach ich es dann richtig??? ich bin total verwirrt......

[linnsche]

def log(n):
if n==0:
return 1
else:
return 1 + log(n/2)

wenn ich 0 eingebe kommt ja auch 1 raus....

[cofi]

1. Es gibt [ python][ /python] Code Tags, damit geht auch die Einrückung nicht baden.
2. DasIch meint das hier:

Code: Alles auswählen

In [2]: 3 / 2
Out[2]: 1

In dem Fall rufst du in der naechsten Iteration

Code: Alles auswählen

1 + log(0)

auf .. und dann immer wieder .. bis zur maximalen Rekursionstiefe. Sprich: Du brauchst mehr Basisfaelle.

[linnsche]

1. Es gibt [ python][ /python] Code Tags, damit geht auch die Einrückung nicht baden.
2. DasIch meint das hier:

Code: Alles auswählen

In [2]: 3 / 2
Out[2]: 1

In dem Fall rufst du in der naechsten Iteration

Code: Alles auswählen

1 + log(0)

auf .. und dann immer wieder .. bis zur maximalen Rekursionstiefe. Sprich: Du brauchst mehr Basisfaelle.

ok, also ich versteh schon dass ich dann sozusagen ja gleich "am Ende" angelangt bin...jedoch, wie kann ich das ändern? was für zusätzliche Basisfälle brauch ich? ich meine, wenn ich n==0 setze, das ist der trivialfall...dann kommt ja im endeffekt 1 raus....wenn ich aber z.B. log(3) eingebe, dann müsste doch 3/2=1 + 1 = 2 rauskommen oder?

liege ich falsch? wieso funktioniert es nicht.....?

[BlackJack]

@linnsche: Schreib es Dir doch einfach mal auf was bei ``log(3)`` jeweils für den Aufruf ersetzt wird. Oder mal anders gefragt was soll ``log(0)`` ergeben und was ergibt das bei Dir?

[linnsche]

ok, log(0) ergibt immer eins...weil ja a^0 immer 1 ergibt........und das hab ich ja jetz geschrieben:

if n==0:
return 1

stimmt das nicht...??

ich hab jetzt den test gemacht..normal müsste für log(100) 7 rauskommen (also eigentlich 6,6....)....be mir kommt 8 raus....jetz frag ich mich, wieso? ach ich mag das mit log nicht....garnicht

[cofi]

Aem log_x(x^y) = y. Also log_x(a^0) = 0, nicht eins. Andersherum: log(1) = 0, fuer alle Basen.

log(0) dagegen ist ziemlich undefiniert (Mit welchem Exponenten bekommt man denn eine 0?!)

[BlackJack]

@linnsche: Schreib Dir doch mal die Rechnung hin wodurch der `log()`-Aufruf in jedem Schritt ersetzt wird. (Und es gibt hier Tags für Code im allgemeinen und Python im besonderen.)

[linnsche]

@linnsche: Schreib Dir doch mal die Rechnung hin wodurch der `log()`-Aufruf in jedem Schritt ersetzt wird. (Und es gibt hier Tags für Code im allgemeinen und Python im besonderen.)

ja aber es gibt doch 1 wenn ich die oben genannte REchnung ausführe? sprich:

log2(0)= 1+log(0/2) und das gäb doch 1.....

ich versteh nicht genau was du meinst, BlackJack!

Ich steh wohl mega auf dem Schlauch und raub euch jeglichen Nerv, aber ich weiß echt nicht wie ich vorgehen soll.......wo genau find ich die Tags? vorallem für Python??? und wie soll ich die Rechnung "aufschreiben"?????

die Rechnung steht doch schon oben. Oder was meinst du???

[DasIch]

Gehen wir mal von einer ursprünglichen Definition aus:

Code: Alles auswählen

def log(n):
    if n == 2:
        return 1
    else:
        return 1 + log(n / 2)

``log(3)`` ist equivalent zu ``1 + log(3 / 2)`` bzw. ``1 + log(1)``. Dies lässt sich weiter auflösen zu ``1 + (1 + log(1 / 2))`` und da ``1 / 2 == 1`` haben wir auch hier einen Aufruf ``log(1)``. Jetzt könnten wir dies auflösen aber letztendlich ändert sich nichts mehr und die Rekursion läuft weiter bis der Stack überläuft oder das Interpreter Limit erreicht ist was zu einem RuntimeError führt.

Wir stellen also fest dass die Abbruchbedingung ``n == 2`` nicht ausreichend (und möglicherweise unnötig) oder falsch ist. Da die Funktion die Eigenschaft ``log(2 ** 2) == 1`` erfüllt trifft ersteres zu.

Ich könnte jetzt noch eine Haskell Lösung posten aber dann wird es wirklich zu einfach.

[linnsche]

ok, also daher kommt auch immer die runtime-error-meldung!

ja aber wenn ich das Ganze abänder auf n==0: return 1, dann stimmts doch oder? Denn wenn ich n==0 setze, also log(0), dann return ich 1......und sonst zählt es ja runter...also wenn ich log(3) mach dann ist es doch 1+log(3/2), das dann 1+(1+log(2/2) etc...oder?

stimmt es dann nicht?

[cofi]

Schau dir nochmal meinen Post an. Bei log(0) 1 zurueckzugeben ist aber in jedem Fall falsch.

[linnsche]

Schau dir nochmal meinen Post an. Bei log(0) 1 zurueckzugeben ist aber in jedem Fall falsch.

ach mist...für n==1: return 0 oder??????? genau anders rum......mann..wieso bin ich sowas von DOOF in python...??? ich versteh zwar schon vieles viel ebsser als im letzten semester (bin durchgerasselt) aber bei so mathematischen dingen (obwohl ich mathe liebe und kann.......) stell ich mich immer total doof an.... :K


also heißt es nun:

Code: Alles auswählen

def log(n):
   if n==1:
      return 0
   else:
      return 1+log(n/2)

[cofi]

Das ist schonmal deutlich besser. Sinnvollerweise solltest du noch den Fall < 1 abfangen (und eine Exception werfen), um Endlosrekursionen zu vermeiden

[linnsche]

stimmt das hab ich mir vorhin noch überlegt, aber dann dachte ich, es sei doch sinnvoller mit n==1....aber hey,

DANKE EUCH für die hilfestellung! echt, ich bin so dankbar dass ich es jetz doch noch rausgefunden hab

DANKE!

[DasIch]

So sieht übrigens die Haskell Lösung mit Test aus:

Code: Alles auswählen

import Test.QuickCheck (Property, (==>), quickCheck)

log2 :: Fractional a => a -> Integer
log2 1 = 0
log2 n = 1 + log2 (n / 2)

testLog2 :: Integer -> Property
testLog2 n = n > 0 ==> log2 (2 ^ n) == n

main :: IO ()
main = quickCheck testLog2

[BlackJack]

Ich konnte nicht widerstehen etwas RPL in meinen HP-Taschenrechner zu hacken:

Code: Alles auswählen

«
  CASE DUP 1 <
    THEN 772 DOERR END
    DUP 1 ==
    THEN DROP 0
    END 2 / FLOOR L2 1 +
  END
»

Das Programm muss unter dem Namen ``L2`` gespeichert werden, damit das mit der Rekursion klappt.

[problembär]

also heißt es nun:

Code: Alles auswählen

def log(n):
   if n==1:
      return 0
   else:
      return 1+log(n/2)

Bin nicht sicher, ob Du mit int (oder nicht doch lieber mit float) rechnen willst.

Für Vielfache von 2 (2, 4, 8, 16) scheint das ja so zu klappen. Für die Werte dazwischen (z.B. 7) eher weniger. Das Abfangen der Endlosrekursion in der Weise, daß das Ergebnis bei den Werten dazwischen dann stimmt, sehe ich auch noch nicht.