Fog Creek Software
Discussion Board




random numbers

I'm using the PHP mt_rand function to get pseudo-random numbers. Is there any reason I could possibly get a greater number of odd numbers, or of even numbers?

The Real PC
Saturday, July 12, 2003

yes, a bug

http://bugs.php.net/bug.php?id=22988


Saturday, July 12, 2003

If you want perfect random numbers use a simple cellular automata implementing the rule 30 as described in "A New Kind of Science".

Pablo
Sunday, July 13, 2003

Could you elaborate on that?

The Real PC
Sunday, July 13, 2003

regarding "A New Kind of Science".. is it worth buying?  Is it actualy fun to read, or does it get bogged down while trudging through heavy mathematics?

Heston Holtmann
Monday, July 14, 2003

I read some reviews, and skimmed over the book in a bookstore, and was thoroughly unimpressed.  It claims to establish some new kind of paradigm for modeling natural processes and studying the physical world.  I think the claim basically is that mathematical equations are not very suited for describing some natural phenomena.  He thinks that cellular automata, i.e. a simple set of rules carried out on a grid, can be more accurate, I believe.  In reality I think he just took some old research on cellular automata and expanded the ideas a bit, and makes grandiose claims about the results.

Also I've read that the book repeatedly says how revolutionary it is.  If the book was so revolutionary in establishing some kind of new paradigm, then you would probably see a lot of researchers jumping on this bandwagon.  But that has not been the case, AFAIK.  In reality, the study of cellular automata is an interesting but limited field that seems to have been exhausted soon after it were introduced.

I read a bunch of stuff on the net around when it came out, and a lot of people were questioning whether Wolfram was a megalomaniac, and there were some serious anecdotes that indicated he had really lost it.

Look at the reviews at amazon, the rating is 3, which is pretty much a 0 at amazon.  (i.e. I have never seen a book below 3).

Also, it is like 1100 pages I think, really dense and thick.  But it was marketed as popular science book for a regular audience.  If you are looking for an intro book on CS stuff that you would typically NOT learn in undergrad, I recommend "The Computational Beauty of Nature" by Flake.  Comes with a bunch of code that is fun to play around with.

Andy
Monday, July 14, 2003

Andy, no offense intended, you don't know what you're talking about.  I mean that in the strict sense that you clearly have only a cursory knowledge of the content (and controversy) of Wolfram's book.  It seems odd to me that you wouldn't recognize this and furthermore that you'd go on to make conclusions out of this ignorance.

Let me just address your points as you enumerated them:

>It claims to establish some new kind of paradigm for
>modeling natural processes and studying the physical
>world.  I think the claim basically is that mathematical
>equations are not very suited for describing some natural
>phenomena.

There's more than one claim in the book.  The one you're thinking about here is probably Wolfram's comments on the unsuitability of partial differential equations to describe natural phenomena.  That's quite a bit more specific than that "mathematical equations" are to be discarded.

The discrete dynamical systems of Wolfram's book are mathematical objects in a very real sense (describable by mathematical equations).  Wolfram's free-form causal network model of space, for instance, can be represented by a digraph.

When Wolfram writes about the unsuitability of "mathematical equations" to describe many classes of natural phenomena, he generally says it in the layman version of the text.  What he's talking about is actually the unsuitability of models that assume continuity of fundamental quantities.

>He thinks that cellular automata, i.e. a simple set of
>rules carried out on a grid, can be more accurate, I
>believe.

This is not correct.  When it comes to modelling physical reality, he favors a free-form network model that has "cellular automata"-like characteristics.  It's a minimal model in the sense that there exist only nodes (discrete spatial locations) and connections between nodes.

>In reality I think he just took some old research on
>cellular automata and expanded the ideas a bit, and
>makes grandiose claims about the results.

Well maybe he expanded on old research, but it was his research.  If you read his collected papers on cellular automata ("Cellular Automata and Complexity") you'll find a lot of fundamental early work in this area (including the use of Rule 30 as a RNG and its application in cryptosystems etc -- incidentally, he uses Rule 30 as the random number generator in Mathematica).

He did play up his case in the layman text.  It's certainly a controversial point, whether or not he should have been so emphatic.  On the one hand, I think it's wonderful to attract more people to the field.  On the other, it's probably still a bit early.  Note, that says nothing about the value of the content of the book.  I think that it's a very valuable book and his work (and the work of his associates) is very interesting.

>If the book was so revolutionary in establishing some
>kind of new paradigm, then you would probably see a
>lot of researchers jumping on this bandwagon.  But
>that has not been the case, AFAIK.

