a rand array

[August Derleth]

Okay, maybe 14 years of C programming experience vs. zero for C++ is the
real reason but I still think it's weird.

I think most C programmers can pick up a C++ subset fairly easily, if they
have a good book. "Thinking in C++ 2nd Edition" by Bruce Eckel is, in my
view, one such book. It's available free online (although you need to
download the compressed (.zip) archive, and it's not browsable online).

http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html

(C++ subsets well, in my opinion. You can approach it from a purely non-OO
view and leverage its typechecking, Standard Template Library, and great,
standardized package of pre-defined algorithms. Eckel calls this the
"Better C" aspect of C++, but you don't need to agree. ;-) Or, if you do
want OO, you don't need to use overloading or multiple inheritance.)

 

[James Kanze]

|> On Fri, 21 May 2004 17:58:42 +0000, Mark A. Odell wrote:

|> > Okay, maybe 14 years of C programming experience vs. zero for C++
|> > is the real reason but I still think it's weird.

|> I think most C programmers can pick up a C++ subset fairly easily,
|> if they have a good book.

I think that most good C programmers are already writing a C++ subset.
The actual incompatibilities in the common subset are fairly minor, and
most of C90 is in the common subset.

 

[Sam Dennis]

I think that most good C programmers are already writing a C++ subset.

So, for example, most good C programmers cast the return value of malloc
and friends, do they?

Good C programmers know enough not to care that their code won't compile
(or will function differently) when given to a C++ compiler. It is also
possible to write C programs that function identically if taken as other
languages that are much more distantly related to C than C++, but no-one
is suggesting that writing for, say, FORTRAN compatibility (this one may
not be possible, but that's not the point) is a good practice.

....I am having a little trouble finding an example of this in a language
other than C++ for completely portable C but I can say with considerable
confidence that it should be possible with Befunge for many tasks.

 

[RoSsIaCrIiLoIA]

How?

if( a==0 || size<2 || superiore<=size)
return;

if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a == a[j]) goto label;

Infinite loop if superiore < size. (wouldn't be fatal if it were
documented)

Yes I have seen it

balle

this is syntax error

It is very clear in this way too
Thank to everyone

 

[RoSsIaCrIiLoIA]

On Fri, 21 May 2004, josh wrote:
seems to me I take O(N*N/2)

O(N*N/2) is O(N^2) because it only differs by a constant factor. (the k
above swallows the /2)

How?

lower_bound = minimum;
upper_bound = maximum - number_of_slots;
for (index=0; index<number_of_slots; ++index)
{
a[index] = random_in_range(lower_bound, upper_bound);
lower_bound = a[index]+1;
++upper_bound;
}

I don't understand, but that seems to me like this

void
ordinator( unsigned* a, unsigned size, unsigned sup_val)
{static int i = 1;
unsigned j, k, h;
/*---------------------*/
if( a==0 || size<2 || sup_val<=size )
return;
if(i)
{i = 0; srand(time(0));}
h = sup_val/size;
for( j = 0; j<size; ++j)
a[j] = j*h + (unsigned) _lrand() % h;
}

or if one has a massive use of array 'a' it is possible
1) write an ordered array 'a' with an algorithm O(N^2)
label:
2) use the partition in 'a' to build a new array 'a' [O(N)]
goto label;

 

[RoSsIaCrIiLoIA]

No. It doesn't compile; if you're going to post code here, take the
time to cut-and-paste the actual code that you've compiled and
executed. The main program is gratuitously written in a different
language which is off-topic in this newsgroup. The sorting algorithm
appears to be Bubblesort or something similar; you might save some
time for small arrays by avoiding the overhead of qsort(), but it's
going to be extraordinarily inefficient for large arrays. It uses a
non-standard function called "_lrand()" without indicating what it is,
or how it differs from the standard "rand()". It assumes that the
value 80000000 will fit in an unsigned int.

It's not worth my time to figure out what else might be wrong with it.

I don't say it is perfect

 

[josh]

It should be possible to get a sorted array of random distinct integers
in time O(N),

How?

lower_bound = minimum;
upper_bound = maximum - number_of_slots;
for (index=0; index<number_of_slots; ++index)
{
a[index] = random_in_range(lower_bound, upper_bound);
lower_bound = a[index]+1;
++upper_bound;
}

I don't understand, but that seems to me like this

The requirement for a sorted array is that a is greater than a[i-1]
and less than a[i+1]. In addition, you are requiring that all of these
numbers be in [0, sup_val). (or in [minimum, maximum) above)

When you fill in a[0], there are no other numbers in the array to
constrain it, so you can choose any number in [0, sup_val). Except this
isn't true: if you select sup_val-1, there is no number you can pick for
a[1] that is greater than sup_val-1 and still in [0, sup_val). In an
array of N integers, there will be N-1 that need to be greater than
a[0], so a[0] must be in [0, sup_val-(N-1)). With integers we can
simplify this to [0, sup_val-N], including the upper bound.

So a[0] must be chosen in [0, sup_val-N]

Next we choose a[1], which must be greater than a[0] and still leave
room for all the rest of the array. Since there are 1 fewer integers
above a[0] than above a[1], we can just bump the upper bound by 1.

So a[1] must be chosen in [a[0]+1, sup_val-N+1]

We then continue at each step by taking the previous value as a lower
bound and increasing the upper bound by 1:

a[2] must be in [a[1]+1, sup_val-N+2]
a[3] must be in [a[2]+1, sup_val-N+3]
a[4] must be in [a[3]+1, sup_val-N+4]
....
a[N-2] must be in [a[N-3]+1, sup_val-2]
a[N-1] must be in [a[N-2]+1, sup_val-1]
(and of course there is no a[N])

So in general, a must be chosen in [a[i-1]+1, sup_val-N+i]:

a[o] = random_in_range(0, sup_val-N);
for (i=1; i<N; ++i)
a = random_in_range(a[i-1]+1, sup_val-N+i);

and the code above should do exactly the same thing.

void
ordinator( unsigned* a, unsigned size, unsigned sup_val)
{static int i = 1;
unsigned j, k, h;
/*---------------------*/
if( a==0 || size<2 || sup_val<=size )
return;
if(i)
{i = 0; srand(time(0));}
h = sup_val/size;
for( j = 0; j<size; ++j)
a[j] = j*h + (unsigned) _lrand() % h;
}

Not quite, this doesn't allow a[0] its full range. (or any of them
really) There are some sequences that a "generate random numbers and
sort" agorithm could generate that this algorithm cannot. Mine can
generate all of them, although I suspect the probability distribution
may be different.

or if one has a massive use of array 'a' it is possible
1) write an ordered array 'a' with an algorithm O(N^2)
label:
2) use the partition in 'a' to build a new array 'a' [O(N)]
goto label;

Not sure what you mean here... (sounds like it'd still be at least O(N^2)?)

If you have room for M bits (where M = sup_val) you can use a bin sort,
which runs in time O(N+M):

for (i=0; i<N; ++i)
{
do
{
value = random_in_range(0, M-1);
} while(is_bit_set(value));

set_bit(value);
}
i=0;
for (j=0; j<M; ++j)
{
if (is_bit_set(j))
a[i++] = j;
}

But since M is much larger than N in your test, I doubt this would be
feasable.

-josh

 

[Keith Thompson]

So, for example, most good C programmers cast the return value of malloc
and friends, do they?

Good C programmers know enough not to care that their code won't compile
(or will function differently) when given to a C++ compiler.

[...]

With some rare exceptions. P.J. Plauger has stated here that he
actually has good reasons to write and distribute code that will
compiler either as C or as C++.

For most of us, however, worrying about whether our C code will
compile as C++ is a waste of time.

 

[Christian Bau]

So, for example, most good C programmers cast the return value of malloc
and friends, do they?

Good C programmers know enough not to care that their code won't compile
(or will function differently) when given to a C++ compiler.

[...]

With some rare exceptions. P.J. Plauger has stated here that he
actually has good reasons to write and distribute code that will
compiler either as C or as C++.

For most of us, however, worrying about whether our C code will
compile as C++ is a waste of time.

One situation where you really want to make sure that your C code is
valid C++ with identical semantics: If you decide to move development
from C to C++ (that is change your code base from C to C++ and then
continue developing in C++), then changing your C code to the common
subset of C and C++ is an obvious first step.

The other situation is that of a library developer who wants lets say
valid C code, C++ code and Java code with the same functionality
(because customers demand all three versions). By using the common
subset of C and C++, he/she needs to write two different versions only
instead of three.

 

[James Kanze]

|> James Kanze wrote:
|> > I think that most good C programmers are already writing a C++
|> > subset.

|> So, for example, most good C programmers cast the return value of
|> malloc and friends, do they?

Good point. There are probably a few other exceptions as well.

|> Good C programmers know enough not to care that their code won't
|> compile (or will function differently) when given to a C++ compiler.

I didn't say the contrary. On the other hand, the code written by good
C programmers will port quickly and easily to C++. It won't resemble
what is commonly called "idiomatic C++", but it will be correct,
compilable C++. The differences in semantics are minimal, and for the
most part, the features of C90 not available in C++ (like implicite
declaration of functions) are not considered good C either.

|> It is also possible to write C programs that function identically if
|> taken as other languages that are much more distantly related to C
|> than C++, but no-one is suggesting that writing for, say, FORTRAN
|> compatibility (this one may not be possible, but that's not the
|> point) is a good practice.

I'm not suggesting that targetting compatibility is good practice. I'm
saying that if you follow good C coding practices, you won't be far from
what is already legal C++.

 

[James Kanze]

|> > James Kanze wrote:
|> > > I think that most good C programmers are already writing a C++
|> > > subset.

|> > So, for example, most good C programmers cast the return value of
|> > malloc and friends, do they?
|> > Good C programmers know enough not to care that their code won't
|> > compile (or will function differently) when given to a C++
|> > compiler.

|> [...]

|> With some rare exceptions. P.J. Plauger has stated here that he
|> actually has good reasons to write and distribute code that will
|> compiler either as C or as C++.

|> For most of us, however, worrying about whether our C code will
|> compile as C++ is a waste of time.

The one exception might be header files and interfaces -- it is actually
fairly frequent to use the same header file for C and C++.

 

[unknown]

E. Robert Tisdale wrote:

- snip -

I use Mozilla to read news.
I can kill threads
but I don't know how to kill individual subscribers.

Get your self a good riflefile.

 

[Grumble]

I use Mozilla to read news.
I can kill threads
but I don't know how to kill individual subscribers.
Can you tell me how to do this with Mozilla?
How would I killfile "Default User" for example?
Or do I need to get a different newsreader?
What newsreader are you using?
And what did you do to killfile "RoSsIaCrIiLoIA"?

Tools - Message Filters

Sender contains "Default User"

Action = Mark read or Delete or ...

 

[Dan Pop]

I use Mozilla to read news.
I can kill threads

You can do more than that.

but I don't know how to kill individual subscribers.
Can you tell me how to do this with Mozilla?

When setting the filter, click on "Subject" and a new menu will open.
Select "Sender" instead of "Subject".

Yeah, it could be more intuitive...

I use a text-based newsreader that doesn't attempt to be anything else but
a newsreader and that does an excellent job of that.

Dan

 

[Michael Wojcik]

One situation where you really want to make sure that your C code is
valid C++ with identical semantics: If you decide to move development
from C to C++ (that is change your code base from C to C++ and then
continue developing in C++), then changing your C code to the common
subset of C and C++ is an obvious first step.

I'm not sure I agree. If I were changing the language a project was
written in, I think that ought to include proper redesign. There
might well be significant reuse of the old C code in the new C++
implementation, but simply rewriting the code in the "common subset"
and recompiling strikes me as a very bad idea indeed.

I don't believe good C code is generally good C++ code. When
switching from one to the other, a rewrite is in order. (Yes, it
would be quicker to simply force the C into some shape that the C++
compiler would accept. That's the sort of reasoning which has
produced the current miserable state of most software.)

--
Michael Wojcik (e-mail address removed)

Pocket #9: A complete "artificial glen" with rocks, and artificial moon,
and forester's station. Excellent for achieving the effect of the
sublime without going out-of-doors. -- Joe Green

 

[Dan Pop]

I think most C programmers can pick up a C++ subset fairly easily, if they
have a good book.

Yup: the subset shared by the two languages ;-)

Dan

 

[Dan Pop]

So, for example, most good C programmers cast the return value of malloc
and friends, do they?

Let's put back the text you've abusively removed from James' post, in
order to make your cheap shot:

The actual incompatibilities in the common subset are fairly minor,
and most of C90 is in the common subset.

Did he or did he not *explicitly* aknowledge the existence of
incompatibilities? Or do you consider the void pointer issue involved in
your example as a *major* incompatibility?

To amend the original statement: most good C programmers are already
capable of writing in a C++ subset. The good question is whether such
code counts as *good* C++ code?...

Dan

 

[Mabden]

In <[email protected]> "E. Robert Tisdale"

You can do more than that.

Ooooh! Ooooh! Pick me! Pick me!

 

[Michael Wojcik]

[snip]

value = (unsigned)rand()/(RAND_MAX/NUM_ELEMENTS);

for (loop=1; loop<NUM_ELEMENTS; loop++)
{
array[loop] = value;
value += (unsigned)rand()/(RAND_MAX/NUM_ELEMENTS);
}

Unsorted and you don't fill array[0].

array[0] is not set, true; but barring overflow that looks sorted to
me. value increases (or remains the same) on each loop iteration.

 

[RoSsIaCrIiLoIA]

It should be possible to get a sorted array of random distinct integers
in time O(N),

How?

lower_bound = minimum;
upper_bound = maximum - number_of_slots;
for (index=0; index<number_of_slots; ++index)
{
a[index] = random_in_range(lower_bound, upper_bound);
lower_bound = a[index]+1;
++upper_bound;
}

I don't understand, but that seems to me like this

The requirement for a sorted array is that a is greater than a[i-1] [...]
So a[0] must be chosen in [0, sup_val-N]

Next we choose a[1], which must be greater than a[0] and still leave
room for all the rest of the array. Since there are 1 fewer integers
above a[0] than above a[1], we can just bump the upper bound by 1.

So a[1] must be chosen in [a[0]+1, sup_val-N+1]

We then continue at each step by taking the previous value as a lower
bound and increasing the upper bound by 1:

a[2] must be in [a[1]+1, sup_val-N+2]
a[3] must be in [a[2]+1, sup_val-N+3]
a[4] must be in [a[3]+1, sup_val-N+4]
...
a[N-2] must be in [a[N-3]+1, sup_val-2]
a[N-1] must be in [a[N-2]+1, sup_val-1]
(and of course there is no a[N])

So in general, a must be chosen in [a[i-1]+1, sup_val-N+i]:

a[o] = random_in_range(0, sup_val-N);
for (i=1; i<N; ++i)
a = random_in_range(a[i-1]+1, sup_val-N+i);

and the code above should do exactly the same thing. [...]
Mine can
generate all of them, although I suspect the probability distribution
may be different.

thank you
but seems to me there are odd results e.g.
if rand_array is like you suggest =>

inserisci il massimo[0 finisce]> 888888888
inserisci il numero di elementi> 20
312557105 548251158 760618515 876091816 886173925 888503572 888804673
888826177
888871515 888882642 888884513 888885725 888887085 888888029 888888553
888888700
888888768 888888843 888888873 888888877
inserisci il massimo[0 finisce]> 0

