在R中优化算法方法

Question

openssl软件包实现了一个bignum类，具有执行任意大小整数计算的相应算术和比较方法。

在密码学中，模幂x^p %% m是一种常见的特殊情况，例如RSA。对于大的p，计算x^p是不可行的，但可以高效地计算x^p %% m，OpenSSL在BN_mod_exp()中实现了这一点。

R是否提供任何机制来实现^.bignum和%%.bignum方法，以便在评估x^y %% z时，我们可以调用这个特殊情况，而不是实际计算x^p？

- Jeroen Ooms

---

问题是是否有一种方法可以导出 ^ 和 %% 方法，这样 x^y %% z 就能使用例如 powm(x,y,z) 而不是 mod(pow(x,y),z)。 - Jeroen Ooms

看一下?Ops。它们是通用的，因此如果您所需的调用未定义这些运算符，则添加特定于类的S3或S4方法不应该很困难。 - IRTFM

我认为可能不完全符合您的要求。像@42-建议的那样为单个二进制运算符编写方法并不是什么大问题，@TheTime提出了一个合理的替代方案，但我认为解析器/用户对解析器的控制不够灵活，无法识别x OP1 y OP2 z应该被解释为F(x,y,z)... - Ben Bolker

我也没有这样想过，但是我认为如果x OP1 y返回所需调度的OP2.class的同一类对象，则可以获得所需的操作。 - IRTFM

Answer 1

迟到了，但是没关系，这是完全可能的，而且在某些语言中（如C++），这是一种常见的编程技巧，被称为 表达式模板。

由于R是弱类型语言，所以无法完全利用该模式。但是轻量级版本仍然是可能的。

简而言之，你需要定义你的^.bignum运算符，使其返回一个代理对象，表示“指数运算”，而不是立即计算结果。此代理对象具有特殊覆盖的%%方法，该方法调用ExpMod实现（例如BM_mod_exp）。它还定义了一种方法，通过计算实际的x ^ y操作将其强制转换为bignum。

代码示例如下：

# 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.

事实上，您甚至可以覆盖=.bignum_mod_exp_proxy、<-.bignum_mod_exp_proxy和assign.bignum_mod_exp_proxy（将assign转换为S3通用函数），以便将赋值z = x ^ y急切地评估为bignum。但是，这可能过于复杂，并且会为每个赋值产生开销。

- Konrad Rudolph