You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@mahout.apache.org by Lance Norskog <go...@gmail.com> on 2011/02/20 02:51:44 UTC
A little programming challenge
What does this program print?
package hack;
import java.util.Random;
public class JDKRandomThreatOrMenace {
public static void main(String[] args) {
Random rnd = new Random(0);
double last = rnd.nextDouble();
long i = 1;
for(; i < Long.MAX_VALUE; i++) {
rnd.setSeed(i);
double next = rnd.nextDouble();
if (Math.abs(next - last) > 0.2)
break;
}
System.out.println(i);
}
}
Your prize if you get it right? A patch would be welcome...
Re: A little programming challenge
Posted by Ted Dunning <te...@gmail.com>.
Mahout has an implementation as well.
On Sunday, February 20, 2011, Dawid Weiss <da...@cs.put.poznan.pl> wrote:
> Ok, I get it. Ted's suggestion is probably something to follow --
> instead of seeding congruential random with a checksum of your vector
> (which I assume you did and caused values < 0.2) you can calculate a
> better checksum (and convert it to a double from bits directly?).
> MurmurHash is a good option, Andrzej Bialecki had an implementation
> for streaming checksums, HPPC has one for permuting primitive types:
>
> http://labs.carrotsearch.com/download/hppc/0.3.3/api/com/carrotsearch/hppc/hash/package-summary.html
>
> Dawid
>
> On Mon, Feb 21, 2011 at 4:08 AM, Ted Dunning <te...@gmail.com> wrote:
>> This is why we normally use prng's based on murmur hash for building
>> deterministic random vectors. Smutty and Jake can probably get you a
>> specific pointer before I get back to a real computer. Alternately
>> search for references to MurmurHash.
>>
>> On Sunday, February 20, 2011, Lance Norskog <go...@gmail.com> wrote:
>>> I discovered this when I wanted to make deterministic random vectors
>>> and matrices. To get the same result from each entry on every access,
>>> I can either cache the values or use an algorithm to recreate unique
>>> seed for that entry. I naively just added the coordinate to the base
>>> seed, and created very not-random vectors and matrices. Yes, the JDK
>>> Random is intended to be lame but fast., but this was just too far
>>> over the line.
>>>
>>> Lance
>>>
>>> On Sun, Feb 20, 2011 at 2:31 AM, Dawid Weiss
>>> <da...@cs.put.poznan.pl> wrote:
>>>> A perhaps better question is what are you trying to prove or what was
>>>> your original intention? :) This is a very strange program indeed --
>>>> what it does is basically check what the next double value from a
>>>> fixed initial seed is... since random uses a relatively simple
>>>> congruential algorithm, the result isn't really that surprising (to
>>>> me?).
>>>>
>>>> Dawid
>>>>
>>>> On Sun, Feb 20, 2011 at 2:51 AM, Lance Norskog <go...@gmail.com> wrote:
>>>>> What does this program print?
>>>>>
>>>>>
>>>>> package hack;
>>>>>
>>>>> import java.util.Random;
>>>>>
>>>>> public class JDKRandomThreatOrMenace {
>>>>>
>>>>> public static void main(String[] args) {
>>>>> Random rnd = new Random(0);
>>>>>
>>>>> double last = rnd.nextDouble();
>>>>> long i = 1;
>>>>> for(; i < Long.MAX_VALUE; i++) {
>>>>> rnd.setSeed(i);
>>>>> double next = rnd.nextDouble();
>>>>> if (Math.abs(next - last) > 0.2)
>>>>> break;
>>>>> }
>>>>> System.out.println(i);
>>>>> }
>>>>>
>>>>> }
>>>>>
>>>>> Your prize if you get it right? A patch would be welcome...
>>>>>
>>>>>
>>>>
>>>
>>>
>>>
>>> --
>>> Lance Norskog
>>> goksron@gmail.com
>>>
>>
>>
>
Re: A little programming challenge
Posted by Dawid Weiss <da...@cs.put.poznan.pl>.
Ok, I get it. Ted's suggestion is probably something to follow --
instead of seeding congruential random with a checksum of your vector
(which I assume you did and caused values < 0.2) you can calculate a
better checksum (and convert it to a double from bits directly?).
MurmurHash is a good option, Andrzej Bialecki had an implementation
for streaming checksums, HPPC has one for permuting primitive types:
http://labs.carrotsearch.com/download/hppc/0.3.3/api/com/carrotsearch/hppc/hash/package-summary.html
Dawid
On Mon, Feb 21, 2011 at 4:08 AM, Ted Dunning <te...@gmail.com> wrote:
> This is why we normally use prng's based on murmur hash for building
> deterministic random vectors. Smutty and Jake can probably get you a
> specific pointer before I get back to a real computer. Alternately
> search for references to MurmurHash.
>
> On Sunday, February 20, 2011, Lance Norskog <go...@gmail.com> wrote:
>> I discovered this when I wanted to make deterministic random vectors
>> and matrices. To get the same result from each entry on every access,
>> I can either cache the values or use an algorithm to recreate unique
>> seed for that entry. I naively just added the coordinate to the base
>> seed, and created very not-random vectors and matrices. Yes, the JDK
>> Random is intended to be lame but fast., but this was just too far
>> over the line.
>>
>> Lance
>>
>> On Sun, Feb 20, 2011 at 2:31 AM, Dawid Weiss
>> <da...@cs.put.poznan.pl> wrote:
>>> A perhaps better question is what are you trying to prove or what was
>>> your original intention? :) This is a very strange program indeed --
>>> what it does is basically check what the next double value from a
>>> fixed initial seed is... since random uses a relatively simple
>>> congruential algorithm, the result isn't really that surprising (to
>>> me?).
>>>
>>> Dawid
>>>
>>> On Sun, Feb 20, 2011 at 2:51 AM, Lance Norskog <go...@gmail.com> wrote:
>>>> What does this program print?
>>>>
>>>>
>>>> package hack;
>>>>
>>>> import java.util.Random;
>>>>
>>>> public class JDKRandomThreatOrMenace {
>>>>
>>>> public static void main(String[] args) {
>>>> Random rnd = new Random(0);
>>>>
>>>> double last = rnd.nextDouble();
>>>> long i = 1;
>>>> for(; i < Long.MAX_VALUE; i++) {
>>>> rnd.setSeed(i);
>>>> double next = rnd.nextDouble();
>>>> if (Math.abs(next - last) > 0.2)
>>>> break;
>>>> }
>>>> System.out.println(i);
>>>> }
>>>>
>>>> }
>>>>
>>>> Your prize if you get it right? A patch would be welcome...
>>>>
>>>>
>>>
>>
>>
>>
>> --
>> Lance Norskog
>> goksron@gmail.com
>>
>
>
Re: A little programming challenge
Posted by Ted Dunning <te...@gmail.com>.
This is why we normally use prng's based on murmur hash for building
deterministic random vectors. Smutty and Jake can probably get you a
specific pointer before I get back to a real computer. Alternately
search for references to MurmurHash.
On Sunday, February 20, 2011, Lance Norskog <go...@gmail.com> wrote:
> I discovered this when I wanted to make deterministic random vectors
> and matrices. To get the same result from each entry on every access,
> I can either cache the values or use an algorithm to recreate unique
> seed for that entry. I naively just added the coordinate to the base
> seed, and created very not-random vectors and matrices. Yes, the JDK
> Random is intended to be lame but fast., but this was just too far
> over the line.
>
> Lance
>
> On Sun, Feb 20, 2011 at 2:31 AM, Dawid Weiss
> <da...@cs.put.poznan.pl> wrote:
>> A perhaps better question is what are you trying to prove or what was
>> your original intention? :) This is a very strange program indeed --
>> what it does is basically check what the next double value from a
>> fixed initial seed is... since random uses a relatively simple
>> congruential algorithm, the result isn't really that surprising (to
>> me?).
>>
>> Dawid
>>
>> On Sun, Feb 20, 2011 at 2:51 AM, Lance Norskog <go...@gmail.com> wrote:
>>> What does this program print?
>>>
>>>
>>> package hack;
>>>
>>> import java.util.Random;
>>>
>>> public class JDKRandomThreatOrMenace {
>>>
>>> public static void main(String[] args) {
>>> Random rnd = new Random(0);
>>>
>>> double last = rnd.nextDouble();
>>> long i = 1;
>>> for(; i < Long.MAX_VALUE; i++) {
>>> rnd.setSeed(i);
>>> double next = rnd.nextDouble();
>>> if (Math.abs(next - last) > 0.2)
>>> break;
>>> }
>>> System.out.println(i);
>>> }
>>>
>>> }
>>>
>>> Your prize if you get it right? A patch would be welcome...
>>>
>>>
>>
>
>
>
> --
> Lance Norskog
> goksron@gmail.com
>
Re: A little programming challenge
Posted by Lance Norskog <go...@gmail.com>.
>From 0 to 2304, Random on seed N+1 produces a double that is less than
0.2 from the output of seed N (out of 0->1). The program hunts for the
first N where this is not true, which is 2304. This means the JDK
standard Random generator class is not all that random, which is
well-known.
On Sun, Feb 20, 2011 at 4:31 PM, Lance Norskog <go...@gmail.com> wrote:
> I discovered this when I wanted to make deterministic random vectors
> and matrices. To get the same result from each entry on every access,
> I can either cache the values or use an algorithm to recreate unique
> seed for that entry. I naively just added the coordinate to the base
> seed, and created very not-random vectors and matrices. Yes, the JDK
> Random is intended to be lame but fast., but this was just too far
> over the line.
>
> Lance
>
> On Sun, Feb 20, 2011 at 2:31 AM, Dawid Weiss
> <da...@cs.put.poznan.pl> wrote:
>> A perhaps better question is what are you trying to prove or what was
>> your original intention? :) This is a very strange program indeed --
>> what it does is basically check what the next double value from a
>> fixed initial seed is... since random uses a relatively simple
>> congruential algorithm, the result isn't really that surprising (to
>> me?).
>>
>> Dawid
>>
>> On Sun, Feb 20, 2011 at 2:51 AM, Lance Norskog <go...@gmail.com> wrote:
>>> What does this program print?
>>>
>>>
>>> package hack;
>>>
>>> import java.util.Random;
>>>
>>> public class JDKRandomThreatOrMenace {
>>>
>>> public static void main(String[] args) {
>>> Random rnd = new Random(0);
>>>
>>> double last = rnd.nextDouble();
>>> long i = 1;
>>> for(; i < Long.MAX_VALUE; i++) {
>>> rnd.setSeed(i);
>>> double next = rnd.nextDouble();
>>> if (Math.abs(next - last) > 0.2)
>>> break;
>>> }
>>> System.out.println(i);
>>> }
>>>
>>> }
>>>
>>> Your prize if you get it right? A patch would be welcome...
>>>
>>>
>>
>
>
>
> --
> Lance Norskog
> goksron@gmail.com
>
--
Lance Norskog
goksron@gmail.com
Re: A little programming challenge
Posted by Lance Norskog <go...@gmail.com>.
I discovered this when I wanted to make deterministic random vectors
and matrices. To get the same result from each entry on every access,
I can either cache the values or use an algorithm to recreate unique
seed for that entry. I naively just added the coordinate to the base
seed, and created very not-random vectors and matrices. Yes, the JDK
Random is intended to be lame but fast., but this was just too far
over the line.
Lance
On Sun, Feb 20, 2011 at 2:31 AM, Dawid Weiss
<da...@cs.put.poznan.pl> wrote:
> A perhaps better question is what are you trying to prove or what was
> your original intention? :) This is a very strange program indeed --
> what it does is basically check what the next double value from a
> fixed initial seed is... since random uses a relatively simple
> congruential algorithm, the result isn't really that surprising (to
> me?).
>
> Dawid
>
> On Sun, Feb 20, 2011 at 2:51 AM, Lance Norskog <go...@gmail.com> wrote:
>> What does this program print?
>>
>>
>> package hack;
>>
>> import java.util.Random;
>>
>> public class JDKRandomThreatOrMenace {
>>
>> public static void main(String[] args) {
>> Random rnd = new Random(0);
>>
>> double last = rnd.nextDouble();
>> long i = 1;
>> for(; i < Long.MAX_VALUE; i++) {
>> rnd.setSeed(i);
>> double next = rnd.nextDouble();
>> if (Math.abs(next - last) > 0.2)
>> break;
>> }
>> System.out.println(i);
>> }
>>
>> }
>>
>> Your prize if you get it right? A patch would be welcome...
>>
>>
>
--
Lance Norskog
goksron@gmail.com
Re: A little programming challenge
Posted by Dawid Weiss <da...@cs.put.poznan.pl>.
A perhaps better question is what are you trying to prove or what was
your original intention? :) This is a very strange program indeed --
what it does is basically check what the next double value from a
fixed initial seed is... since random uses a relatively simple
congruential algorithm, the result isn't really that surprising (to
me?).
Dawid
On Sun, Feb 20, 2011 at 2:51 AM, Lance Norskog <go...@gmail.com> wrote:
> What does this program print?
>
>
> package hack;
>
> import java.util.Random;
>
> public class JDKRandomThreatOrMenace {
>
> public static void main(String[] args) {
> Random rnd = new Random(0);
>
> double last = rnd.nextDouble();
> long i = 1;
> for(; i < Long.MAX_VALUE; i++) {
> rnd.setSeed(i);
> double next = rnd.nextDouble();
> if (Math.abs(next - last) > 0.2)
> break;
> }
> System.out.println(i);
> }
>
> }
>
> Your prize if you get it right? A patch would be welcome...
>
>
Re: A little programming challenge
Posted by José Moreira <ze...@zemanel.eu>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Em 11/02/20 01:51, Lance Norskog escreveu:
> import java.util.Random;
>
> public class JDKRandomThreatOrMenace {
>
> public static void main(String[] args) {
> Random rnd = new Random(0);
>
> double last = rnd.nextDouble();
> long i = 1;
> for(; i < Long.MAX_VALUE; i++) {
> rnd.setSeed(i);
> double next = rnd.nextDouble();
> if (Math.abs(next - last) > 0.2)
> break;
> }
> System.out.println(i);
> }
>
> }
victory:Tmp zemanel$ nano JDKRandomThreatOrMenace.java
victory:Tmp zemanel$ javac JDKRandomThreatOrMenace.java
victory:Tmp zemanel$ java JDKRandomThreatOrMenace
2304
- --
http://zemanel.eu
http://github.com/zemanel
http://pt.linkedin.com/in/josemoreira
http://djangopeople.net/josemoreira
irc://zemanel@irc.freenode.net
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJNZa1mAAoJEKg0eV/edI7mbrQH/AnTEdAL4pzMtV7XqmuP0qz+
xqgLe15+CHac8YBGhWt+FI8Suyto1CqHBSVKdrPoaFrNZMpCDE7cR4UkD8KnH9wH
yEIaXdTZ9L0tz22fJhJcT75Iz90XHg8GxolMF1wffBEFDHzKHYAWhU2zePpsIMUW
43lLZuDDGFKMLplaaPBbLnLFkX9SiE2EUBOmEzLYrNBl/AcyXJY7Ie7GyBB8p9Rm
tgcT6fmpTkYn0vDxqj+Jzi9NQtkQ+PbUq6VzFg9otrUhZqy4/1iNFoDd+QNR3IXc
BzYy7a9shO2IMqOX5/va0omAmTL3XtLBh9l9ix45JjU/djxTeYH7EXagsYm+G5k=
=aIv1
-----END PGP SIGNATURE-----
Re: A little programming challenge
Posted by Sean Owen <sr...@gmail.com>.
I get 2304 by running it. I don't think Random itself is intended to be
cryptographically secure or anything. It's open source and its seeding is
deterministic. The result from similar seeds need not be apparently random.
If all this matters use SecureRandom or MersenneTwisterRNG.
On 20 Feb 2011 04:52, "Lance Norskog" <go...@gmail.com> wrote:
> What does this program print?
>
>
> package hack;
>
> import java.util.Random;
>
> public class JDKRandomThreatOrMenace {
>
> public static void main(String[] args) {
> Random rnd = new Random(0);
>
> double last = rnd.nextDouble();
> long i = 1;
> for(; i < Long.MAX_VALUE; i++) {
> rnd.setSeed(i);
> double next = rnd.nextDouble();
> if (Math.abs(next - last) > 0.2)
> break;
> }
> System.out.println(i);
> }
>
> }
>
> Your prize if you get it right? A patch would be welcome...
>
Re: A little programming challenge
Posted by Krishna Sankar <ks...@gmail.com>.
The program as written is strange. Takes 2304 tries to get to 0.2 delta.
The printed numbers are very uniform ;o(
This works for me:
import java.util.Random;
public class P1 {
public static void main(String[] args) {
Random rnd = new Random();//0);
double last = rnd.nextDouble();
System.out.println("Last ="+last);
long i = 1;
for(; i < Long.MAX_VALUE; i++) {
//rnd.setSeed(i); //
double next = rnd.nextDouble();
System.out.println(next);
if (Math.abs(next - last) > 0.2)
break;
}
System.out.println(i);
}
}
I think Random() actually initializes the seed to
a value based on the current time, which is better than intializing with
a number
BTW, setseed() uses only 48 bits of the given number
Cheers
<k/>
On 2/19/11 Sat Feb 19, 11, "Lance Norskog" <go...@gmail.com> wrote:
>What does this program print?
>
>
>package hack;
>
>import java.util.Random;
>
>public class JDKRandomThreatOrMenace {
>
> public static void main(String[] args) {
> Random rnd = new Random(0);
>
> double last = rnd.nextDouble();
> long i = 1;
> for(; i < Long.MAX_VALUE; i++) {
> rnd.setSeed(i);
> double next = rnd.nextDouble();
> if (Math.abs(next - last) > 0.2)
> break;
> }
> System.out.println(i);
> }
>
>}
>
>Your prize if you get it right? A patch would be welcome...
>