Hey Leute, wie angekündigt, nun eine Frage zum Beweis des Algorithmus.
Ich habe also einen Algorithmus, der mir a^(2^m) in m schritten berechnet.
eine funktion pow(a, n) wobei n = 2^m ist.
(m wird dann mit log zur basis 2 von n berechnet)
pseudocode (E soll element aus heißen, dieses komische e halt):
function pow(a, n){
m = log2(n)
if not m E N return fehler //also wenn m keine natürliche zahl ist..
x = a
for i = 0, i < m, i++
x = x * x
end
return x
end function
terminierung habe ich eigentlich bewiesen, das es m schritte sind auch. jetzt muss
ich die korrektheit durch induktion beweisen.
Ich könnte also für n = k über k indu…zieren? :
-
Induktionsanfang: k = 1:
pow(a, 1) = a^(2^1) = a^2
m ist ja log2 von 1, also 0,
die schleife wird 0 mal ausfeführt, ergebnis ist x also a -
Induktionsschritt: und hier ist mein problem. Die Annahme wäre das es für jedes
k oder n E N0 also für jedes n oder k größer 0 gilt.
jetzt muss ich das ja für pow(a, n + 1) beweisen…
Könnte mir jemand helfen, wie ich das machen soll?
Danke…
*** Edit ***
theoreetisch… müsste ich doch beweisen das:
pow(a, n) * log2(n) = pow(a, n + 1), das wäre doch mein induktionsschritt oder?
aber wie beweise ich das?
(a * a * a… log2(n) mal) * log2(n) = (a * a… log2(n) + 1 mal…
aber das ist doch kein beweis, oder?