| How can I use very large integers like TIOS?

Previous | Miscellaneous | Next

Q:

I need to know more about how the TIOS stores and references big integers. In other words, what would be the C structure that would be used to represent any arbitrarily-long binary integer? In addition, I am particularly interested about how two extermely long binary integers would be multiplied and divided. Does TIOS have its own binary multiplication routine somewhere in the ROM? Something that works similarly to BCD multiplication/division, I'm guessing?

A:

TIOS stores all integers (both small and large) in the following format (looking from lower to higher addresses):

1. Bytes of the integer in little endian (up to 255 bytes);
2. The number of bytes occupied by integer (one byte);
3. POSINT_TAG or NEGINT_TAG, depending on the sign.

These integers are kept on the expression stack, or in TI-Basic variables (of course, in TI-Basic variables, there are two extra bytes at the begining, which represents the length of a variable). In other words, integers are kept in a structure which is similar to the BN structure defined in the rsa.h header file, except the length byte is at the end, not at the begining (because data on the expression stack is always in RPN). So, such a structure can't be strictly represented using valid C syntax, because it requires something like

    struct big_int
      {
        BYTE data[size];   // but 'size' is not known in advance
        BYTE size;
        BYTE tag;
      }

Routines for multiplying and dividing very long integers surely exist in the TIOS, but the strange fact is that such routines are not in the TIOS jump table (read: they are not usable). Anyway, you can always use general eveluating routines like NG_rationalESI and NG_approxESI. For example, to multiply two very-long-integers, you can use the following template:

    push two very-long-ints on the estack
    push_quantum (MULT_TAG);
    NG_approxESI (top_estack);

However, two routines for working with long integers are in TIOS jump table: for calculating `'(A*B)%N'` and `'(A^B)%N'` where "%" is the "modulus" operation, and "^" is "raising to a power". These operations are used in the RSA cryptosystem. Both of them are defined in the rsa.h header file. They may be used for multiplying and raising to a power: you always can set `N` to very a big number, then `(A*B)%N = A*B`. Also, you can use them for calculating modulus (if you set `B` to 1). But, I am not sure how you can simulate division. I think that TI never uses integer division: everything like `'A/B'` is kept as a fraction, except in approx mode; TIOS then uses NG_approxESI.