1. 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.  2.

3. 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.  4. 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.  5. 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.  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   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement