Hi all,

As a side project, I am porting the rand* commands on TI-84 PLUS (rand, randInt, randBin, randIntNoRep, randM and randNorm) to Python. This will enable you to generate random numbers on your PC that are the same as the ones the calculator gives.

For example, to make groups, my teacher asks me a seed for rand, gives us all a number and then divides groups with randInt. I would like to generate a seed so I am together in a group with a friend of mine. In order to do that, I want to bruteforce a seed that sets us together on my PC.

So I started with porting the rand command to python. Thanks Richard. I then ported randInt and randBin (just for completeness). I am now stuck at randIntNoRep. Can anyone post an implementation of it in TI-BASIC or another PL? It will need to ouput the same numbers as the original randIntNoRep command (assuming you are using the same seed).

In case you are curious, here is the code I already have.

I added support for randM. An implementation of randIntNoRep is still wanted

I haven't looked into the OS to see how it implements randInNoRep, but have you tried the equivalent of the following?

Code:

Is this the same as the implementation on http://tibasicdev.wikidot.com/randintnorep ? Tried that, it didn't work. (it worked but gave other values).

Code:

Can you not just use random? For example:

Code:

obviously there's more in the library.

Why do you need your own library if there's random?

The PRNG underlying Python's random numbers is not the same as the one that TI-BASIC uses. He wants to be able to get the same random numbers from the same seed that he would get on a calculator.

Yes, it's essentially the same as that, but in Python.

Do we know where the OS PRNG is located?

The algorithm is documented in many places, here is an example.

@CVSoft
I already have the algorithm for rand, and then derived randInt, randBin, randM. The problem is that I don't know how the algorithm for shuffeling (randIntNoRep) works.
@elfprince13
What (free & opensource) tools would one use to reverse engineer this?

An emulator (e.g. jsTIfied, WabbitEmu) and/or https://github.com/drdnar/eZDisasm are important tools for reverse engineering.

Resurrecting this topic because I've found that although the known algorithm generates correct results in general, I also want to understand the rounding behavior of EOS because it seems that the guard digits (which the calculator normally never displays) differ from what I get with implementations that have greater precision.

To begin, I threw together this TI-BASIC program to display all 14 digits of a number (including the 4 guard digits) from Ans, and verified the results by checking the contents of Ans in memory using a debugger:
Code:


When I start with the default seed on a calculator (0->rand), the digits of the first result are 94359740249213. Now compare with the results of this Python implementation, still using decimal floats and arbitrary precision:

Code:


This yields Decimal('0.9435974025194436377625489653'), which differs from the calculator beginning in the 10th digit (which rounds to the same value as displayed by a calculator).

Where things get a bit weird is that by inspecting the algorithm, all of the operations are integer arithmetic except the division to compute result so there doesn't seem to be much room for EOS to introduce rounding error. Possibly the integer multiplications could get large enough that they get rounded off, but offhand I doubt that's actually possible.

So does anybody else have ideas of where the error creeps in? Bonus points if you can express it in Python to get the Python version to yield the exact same result as EOS returns; I hope it might just be doing a x.round(10) or something in the right place!

I don't really want to try to completely reverse-engineer the romcall for generating random numbers, so I ran through evaluating rand in an emulator with watchpoints set on the OP pseudo-registers while watching their values. At various times I saw the expected default seed values (12345 and 67890) and several of the expected intermediate values seed1*mult1=493972830 and (seed2*mult2)%mod2=615096481.

At one point I noticed a value that differed ever so slightly from the documented values: I saw 2147483562 which is one less than the documented value for mod1. Just modifying the code to use that value for mod1 yields a result closer to what EOS returns, but still not perfectly accurate: I get 0.9435974024931791305604415146, which now differs in the 12th digit. Possibly TI's programmers slightly modified the constants used in L'Ecuyer's algorithm as a kind of trapdoor to detect implementations that copy theirs? (Although based on the description of section 4 of the paper, modifying the constants could negatively impact the quality of random numbers.)

I also saw the value 0.230025340985317 fly past at one point, which got the last digit rounded off (..317 became ..320). That doesn't seem to correlate very well with any values that actually appear in the algorithm, but observing that round-off might provide evidence for other rounding that I'm not currently accounting for.

I was reviewing the paper in more detail because I wasn't making much progress continuing to use a debugger, and realized that the algorithm detailed in Figure 3 includes many of the mystery constants that I saw moving through the OP registers (including 53668, 12211, 52774, 2147483562 and something with mantissa 4656613059555)!

That algorithm transcribed (it's apparently written in Pascal):
Code:


A quick reimplementation of this in Python didn't yield results at all like what I expect, but I'm confident this does accurately reflect what EOS does and the weird result I got is just an issue with my implementation.

---

Updated: I learned that DIV in Pascal is integer division (after I noticed that it didn't make sense to be taking seed1 / 53668 then multiplying that by 53668 again), and this Python version now yields a precise result when compared with EOS:
Code:

The first value returned by this implementation is 0.9435974024921307499605, which rounds to the value 0.94359740249213 that EOS generates!

A few bonus comments:

TI's constant for multiplying z is close to 2147483562⁻¹ (which would be the right choice to uniformly distribute output values given the range of z), but is about 5e-12 larger than the actual value of 2147483562⁻¹. Given the calculator has the precision to match to within 5e-15, it's not clear to me why it differs.

The choice of L'Ecuyer's algorithm is rather silly, given it's actually implemented with floating-point arithmetic but the algorithm is designed to be efficiently implemented with mostly 32-bit integer operations. Possibly they used this algorithm to match older calculators that did implement it with integer arithmetic, though I also feel a good calculator RNG could simply generate 14 digits in the range 0-9 to yield a value in the half-open range [0,1) and that could be much simpler.

It seems likely that this algorithm was used since at least the TI-81 (introduced in 1990) so the implementation in EOS probably does predate algorithms that are now more common and have much longer periods such as the Mersenne Twister (though MT needs quite a lot of state and the TinyMT variant that only needs 16 bytes of state wasn't proposed until 2011).