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(4): Jump Start-typo? Comment 11 of 11 |
(In reply to re(3): Jump Start-typo? by goFish)

"there is a "+1" missing and the rhs should read floor(Ka) (floor(Kb)+1). "  YES. Correction made in my post. Sorry for losing the 1.

The observations of the first two posts are important here: integers contained in the argument of a floor (or ceiling) function can be pulled out. Doing this in each step (including the 0th step if a>b) provides the simplification that makes the algorithm effective. You need to keep using the formula over and over with the same K but with a or b getting smaller each time.  There is a very well-known (and ancient) algorithm embedded in this!

Edited on February 19, 2006, 2:53 pm
  Posted by Richard on 2005-12-30 13:06:47

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