While everybody keeps repeating this line, you might want to read this:

http://arxiv.org/PS_cache/math/pdf/0306/0306303.pdf

and this:

http://www.lns.cornell.edu/spr/2002-05/msg0041891.html

As well as lots of other resources on the web and in print.  I'd be amazed if you could walk away thinking that there isn't a lot of very intense work being done by very smart people on these (and related) subjects.

A choice quote from that second link by Ed Fredkin (an early inspiration for Wolfram's work):

"I am in complete agreement with the idea that a totally discrete process must underlie QM.  I have been preaching this since the early 1960's.  I spent one year 1974-1975 working closely with Richard Feynman (as a Fairchild Distinguished Scholar at Caltech; while Hawking also had the same kind of position at Caltech as I did).  The absolute primary objectives I had were: 1.  to solve the problem of reversible computing in a way that was compatible with the idea of discrete models of physics,  and 2.  to have Feynman teach me what I didn't know about QM so as to be certain that nothing in QM ruled out totally discrete models.  While at Caltech I invented the so called Fredkin Gate, solving problem 1. and Feynman succeeded in teaching me everything he felt I needed to know about QM (he even gave me a final exam which I passed).  I was able to convince Feynman that discrete computational models of physics were not ruled out by QM, despite the fact that he did not then fully believe in them.  By 1982 he had changed his mind."

Plenty of researchers do work in this area and it's growing all the time.

>In reality, the study of cellular automata is an interesting
>but limited field that seems to have been exhausted soon
>after it were introduced.

This just demonstrates a complete ignorance of the history of the field and the current state of affairs (furthermore, it assumes that the whole "A New Kind of Science" thing is about cellular automata, but CA are just a subset of the systems ANKOS covers).

Von Neumann and Ulam studied an early form of cellular automata (the 2-dimensional case with some large number of states).  They didn't spend much time with it, but similar systems were later picked up by Fredkin and others -- with Wolfram eventually laying down a simple formalism for classifying and studying them (starting with a few years of work on the 1-dimensional 2-state CAs, which are the introductory subject of his book).  They have had numerous uses in recent years (CA models, and other similar models, are being used more and more all the time -- especially by biologists).  They're used almost everywhere for modelling things like traffic and weather and wildfire behavior.  They're used for numerical approximation techniques when simulating differential equations.

Well, you may dismiss "the field" to your own detriment.

>I read a bunch of stuff on the net around when it came
>out, and a lot of people were questioning whether
>Wolfram was a megalomaniac, and there were some
>serious anecdotes that indicated he had really lost it.

Well it's a good thing I didn't decide to discredit your assertions about Wolfram by questioning your character.  God forbid we actually evaluate what the man has to say!

>Also, it is like 1100 pages I think, really dense and thick.
>But it was marketed as popular science book for a regular
>audience.

The first 700 pages or so work great for a popular audience.  There aren't any equations or complex math.  The systems are described (usually) with simple pictures depicting their behavior.  It's a very entertaining read (aside from his slightly awkward writing style).

>If you are looking for an intro book on CS stuff that you
>would typically NOT learn in undergrad, I recommend "The
>Computational Beauty of Nature" by Flake.  Comes with a
>bunch of code that is fun to play around with.

The fish+chips book is interesting too.  In fact, I would suggest that it be read before ANKOS at least to have some familiarity with discrete dynamical systems and certain other types of computational systems (the bit on Craig Reynolds work sort of detracts from that theme).

But don't discount ANKOS and the "digital physics" movement just because of recent controversy.  Take some time out and research it.

K
Monday, July 14, 2003

I know enough of what I'm talking about to answer the original poster's question.  I'm making the assumption that the poster is from the general audience of science-literate people that the book was marketed toward, and not a researcher in discrete dynamical systems.

Anyway, this debate has been done to death, and to anyone who is interested in really evaluating the book, I would refer them to:

http://www.math.usf.edu/~eclark/ANKOS_reviews.html

Whether the claims in the book are true or not, I don't know, because I said I hadn't read the book.  From what I have read, it appears they are true, but then Wolfram goes on to claim that they will solve all of life's problems.

Here are some quotes copied from a review:

"has vastly richer implications than the laws of thermodynamics — or for that matter, than essentially any single collection of laws in science" (p. 726)? Or that they have made "one of the more important single discoveries in the whole history of theoretical science" (p. 2)?

He also apparently thinks that his results will have implications in "fine art".  And also many people have noted that he has failed to reference his work in a scientifically acceptable way, i.e. it looks like he is reluctant to give credit to his predecessors, notably Zuse.

Again, I agree that none of this logically implies anything about the truth of the results in the books.  The point is that the book may be strictly correct, but it makes grandiose, unsubstantiated claims about its applicability to biology and physics and psychology and a number of other fields -- WHICH IS WHAT SOLD THE BOOK, and is apparently what people are expecting from it.

If the original poster was not under this impression, and was looking for a book about discrete dynamical systems, then I apologize.

Also, as for my comment about the field of cellular automata, I will retract it.  What I meant by the comment was that in a lot of books (even the Flake book), cellular automata are sold as having a broad applicability to a wide variety of fields.  When they were first investigated, I believe people made claims very similar to Wolfram's, that they would enable new discoveries in a wide range of disciplines.  With my admittedly limited knowledge of the field, I don't think it has panned out.

If I am mistaken, I would be very eager to hear how biology, physics, psychology, or even fine art has benefited from the study of CA -- and I mean real results, not speculation, which I have heard plenty of.

Andy
Monday, July 14, 2003

Is there any way I can improve my understanding of DP and CA without reading the whole Wolfram book, or is there something shorter I can read first? I am on Fredkin's DP mailing list but I need to improve my general knowledge of the subject, and 1200 pages is too much.
I have a feeling they are correct about reality being discrete but am not qualified to argue about it.

Regarding my original post -- how can any algorithm produce truly random numbers?

The Real PC
Monday, July 14, 2003

Real PC:

No algorithm can produce "truly random numbers" (for certain definitions of "truly random").  Using CA Rule 30 you can see how this is in a very simple way.  If you use a fixed-width cyclical CA, eventually it will revisit one of its previous states (the probability that it will is 2^w, where w is the width of the CA), and so the length of the repeat period is the number of steps it took to get from the initial state back to itself.  On the other hand, with an expansive CA you can avoid this problem in theory, but in reality you eventually run out of memory (2*s + w bits are required to store the CA state, where s is the step you're on and w was the initial CA state [clearly as s -> infinity, the memory requirement -> infinity too]).  Knuth has a good treatment of this subject in his "Seminumerical Algorithms" book also.

Of course, if reality is continuous then it would be true that the universe could produce "truly random numbers" (since it'd have infinite memory and infinite computation to use).  But there are "aesthetic" problems with continuity working here in the real world (see Cantor, Banach-Tarski, etc).

Andy:

Clearly you're taking your opinion from someplace else.  Unfortunately you're taking opinions from some mutually incompatible sources.  Clark is on the CA newsgroup -- I read the posts of his that came with that website.  He has lots to say about Wolfram's ego and Wolfram's hyperbole, but he doesn't disagree with the spirit of Wolfram's work.

You bring up Zuse without really understanding the charge.  If you read that first link I'd sent to you, you might be less sensitive to this kind of thing.  Chaitin (the author of that paper and creator of the so-called "Chaitin's Constant") believes that Leibniz's work predates Wolfram's.  The CA newsgroup folks are keen to harp on Fredkin's authority (he was saying "the universe is a CA" before Wolfram came along).  Zuse thought something similar, including that the universe is computable.  He did a lot of great work, but his model of the universe isn't the same as Wolfram's.  For God's sake, Wolfram's might not even be right -- but the very least you can do if you're going to denigrate the man's work is actually evaluate it (and if you're going to parrot all the naysayers you can at least be so honest -- other people might otherwise mistake you for somebody who knows what he's talking about).

I'll reply to more of this later; I've got to go to work.

Real PC, the digitalphysics website is a fine place to start.  You can also look up some of the stuff that Feynman had to say about it (and look up details about CA models and "CA-like" models).  What's said in ANKOS is really in the last 300 pages (the "notes" section).  You might also approach some texts on Quantum Mechanics, but with an eye to discrete computational systems -- look up Bell's Inequality and ask yourself if "mainstream science" decided to take a particular direction that could (by discarding some unreasonable assumptions) go a couple other ways.

OK, gotta go...

K
Monday, July 14, 2003

Both of these web pages from my bookmarks have details on random number generators

The Mersenne Twister homepage which should give you more information on mt_rand
http://www.math.keio.ac.jp/~matumoto/emt.html

http://random.mat.sbg.ac.at/generators/ has some useful links pages and discussions.

Peter Ibbotson
Monday, July 14, 2003

I feel I must quote Mulder from the X-files here and say "nobody likes a math geek."

Kero
Monday, July 14, 2003

"Real PC", it would help if we knew _why_ you wanted better randomness.  I would recommend different algorithms depending on whether you were writing a game, a Monte-Carlo-method financial package, a server-load balancer or a salted hash generator.

What are you doing with random numbers, and why do you want good ones?

Eric

Eric Lippert
Monday, July 14, 2003

He's looking for God.

(grinning, ducking, running)

Alyosha`
Monday, July 14, 2003

Not that anyone, including me, cares any more, but have a look at quotes from you:

"Clearly you're taking your opinion from someplace else"

"and if you're going to parrot all the naysayers you can at least be so honest"

and me:

"Whether the claims in the book are true or not, I don't know, because I said I hadn't read the book"

"I read some reviews, and skimmed over the book in a bookstore"

"And also many people have noted that he has failed to reference his work in a scientifically acceptable way"

"anyone who is interested in really evaluating the book, I would refer them to:"

"Here are some quotes copied from a review:"

Also note I didn't quote Clark, I quoted Clark quoting Wolfram to show what was in Wolfram's book.  Since I don't have it.  What Clark has to say and what it contradicts is irrelevant.

So, because this argument is boring, and because you are clearly intent on accusing and insulting me for things I have admitted, I will put an end to it now.  I already posted a website where anyone could read hundreds of other people's opinions (from academics in many fields and laymen).  IMPORTANT NOTE: I am operating under the assumption that there is NOT A CONSPIRACY against Wolfram.

And of course I still stand by my original recommendation.  If anyone would like any recommendations of books to read rather than Wolfram, if you are interested in computer science-y general interest books, I already provided one and could recommend several more.  They have interesting content and as a bonus don't suffer from the diarrhea of the pen that K has inherited from Wolfram.

Andy
Tuesday, July 15, 2003

That'd be a fine demonstration of my senseless attack on you if the sets of quotes you cite are related.  But they're not related, so this example of your taking comments out of context just further establishes your problems with argument.

Let me demonstrate:

You write:

"Whether the claims in the book are true or not, I don't know, because I said I hadn't read the book.  From what I have read, it appears they are true, but then Wolfram goes on to claim that they will solve all of life's problems."

But you can't possibly back this up because Wolfram hasn't claimed anything like that.  You don't even know what the "claims" are, but "from what [you've] read, it appears they are true."

Hence my quote:

"Clearly you're taking your opinion from someplace else."

It's a trivially obvious conclusion.  The conclusion you make above can't possibly be supported by anything that you read.  You don't even know what his "claims" are.

"And also many people have noted that he has failed to reference his work in a scientifically acceptable way, i.e. it looks like he is reluctant to give credit to his predecessors, notably Zuse."

This is parroting.  There's one man making a lot of noise about Zuse.  His argument is flawed (for reasons I will omit in order to avoid "diarrhea of the pen").  You might hear that he has failed to attribute the work of Ed Fredkin also (Fredkin's a MUCH better argument than Zuse, in that he's worked directly in this field).  However, as you would see if you read the second of the links I gave to you above, Fredkin is very happy with Wolfram's book.

"The point is that the book may be strictly correct, but it makes grandiose, unsubstantiated claims about its applicability to biology and physics and psychology and a number of other fields."

Surely you could list the unsubstantiated claims directly from the book (except clearly this isn't your opinion either).

There are several demonstrations of applications to physics, biology and psychology in the layman text (and in more depth in the notes section).  For example, there's the natural enumeration of conch shells, the 2D thermodynamical cellular automaton snowflake, and a proposed system by which humans break down patterns in what they see (this is psychology in the strict sense -- the modern "computational theory of the mind").  Of course, there are plenty more.

Several people fell victim to the hype that was created by Forbes magazine.  Everybody who was interested in this field before ANKOS came out knew that it was just an (unfortunate) renaming of his earlier planned book "A Science of Complexity."  The expectations that many people seem to have had for the book are unrealistic.  However, if you're just going to go read a survey book anyway your expectations aren't the same.  You might as well read ANKOS with similar expectations and be pleasantly surprised rather than read it with impossible expectations and be (inevitably) disappointed.

You have to be willing to put up with some bad writing in reading ANKOS.  The survey books have the benefit that their authors are talented writers.  Wolfram's specialty has always been in fundamental research, and even going back to past works you'll find that his style (unfortunately) hasn't changed very much.  However, if you're interested in some new ideas with broad applications then it's a book worth reading (especially if you're a programmer).

K
Tuesday, July 15, 2003

*  Recent Topics

*  Fog Creek Home