Another Man's Floor (Posted on 2005-11-23)

	Submitted by Richard
Rating: 4.5000 (2 votes)
Solution:	(Hide)
The title is intended to be a hint that refers to the Paul Simon song "One Man's Ceiling Is Another Man's Floor." Here the ceiling being referred to is the function ceiling, which is similar to function floor, except that non-integers are rounded up instead of down. To obtain a formula upon which a fast algorithm may be based, one may exploit the fact that 1 + floor(x) - ceiling(x) = 1 or 0 according as x is an integer or not in order to express the extra contribution that the "diagonal" makes to the lattice point count of an embedding rectangle when the lattice points of the two included triangles are added together. See "Dotty Right Triangle" for a similar analysis, although there the lattice points on the axes were also being counted, and the vertices were all lattice points. A suitable formula that can be obtained in this way is Sum_{0<=k<=KB} floor(kA/B) + Sum_{0<=l<=KA}ceiling(lB/A)=floor(KA)floor(KB+1) where K is any positive real number. This formula, with K fixed at K=m/b, and initially with A=a and B=b, but with A and B systematically reduced in stages as the algorithm progresses, makes possible the fast evaluation of Sum_{0<=k<=m} floor(ka/b). This is because, by extracting explicitly visible integer components from arguments of floors or ceilings for whichever of A/B or B/A is an improper fraction, it allows the computations to be organized into elementary stages that are based on, and synchronized with, the stages of Euclid's algorithm. A bc function that implements an algorithm based on this idea is as follows: define floorsum(a,b,m) { auto aa,bb,sum,kb,q,r,qp,rp,kr,krp scale = 0 aa = a; bb = b; sum = 0; kb = m while(1) { q = aa / bb; r = aa % bb sum = sum + (q * kb * (kb + 1)) / 2 if(r == 0) return(sum) kr=(m * r) / b sum = sum + kr * (kb + 1) qp = bb / r; rp = bb % r sum = sum - (qp * kr * (kr + 1)) / 2 if(rp == 0) return(sum) krp =(m * rp) / b sum = sum - kr * (krp + 1) aa = r; bb = rp; kb = krp} }

	Subject	Author	Date
	re(4): Jump Start-typo?	Richard	2005-12-30 13:06:47
	re(3): Jump Start-typo?	goFish	2005-12-30 06:50:07
	re(2): Jump Start	Richard	2005-12-30 03:25:02
	re: Jump Start	goFish	2005-12-30 02:41:38
	Jump Start	Richard	2005-12-29 21:16:02
	My best solution	goFish	2005-12-29 18:38:06
	re: Solution (part 1)	Tristan	2005-12-28 00:40:01
	re: Solution (part 1)	Hugo	2005-12-24 09:22:38
	Solution (part 1)	Tristan	2005-12-24 02:11:24
	A contribution	goFish	2005-11-23 18:11:09
	A simplification	e.g.	2005-11-23 13:14:53