Latest revision |
Your text |
Line 76: |
Line 76: |
| [[Special:Contributions/141.101.76.194|141.101.76.194]] 09:49, 11 March 2021 (UTC) | | [[Special:Contributions/141.101.76.194|141.101.76.194]] 09:49, 11 March 2021 (UTC) |
| | | |
− |
| |
− | <pre>
| |
− | First: almost all invocations are with exactly 3 arguments (The output of the previous invocation), so we don't have to deal with N inputs at all.
| |
− | Notation: In iteration n we have the values min[n] <= mid[n] <= max[n] (in any order) and can compute AM[n], GM[n] (and median[n] = mid[n]).
| |
− | Let Q[n] := max[n]/min[n] >= 1, R[n] := max[n]-min[n] = (Q[n]-1)*min[n].
| |
− | We already established that R is decreasing and min is increasing, so Q is decreasing.
| |
− |
| |
− | Theorem: There is an n0 with R[n+1] <= R[n]*2/3 for all n > n0.
| |
− |
| |
− | Proof (by case discrimination for each n):
| |
− | case 1: mid[n+1] != AM[n]:
| |
− | R[n+1] <= Max(max[n]-AM[n],AM[n]-min[n])
| |
− | = Max(max[n]*3-(max[n]+mid[n]+min[n]),(max[n]+mid[n]+min[n])-min[n]*3)/3
| |
− | = Max(max[n]*2-(mid[n]+min[n]),(max[n]+mid[n])-min[n]*2)/3
| |
− | <= (max[n]-min[n])*2/3
| |
− | = R[n]*2/3
| |
− | Hence: R[n+1] <= R[n]*2/3
| |
− |
| |
− | case 2: mid[n+1] == AM[n]:
| |
− | because GM <= AM: min[n+1] = GM[n], max[n+1] = mid[n]
| |
− | Q[n+1] = mid[n]/GM[n]
| |
− | = (mid[n]^3/(max[n]*mid[n]*min[n]))^(1/3)
| |
− | = (mid[n]^2/(max[n]*min[n]))^(1/3)
| |
− | <= (mid[n]/min[n])^(1/3)
| |
− | <= Q[n]^(1/3)
| |
− | R[n+1] = (Q[n+1]-1)*min[n+1]
| |
− | <= (Q[n]^(1/3)-1)*GM[n]
| |
− | <= (Q[n]^(1/3)-1)*(max[n]^2*min[n])^(1/3)
| |
− | = (Q[n]^(1/3)-1)*Q[n]^(2/3)*min[n]
| |
− | = (Q[n]-Q[n]^(2/3))*min[n]
| |
− | = R[n]-(Q[n]^(2/3)-1)*min[n]
| |
− | <= R[n]-(Q[n]-1)*min[n]/(Q[n]^(1/3)+1))
| |
− | = R[n]-R[n]/(Q[n]^(1/3)+1)
| |
− | = R[n]*(1-1/(Q[n]^(1/3)+1))
| |
− | Now we can pick a q1 = Q(n1) with q1 > Q[n] >= 1 for n > n1 because Q is decreasing:
| |
− | R[n+1] <= R[n]*(1-1/(q1^(1/3)+1))
| |
− |
| |
− | Together with case 1, this gives R -> 0 and thus Q -> 1. So we can pick another q0 = Q(n0) with q0 <= 8:
| |
− | R[n+1] <= R[n]*(1-1/(q0^(1/3)+1)) <= R[n]*2/3
| |
− | </pre>
| |
− | -- [[User:Xorg|Xorg]] ([[User talk:Xorg|talk]]) 17:34, 11 March 2021 (UTC)
| |
| | | |
| == Better Python implementations == | | == Better Python implementations == |