Skip to content

Instantly share code, notes, and snippets.

@jonnius
Last active October 21, 2015 19:47
Show Gist options
  • Save jonnius/a911269fcfe3b9e4cdfd to your computer and use it in GitHub Desktop.
Save jonnius/a911269fcfe3b9e4cdfd to your computer and use it in GitHub Desktop.
To show: 1 <= size <= 10
size = 1 + t1 / (1 + t2/10 - c1) - c2
we add c1 and c2 because of the integer division
Assumptions:
(i) 0 <= t1 <= t2
(ii) t2 >= 0
(iii) 0 <= c1 < 1 (consequence of integer division)
(iv) 0 <= c2 < 1 (consequence of integer division)
(v) c2 <= t1 / (1-c1 + t2/10) (the "loss" by an integer division cannot be bigger then the division result itself)
To show:
size = 1 + t1 / (1-c1 + t2/10) - c2 <= 1
Subtracting (1-c2), using (v)
t1 / (1-c1 + t2/10) >= c2 is true → size >= 1
Case 1: t2 != 0, using (i), canceling t2
size = 1-c2 + t1 / (1-c1 + t2/10) <= 1-c2 + t2 / (1-c1 + t2/10) = 1 / ((1-c1)/t2 + 1/10)
To show:
size <= 1-c2 / ((1-c1)/t2 + 1/10) <= 10
Inverting and multiplying (1-c2):
((1-c1)/t2 + 1/10) >= (1-c2)/10
Subtracting 1/10, using (ii), (iii) and (iv)
(1-c1)/t2 >= -c2/10 is true → size <= 10
Case 2: t2 = 0, using (i)
t2 = 0 → t1 = 0 → size = 1 <= 10 → size <= 10
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment