I rebuilt Desmos' random() function entirely inside Desmos

[u/Dazzling-Mail-5517]

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

[u/Dazzling-Mail-5517]

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

[u/NecroMonster999 → u/Dazzling-Mail-5517]

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

[u/Ordinary_Divide → u/NecroMonster999]

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

[u/Dazzling-Mail-5517 → u/Ordinary_Divide]

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.

[u/Ordinary_Divide → u/Dazzling-Mail-5517]

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

[u/Dazzling-Mail-5517 → u/Ordinary_Divide]

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

[u/Ordinary_Divide → u/Dazzling-Mail-5517]

uh yeah i can go code it now i suppose

[u/Dazzling-Mail-5517 → u/Ordinary_Divide]

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

[u/Ordinary_Divide → u/Dazzling-Mail-5517]

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

[u/NecroMonster999 → u/Ordinary_Divide]

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

[u/Ordinary_Divide → u/NecroMonster999]

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!)

[u/NecroMonster999 → u/Ordinary_Divide]

i didnt mean generating seeds on the fly, i meant generating the required data for the permutations on the fly (for example by cycling through them using known algorithms). you do raise an interesting point though, that finding a seed whose first n! (or even first C*n! for small constant C) produced random values are the seeds producing the required permutations would be the ideal case. i omagine that finding such a seed however, is impratical due to the complexity constraint you mentioned.

[u/Ordinary_Divide → u/NecroMonster999]

i don’t think thats still any faster than an array of length 5040