Daniel Marschall, 6.5.12

GRUNDSÄTZLICHES
===============

     1 * [0..9] = [0.. 9], 4,5[avg]
[0..9] * [0..9] = [0..81], 20,25[avg]

[] = Kommentare

EINE INTERPOLATION FÜR DEN PARAMETER R (AVG-CASE)
======================================

r(x) = r(x-1)/10 + 4,5[avg] + sum(x)*2 + 20,25[avg]/2[nur bei ungeraden x] = r(x-1)/10 + sum(x)*2 + 14,625
r(x-1) =~ r(x) - 20,25[avg] - 4,5[avg] + 20,25[avg]/2[nur bei ungeraden x] = r(x) - 14,625[avg]
sum(x) = x/2 * 20,25[avg]

r(x) = r(x-1)/10 + sum(x)*2 + 14,625
r(x) = r(x-1)/10 + (x/2 * 20,25)*2 + 14,625
r(x) = r(x-1)/10 + 20,25x + 14,625
r(x) = (r(x) - 14,625)/10 + 20,25x + 14,625
r(x) = r(x)/10 - 14,625/10 + 20,25x + 14,625
r(x) - r(x)/10 = -14,625/10 + 20,25x + 14,625
0,9 r(x) = -14,625/10 + 20,25x + 14,625
0,9 r(x) = -1,4625 + 20,25x + 14,625
0,9 r(x) = 20,25x + 13,1625
0,9 r(x) = 20,25x + 13,1625
r(x) = 22,5x + 14,625

+ ---------------------- +
| r(x) = 22,5 x + 14,625 |
+ ---------------------- +

* Test mit dem Überlaufpunkt von UInt32:

r(x) >= 4294967296
4294967296 <= 22,5 x + 14,625
4294967296 - 14,625 <= 22,5 x
4294967281,375 <= 22,5 x
4294967281,375 / 22,5 <= x
~190887435 <= x

x >= 1908'87435 (Step 1908)
Genauer Überlauf bei 1908'75593

Abweichung:
190887435 - 190875593 = +11842

* Test mit dem Überlaufpunkt von UInt64:

r(x) >= 18446744073709551616
18446744073709551616 <= 22,5 x + 14,625
18446744073709551616 - 14,625 <= 22,5 x
18446744073709551601,375 <= 22,5 x
18446744073709551601,375 / 22,5 <= x
~819855292164868960 <= x

x >= 8198552921648'68960 (Step 8198552921648)

EINE INTERPOLATION FÜR DEN PARAMETER SUM (AVG-CASE)
========================================

sum(x) = x/2 * 20,25[avg]
sum(x) = 10,125[avg] x

+ ----------------- +
| sum(x) = 10,125 x |
+ ----------------- +

* Test mit dem Überlaufpunkt von UInt32:

sum(x) >= 4294967296
4294967296 <= 10,125 x
4294967296 / 10,125 <= x
~424194301 <= x

x >= 4241'94301 (Step 4241)

* Test mit dem Überlaufpunkt von UInt64:

sum(x) >= 18446744073709551616
18446744073709551616 <= 10,125 x
18446744073709551616 / 10,125 <= x
~1821900649255264357 <= x

x >= 18219006492552'64357 (Step 18219006492552)