Notices
Results 1 to 4 of 4

Thread: Ceiling function/algorithm

  1. #1 Ceiling function/algorithm 
    New Member
    Join Date
    Apr 2008
    Location
    Canada
    Posts
    3
    Hello,
    The ceiling function is typically defined as ceiling(x) = min{n : x <= n}, where n is an integer.
    What's the fastest algorithm that could perform this operation? (Without using the floor function.) Assume that the only operations you have available are addition, subtraction, multiplication, division, module, logarithm, and powers/exponents.


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Well, if by "module" you mean the operation "a mob b" which returns the (unique) number 0 ≤ r < b such that there is an integer q with a = qb+r. If you're giving yourself this, then you could do:

    x + ((-x) mod 1)

    This works because, if the ceiling returns n, then n = x+r, where 0 ≤ r < 1. Then we have -x = -n+r, and according to the above definition, (-x) mod 1 = r.

    I feel like this is kind of cheating, because mod is doing all the work. So I'd say it'd be more interesting to get rid of this function. The simplest thing you could do is subtract 1 from x until you get a nonpositive number, and the number of times you subtract 1 is your answer.

    But you can be smarter than this: if a number is big, you know you'll have to subtract 1 a lot of times, so we can figure out how many times by applying log base 10 and seeing what the highest power of 10 you can subtract off. Then this becomes basically the same question as finding the decimal expansion of x.

    What are your ideas?


    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    Apr 2008
    Location
    Canada
    Posts
    3
    Hi, thanks for the reply.
    Yes that does seem like the best solution. The reason I allowed the modulo operator was because in my application of this problem, I happened to have it available. You're right though: the problem is more interesting without the modulo operator.

    Your suggestion about using log is interesting. Say the decimal number is 150. Then log150 is 2.17... . So you know you can subtract off 10^2 = 100. But in order to figure that out, you have to use the floor function on 2.17..., don't you? I deliberately omitted the floor operation from the list of available operators, though.
    Reply With Quote  
     

  5. #4  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    You're right about the log thing, I hadn't even noticed. However, notice that having the ceiling function call itself is fine, and it seems a lot faster to compute log, run the floor function (which is essentially the same as the ceiling function), and find out we have to subtract 100 instead up subtracting 1 100 times. But running times have never been my strong suit, so I'm not entirely sure about my speed claims.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •