Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3285 > unrolled thread

Compare two methods of random permutations

Back to article view | Back to comp.programming

Contents

  Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-08 23:35 +0200
    Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-11 21:31 -0700
      Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 08:07 +0200
        Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-13 02:34 -0700
    Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 08:01 +0200
    Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-13 08:26 -0700
      Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-13 11:42 -0700
        Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-16 13:46 -0700
      Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 21:09 +0200
        Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-13 12:57 -0700
          Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 22:59 +0200
            Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-13 15:28 -0700
              Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-14 10:54 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-14 05:32 -0700
                  Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-14 22:46 +0200
                    Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-14 14:19 -0700
                      Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-14 15:06 -0700
                        Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-15 10:16 +0200
                          Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-15 03:54 -0700
                        Re: Compare two methods of random permutations Patricia Shanahan <pats@acm.org> - 2013-05-15 07:11 -0700
                          Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-15 11:04 -0700
                            Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-15 11:06 -0700
                            Re: Compare two methods of random permutations Patricia Shanahan <pats@acm.org> - 2013-05-15 12:55 -0700
                            Re: Compare two methods of random permutations "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-05-16 06:10 +0100
                              Re: Compare two methods of random permutations pacman@kosh.dhis.org (Alan Curry) - 2013-05-16 06:57 +0000
                                Re: Compare two methods of random permutations "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-05-16 09:26 +0100
                              Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-16 01:35 -0700
                                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-17 14:11 +0200
                                  Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-17 08:13 -0700
                                    Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 11:06 +0200
                                      Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 03:14 -0700
                                        Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 13:26 +0200
                                          Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 04:59 -0700
                                            Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 14:13 +0200
                                              Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 05:52 -0700
                                                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 15:06 +0200
                                                  Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 06:50 -0700
                                                    Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 16:14 +0200
                                                      Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 08:11 -0700
                                                        Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 17:15 +0200
                                                        Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 17:24 +0200

Page 1 of 3  [1] 2 3  Next page →

#3285 — Compare two methods of random permutations

I want to compare in a practical sense two methods of random
permutations -- one theoretically perfect, namely that of Fisher and
Yates, and another ad hoc, let's call it X. A way of comparison I could
think of is the following:

One starts from the standard configuration of n objects [0, 1, 2,
...., n-1] and apply each method a fairly large number of times
successively to permute them and each time one computes the Hamming
distance of the result from the standard configuaration. One obtains
thus the frequency distribution of the Hamming distances for each
method. If the frequency distributions are fairly comparable to each
other, then X could be practically employed in place of the
theoretically perfect one.

Is this line of thought of mine correct? Does anyone have an idea of
a better method of comparison? Thanks in advance.

M. K. Shen

[toc] | [next] | [standalone]

#3288

On May 9, 4:35 am, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
> I want to compare in a practical sense two methods of random
> permutations -- one theoretically perfect, namely that of Fisher and
> Yates, and another ad hoc ...

No one answered yet, so let me take a stab at a possible approach.

Pick a small set size, perhaps 9 or 10.  Do the shuffle several
million times, preparing a histogram for the 9! (or 10!) possible
results. Prepare a histogram of the population counts in the 1st
histogram; calculate its statistical moments. Compare said
moments with the theoretically perfect moments.

James

[toc] | [prev] | [next] | [standalone]

#3290

Please kindly take a look of my computational results reported
in the thread in sci.stat.math (08.05.2013 11:29).

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#3291

On May 13, 1:07 pm, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
> Please kindly take a look of my computational results reported
> in the thread in sci.stat.math (08.05.2013 11:29).
>
> M. K. Shen

Not to nitpick, but this is why Usenet has the concept of
posting to multiple groups.  You don't create two different
threads and then add posts referencing one to the other.  ::whack::
You put two newsgroups on the Newsgroups line,
separated by a comma.

There are newbie groups to explain this further and help
you get started on Usenet.

James

[toc] | [prev] | [next] | [standalone]

#3289

Am 08.05.2013 23:35, schrieb Mok-Kong Shen:
>
> I want to compare in a practical sense two methods of random
[snip]

The OP was also posted to sci.stat.math (08.05.2013 11:29). There
have been some discussions, with one post of mine containing
certain computational results of mine. Please kindly take a
look there.

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#3292

On Wednesday, May 8, 2013 4:35:18 PM UTC-5, Mok-Kong Shen wrote:
> I want to compare in a practical sense two methods of random
> 
> permutations -- one theoretically perfect, namely that of Fisher and
> 
> Yates, and another ad hoc, let's call it X. A way of comparison I could
> 
> think of is the following:
> 
> 
> 
> One starts from the standard configuration of n objects [0, 1, 2,
> 
> ...., n-1] and apply each method a fairly large number of times
> 
> successively to permute them and each time one computes the Hamming
> 
> distance of the result from the standard configuaration. One obtains
> 
> thus the frequency distribution of the Hamming distances for each
> 
> method. If the frequency distributions are fairly comparable to each
> 
> other, then X could be practically employed in place of the
> 
> theoretically perfect one.
> 
> 
> 
> Is this line of thought of mine correct? Does anyone have an idea of
> 
> a better method of comparison? Thanks in advance.
> 
> 
> 
> M. K. Shen

Why would you not use the method of random permutation that is theoretically perfect?  Isn't it pretty much trivial to implement and not very hard to understand?

You basically have a vector of stuff.

Then you pick one random item from the vector.

Make it the first in the new list.

Remove it from the vector.

Pick another random item from the vector.

Make it the second in the new list.

Remove it from the vector.

Repeat until your initial vector is empty.

Thanks.

[toc] | [prev] | [next] | [standalone]

#3296

On May 13, 10:26 pm, bob <b...@coolfone.comze.com> wrote:
> On Wednesday, May 8, 2013 4:35:18 PM UTC-5, Mok-Kong Shen wrote:
> > I want to compare in a practical sense two methods of random
>
> Why would you not use the method of random permutation that is theoretically perfect?  Isn't it pretty much trivial to implement and not very hard to understand?

Good question.  I'm going to guess he's worried about speed,
but still don't know how expects to improve on Fisher shuffle,
which only needs 51 small random integers for a 52-card deck.

Perhaps he doesn't know that you can get several independent
small integers from a single random-number, e.g. to get a
12-permutation from a 31-bit random:

        int     a, b;
        do a = rand();
        while (a >= 1916006400);
        b = a % 12; a /= 12; doshufstep(12, b);
        b = a % 11; a /= 11; doshufstep(11, b);
        b = a % 10; a /= 10; doshufstep(10, b);
        b = a %  9; a /=  9; doshufstep( 9, b);
        b = a %  8; a /=  8; doshufstep( 8, b);
        b = a %  7; a /=  7; doshufstep( 7, b);
        b = a %  6; a /=  6; doshufstep( 6, b);
        b = a %  5; a /=  5; doshufstep( 5, b);
        b = a %  4; a /=  4; doshufstep( 4, b);
        b = a %  3; a /=  3; doshufstep( 3, b);
        b = a %  2; a /=  2; doshufstep( 2, b);

(A good compiler will remember the quotient
after doing the modulus.)

IIRC, I explained this to someone with a name
similar to OP's last decade.

James

[toc] | [prev] | [next] | [standalone]

#3322

On Monday, May 13, 2013 1:42:30 PM UTC-5, James Dow Allen wrote:
> On May 13, 10:26 pm, bob <b...@coolfone.comze.com> wrote:
> 
> > On Wednesday, May 8, 2013 4:35:18 PM UTC-5, Mok-Kong Shen wrote:
> 
> > > I want to compare in a practical sense two methods of random
> 
> >
> 
> > Why would you not use the method of random permutation that is theoretically perfect?  Isn't it pretty much trivial to implement and not very hard to understand?
> 
> 
> 
> Good question.  I'm going to guess he's worried about speed,
> 
> but still don't know how expects to improve on Fisher shuffle,
> 
> which only needs 51 small random integers for a 52-card deck.
> 
> 
> 
> Perhaps he doesn't know that you can get several independent
> 
> small integers from a single random-number, e.g. to get a
> 
> 12-permutation from a 31-bit random:
> 
> 
> 
>         int     a, b;
> 
>         do a = rand();
> 
>         while (a >= 1916006400);
> 
>         b = a % 12; a /= 12; doshufstep(12, b);
> 
>         b = a % 11; a /= 11; doshufstep(11, b);
> 
>         b = a % 10; a /= 10; doshufstep(10, b);
> 
>         b = a %  9; a /=  9; doshufstep( 9, b);
> 
>         b = a %  8; a /=  8; doshufstep( 8, b);
> 
>         b = a %  7; a /=  7; doshufstep( 7, b);
> 
>         b = a %  6; a /=  6; doshufstep( 6, b);
> 
>         b = a %  5; a /=  5; doshufstep( 5, b);
> 
>         b = a %  4; a /=  4; doshufstep( 4, b);
> 
>         b = a %  3; a /=  3; doshufstep( 3, b);
> 
>         b = a %  2; a /=  2; doshufstep( 2, b);
> 
> 
> 
> (A good compiler will remember the quotient
> 
> after doing the modulus.)
> 
> 
> 
> IIRC, I explained this to someone with a name
> 
> similar to OP's last decade.
> 
> 
> 
> James

I think what you are talking about is called "permutation unranking".

Basically, you take a number (a rank), and you use some math to convert it to a permutation.  Each rank corresponds to a unique permutation.

Thanks.

[toc] | [prev] | [next] | [standalone]

#3298

Am 13.05.2013 17:26, schrieb bob:
> Why would you not use the method of random permutation that is
> theoretically perfect?

It was my fault that I din't cross-post to 2 groups (thus I later
requested you to kindly look up there). I explained in sci.stat.math
my motivation as follows (note also that n=52 is only an example case):

...... In particular I don't need to
generate the whole range of possible permutations but on the other hand
a not too limited small range. Consider the case n=52, one knows that
in-shuffle and out-shuffle have periods of 52 and 8 respectively, which
are negligibly small compared to the whole range (of size (52!)). On the
other hand, the method of Fisher and Yates needs n-1 (pseudo-)random
numbers. In one of my applications a couple of such random numbers are
already available for other reasons, so it would certainly be
conveninent and advantageous, if I could just use them for doing random
permutation without having to invoke a PRNG to acquire the n-1 random
numbers needed for F&Y. This was the motivation of my OP and, as it
turns out, my scheme runs also much faster than F&Y as reported further
below.

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#3300

On Monday, May 13, 2013 2:09:36 PM UTC-5, Mok-Kong Shen wrote:
> Am 13.05.2013 17:26, schrieb bob:
> 
> > Why would you not use the method of random permutation that is
> 
> > theoretically perfect?
> 
> 
> 
> It was my fault that I din't cross-post to 2 groups (thus I later
> 
> requested you to kindly look up there). I explained in sci.stat.math
> 
> my motivation as follows (note also that n=52 is only an example case):
> 
> 
> 
> ...... In particular I don't need to
> 
> generate the whole range of possible permutations but on the other hand
> 
> a not too limited small range. Consider the case n=52, one knows that
> 
> in-shuffle and out-shuffle have periods of 52 and 8 respectively, which
> 
> are negligibly small compared to the whole range (of size (52!)). On the
> 
> other hand, the method of Fisher and Yates needs n-1 (pseudo-)random
> 
> numbers. In one of my applications a couple of such random numbers are
> 
> already available for other reasons, so it would certainly be
> 
> conveninent and advantageous, if I could just use them for doing random
> 
> permutation without having to invoke a PRNG to acquire the n-1 random
> 
> numbers needed for F&Y. This was the motivation of my OP and, as it
> 
> turns out, my scheme runs also much faster than F&Y as reported further
> 
> below.
> 
> 
> 
> M. K. Shen

I think you may be overestimating the computational expense of creating pseudo-random numbers.  In general, it is not that expensive as this code from Java shows:

    /**
     * Returns a pseudo-random uniformly distributed {@code int} value of
     * the number of bits specified by the argument {@code bits} as
     * described by Donald E. Knuth in <i>The Art of Computer Programming,
     * Volume 2: Seminumerical Algorithms</i>, section 3.2.1.
     *
     * <p>Most applications will want to use one of this class' convenience methods instead.
     */
    protected synchronized int next(int bits) {
        seed = (seed * multiplier + 0xbL) & ((1L << 48) - 1);
        return (int) (seed >>> (48 - bits));
    }



Thanks.

[toc] | [prev] | [next] | [standalone]

#3301

Am 13.05.2013 21:57, schrieb bob:
> On Monday, May 13, 2013 2:09:36 PM UTC-5, Mok-Kong Shen wrote:
>> Am 13.05.2013 17:26, schrieb bob:
>>
>>> Why would you not use the method of random permutation that is
>>
>>> theoretically perfect?
>>
>>
>>
>> It was my fault that I din't cross-post to 2 groups (thus I later
>>
>> requested you to kindly look up there). I explained in sci.stat.math
>>
>> my motivation as follows (note also that n=52 is only an example case):
>>
>>
>>
>> ...... In particular I don't need to
>>
>> generate the whole range of possible permutations but on the other hand
>>
>> a not too limited small range. Consider the case n=52, one knows that
>>
>> in-shuffle and out-shuffle have periods of 52 and 8 respectively, which
>>
>> are negligibly small compared to the whole range (of size (52!)). On the
>>
>> other hand, the method of Fisher and Yates needs n-1 (pseudo-)random
>>
>> numbers. In one of my applications a couple of such random numbers are
>>
>> already available for other reasons, so it would certainly be
>>
>> conveninent and advantageous, if I could just use them for doing random
>>
>> permutation without having to invoke a PRNG to acquire the n-1 random
>>
>> numbers needed for F&Y. This was the motivation of my OP and, as it
>>
>> turns out, my scheme runs also much faster than F&Y as reported further
>>
>> below.
>>
>>
>>
>> M. K. Shen
>
> I think you may be overestimating the computational expense of creating pseudo-random numbers.  In general, it is not that expensive as this code from Java shows:
>
>      /**
>       * Returns a pseudo-random uniformly distributed {@code int} value of
>       * the number of bits specified by the argument {@code bits} as
>       * described by Donald E. Knuth in <i>The Art of Computer Programming,
>       * Volume 2: Seminumerical Algorithms</i>, section 3.2.1.
>       *
>       * <p>Most applications will want to use one of this class' convenience methods instead.
>       */
>      protected synchronized int next(int bits) {
>          seed = (seed * multiplier + 0xbL) & ((1L << 48) - 1);
>          return (int) (seed >>> (48 - bits));
>      }

There are of course lots of fast PRNGs, but how good these are
is not always clear. Anyway, I believe that for large n, the
efficiency issue may be something worthy of consideration.

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#3302

On Monday, May 13, 2013 3:59:30 PM UTC-5, Mok-Kong Shen wrote:
> Am 13.05.2013 21:57, schrieb bob:
> 
> > On Monday, May 13, 2013 2:09:36 PM UTC-5, Mok-Kong Shen wrote:
> 
> >> Am 13.05.2013 17:26, schrieb bob:
> 
> >>
> 
> >>> Why would you not use the method of random permutation that is
> 
> >>
> 
> >>> theoretically perfect?
> 
> >>
> 
> >>
> 
> >>
> 
> >> It was my fault that I din't cross-post to 2 groups (thus I later
> 
> >>
> 
> >> requested you to kindly look up there). I explained in sci.stat.math
> 
> >>
> 
> >> my motivation as follows (note also that n=52 is only an example case):
> 
> >>
> 
> >>
> 
> >>
> 
> >> ...... In particular I don't need to
> 
> >>
> 
> >> generate the whole range of possible permutations but on the other hand
> 
> >>
> 
> >> a not too limited small range. Consider the case n=52, one knows that
> 
> >>
> 
> >> in-shuffle and out-shuffle have periods of 52 and 8 respectively, which
> 
> >>
> 
> >> are negligibly small compared to the whole range (of size (52!)). On the
> 
> >>
> 
> >> other hand, the method of Fisher and Yates needs n-1 (pseudo-)random
> 
> >>
> 
> >> numbers. In one of my applications a couple of such random numbers are
> 
> >>
> 
> >> already available for other reasons, so it would certainly be
> 
> >>
> 
> >> conveninent and advantageous, if I could just use them for doing random
> 
> >>
> 
> >> permutation without having to invoke a PRNG to acquire the n-1 random
> 
> >>
> 
> >> numbers needed for F&Y. This was the motivation of my OP and, as it
> 
> >>
> 
> >> turns out, my scheme runs also much faster than F&Y as reported further
> 
> >>
> 
> >> below.
> 
> >>
> 
> >>
> 
> >>
> 
> >> M. K. Shen
> 
> >
> 
> > I think you may be overestimating the computational expense of creating pseudo-random numbers.  In general, it is not that expensive as this code from Java shows:
> 
> >
> 
> >      /**
> 
> >       * Returns a pseudo-random uniformly distributed {@code int} value of
> 
> >       * the number of bits specified by the argument {@code bits} as
> 
> >       * described by Donald E. Knuth in <i>The Art of Computer Programming,
> 
> >       * Volume 2: Seminumerical Algorithms</i>, section 3.2.1.
> 
> >       *
> 
> >       * <p>Most applications will want to use one of this class' convenience methods instead.
> 
> >       */
> 
> >      protected synchronized int next(int bits) {
> 
> >          seed = (seed * multiplier + 0xbL) & ((1L << 48) - 1);
> 
> >          return (int) (seed >>> (48 - bits));
> 
> >      }
> 
> 
> 
> There are of course lots of fast PRNGs, but how good these are
> 
> is not always clear. Anyway, I believe that for large n, the
> 
> efficiency issue may be something worthy of consideration.
> 
> 
> 
> M. K. Shen

If you want to learn more about how well different PRNG algorithms work, you may want to read the book

Seminumerical Algorithms

by Donald Knuth.

Here's an outline of it:

Chapter 3 – Random Numbers

    3.1. Introduction
    3.2. Generating Uniform Random Numbers
        3.2.1. The Linear Congruential Method
            3.2.1.1. Choice of modulus
            3.2.1.2. Choice of multiplier
            3.2.1.3. Potency
        3.2.2. Other Methods
    3.3. Statistical Tests
        3.3.1. General Test Procedures for Studying Random Data
        3.3.2. Empirical Tests
        3.3.3. Theoretical Tests
        3.3.4. The Spectral Test
    3.4. Other Types of Random Quantities
        3.4.1. Numerical Distributions
        3.4.2. Random Sampling and Shuffling
    3.5. What Is a Random Sequence?
    3.6. Summary


(from http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming)

Thanks.

[toc] | [prev] | [next] | [standalone]

#3303

Am 14.05.2013 00:28, schrieb bob:

> If you want to learn more about how well different PRNG algorithms work,
 > you may want to read the book Seminumerical Algorithms
> by Donald Knuth.
[snip]

It's nice that you post the reference. I am in possession of that
great book since over a decade. I am interested in the topic of
PRN generation and has myself attempted to design PRNGs several times.
Recently I designed one, which is the function genrandom() that is
contained in my encryption software source code named JADE
(http://s13.zetaboards.com/Crypto/topic/6948465/1/#new). I should
be very grateful, if interested readers of this group would kindly
look at that PRNG and eventually give me comments and critiques.
(My email address above is a valid one.)

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#3304

On May 14, 3:54 pm, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
> be very grateful, if interested readers of this group would kindly

Would be delighted to chit-chat.
When are you going to acknowledge my code fragment
which demonstrates finding a perfect random 12-permutation
with a single call to random()?
A 52-permutation can be formed from eight 32-bit randoms.

James

[toc] | [prev] | [next] | [standalone]

#3305

Am 14.05.2013 14:32, schrieb James Dow Allen:
> On May 14, 3:54 pm, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
>> be very grateful, if interested readers of this group would kindly
>
> Would be delighted to chit-chat.
> When are you going to acknowledge my code fragment
> which demonstrates finding a perfect random 12-permutation
> with a single call to random()?
> A 52-permutation can be formed from eight 32-bit randoms.

I am confused. In which follow-up did you mention your code?

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#3306

On May 15, 3:46 am, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
> I am confused. In which follow-up did you mention your code?

Message-ID: <33a7d2bf-c504-471a-
b79e-93da93ef9e69@oy9g2000pbb.googlegroups.com>

https://groups.google.com/group/comp.programming/msg/38c32bb27f26201a?dmode=source

James

[toc] | [prev] | [next] | [standalone]

#3307

On May 15, 4:19 am, James Dow Allen <jdallen2...@yahoo.com> wrote:
> On May 15, 3:46 am, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
>
> > I am confused. In which follow-up did you mention your code?
> https://groups.google.com/group/comp.programming/msg/38c32bb27f26201a...
>
> James

And, the reason I've been brusque or snippy in this thread is that
I EXPLAINED THIS TO YOU FOUR YEARS AGO, with you refusing to
take a few seconds to understand it.
https://groups.google.com/group/comp.programming/msg/da8573d12cad698f?dmode=source

You claimed then the method didn't work.
You were wrong then.  You're still wrong.
Shall be bet money?

James

[toc] | [prev] | [next] | [standalone]

#3308

Am 15.05.2013 00:06, schrieb James Dow Allen:
> On May 15, 4:19 am, James Dow Allen <jdallen2...@yahoo.com> wrote:
>> On May 15, 3:46 am, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
>>
>>> I am confused. In which follow-up did you mention your code?
>> https://groups.google.com/group/comp.programming/msg/38c32bb27f26201a...
>>
>> James
>
> And, the reason I've been brusque or snippy in this thread is that
> I EXPLAINED THIS TO YOU FOUR YEARS AGO, with you refusing to
> take a few seconds to understand it.
> https://groups.google.com/group/comp.programming/msg/da8573d12cad698f?dmode=source
>
> You claimed then the method didn't work.
> You were wrong then.  You're still wrong.
> Shall be bet money?

Oh, you should have provided a tiny little bit of context when
referring to matters 4 years ago! I'll look at the matter again.
Please give me 10 day time, ok?

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#3309

On May 15, 3:16 pm, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:

> Oh, you should have provided a tiny little bit of context when
> referring to matters 4 years ago! I'll look at the matter again.
> Please give me 10 day time, ok?

Fine.  But just to clear up one more of your confusions:
The code snippet in question which I linked to just now,
WAS POSTED JUST A FEW HOURS AGO; it wasn't
from the 4-years-ago thread.

James

[toc] | [prev] | [next] | [standalone]

#3310

On 5/14/2013 3:06 PM, James Dow Allen wrote:
> On May 15, 4:19 am, James Dow Allen <jdallen2...@yahoo.com> wrote:
>> On May 15, 3:46 am, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
>>
>>> I am confused. In which follow-up did you mention your code?
>> https://groups.google.com/group/comp.programming/msg/38c32bb27f26201a...
>>
>> James
>
> And, the reason I've been brusque or snippy in this thread is that
> I EXPLAINED THIS TO YOU FOUR YEARS AGO, with you refusing to
> take a few seconds to understand it.
> https://groups.google.com/group/comp.programming/msg/da8573d12cad698f?dmode=source
>
> You claimed then the method didn't work.
> You were wrong then.  You're still wrong.
> Shall be bet money?

The objection back then was "Anyway, I doubt the usefulness of % here,
since, if t is uniformly distributed in [0, n-1], then for m<n the
values t mod m wouldn't be uniformly distributed in [0, m-1]
in general, if I don't err."

That seems to me to be a good point. Suppose, for example that n is 16,
and m is 7. The results of the % for each value of t are:

0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4
5 -> 5
6 -> 6
7 -> 0
8 -> 1
9 -> 2
10 -> 3
11 -> 4
12 -> 5
13 -> 6
14 -> 0
15 -> 1

Three inputs map to each of 0 and 1, but only two inputs map to each of
the other values. If t were uniformly distributed over [0,15] then t%7
would not be uniformly distributed.

The % method does work correctly if m is a factor of n.

java.util.Random contains code to correct for this effect in its
nextInt(int).

Patricia

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.programming

csiph-web