| Author |
Message
|
| mlalkaka |
 Posted: Sat Apr 26, 2008 11:32 am Post subject: Ceiling function/algorithm |
 |
|
Forum Freshman
Joined: 04 Apr 2008
Posts: 5
Location: Canada
|
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. |
|
| Back to top |
|
 |
| serpicojr |
| Posted: Sat Apr 26, 2008 1:00 pm Post subject: |
|
|
Forum Ph.D.
Joined: 17 Jul 2007
Posts: 871
Location: JRZ
|
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? |
|
| Back to top |
|
|
| mlalkaka |
| Posted: Sat Apr 26, 2008 2:22 pm Post subject: |
|
|
Forum Freshman
Joined: 04 Apr 2008
Posts: 5
Location: Canada
|
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. |
|
| Back to top |
|
|
| serpicojr |
| Posted: Sat Apr 26, 2008 3:11 pm Post subject: |
|
|
Forum Ph.D.
Joined: 17 Jul 2007
Posts: 871
Location: JRZ
|
| 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. |
|
| Back to top |
|
|
|
|
|