rand_array1 seems 'ok'
inserisci il massimo[0 finisce]> 99
inserisci il numero di elementi> 98
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
26 27 28 29
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
53 54 55 5
6 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
80 81 82
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
inserisci il massimo[0 finisce]> 300
inserisci il numero di elementi> 50
4 5 6 11 17 24 25 29 44 47 58 60 63 70 82 85 94 98 99 103 108 120 127
130 132 1
43 150 151 165 166 167 176 191 192 195 201 210 214 216 230 233 245 246
248 263 2
64 272 274 275 277
inserisci il massimo[0 finisce]> 300
inserisci il numero di elementi> 50
1 4 8 10 22 25 31 40 47 49 52 53 54 67 77 86 87 92 105 113 114 119
128 133 136
142 146 147 163 166 173 184 191 197 203 207 215 218 223 232 234 241
242 254 256
263 269 274 280 281
inserisci il massimo[0 finisce]> 8888888
inserisci il numero di elementi> 10
539728 635645 1238316 1973567 2832166 2844598 4184902 5806132 6061761
7364582
inserisci il massimo[0 finisce]> 0

/* C++ and C but you use a C++ compiler and try ... */
#include <iostream.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define U unsigned
#define F for
#define W while
#define R return
#define os cout <<
#define is cin >>

int
BogusRandArray( U* a, U size, U max_val)
{static int i = 1;
unsigned j, t, m1;
double m, u;
/*---------------------*/
if( a==0 || size<2 || max_val<=size )
return 0;
if(i)
{i = 0; srand(time(0));}

m = (double) UINT_MAX/(size+1); m1 = m;
a[0] = (U) _lrand() % m1;
for( j = 1; j<size; ++j)
a[j] = a[j - 1] + 1 + (U) _lrand() % m1;
if(a[size - 1] > max_val)
{
m = (double) max_val/ size; m1 = m;
u = (double)(size - 1) * m + (double)((U) _lrand() % m1);
/* os "u==" << u << "(size)*m=" << (size)*m; */
u = ( (double) a[size - 1] / u );
for( j = 0, t = 0; j<size; ++j)
{
a[j] = (double) a[j] / u;
if(a[j] <= t && j!=0)
++a[j];
t = a[j];
}
}
return 1;
}



U rand_array( U* a, U size, U sup_val )
{static int i = 1;
unsigned j, k, h;
/*---------------------*/
if( a==0 || size<2 || sup_val<=size )
return 0;
if(i)
{i = 0; srand(time(0));}

h = sup_val - size;
a[0] = (U) _lrand() % h;

for( j = 1; j<size; ++j)
a[j] = a[j-1] + 1 + (U) _lrand() % (h - a[j-1]-1 + j);
R 1;
}


U intervallo(U a, U b)
{R a + (U) _lrand() % (b-a);}

U rand_array1( U* a, U size, U sup_val )
{static int i = 1;
unsigned j, k, h;
/*---------------------*/
if( a==0 || size<2 || sup_val<=size )
return 0;
if(i)
{i = 0; srand(time(0));}

k = sup_val / size;
a[0] = (k<=1 ? 0 : (U) _lrand() % k);

for( j = 1; j<size; ++j)
a[j] =
(a[j-1]+1 >= (h=j*k)
? a[j-1] + 1
: intervallo( a[j-1] + 1, h)
);
R 1;
}



/* it is a c++ main */
int main(void)
{U a[100] = {0}, i, j=1, k, z;
/*--------------------------------*/
W(j!=0)
{
os "inserisci il massimo[0 finisce]> "; is j;
if(j==0) break;
os "inserisci il numero di elementi> "; is k;
if(k>100) {os "Troppi elementi\n";continue;}
z = rand_array1( a, k, j);
if(z)
{
F( i = 0; i<k; ++i)
os " " << a;
os "\n";
}
else os "Errore\n";
}
R 0;
}