[TUHS] early unix rand

[TUHS] early unix rand

[Douglas McIlroy]

[-- Attachment #1: Type: text/plain, Size: 830 bytes --]

 > The author of this routine has been writing
>   random-number generators for many years and has
>   never been known to write one that worked.

It sounds like Ken to me. Although everybody had his
own favorite congruential random number generator,
some worse than others, I believe it was Ken who put
one in the math library.

The very fact that rand existed, regardless of its quality,
enabled a lovely exploit. When Ken pioneered password
cracking by trying every word in word lists at hand, one
of the password files he found plenty of hits in came from
Berkeley. He told them and they responded by assigning
random passwords to everybody. That was a memorable
error. Guessing that the passwords were generated by
a simple encoding of the output of rand, Ken promptly
broke 100% of the newly "hardened" password file.

Doug

[-- Attachment #2: Type: text/html, Size: 1124 bytes --]

[TUHS] Re: early unix rand

[Paul Winalski]

On 3/12/24, Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote:
>
> That was a memorable
> error. Guessing that the passwords were generated by
> a simple encoding of the output of rand, Ken promptly
> broke 100% of the newly "hardened" password file.

To do that wouldn't you need to know the seed value that was used?  Or
did this version of rand() always generate the same sequence of
pseudo-random numbers?

One problem with random password generation is to avoid generating
passwords that are or contain naughty words.  VAX/VMS version 4.0
added an option for random password generation.  They had a very
extensive list of naughty words in many different languages to filter
the random passwords.  During beta test they got a bug report from a
high school.  The naughty words text file was world-readable and
students were amusing themselves by reading it.  At release the file
was protected so that only privileged users could read it.

-Paul W.

[TUHS] Re: early unix rand

[Ken Thompson]

[-- Attachment #1: Type: text/plain, Size: 1682 bytes --]

i wrote the generator.
dmr or rhm wrote the comment.
it came about after one of the first
drafts of a graphical pool game.
the balls were points and the test
was the bouncing off the edge of
the pool table. the balls were placed
at "random" places on the table,
they were started with "random"
directions and "random" velocities.
frictionless it ran forever.

after many minutes, from a mess
of dots, they form a line, later a couple
lines, later several points, and finally
after a large fraction of an hour, all the
balls would converge on a single dot.

that version of the program was saved
with the name "wierd" (spelling on purpose).
i have no idea if it exists now.


On Tue, Mar 12, 2024 at 7:38 AM Douglas McIlroy <
douglas.mcilroy@dartmouth.edu> wrote:

>  > The author of this routine has been writing
> >   random-number generators for many years and has
> >   never been known to write one that worked.
>
> It sounds like Ken to me. Although everybody had his
> own favorite congruential random number generator,
> some worse than others, I believe it was Ken who put
> one in the math library.
>
> The very fact that rand existed, regardless of its quality,
> enabled a lovely exploit. When Ken pioneered password
> cracking by trying every word in word lists at hand, one
> of the password files he found plenty of hits in came from
> Berkeley. He told them and they responded by assigning
> random passwords to everybody. That was a memorable
> error. Guessing that the passwords were generated by
> a simple encoding of the output of rand, Ken promptly
> broke 100% of the newly "hardened" password file.
>
> Doug
>

[-- Attachment #2: Type: text/html, Size: 2440 bytes --]

[TUHS] Re: NSFW passwords

[William Cheswick]

Ron Harden’s insult generator solved the NSFW passphrase problem.  It is available at
https://cheswick <https://cheswick/>.com/insults

> On Mar 12, 2024, at 12:23 PM, Paul Winalski <paul.winalski@gmail.com> wrote:
> 
> One problem with random password generation is to avoid generating
> passwords that are or contain naughty words.  VAX/VMS version 4.0
> added an option for random password generation.  They had a very
> extensive list of naughty words in many different languages to filter
> the random passwords.  During beta test they got a bug report from a
> high school.  The naughty words text file was world-readable and
> students were amusing themselves by reading it.  At release the file
> was protected so that only privileged users could read it.

[TUHS] Re: early unix rand

[Russ Cox]

[-- Attachment #1: Type: text/plain, Size: 1609 bytes --]

On Tue, Mar 12, 2024 at 12:23 PM Paul Winalski <paul.winalski@gmail.com>
wrote:

> On 3/12/24, Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote:
> >
> > That was a memorable
> > error. Guessing that the passwords were generated by
> > a simple encoding of the output of rand, Ken promptly
> > broke 100% of the newly "hardened" password file.
>
> To do that wouldn't you need to know the seed value that was used?  Or
> did this version of rand() always generate the same sequence of
> pseudo-random numbers?


Any LCG-based version of rand (including, say, java.lang.Math.random)
always generates the same periodic sequence of numbers; the seed only
controls where in the sequence you start (you start where the seed appears).

Worse, any LCG-based rand truncated to k bits is itself just a periodic
sequence of the 2^k possible truncations. The trivial k=1 case of this is
that if
you look at the bottom bit of successive rand outputs on any of these
generators, it is always alternating between even and odd, no matter
what constants you pick. (Almost. If you pick bad constants you could
get all even or all odd instead.)

I don't know what the simple BSD encoding was, but those two facts
combined mean that an example of an encoding that would be easily broken
would be to pick a fixed-length sequence of letters drawn from
"abcdefghijklmnopqrstuvwxyz123456"[rand()&31].
That would just produce the same 32-character permutation
over and over again, so there would only be 32 possible passwords,
depending only on where in the sequence you start.

Best,
Russ

[-- Attachment #2: Type: text/html, Size: 2240 bytes --]

[TUHS] Re: early unix rand

[Dave Horsfall]

On Wed, 13 Mar 2024, Clem Cole wrote:

> Prof Kahan's Floating Point Test Program - the original from his and his
> students in his computer arithmetic seminar wrote during my days at UCB:
> https://www.netlib.org/paranoia/

I remember that well; it crashed a colleague's Xenix box...

-- Dave

[TUHS] Re: early unix rand

[Clem Cole]

[-- Attachment #1: Type: text/plain, Size: 5046 bytes --]

Prof Kahan's Floating Point Test Program - the original from his and his
students in his computer arithmetic seminar wrote during my days at UCB:
https://www.netlib.org/paranoia/
Kahan was always miffed at how bad the different floating point units were
- (Seymour was notorious for being fast but not very precise on most of his
FP units).
Here is an updated FORTRAN 90 version:
https://people.math.sc.edu/Burkardt/f_src/paranoia/paranoia.html
ᐧ

On Wed, Mar 13, 2024 at 4:25 PM Rob Pike <robpike@gmail.com> wrote:

> Norm Schryer wrote a (nearly?) exhaustive floating-point tester that he
> ran when a new CPU arrived, always with wrong results. Doug McIlroy
> probably knows more about it than I do, who only observed it from afar.
>
> -rob
>
>
> On Thu, Mar 14, 2024 at 4:18 AM ron minnich <rminnich@gmail.com> wrote:
>
>> Got the name wrong: Computer Engineering: A DEC View of Hardware Systems
>> Design
>>
>> On Wed, Mar 13, 2024 at 9:41 AM ron minnich <rminnich@gmail.com> wrote:
>>
>>> by the way, I realize that random number urban legend sounds ridiculous,
>>> in light of how hardware design is done today, but those of you who did
>>> hardware design in those days (guilty!), and had access to -11
>>> schematics and boards, might wonder if it's not possible. There was a
>>> habit, in those days,  for performance reasons, of subbing transparent
>>> latches for flip-flops to gain a little time. An engineer I knew at Amdahl
>>> said that was a pretty hot topic there. Certainly, the technique of design
>>> for testability was not really in wide use in the -11 days. Gordon Bell's
>>> book "Computer Design" is particularly instructive.
>>>
>>> E.g., how did you verify the floating point on your new machine? Put an
>>> older machine next to a new machine, do lots of computation, see if there
>>> is disagreement, you've found a bug in the new machine, right? Maybe.
>>> Sometimes,  you discover the older machine had a bug the newer one did not
>>> ... happened more than once, including on the 360 to 370 transition.
>>>
>>> On Tue, Mar 12, 2024 at 6:09 PM ron minnich <rminnich@gmail.com> wrote:
>>>
>>>> There used to be an urban legend about multiply overflow and the PDP 11.
>>>>
>>>> This would’ve been circa 1976. Someone from DEC told us that on a
>>>> multiply overflow, the contents of the destination register would be “kind
>>>> of” random. I was never able to verify that claim. But that might explain
>>>> this code.
>>>>
>>>> On Tue, Mar 12, 2024 at 16:05 Jonathan Gray <jsg@jsg.id.au> wrote:
>>>>
>>>>> On Tue, Mar 12, 2024 at 08:55:02AM -0400, Russ Cox wrote:
>>>>> > Hi all (and TUHS),
>>>>> >
>>>>> > The Third Edition rand(III) page [1] ends with
>>>>> >
>>>>> > WARNING  The author of this routine has been writing
>>>>> >     random-number generators for many years and has
>>>>> >     never been known to write one that worked.
>>>>> >
>>>>> > My understanding is that Ken wrote the rand implementation.
>>>>> > But I'm curious about the origin of this warning.
>>>>> > I had assumed that Ken wrote it as a combination warning+joke,
>>>>> > but Rob suggested that to him it didn't sound like Ken and
>>>>> > perhaps Doug or Dennis had written it. Does anyone remember?
>>>>> >
>>>>> > Separately, I am trying to find out what the very first
>>>>> > Unix rand implementation was. In the TUHS archives,
>>>>> > the incomplete V2 sources contain a reference to srand
>>>>> > in cmd/bas0.s [2], but there is no definition in the tree.
>>>>> > The V3 man pages list it, but as far as I can tell full
>>>>> > library sources do not appear in the TUHS archives
>>>>> > until the V6 snapshot. The V6 rand [3] is:
>>>>> >
>>>>> > rand:
>>>>> >     mov r1,-(sp)
>>>>> >     mov ranx,r1
>>>>> >     mpy $13077.,r1
>>>>> >     add $6925.,r1
>>>>> >     mov r1,r0
>>>>> >     mov r0,ranx
>>>>> >     bic $100000,r0
>>>>> >     mov (sp)+,r1
>>>>> >     rts pc
>>>>>
>>>>> matches V5:
>>>>> https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.s
>>>>> Distributions/Research/Dennis_v5/v5root.tar.gz
>>>>> <https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.sDistributions/Research/Dennis_v5/v5root.tar.gz>
>>>>>
>>>>> >
>>>>> > Perhaps this is the original rand as well? It is hard to imagine
>>>>> > a much simpler one, other than perhaps removing the addition,
>>>>> > but doing so would create a sequence of only odd numbers.
>>>>> > >From the man page description it sounds like this has to be the
>>>>> > original generator, perhaps with different constants.
>>>>> >
>>>>> > Thanks!
>>>>> >
>>>>> > Best,
>>>>> > Russ
>>>>> >
>>>>> > [1]
>>>>> >
>>>>> https://github.com/dspinellis/unix-history-repo/blob/Research-V3/man/man3/rand.3
>>>>> > [2]
>>>>> >
>>>>> https://github.com/dspinellis/unix-history-repo/blob/Research-V2/cmd/bas0.s
>>>>> > [3]
>>>>> >
>>>>> https://github.com/dspinellis/unix-history-repo/blob/Research-V6/usr/source/s3/rand.s
>>>>>
>>>>

[-- Attachment #2: Type: text/html, Size: 7852 bytes --]

[TUHS] Re: early unix rand

[Rob Pike]

[-- Attachment #1: Type: text/plain, Size: 4405 bytes --]

Norm Schryer wrote a (nearly?) exhaustive floating-point tester that he ran
when a new CPU arrived, always with wrong results. Doug McIlroy probably
knows more about it than I do, who only observed it from afar.

-rob


On Thu, Mar 14, 2024 at 4:18 AM ron minnich <rminnich@gmail.com> wrote:

> Got the name wrong: Computer Engineering: A DEC View of Hardware Systems
> Design
>
> On Wed, Mar 13, 2024 at 9:41 AM ron minnich <rminnich@gmail.com> wrote:
>
>> by the way, I realize that random number urban legend sounds ridiculous,
>> in light of how hardware design is done today, but those of you who did
>> hardware design in those days (guilty!), and had access to -11
>> schematics and boards, might wonder if it's not possible. There was a
>> habit, in those days,  for performance reasons, of subbing transparent
>> latches for flip-flops to gain a little time. An engineer I knew at Amdahl
>> said that was a pretty hot topic there. Certainly, the technique of design
>> for testability was not really in wide use in the -11 days. Gordon Bell's
>> book "Computer Design" is particularly instructive.
>>
>> E.g., how did you verify the floating point on your new machine? Put an
>> older machine next to a new machine, do lots of computation, see if there
>> is disagreement, you've found a bug in the new machine, right? Maybe.
>> Sometimes,  you discover the older machine had a bug the newer one did not
>> ... happened more than once, including on the 360 to 370 transition.
>>
>> On Tue, Mar 12, 2024 at 6:09 PM ron minnich <rminnich@gmail.com> wrote:
>>
>>> There used to be an urban legend about multiply overflow and the PDP 11.
>>>
>>> This would’ve been circa 1976. Someone from DEC told us that on a
>>> multiply overflow, the contents of the destination register would be “kind
>>> of” random. I was never able to verify that claim. But that might explain
>>> this code.
>>>
>>> On Tue, Mar 12, 2024 at 16:05 Jonathan Gray <jsg@jsg.id.au> wrote:
>>>
>>>> On Tue, Mar 12, 2024 at 08:55:02AM -0400, Russ Cox wrote:
>>>> > Hi all (and TUHS),
>>>> >
>>>> > The Third Edition rand(III) page [1] ends with
>>>> >
>>>> > WARNING  The author of this routine has been writing
>>>> >     random-number generators for many years and has
>>>> >     never been known to write one that worked.
>>>> >
>>>> > My understanding is that Ken wrote the rand implementation.
>>>> > But I'm curious about the origin of this warning.
>>>> > I had assumed that Ken wrote it as a combination warning+joke,
>>>> > but Rob suggested that to him it didn't sound like Ken and
>>>> > perhaps Doug or Dennis had written it. Does anyone remember?
>>>> >
>>>> > Separately, I am trying to find out what the very first
>>>> > Unix rand implementation was. In the TUHS archives,
>>>> > the incomplete V2 sources contain a reference to srand
>>>> > in cmd/bas0.s [2], but there is no definition in the tree.
>>>> > The V3 man pages list it, but as far as I can tell full
>>>> > library sources do not appear in the TUHS archives
>>>> > until the V6 snapshot. The V6 rand [3] is:
>>>> >
>>>> > rand:
>>>> >     mov r1,-(sp)
>>>> >     mov ranx,r1
>>>> >     mpy $13077.,r1
>>>> >     add $6925.,r1
>>>> >     mov r1,r0
>>>> >     mov r0,ranx
>>>> >     bic $100000,r0
>>>> >     mov (sp)+,r1
>>>> >     rts pc
>>>>
>>>> matches V5:
>>>> https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.s
>>>> Distributions/Research/Dennis_v5/v5root.tar.gz
>>>> <https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.sDistributions/Research/Dennis_v5/v5root.tar.gz>
>>>>
>>>> >
>>>> > Perhaps this is the original rand as well? It is hard to imagine
>>>> > a much simpler one, other than perhaps removing the addition,
>>>> > but doing so would create a sequence of only odd numbers.
>>>> > >From the man page description it sounds like this has to be the
>>>> > original generator, perhaps with different constants.
>>>> >
>>>> > Thanks!
>>>> >
>>>> > Best,
>>>> > Russ
>>>> >
>>>> > [1]
>>>> >
>>>> https://github.com/dspinellis/unix-history-repo/blob/Research-V3/man/man3/rand.3
>>>> > [2]
>>>> >
>>>> https://github.com/dspinellis/unix-history-repo/blob/Research-V2/cmd/bas0.s
>>>> > [3]
>>>> >
>>>> https://github.com/dspinellis/unix-history-repo/blob/Research-V6/usr/source/s3/rand.s
>>>>
>>>

[-- Attachment #2: Type: text/html, Size: 6373 bytes --]

[TUHS] Re: early unix rand

[ron minnich]

[-- Attachment #1: Type: text/plain, Size: 4004 bytes --]

Got the name wrong: Computer Engineering: A DEC View of Hardware Systems
Design

On Wed, Mar 13, 2024 at 9:41 AM ron minnich <rminnich@gmail.com> wrote:

> by the way, I realize that random number urban legend sounds ridiculous,
> in light of how hardware design is done today, but those of you who did
> hardware design in those days (guilty!), and had access to -11
> schematics and boards, might wonder if it's not possible. There was a
> habit, in those days,  for performance reasons, of subbing transparent
> latches for flip-flops to gain a little time. An engineer I knew at Amdahl
> said that was a pretty hot topic there. Certainly, the technique of design
> for testability was not really in wide use in the -11 days. Gordon Bell's
> book "Computer Design" is particularly instructive.
>
> E.g., how did you verify the floating point on your new machine? Put an
> older machine next to a new machine, do lots of computation, see if there
> is disagreement, you've found a bug in the new machine, right? Maybe.
> Sometimes,  you discover the older machine had a bug the newer one did not
> ... happened more than once, including on the 360 to 370 transition.
>
> On Tue, Mar 12, 2024 at 6:09 PM ron minnich <rminnich@gmail.com> wrote:
>
>> There used to be an urban legend about multiply overflow and the PDP 11.
>>
>> This would’ve been circa 1976. Someone from DEC told us that on a
>> multiply overflow, the contents of the destination register would be “kind
>> of” random. I was never able to verify that claim. But that might explain
>> this code.
>>
>> On Tue, Mar 12, 2024 at 16:05 Jonathan Gray <jsg@jsg.id.au> wrote:
>>
>>> On Tue, Mar 12, 2024 at 08:55:02AM -0400, Russ Cox wrote:
>>> > Hi all (and TUHS),
>>> >
>>> > The Third Edition rand(III) page [1] ends with
>>> >
>>> > WARNING  The author of this routine has been writing
>>> >     random-number generators for many years and has
>>> >     never been known to write one that worked.
>>> >
>>> > My understanding is that Ken wrote the rand implementation.
>>> > But I'm curious about the origin of this warning.
>>> > I had assumed that Ken wrote it as a combination warning+joke,
>>> > but Rob suggested that to him it didn't sound like Ken and
>>> > perhaps Doug or Dennis had written it. Does anyone remember?
>>> >
>>> > Separately, I am trying to find out what the very first
>>> > Unix rand implementation was. In the TUHS archives,
>>> > the incomplete V2 sources contain a reference to srand
>>> > in cmd/bas0.s [2], but there is no definition in the tree.
>>> > The V3 man pages list it, but as far as I can tell full
>>> > library sources do not appear in the TUHS archives
>>> > until the V6 snapshot. The V6 rand [3] is:
>>> >
>>> > rand:
>>> >     mov r1,-(sp)
>>> >     mov ranx,r1
>>> >     mpy $13077.,r1
>>> >     add $6925.,r1
>>> >     mov r1,r0
>>> >     mov r0,ranx
>>> >     bic $100000,r0
>>> >     mov (sp)+,r1
>>> >     rts pc
>>>
>>> matches V5:
>>> https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.s
>>> Distributions/Research/Dennis_v5/v5root.tar.gz
>>> <https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.sDistributions/Research/Dennis_v5/v5root.tar.gz>
>>>
>>> >
>>> > Perhaps this is the original rand as well? It is hard to imagine
>>> > a much simpler one, other than perhaps removing the addition,
>>> > but doing so would create a sequence of only odd numbers.
>>> > >From the man page description it sounds like this has to be the
>>> > original generator, perhaps with different constants.
>>> >
>>> > Thanks!
>>> >
>>> > Best,
>>> > Russ
>>> >
>>> > [1]
>>> >
>>> https://github.com/dspinellis/unix-history-repo/blob/Research-V3/man/man3/rand.3
>>> > [2]
>>> >
>>> https://github.com/dspinellis/unix-history-repo/blob/Research-V2/cmd/bas0.s
>>> > [3]
>>> >
>>> https://github.com/dspinellis/unix-history-repo/blob/Research-V6/usr/source/s3/rand.s
>>>
>>

[-- Attachment #2: Type: text/html, Size: 5499 bytes --]

[TUHS] Re: early unix rand

[ron minnich]

[-- Attachment #1: Type: text/plain, Size: 3739 bytes --]

by the way, I realize that random number urban legend sounds ridiculous, in
light of how hardware design is done today, but those of you who did
hardware design in those days (guilty!), and had access to -11
schematics and boards, might wonder if it's not possible. There was a
habit, in those days,  for performance reasons, of subbing transparent
latches for flip-flops to gain a little time. An engineer I knew at Amdahl
said that was a pretty hot topic there. Certainly, the technique of design
for testability was not really in wide use in the -11 days. Gordon Bell's
book "Computer Design" is particularly instructive.

E.g., how did you verify the floating point on your new machine? Put an
older machine next to a new machine, do lots of computation, see if there
is disagreement, you've found a bug in the new machine, right? Maybe.
Sometimes,  you discover the older machine had a bug the newer one did not
... happened more than once, including on the 360 to 370 transition.

On Tue, Mar 12, 2024 at 6:09 PM ron minnich <rminnich@gmail.com> wrote:

> There used to be an urban legend about multiply overflow and the PDP 11.
>
> This would’ve been circa 1976. Someone from DEC told us that on a multiply
> overflow, the contents of the destination register would be “kind of”
> random. I was never able to verify that claim. But that might explain this
> code.
>
> On Tue, Mar 12, 2024 at 16:05 Jonathan Gray <jsg@jsg.id.au> wrote:
>
>> On Tue, Mar 12, 2024 at 08:55:02AM -0400, Russ Cox wrote:
>> > Hi all (and TUHS),
>> >
>> > The Third Edition rand(III) page [1] ends with
>> >
>> > WARNING  The author of this routine has been writing
>> >     random-number generators for many years and has
>> >     never been known to write one that worked.
>> >
>> > My understanding is that Ken wrote the rand implementation.
>> > But I'm curious about the origin of this warning.
>> > I had assumed that Ken wrote it as a combination warning+joke,
>> > but Rob suggested that to him it didn't sound like Ken and
>> > perhaps Doug or Dennis had written it. Does anyone remember?
>> >
>> > Separately, I am trying to find out what the very first
>> > Unix rand implementation was. In the TUHS archives,
>> > the incomplete V2 sources contain a reference to srand
>> > in cmd/bas0.s [2], but there is no definition in the tree.
>> > The V3 man pages list it, but as far as I can tell full
>> > library sources do not appear in the TUHS archives
>> > until the V6 snapshot. The V6 rand [3] is:
>> >
>> > rand:
>> >     mov r1,-(sp)
>> >     mov ranx,r1
>> >     mpy $13077.,r1
>> >     add $6925.,r1
>> >     mov r1,r0
>> >     mov r0,ranx
>> >     bic $100000,r0
>> >     mov (sp)+,r1
>> >     rts pc
>>
>> matches V5:
>> https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.s
>> Distributions/Research/Dennis_v5/v5root.tar.gz
>> <https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.sDistributions/Research/Dennis_v5/v5root.tar.gz>
>>
>> >
>> > Perhaps this is the original rand as well? It is hard to imagine
>> > a much simpler one, other than perhaps removing the addition,
>> > but doing so would create a sequence of only odd numbers.
>> > >From the man page description it sounds like this has to be the
>> > original generator, perhaps with different constants.
>> >
>> > Thanks!
>> >
>> > Best,
>> > Russ
>> >
>> > [1]
>> >
>> https://github.com/dspinellis/unix-history-repo/blob/Research-V3/man/man3/rand.3
>> > [2]
>> >
>> https://github.com/dspinellis/unix-history-repo/blob/Research-V2/cmd/bas0.s
>> > [3]
>> >
>> https://github.com/dspinellis/unix-history-repo/blob/Research-V6/usr/source/s3/rand.s
>>
>

[-- Attachment #2: Type: text/html, Size: 5048 bytes --]

[TUHS] Re: early unix rand

[ron minnich]

[-- Attachment #1: Type: text/plain, Size: 2580 bytes --]

There used to be an urban legend about multiply overflow and the PDP 11.

This would’ve been circa 1976. Someone from DEC told us that on a multiply
overflow, the contents of the destination register would be “kind of”
random. I was never able to verify that claim. But that might explain this
code.

On Tue, Mar 12, 2024 at 16:05 Jonathan Gray <jsg@jsg.id.au> wrote:

> On Tue, Mar 12, 2024 at 08:55:02AM -0400, Russ Cox wrote:
> > Hi all (and TUHS),
> >
> > The Third Edition rand(III) page [1] ends with
> >
> > WARNING  The author of this routine has been writing
> >     random-number generators for many years and has
> >     never been known to write one that worked.
> >
> > My understanding is that Ken wrote the rand implementation.
> > But I'm curious about the origin of this warning.
> > I had assumed that Ken wrote it as a combination warning+joke,
> > but Rob suggested that to him it didn't sound like Ken and
> > perhaps Doug or Dennis had written it. Does anyone remember?
> >
> > Separately, I am trying to find out what the very first
> > Unix rand implementation was. In the TUHS archives,
> > the incomplete V2 sources contain a reference to srand
> > in cmd/bas0.s [2], but there is no definition in the tree.
> > The V3 man pages list it, but as far as I can tell full
> > library sources do not appear in the TUHS archives
> > until the V6 snapshot. The V6 rand [3] is:
> >
> > rand:
> >     mov r1,-(sp)
> >     mov ranx,r1
> >     mpy $13077.,r1
> >     add $6925.,r1
> >     mov r1,r0
> >     mov r0,ranx
> >     bic $100000,r0
> >     mov (sp)+,r1
> >     rts pc
>
> matches V5:
> https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.s
> Distributions/Research/Dennis_v5/v5root.tar.gz
> <https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.sDistributions/Research/Dennis_v5/v5root.tar.gz>
>
> >
> > Perhaps this is the original rand as well? It is hard to imagine
> > a much simpler one, other than perhaps removing the addition,
> > but doing so would create a sequence of only odd numbers.
> > >From the man page description it sounds like this has to be the
> > original generator, perhaps with different constants.
> >
> > Thanks!
> >
> > Best,
> > Russ
> >
> > [1]
> >
> https://github.com/dspinellis/unix-history-repo/blob/Research-V3/man/man3/rand.3
> > [2]
> >
> https://github.com/dspinellis/unix-history-repo/blob/Research-V2/cmd/bas0.s
> > [3]
> >
> https://github.com/dspinellis/unix-history-repo/blob/Research-V6/usr/source/s3/rand.s
>

[-- Attachment #2: Type: text/html, Size: 3617 bytes --]

[TUHS] Re: early unix rand

[Jonathan Gray]

On Tue, Mar 12, 2024 at 08:55:02AM -0400, Russ Cox wrote:
> Hi all (and TUHS),
> 
> The Third Edition rand(III) page [1] ends with
> 
> WARNING  The author of this routine has been writing
>     random-number generators for many years and has
>     never been known to write one that worked.
> 
> My understanding is that Ken wrote the rand implementation.
> But I'm curious about the origin of this warning.
> I had assumed that Ken wrote it as a combination warning+joke,
> but Rob suggested that to him it didn't sound like Ken and
> perhaps Doug or Dennis had written it. Does anyone remember?
> 
> Separately, I am trying to find out what the very first
> Unix rand implementation was. In the TUHS archives,
> the incomplete V2 sources contain a reference to srand
> in cmd/bas0.s [2], but there is no definition in the tree.
> The V3 man pages list it, but as far as I can tell full
> library sources do not appear in the TUHS archives
> until the V6 snapshot. The V6 rand [3] is:
> 
> rand:
>     mov r1,-(sp)
>     mov ranx,r1
>     mpy $13077.,r1
>     add $6925.,r1
>     mov r1,r0
>     mov r0,ranx
>     bic $100000,r0
>     mov (sp)+,r1
>     rts pc

matches V5:
https://www.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/s3/rand.s
Distributions/Research/Dennis_v5/v5root.tar.gz

> 
> Perhaps this is the original rand as well? It is hard to imagine
> a much simpler one, other than perhaps removing the addition,
> but doing so would create a sequence of only odd numbers.
> >From the man page description it sounds like this has to be the
> original generator, perhaps with different constants.
> 
> Thanks!
> 
> Best,
> Russ
> 
> [1]
> https://github.com/dspinellis/unix-history-repo/blob/Research-V3/man/man3/rand.3
> [2]
> https://github.com/dspinellis/unix-history-repo/blob/Research-V2/cmd/bas0.s
> [3]
> https://github.com/dspinellis/unix-history-repo/blob/Research-V6/usr/source/s3/rand.s

[TUHS] Re: early unix rand

[Russ Cox]

[-- Attachment #1: Type: text/plain, Size: 275 bytes --]

Someone asked off-list for a C translation of the PDP-11 assembly code. I
believe the equivalent modern C would be:

unsigned int ranx;

void
srand(unsigned int seed)
{
    ranx = seed;
}

int
rand(void)
{
    ranx = 13077*ranx + 6925;
    return ranx & 32767;
}

Best,
Russ

[-- Attachment #2: Type: text/html, Size: 428 bytes --]