What algorithm for random() function?

Got a LiveCode personal license? Are you a beginner, hobbyist or educator that's new to LiveCode? This forum is the place to go for help getting started. Welcome!

Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller

stam
Posts: 2634
Joined: Sun Jun 04, 2006 9:39 pm
Location: London, UK

Re: What algorithm for random() function?

Post by stam » Wed Jul 14, 2021 8:04 am

MichaelBluejay wrote:
Tue Jul 13, 2021 2:50 am
A few years ago a professor created a new algorithm, PCG. On her website she details the various qualities desirable in an algorithm, and how the existing algorithms aren't as good as PCG. Granted that she could be biased, but I haven't seen any reputable criticism of her work or her claims.
Hmmmm, i dunno... i come from a completely different scientific background (medicine) but i'm pretty sure I would take a paper that's published on a website because it was rejected by peer review with a sizeable pinch of salt...

richmond62
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 9287
Joined: Fri Feb 19, 2010 10:17 am
Location: Bulgaria

Re: What algorithm for random() function?

Post by richmond62 » Wed Jul 14, 2021 8:41 am

rejected by peer review
I wonder how you discovered that when the web-page (unsurprisingly) does not mention that as far as I can see.

I spend quite a lot of my time polishing translations of what passes for academic stuff round these parts and am
mind-blowingly surprised at the utter nonsense that DOES get passed by peer review, so, obviously to get
rejected you have to "work really hard."

I would not touch that with a 10 foot pole.

richmond62
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 9287
Joined: Fri Feb 19, 2010 10:17 am
Location: Bulgaria

Re: What algorithm for random() function?

Post by richmond62 » Wed Jul 14, 2021 9:47 am

Because I rarely find what I'm looking for in the docs.
Ludwig Wittgenstein stated that the reason many people never found answers
was because they asked the wrong questions.

What MichaelBlueJay has not explained is WHY he needs to know the way LiveCode generates
its pseudorandoms, NOR why that matters to him.

stam
Posts: 2634
Joined: Sun Jun 04, 2006 9:39 pm
Location: London, UK

Re: What algorithm for random() function?

Post by stam » Wed Jul 14, 2021 4:05 pm

richmond62 wrote:
Wed Jul 14, 2021 8:41 am
rejected by peer review
I wonder how you discovered that when the web-page (unsurprisingly) does not mention that as far as I can see.
Actually the web site mentions this abundantly although phrased more politely, so you’d be forgiven for not realising the author submitted and it was rejected, and it’s been put online instead…

https://www.pcg-random.org/paper.html
https://www.pcg-random.org/posts/histor ... paper.html

FourthWorld
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9802
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

Re: What algorithm for random() function?

Post by FourthWorld » Thu Jul 15, 2021 2:08 am

MichaelBluejay wrote:
Tue Jul 13, 2021 5:55 pm
Because I rarely find what I'm looking for in the docs. That's why when I went to look up random(), I thought, "They're not even gonna bother to mention what algorithm they use." I was right for a reason.
If the reason you had in mind is that it's minutiae too specialized for inclusion in an essential reference, you would be right.

FWIW, in my 30 years using nearly every dialect of this family of languages, this is the first time it's come up.

And this is the only dialect in this family of languages where the answer to that and any other similarly specialized question can be a answered directly by reading the source.

And it's worth noting that the only reason it's come up here isn't related to building anything in LiveCode, but a battle of wits with someone else who isn't here and isn't using LiveCode.

If there's a project-related reason why knowing the algo is important I'd help you find it. But for just settling an argument elsewhere that seems, near as I can tell, inconsequential for any specific application, I can't guarantee I'll find the time.
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn

richmond62
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 9287
Joined: Fri Feb 19, 2010 10:17 am
Location: Bulgaria

Re: What algorithm for random() function?

Post by richmond62 » Thu Jul 15, 2021 7:43 am

isn't related to building anything in LiveCode
'nuff said.

jacque
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 7215
Joined: Sat Apr 08, 2006 8:31 pm
Location: Minneapolis MN
Contact:

Re: What algorithm for random() function?

Post by jacque » Thu Jul 15, 2021 5:20 pm

From what I can see, he wants to translate it into LC.
I'd love to implement it in LiveCode, but I can't translate from the C-language example on the site, which is daunting.
That seems relevant.
Jacqueline Landman Gay | jacque at hyperactivesw dot com
HyperActive Software | http://www.hyperactivesw.com

FourthWorld
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9802
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

Re: What algorithm for random() function?

Post by FourthWorld » Thu Jul 15, 2021 6:08 pm

jacque wrote:
Thu Jul 15, 2021 5:20 pm
From what I can see, he wants to translate it into LC.
I'd love to implement it in LiveCode, but I can't translate from the C-language example on the site, which is daunting.
That seems relevant.
Might be, but from the descriptions offered so far it appears to be part of an intellectual jousting match with a professor.

If this is related to work on a LiveCode project, it would be helpful to learn more about the nature of the randomness desired, for the reasons I took the time to outline and link to a talk about. In short, even distribution is what most psuedorandom algos aim for but isn't reflective of true randomness, and even distribution isn't often what meets user expectations in many contexts, nor what reflects much real-world modeling of circumstances involving uncertainty.

