Class: Integer

Inherits:
Object
  • Object
show all
Defined in:
(unknown)

Instance Method Summary collapse

Instance Method Details

#bits_set ⇒ Object

SWAR algorithm for finding the number of set bits.



11
12
13
14
15
16
17
 
# File 'ext/csyndi/integer.c', line 11

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(exponent, modulus) ⇒ Object

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



20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'ext/csyndi/integer.c', line 20

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;
}