All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Another Man's Floor (Posted on 2005-11-23) Difficulty: 4 of 5
Let a, b, and m be positive whole numbers. Required is a fast algorithm for evaluating Σk=0..m floor(ka/b), floor(x) being the greatest integer that does not exceed the real number x.

See The Solution Submitted by Richard    
Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re(3): Jump Start-typo? | Comment 10 of 11 |
(In reply to re(2): Jump Start by Richard)

Richard

You wrote

"I claim that it is always the case that for general a,b, and K

Sum_{0<=k<=Kb} floor(ka/b) + Sum_{0<=l<=Ka} ceiling(lb/a) = floor(Ka)floor(Kb)"

Let a = 5, b = 17, m = 23, K = 23/17, then this becomes

70 + 74 = 144 but 6 * 23 = 138 so I suspect there is a "+1" missing and the rhs should read floor(Ka) (floor(Kb)+1).

If I do this and rewrite in terms of the given iterator,k, and parameters a, b and m, I obtain

s( a, b, m) = (m+1) Floor [ a m / b] - Sum (for k = 0 to a m / b) Ceiling [ k b / a]

(for a given (a, b,m) K is not totally independent and I have used K = m/b).

I have tested this and found no errors.  However this formulation is not very efficient since, for example, if a>b then the length of the residual series is actually greater than the original.


  Posted by goFish on 2005-12-30 06:50:07
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information