And most of all, the if algo is especially popular it's likely that's what's already in the engine (the engine maintainers rarely reinvent common wheels), so we may find that a source review is all that's needed.
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn

richmond62
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 9287
Joined: Fri Feb 19, 2010 10:17 am
Location: Bulgaria

Re: What algorithm for random() function?

Post by richmond62 » Thu Jul 15, 2021 7:29 pm

"the reviewers would have preferred to have a paper that had far less review content. A much shorter paper might have been possible, but the review process took 320 days before any feedback was given."

Well it obviously didn't grab the reviewers by the curly bits if it took them the better part of a year to revert.

Chummy avoids mentioning any actual comments made beyond that it contains a lot of review content.

This reminds me of a Docent book I went through recently where, in 450 pages, about 350 pages were quotes from other people
and a literature review interspersed with promises of what was to come in the remainder. In the last 100 pages there were
50 where the author never got to the point, and 50 of bibliography. The blasted thing was accepted for publication!

Obviously padding out your papers and books with high-sounding 'bumf' so they are longer and superficially more impressive
than if you wrote a quick, 10 page thing that got straight to the point, is the way things are done today.

MichaelBluejay
Posts: 222
Joined: Thu Jul 01, 2010 11:50 am

Re: What algorithm for random() function?

Post by MichaelBluejay » Wed Sep 29, 2021 7:31 am

FourthWorld wrote:
Thu Jul 15, 2021 2:08 am
And it's worth noting that the only reason it's come up here isn't related to building anything in LiveCode, but a battle of wits with someone else who isn't here and isn't using LiveCode.

If there's a project-related reason why knowing the algo is important I'd help you find it. But for just settling an argument elsewhere that seems, near as I can tell, inconsequential for any specific application, I can't guarantee I'll find the time.
Wow.

Half of this seems directed at me and half doesn't. I mean, I'm here and I'm using LiveCode. If it's directed at me, *of course* I have a project in mind! It's one in which the results hinge on the quality of the random numbers generated. But since it seems I'm being attacked just for asking about randomness in LC, heck if I'm gonna give the details here. If you didn't assume I had a legitimate reason for asking, then I'd expect that I'd also be graded on whether my project were legitimate enough in your eyes, so no thanks.

LCMark
Livecode Staff Member
Livecode Staff Member
Posts: 1206
Joined: Thu Apr 11, 2013 11:27 am

Re: What algorithm for random() function?

Post by LCMark » Wed Sep 29, 2021 9:25 am

@MichaelBluejay: The algorithm the engine uses is the UNIX (POSIX) standard drand48 algorithm: https://pubs.opengroup.org/onlinepubs/7 ... and48.html.

This isn't actually mentioned explicitly in the source-code - although given the name of the internal function (MCU_drand), and the engine's UNIX heritage it makes perfect sense... After all, as odd as it sounds, pseudo-random number generators have to be consistent - I suspect the engine originally uses a UNIX C library function, but when it was ported, its own implementation was needed so it gave the same results on different platforms.

The reason it isn't mentioned in the docs is because no-one has ever asked before, nor had a reason to need to know I guess.

I must confess the 'PCG' paper you cite does look to me a bit like various papers over the years I've seen claiming 'Ive found the best compression algorithm which compresses everything better' - I only skim read it, but couldn't actually find direct comparisons of the proposed PCG functions with the other test bed random number generators quoted (and thus can see why it was rejected, it looks like it spends most of the paper comparing other functions, without putting the proposed one up to scrutiny!).

Another red flag with the paper is that it attempts to compare arc4random with the others - arc4random is a pseudo-random number generator, certainly, but is designed to give cryptographic quality results by using an separate entropy mechanism to ensure the internal state from which the pseudo-random numbers are generated is essentially random - https://man.openbsd.org/arc4random.3. (The point here is that this makes it completely unpredictable in any given instance as the state used to generate the number is not knowable).

Anyway, if you want a pseudo-random number generator - i.e. so you do have repeatability from a seed (which is really important for procedural generation, for example - e.g. a minecraft world is completeld determined by a seed value for such a thing) - then I don't think drand is bad but there are obviously others to explore.

If you actually want a much closer approximation to randomness (which is not reproducible via a seed) then you probably want to use the randomBytes() function - this returns 'cryptographic quality' random bytes using the host OS's generator of such. On mac/iOS it uses arc4random_buf, on linux/Android it uses /dev/random (https://en.wikipedia.org/wiki//dev/random) - and on Windows it uses CryptGenRandom (https://docs.microsoft.com/en-us/window ... tgenrandom).

[ Note: The reason we use arc4random where it is available - i.e. on mac/iOS - is because it has better performance than directly pulling bytes from the OS's entropy pool and is generally considered not to have any impact on the quality of the random data ]

FourthWorld
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9802
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

Re: What algorithm for random() function?

Post by FourthWorld » Wed Sep 29, 2021 9:36 am

Good to see you back here, Michael.

Any personal reference was about the instructor you mentioned, not you.

It seems you missed my earlier posts, this one in particular:
viewtopic.php?f=7&t=36091#p206954

The video of the talk I linked to there may help clarify where I'm coming from with randomness.

Without knowing the application, there is no way to say one psuedorandom algo is "better" than another.
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn

Post Reply

Return to “Getting Started with LiveCode - Complete Beginners”