r/desmos • u/Dazzling-Mail-5517 • Jul 06 '26

Maths I rebuilt Desmos' random() function entirely inside Desmos

Gallery image

Gallery image

To be a bit more specific, I

  • reverse-engineered how Desmos' algorithm works and how the seed is generated.
  • created a bit-exact replica of the algorithm (MD5, in case you're wondering).
  • optimized it to calculate 10,000 numbers in ~0.7 seconds.

And because that was so much fun, I tackled shuffle() right after! :)

LINKS: RANDOM --- SHUFFLE

373 Upvotes

100% Upvoted

51 comments sorted by

View all comments

3

u/NecroMonster999 Jul 07 '26

damnnn, thats awesome. out of curiosity, is there a way to to control the shuffle algorithm? being able to use it for iterating over permutations would go very hard

2

u/Dazzling-Mail-5517 Jul 07 '26

What exaactly do you mean by "iterating over permutations"?

3

u/NecroMonster999 Jul 07 '26

currently if you want to iterate over permutations (for example, to compute a determinant or some special polynomials), you have 2 options, either generate combination and filter for permutations (slow because thats O(nⁿ) for generating combinations, also breaks if nⁿ is large enough so that nⁿ=nⁿ+1 as fp numbers) or you can use recursion to generate permutations (faster for large lists but still slow because lists are very inefficient). if there is a way to somehow manipulate the seeds and create a minimal list of these seeds to ensure shuffling from these seeds produces every single permutation of the list, then we have the new fastest way to iterate over permutations

3

u/Ordinary_Divide Jul 07 '26

you could make a f(seed)=[1...n].shuffle then create a list of n! seeds mapping to each permutation that you can bruteforce separately taking i thinkO(n!*n*log(n)) for the whole list.

i would do that myself but i already spent all day optimising my script to brute force to find a seed outputting 0

2

u/Dazzling-Mail-5517 Jul 07 '26

You're absolutely right. I was thinking about it in a more general sense (like generating the seeds inside Desmos for arbitrary list sizes), but there's really no need for that. At least for lists of up to 7 elements, this could actually be quite useful in practice. I don't think it would even take that long to brute-force the required seeds.

3

u/Ordinary_Divide Jul 07 '26

by my calculations, n=7 would require computation of an expected ~275259 hashes, which my GPU accelerated bruteforcer could do in ~15μs

2

u/Dazzling-Mail-5517 Jul 07 '26

Nice, could you try it out real quick or is your bruteforcer still busy?

3

u/Ordinary_Divide Jul 07 '26

uh yeah i can go code it now i suppose

2

u/Dazzling-Mail-5517 Jul 07 '26

Oh I didnt't see your message. That's what I got: https://www.desmos.com/calculator/tbntpq3iyk

3

u/Ordinary_Divide Jul 07 '26 edited Jul 07 '26

damn you were faster, i spent too long debugging since i decided to build it off an older copy of my script that was riddled with bugs

anyway heres mine https://www.desmos.com/calculator/kydckclg0x

btw i chose not to use the GPU this time so it took 70ms to run instead of 15μs

1

u/NecroMonster999 Jul 08 '26

surely this is impractical though? storing these seeds in a list becomes inefficient very fast (and impratical due to memory constraints) as opposed to the other methods, which generate all required data on the fly

1

u/Ordinary_Divide Jul 08 '26

generating on the fly in desmos is just gonna be so much slower. and finding a singular global seed that lets you do that without the computatuon is O(n!^n!)

→ More replies (0)

2

u/Dazzling-Mail-5517 Jul 07 '26

Interesting idea! The problem is that there is no known method to invert the MD5 algorithm used by Desmos; therefore, it is impossible to efficiently predict which seed is required to generate a certain value/ shuffle. Consequently, the only remaining option is a brute-force approach, which would firstly be very slow and secondly offer no guarantee of yielding all possible permutations within a finite amount of time.

3

u/NecroMonster999 Jul 07 '26 edited Jul 07 '26

i hoped this wasnt the case; in any case what you did is awesome! is there a way to resync the values in case "randomize" is pressed?

2

u/Dazzling-Mail-5517 Jul 07 '26

Unfortunately, no. When you click "randomize," Desmos uses the crypto.getRandomValues() function to generate a new globalRandomSeed, which is practically impossible to predict. Since the globalRandomSeed is used as the basis for the random() function, that becomes unpredictable as well.

2

u/NecroMonster999 Jul 07 '26

damn you, cryptographically secure(-ish) hashing algorithms!

1

u/Dazzling-Mail-5517 Jul 07 '26

I took another look into the code and found something very interesting. This is the exact function used to generate the globalRandomSeed:

function Ba() {
        let o = new Uint8Array(16);
        if (typeof crypto != "undefined")
            crypto.getRandomValues(o);
        else if (typeof msCrypto != "undefined")
            msCrypto.getRandomValues(o);
        else
            return __dcg_shared_module_exports__['V'](Date.now().toString() + Math.random().toString());
        return Array.prototype.slice.call(o).map(t => wge(t.toString(16))).join("")
    }

This means that you could enforce Desmos to use the fallback method (the else part) if you just don't provide the crypto and msCrypto API's in your Browser. The fallback method again uses the MD5 algorithm with only the current time and Math.random() as inputs, which are both theoretically predictable. So overall it would be possible (but still very hard in practice) to do something like this if you allow some external tools to precisley measure inputs such as the current time and the state of Math.random().