Programming Puzzle

[Kai-Uwe Bux]

#include "card_t.h" /* This is part of the program, NOT the
#implementation*/ define DECKSIZE 52
...
int i,j;
card_t deck[DECKSIZE];

/* bogo-shuffle the cards */
for (i = 0; i < DECKSIZE; i++) {
for (j = 0; j < DECKSIZE; j++) {
/*
* DO NOT CHANGE THE LINE OF CODE BELOW.
* Note: rand() % 2 is used here because it is
* a poor random number generator in many
* implementations, and if it isn't possible to
* cheat, *THEY* will break your legs repeatedly
* and cut off your supply of semicolons.
*/
if (rand() % 2) {
swap(&deck, &deck[j]);
}
}
}

Hi,

I apologize, for this might not be the topic of this thread, however I feel
compelled to comment on this bogo-shuffle: is that taken from a text on how
*not* to generate a random permutation?

a) The use of rand() % 2 is bad. In a different thread I came across a
random number generator that would produce a strictly alternating sequence
of bits when used this way. The funny comment indicates that the author was
acutally aware of this shortcoming.

b) The method has quadratic runtime in DECKSIZE. Clearly a random-shuffle
can and should be done in linear time.

c) Finally, even with a perfect random number generator, this method is
guaranteed *not* to give equal probabilities to the different permutations.
For small DECKSIZE, the difference is even noticable.


Best

Kai-Uwe

 

[Risto Lankinen]

Please describe a situation where two variables share the same memory
location.

There is a doubly-linked-list algorithm that uses the same
memory location for both forward and backward pointers.
They are stored as XORred, and given the address of an
anchor node, the chain of nodes can be traversed at either
direction.

- Risto -

 

[Risto Lankinen]

You are right about that, however in reality a decent swap
implementation would check if the passed arguments have the same value
so as to avoid unneeded operations.

There are some algorithms for which the check itself is
an unneeded operation (i.e. which can be proved to be
"correct by construction") become inefficient if the swap
function itself makes such a redundant check. Various
sort algorithms belong to this category, because it is a
characteristic of the sort algorithm [and not a safety net
of swap] to compare items before swapping.

But then there are also some algorithms for which the
check is - if perhaps not redundant - but inefficient as
long as the swap preserves original value in the case of
self-swap.

[I know it's easy to code "more correctly", but] one such
algorithm would be string reversal which might be coded
so that the middle element will be "swapped" with itself
just before the algorithm tests for the termination. Then
you don't need to make an extra check every time before
entering the loop - you just enter the loop every time and
let it do the "right thing" even with strings of length one.

More examples can be found from permutation generation
algorithms, where a straightforward algorithm might benefit
from not having to make the check every time, even given
the cost of occasional self-swap.

- Risto -

 

[Risto Lankinen]

That said, I would not place the equality/inequality check for the
possibility of the same variable passed in mind, but for efficiency.

Whoa!

Without check you have (assuming the temp var is in reg):

R = read memory * 2
W = write memory * 2

With check you have:

R = read memory * 2
C = compare registers
W = write memory * 2 * (1-p) where p = probability of match

For the equality-checking version to be more efficient you have...

C + W*2*(1-p) < W*2 => p > C/(W*2)

In other words, the probability of [arguments-have-the-same
value] should be higher than the ratio of the [comparison-cost]
and the [cost-of-two-writes]. I would guess that in most cases
comparing the arguments is really a pessimization...

Note that some systems can execute the writes in parallel,
and that a write and a compare both can be executed in one
cycle -> p = 1/1 which is a certain non-optimization. Also
note that the cost of the jump (which can be optimized away
if swap is a stand-alone function, but typically can not if it is
an inline function) has not even been factored in yet.

This is a micro-optimization at its finest!

- Risto -

 

[Risto Lankinen]

c) Finally, even with a perfect random number generator, this method is
guaranteed *not* to give equal probabilities to the different

permutations.

However, given a suitably non-perfect random number generator, it
can be made so.

Offtopic: Given an unfair coin with p = p(Heads), find 'p' such that an
evenly distributed three-way choice can be made with a finite number
of tosses.

- Risto -

 

[JKop]

Ioannis Vranos posted:

template<class T>
void swap(T &a, T &b)
{
if(a!=b)
{
// ...
}
}

Depends if you want a shallow swap or a deep swap. With my own template, I
was going for a shallow swap. Not how your example makes use of the !=
operator of the class, while mine doesn't even need a definiton of the class
at all. Then again, yours is probably a deep swap.

-JKop

 

[Joona I Palaste]

JKop <[email protected]> scribbled the following

Ioannis Vranos posted:

Depends if you want a shallow swap or a deep swap. With my own template, I
was going for a shallow swap. Not how your example makes use of the !=
operator of the class, while mine doesn't even need a definiton of the class
at all. Then again, yours is probably a deep swap.

If you're going to talk about C++-specific features, then please stop
crossposting to comp.lang.c. Thanks.

--
/-- Joona Palaste ([email protected]) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"A bee could, in effect, gather its junk. Llamas (no poor quadripeds) tune
and vow excitedly zooming."
- JIPsoft

 

[JKop]

Joona I Palaste posted:

JKop <[email protected]> scribbled the following



If you're going to talk about C++-specific features, then please stop
crossposting to comp.lang.c. Thanks.

