Optimized arithmetic methods in R

Question

The openssl package implements a bignum class with the corresponding methods for arithmetic and comparison to perform calculations on arbitrary sized integers.

In cryptography there is a common special case for the modular exponent x^p %% m which is used by e.g. rsa. For large p, calculating x^p is not feasible, but x^p %% m can be calculated efficiently which OpenSSL implements in BN_mod_exp().

Does R provide any mechanism to implement the ^.bignum and %%.bignum methods such that when evaluating x^y %% z we can call this special case rather than actually calculating x^p?

Answer 1

Late to the party but yes, this is absolutely possible, and it’s a moderately common programming technique in some languages, such as C++, where the technique is known as expression templates.

R, being weakly typed, cannot quite harness the pattern to the same extent. But a “light” version is still possible.

In a nutshell, you define your ^.bignum operator so that, instead or computing the result immediately, it returns a proxy object that signifies “exponentiation operation”. This proxy object has a specially overridden %% method that invokes the ExpMod implementation (e.g. BM_mod_exp). It also defines a method that coerces it to a bignum by evaluating the actual x ^ y operation.

In code this may look as follows:

# Vectorisation left as an exercise for the reader.

`^.bignum` = function (x, y)
    structure(c(x, y), class = 'bignum_mod_exp_proxy')

eval_exp = function (x)
    call_actual_exp(x[1], x[2])

as.bignum = function (x)
    if (inherits(x, 'bignum_mod_exp_proxy'))
        eval_exp(x)
    else
        # … implement other coercions to bignum, e.g. from `numeric`.

`%%.bignum_mod_exp_proxy` = function (x, y)
    call_BN_mod_exp(x[1], x[2], y)

# Pretend that a `bignum_mod_exp_proxy` in all other contexts. E.g.:

print.bignum_mod_exp_proxy = function (x, ...)
    print(eval_exp(x))

# … etc., for the rest of the `bignum` operations.

In fact, you could even override =.bignum_mod_exp_proxy, <-.bignum_mod_exp_proxy and assign.bignum_mod_exp_proxy (converting assign into an S3 generic), so that assignments z = x ^ y are eagerly evaluated to a bignum. However, this is probably overkill and would incur an overhead for each assignment.