class Integer

Public Instance Methods

bits_set() click to toggle source

SWAR algorithm for finding the number of set bits.

VALUE swar_bits_set(VALUE self)
{
    long long l = NUM2LONG(self);
    l -= ((l >> 1) & 0x55555555);
    l = (l & 0x33333333) + ((l >> 2) & 0x33333333);
    return INT2FIX((((l + (l >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24);
}
mod_exp(p1, p2) click to toggle source

c = PI(n-1, i=0, (b^2^i)) % m

VALUE modular_power(VALUE self, VALUE exponent, VALUE modulus)
{
    VALUE result = INT2FIX(1);
    VALUE base = self;

    int exp = NUM2INT(exponent);

    if( (modulus << 1) == 0 )
    {
        // Avoid divide by zero
        return Qnil;
    }

    while(exp > 0)
    {   
        if(exp & 1)
            result = rb_funcall(rb_funcall(result, SYM(*), 1, base), SYM(%), 1, modulus);
        exp >>= 1;
        base = rb_funcall(rb_funcall(base, SYM(*), 1, base), SYM(%), 1, modulus);
    }

    // If the numbers become an issue we will switch to INT2NUM to allow for Bignums
    return result;
}