Extreme Efficiency for Odd/Even

[Frederick Gotham]

I'm trying to write extremely efficient, fully portable algorithms to
determine if an integer is odd or even. The most basic algorithms would be:

#define IS_ODD(x) ((x) % 2)

#define IS_EVEN(x) (!((x) % 2))

Attempting to make them slightly more efficient, we could change them to:

#define IS_ODD(x) ((x) & 1)

#define IS_EVEN(x) (!((x) & 1))

(Yes, some compilers may actually compile the former into the latter, but
we're playing the efficiency game here.)

Only thing though:-
The latter two will malfunction on One's Complement systems when
dealing with negative numbers. Thus, I have the following code... I'd
appreciate any comments or suggestions. No changes are required for Sign-
magnitude or for Two's Complement, but we must improvise for One's
Complement. Here we go:

#define SIGNMAG 0
#define ONES 1
#define TWOS 2

#if -1 & 3 == 1
#define NUMSYS SIGNMAG
#elif -1 & 3 == 2
#define NUMSYS ONES
#else
#define NUMSYS TWOS
#endif

#if NUMSYS != ONES
#define IS_ODD(x) ((x) & 1)
#define IS_EVEN(x) (!((x) & 1))
#else
#define ONE_IF_NEGATIVE(x) ((x) < 0)

#define IS_ODD(x) ( !((x) & 1) == ONE_IF_NEGATIVE((x)) )
#define IS_EVEN(x) ( !((x) & 1) != ONE_IF_NEGATIVE((x)) )
#endif

Unfortunately though, the One's Complement version evaluates the argument
twice.

Yes, I realise that the smart thing would probably just be to write "x %
2" and forget about it, but this is more for kicks than anything else.

 

[Michal Nazarewicz]

I'm trying to write extremely efficient, fully portable algorithms to
determine if an integer is odd or even. [cut]
#if -1 & 3 == 1

I'm not really sure if you can assume that preprocessor uses the same
arithmetic as the program will use itself. What if you are compiling
a program for one architecture on another - like compiling for ix86
(which is two's complement) on some one's complement system.

[one's compelment version:]

#define ONE_IF_NEGATIVE(x) ((x) < 0)
#define IS_ODD(x) ( !((x) & 1) == ONE_IF_NEGATIVE((x)) )
#define IS_EVEN(x) ( !((x) & 1) != ONE_IF_NEGATIVE((x)) )

#v+
#define IS_ODD(x) ((x) % 2)
#define IS_EVEN(x) (!IS_ODD(x))
#v-

Would probably be faster anyway.

Yes, I realise that the smart thing would probably just be to write "x %
2" and forget about it, but this is more for kicks than anything else.

If you really want portability you should stick to '% 2' version and
let compiler do the optimization.

 

[Steffen Buehler]

#define IS_ODD(x) ((x) % 2)

Would probably be faster anyway.

It's been a long time I optimized code for speed, but wouldn't

#define IS_ODD(x) ((x) & 1)

be even faster? Doesn't modulo always require a time-consuming division
(if the compiler isn't clever enough to handle modulo 2 differently)?

Regards
Steffen

 

[Guest]

I'm trying to write extremely efficient, fully portable algorithms to
determine if an integer is odd or even. [cut]
#if -1 & 3 == 1

I'm not really sure if you can assume that preprocessor uses the same
arithmetic as the program will use itself. What if you are compiling
a program for one architecture on another - like compiling for ix86
(which is two's complement) on some one's complement system.

In C99, that's a safe assumption. Preprocessor arithmetic is done (as
if) in the target's (u)intmax_t types. IIRC C99 changed the rules for
that, though, so it may not be safe in C89.

 

[Michal Nazarewicz]

It's been a long time I optimized code for speed, but wouldn't

#define IS_ODD(x) ((x) & 1)

be even faster? Doesn't modulo always require a time-consuming division
(if the compiler isn't clever enough to handle modulo 2 differently)?

It would but won't work in one's complement arithmetic and I was
referring to IS_ODD, IS_EVEN macros defined for such arithmetic.

(The other thing is that compiler is free to optimize the code in such
a way that AND instruction will be used in both cases if appropriate)

 

[Frederick Gotham]

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:

In C99, that's a safe assumption. Preprocessor arithmetic is done (as
if) in the target's (u)intmax_t types. IIRC C99 changed the rules for
that, though, so it may not be safe in C89.

In this any site on the internet which explains how preprocessor arithmetic
works and so forth?

 

[Guest]

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:

In this any site on the internet which explains how preprocessor arithmetic
works and so forth?

I'm not aware of one, but for C99 it's quite simple. There are
effectively only two types during preprocessor arithmetic: a signed
one, and an unsigned one. Everything has the same width and
representation, and they must match those of the target's intmax_t and
uintmax_t types.

 

[Kenny McCormack]

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:



In this any site on the internet which explains how preprocessor arithmetic
works and so forth?

No, it isn't. It is a Usenet newsgroup.

 

[mark]

I'm trying to write extremely efficient, fully portable algorithms to
determine if an integer is odd or even. The most basic algorithms would be:

#define IS_ODD(x) ((x) % 2)

#define IS_EVEN(x) (!((x) % 2))

Attempting to make them slightly more efficient, we could change them to:

#define IS_ODD(x) ((x) & 1)

#define IS_EVEN(x) (!((x) & 1))

(Yes, some compilers may actually compile the former into the latter, but
we're playing the efficiency game here.)

Only thing though:-
The latter two will malfunction on One's Complement systems when
dealing with negative numbers. Thus, I have the following code... I'd
appreciate any comments or suggestions. No changes are required for Sign-
magnitude or for Two's Complement, but we must improvise for One's
Complement. Here we go:

#define SIGNMAG 0
#define ONES 1
#define TWOS 2

#if -1 & 3 == 1
#define NUMSYS SIGNMAG
#elif -1 & 3 == 2
#define NUMSYS ONES
#else
#define NUMSYS TWOS
#endif

#if NUMSYS != ONES
#define IS_ODD(x) ((x) & 1)
#define IS_EVEN(x) (!((x) & 1))
#else
#define ONE_IF_NEGATIVE(x) ((x) < 0)

#define IS_ODD(x) ( !((x) & 1) == ONE_IF_NEGATIVE((x)) )
#define IS_EVEN(x) ( !((x) & 1) != ONE_IF_NEGATIVE((x)) )
#endif

Whats wrong with

#define IS_ODD(x) ((unsigned)(x) & 1)

Mark Williams

 

[Frederick Gotham]

mark posted:

Whats wrong with

#define IS_ODD(x) ((unsigned)(x) & 1)

Let's test it.

If we try it with an expression of type "int" whose value is -5, then we
get:

(unsigned)-5 & 1

which is equivalent to:

(unsigned)UINT_MAX - (5-1) & 1

which, for 16-Bit int's would be:

65535U - (5-1) & 1

65531 & 1

which would register as an odd number.

Looks good. Only thing though, I wonder if the machine would have to do any
processing in order to convert the -5 to an unsigned integer expression?

 

[Frederick Gotham]

Frederick Gotham posted:

65531 & 1

I should have written:

65531U & 1

 

[Peter Nilsson]

I'm trying to write extremely efficient, fully portable algorithms to
determine if an integer is odd or even. The most basic algorithms would be:

#define IS_ODD(x) ((x) % 2)

#define IS_EVEN(x) (!((x) % 2))

Attempting to make them slightly more efficient, we could change them to:

#define IS_ODD(x) ((x) & 1)

#define IS_EVEN(x) (!((x) & 1))

(Yes, some compilers may actually compile the former into the latter, but
we're playing the efficiency game here.)

If x is an unknown signed int, then many/most compilers _can't_ compile
the former to the latter. [Or at least not without additional checks.]

Note that x&1 produces 0 or 1, but x % 2 can produce -1, 0 or 1.

 

[Skarmander]

I'm trying to write extremely efficient, fully portable algorithms to
determine if an integer is odd or even. The most basic algorithms would be:

#define IS_ODD(x) ((x) % 2)

#define IS_EVEN(x) (!((x) % 2))

Attempting to make them slightly more efficient, we could change them to:

#define IS_ODD(x) ((x) & 1)

#define IS_EVEN(x) (!((x) & 1))

(Yes, some compilers may actually compile the former into the latter, but
we're playing the efficiency game here.)

If x is an unknown signed int, then many/most compilers _can't_ compile
the former to the latter. [Or at least not without additional checks.]

Note that x&1 produces 0 or 1, but x % 2 can produce -1, 0 or 1.

Which is mostly irrelevant, since IS_ODD(x) will typically be used as a
conditional expression. ((x) % 2) is equivalent to ((x) % 2) != 0 in those
circumstances, which always works.

I think you'll find compilers can optimize this quite nicely, and many will,
since parity testing is quite common and generic modulo is typically slow.

S.

 

[Peter Nilsson]

I'm trying to write extremely efficient, fully portable algorithms to
determine if an integer is odd or even. The most basic algorithms would be:

#define IS_ODD(x) ((x) % 2)

#define IS_EVEN(x) (!((x) % 2))

Attempting to make them slightly more efficient, we could change them to:

#define IS_ODD(x) ((x) & 1)

#define IS_EVEN(x) (!((x) & 1))

(Yes, some compilers may actually compile the former into the latter, but
we're playing the efficiency game here.)

If x is an unknown signed int, then many/most compilers _can't_ compile
the former to the latter. [Or at least not without additional checks.]

Note that x&1 produces 0 or 1, but x % 2 can produce -1, 0 or 1.

Which is mostly irrelevant, since IS_ODD(x) will typically be used as a
conditional expression. ((x) % 2) is equivalent to ((x) % 2) != 0 in those
circumstances, which always works.

You're ignoring the disease because you _think_ the symptoms are
trivial.
In C, the symptoms of bugs may be subtle, but they are rarely trivial.

I think you'll find compilers can optimize this quite nicely, and many will,
since parity testing is quite common and generic modulo is typically slow.

Which just reinforces the reasons behind just using % in the first
place...

#define IS_ODD(x) ((x) % 2 != 0)
#define IS_EVEN(x) ((x) % 2 == 0)

 

[Skarmander]

Frederick Gotham wrote:
I'm trying to write extremely efficient, fully portable algorithms to
determine if an integer is odd or even. The most basic algorithms would be:

#define IS_ODD(x) ((x) % 2)

#define IS_EVEN(x) (!((x) % 2))

Attempting to make them slightly more efficient, we could change them to:

#define IS_ODD(x) ((x) & 1)

#define IS_EVEN(x) (!((x) & 1))

(Yes, some compilers may actually compile the former into the latter, but
we're playing the efficiency game here.)
If x is an unknown signed int, then many/most compilers _can't_ compile
the former to the latter. [Or at least not without additional checks.]

Note that x&1 produces 0 or 1, but x % 2 can produce -1, 0 or 1.

Which is mostly irrelevant, since IS_ODD(x) will typically be used as a
conditional expression. ((x) % 2) is equivalent to ((x) % 2) != 0 in those
circumstances, which always works.

You're ignoring the disease because you _think_ the symptoms are
trivial.
In C, the symptoms of bugs may be subtle, but they are rarely trivial.

Oh, come on. You know the fix already, which is to add the test to *force*
this expression to always be a conditional expression. Do you really think
I'm advocating leaving it as-is? I for one hate crypto-conditional
expressions (doing it for pointers is one thing, but non-boolean integral
expressions are right out), so I would have added the test even if I had
*not* been aware of the subtlety, and I would have avoided a potential
source of bugs in the process.

There's no "disease" here, just an expression that might not do what you
think it does. If that's a disease, then C is positively plague-ridden. My
comment was intended to specifically criticize your rather spurious "the
compiler can't compile this like that" angle. In those cases where the
expression evaluates to what you expect it evaluates, the compiler can
certainly do this and probably will. In those cases where the expression
doesn't evaluate to what you think it evaluates, what the compiler does to
it doesn't matter.

We are in agreement; I just think you pointed out the issue in a misleading way.

S.

 

[Skarmander]

mark posted:



Let's test it.

Better yet, let's think about it.

If we try it with an expression of type "int" whose value is -5, then we
get:

<snip>
The type of the expression is irrelevant (well, as long as it's integral, of
course). "If the new type is unsigned, the value is converted by repeatedly
adding or subtracting one more than the maximum value that can be
represented in the new type until the value is in the range of the new type."

In fact, not even the unsigned type is relevant; all that matters is that
its maximum value is odd, so that adding or subtracting one plus the maximum
value preserves parity. As luck would have it (well, not really), the
maximum values of unsigned types are always odd, since they're one less than
a power of two.

Looks good. Only thing though, I wonder if the machine would have to do any
processing in order to convert the -5 to an unsigned integer expression?

You don't know and probably shouldn't care. Aside from that, you're on the
wrong level. This expression passes the compiler first, and there's no
guarantee what it will actually to obtain the result. A smart compiler won't
generate instructions for explicit conversion if that's not the best
approach, but then again, a smart compiler would also handle "x % 2 != 0"
efficiently, so you're down to guessing.

That said, if you really have an aversion to "x % 2 != 0" on guessological
grounds, this alternative is about as good as it gets. It's certainly better
than the code you posted upthread for one's complement machines, which can
fail on -0 (and is less likely to be optimized well). The moral of that
story is to not construct clever solutions for simple problems; you just end
up with more problems.

S.

 

[pete]

Peter Nilsson wrote:

#define IS_ODD(x) ((x) % 2 != 0)

#define IS_EVEN(x) (!IS_ODD(x))

 

[pete]

Better yet, let's think about it.

<snip>
The type of the expression is irrelevant
(well, as long as it's integral, of course).
"If the new type is unsigned, the value is converted by repeatedly
adding or subtracting one more than the maximum value that can be
represented in the new type until the value is
in the range of the new type."

In fact, not even the unsigned type is relevant;
all that matters is that its maximum value is odd,
so that adding or subtracting one plus the maximum
value preserves parity. As luck would have it
(well, not really), the maximum values of unsigned types
are always odd, since they're one less than a power of two.

If INT_MIN equals (-INT_MAX - 1)
and UINT_MAX equals (2 * INT_MAX + 1)
then, -5 and (unsigned)-5,
have identical representations.

 

[pete]

If INT_MIN equals (-INT_MAX - 1)
and UINT_MAX equals (2 * INT_MAX + 1)

and UINT_MAX equals (2U * INT_MAX + 1)

 

[dcorbit]

I'm trying to write extremely efficient, fully portable algorithms to
determine if an integer is odd or even. The most basic algorithms would be:

#define IS_ODD(x) ((x) % 2)

#define IS_EVEN(x) (!((x) % 2))

Attempting to make them slightly more efficient, we could change them to:

#define IS_ODD(x) ((x) & 1)

#define IS_EVEN(x) (!((x) & 1))

1. Function macros are evil.
2. You are assuming two's complement.
http://groups.google.com/group/comp...27a8d?lnk=st&q=&rnum=3&hl=en#07979c1d11727a8d