What's a hackish way to do a ceiling divide on integers?

[luser droog]

I keep finding myself resorting to floating-point and lots
of conversions. But I'm not really showing any integer
ability. Better way?

union object *o = (union object *)n; n+=(int)ceil((double)sizeof*o/sizeof*n);

https://github.com/luser-dr00g/sexp.c/blob/master/sexp.c#L94

[James Kuyper]

Post by luser droog
I keep finding myself resorting to floating-point and lots
of conversions. But I'm not really showing any integer
ability. Better way?
union object *o = (union object *)n; n+=(int)ceil((double)sizeof*o/sizeof*n);
https://github.com/luser-dr00g/sexp.c/blob/master/sexp.c#L94

n += (sizeof *o + sizeof *n - 1)/sizeof *n

[Ben Bacarisse]

Post by luser droog
I keep finding myself resorting to floating-point and lots
of conversions. But I'm not really showing any integer
ability. Better way?
union object *o = (union object *)n; n+=(int)ceil((double)sizeof*o/sizeof*n);

I'd go with (x + y - 1) / y but there are many other integer-only
expressions such as x/y + !!(x%y).

[Bartc]

Post by luser droog
I keep finding myself resorting to floating-point and lots
of conversions. But I'm not really showing any integer
ability. Better way?
union object *o = (union object *)n; n+=(int)ceil((double)sizeof*o/sizeof*n);

If you're worried about the speed of this, I don't think it will be a
problem as the whole thing should be reduced to a compile-time constant.

(Depending on compiler, but even gcc -O0 managed that on a similar
expression.)

[luser droog]

Post by Bartc

Post by luser droog
I keep finding myself resorting to floating-point and lots
of conversions. But I'm not really showing any integer
ability. Better way?
union object *o = (union object *)n; n+=(int)ceil((double)sizeof*o/sizeof*n);

If you're worried about the speed of this, I don't think it will be a
problem as the whole thing should be reduced to a compile-time constant.
(Depending on compiler, but even gcc -O0 managed that on a similar
expression.)

Not the speed per se, but the parsimony. In earlier
postings about this barely-functional lisp chicken-
scratch, I tried to explain that chief of the goals
for the code was to be *axiomatic*. To conjure its
own internal universe by separating the memory region
beneath from the memory region above, placing an
integer array firmly in the middle.

So, bringing in the math library for 1 function used
exactly 4 times was ... unparsimonious.

[Richard Heathfield]

On 13/02/15 05:56, luser droog wrote:

<parsimonious snip ("parsnip" for short)>

Post by luser droog
So, bringing in the math library for 1 function used
exactly 4 times was ... unparsimonious.

Good word, parsimony. And it's a good concept, too. Not dragging extra
cruft into the system just for the sake of it, or even if there /is/
some short-term nebulous advantage to it. This is why computers don't
have tail fins. It's also why RISC is such a pleasing idea.

[BGB]

Post by Richard Heathfield
<parsimonious snip ("parsnip" for short)>

Post by luser droog
So, bringing in the math library for 1 function used
exactly 4 times was ... unparsimonious.

Good word, parsimony. And it's a good concept, too. Not dragging extra
cruft into the system just for the sake of it, or even if there /is/
some short-term nebulous advantage to it. This is why computers don't
have tail fins. It's also why RISC is such a pleasing idea.

the big drawback of typical RISCs (such as ARM) though is that it
doesn't make the compiler or assembler machinery any nicer (actually,
these are generally turned into more of a mess, as dealing with
immediate, memory addresses/offsets, ... is made a lot more complicated
in-general), and to compete well with modern CISC processors (such as
x86) on the performance front (say, executing multiple instructions per
clock, ...), they need most of the same basic complexities on the
hardware end.


so, it is debatable if there is any real advantage at this point for
RISC over a "well designed" CISC, say, if someone were to design a
processor using a scaled-up (32 or 64-bit) version of an ISA like the
one from the MSP430 micro-controllers.

this ISA is vaguely RISC like in terms of encoding, however:
many instructions can directly perform operations with memory operands;
instructions can use additional instruction words for things like
immediate values and similar (like, this amazing thing: don't need to
deal with needing to have a table within a +/- 2k-word window to be able
to deal with immediate values and memory addresses, and the consequent
addition of hidden jumps over these tables when they need to be stuck in
the middle of the instruction-stream to avoid being out-of-range, ...).


but, yeah, a RISC could be ok if it allows easily/efficiently working
with memory variables and supports the ability to easily get immediate
values loaded into registers, ...

even a convenient two-part load instruction could work (where a pair of
instructions is used to load an immediate which is split into multiple
parts).


or such...

[Keith Thompson]

Post by Richard Heathfield
<parsimonious snip ("parsnip" for short)>

Post by luser droog
So, bringing in the math library for 1 function used
exactly 4 times was ... unparsimonious.

Good word, parsimony. And it's a good concept, too. Not dragging extra
cruft into the system just for the sake of it, or even if there /is/
some short-term nebulous advantage to it. This is why computers don't
have tail fins. It's also why RISC is such a pleasing idea.

And now I have a sudden urge to add tail fins to my computer.

[Richard Bos]

Post by Keith Thompson

Post by Richard Heathfield
Good word, parsimony. And it's a good concept, too. Not dragging extra
cruft into the system just for the sake of it, or even if there /is/
some short-term nebulous advantage to it. This is why computers don't
have tail fins. It's also why RISC is such a pleasing idea.

And now I have a sudden urge to add tail fins to my computer.

I _do_ have tail fins on my internet router. I suspect they're there to
hide the wireless antennae, but I must admit my first thought was
"Oldsmobile".

Richard

[luser droog]

Post by Richard Heathfield
<parsimonious snip ("parsnip" for short)>

I retconned the 'Piggy' part, but 'Pasternak' really
does mean Parsnip.

[Kaz Kylheku]

Post by luser droog
I keep finding myself resorting to floating-point and lots
of conversions. But I'm not really showing any integer
ability. Better way?
union object *o = (union object *)n;
n+=(int)ceil((double)sizeof*o/sizeof*n);

If you want to know how many N-cell units are enough to hold
something that requires M cells:

(M + N - 1) / N [slash is round-toward-zero integer division]
[N is at least 2]

Proof:

For any given positive integer M, there is an integer k in the range
[0, N) such that M + k is evenly divisible by N.

This k represents the number of cells of padding we need to completely fill the
last partially filled N-cell unit, if it is partially filled.

The number of N-cells required to hold M is (M + k) / N.

Obviously if M is already divisible by N, then that is a situation
in where k = 0, and (M + k)/N = M/N: M does not have to be padded;
it is already divisible by the cell size N.

We can rewrite the formula to be proven in terms of M + k, like this:

(M + k - k + N - 1) / N [ + k - k cancels to zero ]

And of course this is:

(M + k) / N + (N - k - 1) / N

But note that k is in the range [0, N). This means that
(N - k) is in the range [1, N], and (N - k - 1) is in the
range [0, N). Which means that (N - k - 1)/N is necessarily zero,
since the numerator is nonnegative, and strictly less than N.

So the formula reduces to:

(M + k) / N

which, we already noted earlier, is the number of N-cells required to hold M.

[Richard Heathfield]

Post by Kaz Kylheku

Post by luser droog
I keep finding myself resorting to floating-point and lots
of conversions. But I'm not really showing any integer
ability. Better way?
union object *o = (union object *)n;
n+=(int)ceil((double)sizeof*o/sizeof*n);

If you want to know how many N-cell units are enough to hold
(M + N - 1) / N [slash is round-toward-zero integer division]
[N is at least 2]

Why the qualification?

Let N = 1

The expression is now:

(M + 1 - 1) / 1, which is M, which is exactly how many 1-cell units you
need to hold something that requires M cells.

I do, however, foresee a potential difficulty with N = 0. ;-)

[Tim Rentsch]

Post by luser droog
I keep finding myself resorting to floating-point and lots
of conversions. But I'm not really showing any integer
ability. Better way?
union object *o = (union object *)n; n+=(int)ceil((double)sizeof*o/sizeof*n);

To get a/b rounded up (ie, towards positive infinity):

if a>0 and b>0 : 1 + (a-1)/b

if b>0 : a/b + (a%b > 0)

if b<0 : a/b + (a%b < 0)

(combine the previous two if the sign of b is not known)

These should work for all values of a and b under
the respective stated conditions, including C90
rules for division and remainder.