Did I crosspost? According to my newsreader I'm only posting to
comp.lang.c++

-JKop

 

[Dan Pop]

In C90 a return statement is required, in C99 it is not.

Nope, in C90 a return statement is NOT required. Please restrict
yourself to topics you have a clue about.

Dan

 

[Dan Pop]

C:\TEMP>type test.c
#include <stdio.h>

int main(void) {
int *foo = NULL;

fprintf(stdout, "%i\n", *foo);
}


C:\TEMP>cl -c test.c
Microsoft (R) C/C++ Optimizing Compiler Version 8.00c
Copyright (c) Microsoft Corp 1984-1993. All rights reserved.

test.c
test.c(7) : warning C4035: 'main' : no return value

What part of "chapter and verse" was too difficult for you to understand?
Free clue: the C programming language is not defined by the behaviour of
one compiler or another.

Dan

 

[Dan Pop]

You are right about that, however in reality a decent swap
implementation would check if the passed arguments have the same value
so as to avoid unneeded operations.

I have pointed this out myself, upthread. No need to repeat what I have
already said.

Dan

 

[Dan Pop]

I think the non-temporary requirement is not for space concerns but to
find out how c00l we are.

As usual, your thinking abilities are severely limited.

Even under severe space concerns there is
always space for a *temporary* variable. If there are space concerns to
the extreme, then we should write numbers in its memory directly.

Imagine that the universal swap function has the following interface:

void swap(void *p, void *q, size_t size);

What are you going to do if malloc(size) fails?

Dan

 

[Dan Pop]

JKop <[email protected]> scribbled the following
on comp.lang.c:
Am I the only person here that thinks it's complete bullshit to think you
can swap the values of two variables without a temporary variable?! It ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[snip]
And the only good reason I can imagine is the failure to allocate memory
for a temporary object (some objects can be greater than others, some

^^^^^^^^^^^^^^^^^^

Your answer is completely irrelevant. ;-)

To comp.lang.c++: sorry I didn't notice the cross-post at
the beginning. You can safely ignore my out-of-context reply.
What my post really amounts to is a (rather subtle) critique of
Dan Pop's lack of clarity in the replied-to post. [It took me
three to four readings to get his logic!] ^^^^^^^^^^^

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Which doesn't necessarily mean lack of clarity in my message ;-)
Especially considering that you were the only one to complain!

Dan

 

[Dan Pop]

However in C++98 I did not find anything else than this:


5.12 Bitwise exclusive OR operator

exclusive-or-expression:
and-expression
exclusive-or-expression ^ and-expression

The usual arithmetic conversions are performed; the result is the
bitwise exclusive OR function of the operands. The operator applies only
to integral or enumeration operands."

This is also what C99 says about the ^ operator itself. OTOH, it is
downright foolishness to imagine that, if this text doesn't mention the
possibility, it can't happen: my own example involved *other* parts of
the C99 standard.

Note that I don't know whether this can be an issue in C++, my answer
was *explicity* related to C99, this thread being crossposted. In C90,
the ^ operator is always OK on signed operands, it is only refinements
introduced by C99 that create the theoretical possibility of invoking
undefined behaviour.

Dan

 

[Alex Fraser]

Consider, for example, 0 ^ 0, whose result (an int with all bits set)

[...]

*cough*

Alex

 

[Ioannis Vranos]

Imagine that the universal swap function has the following interface:

void swap(void *p, void *q, size_t size);

What are you going to do if malloc(size) fails?

That is not much universal in my C++ world, since for non-POD types such
a generic function would invoke undefined behaviour.

For POD types, I would use a char/unsigned char array of fixed size (or
VLA in your world) or a char/unsigned char in the extreme, if malloc()
family failed.






Regards,

Ioannis Vranos

 

[Ioannis Vranos]

This is also what C99 says about the ^ operator itself. OTOH, it is
downright foolishness to imagine that, if this text doesn't mention the
possibility, it can't happen: my own example involved *other* parts of
the C99 standard.

Note that I don't know whether this can be an issue in C++, my answer
was *explicity* related to C99, this thread being crossposted. In C90,
the ^ operator is always OK on signed operands, it is only refinements
introduced by C99 that create the theoretical possibility of invoking
undefined behaviour.

Ok, in C++98 in the other parts XOR operator is mentioned, is inside
some tables about keyword alternatives and keyword summaries.






Regards,

Ioannis Vranos

 

[Dan Pop]

Consider, for example, 0 ^ 0, whose result (an int with all bits set)

[...]

*cough*

Indeed! A first class brain fart...

Dan

 

[pete]

Consider, for example, 0 ^ 0, whose result (an int with all bits set)

[...]

*cough*

Indeed! A first class brain fart...

(a ^ -a) is negative zero, on implementations
which have a representation for negative zero.

 

[Dan Pop]

Ok, in C++98 in the other parts XOR operator is mentioned, is inside
some tables about keyword alternatives and keyword summaries.

You're really dense if you don't realise that the issue is NOT specific
to the XOR operator, therefore it doesn't make much sense to grep the
standard for the XOR operator.

If the standard supports the concept of trap representation for the
signed integer types (without *necessarily* involving padding bits),
*any* bitwise operator can generate a trap representation (given the
"right" operands).

If the C++ standard doesn't have such features, expect them after its
first major revision ;-)

Dan