4

I am working on a big integer library in the online compiler. Currently having gas/computational time issues with the modulus function.

I first implemented it using repeated subtraction:

function mod2(uint8[2] x, uint8[2] m) returns(uint8[2])
{
    // Check some special cases
    if (compa(m, [0, 0]) == 0)
        throw;
    if (compa(x, [0, 0]) == 0)
        return x;
    if (compa(m, x) == 0)
        return [0, 0];
    if (compa(m, x) == 1)
        return x;

    uint8[2] memory r = x;

    // Subtract
    while (compa(r, m) != -1)
        (r,) = sub(r, m);

    return r;
}

I then tried bit-shift and subtract:

function mod(uint8[2] x, uint8[2] m) returns(uint8[2])
{
    // Check some special cases
    if (compa(m, [0, 0]) == 0)
        throw;
    if (compa(x, [0, 0]) == 0)
        return x;
    if (compa(m, x) == 0)
        return [0, 0];
    if (compa(m, x) == 1)
        return x;

    uint8[2] memory r = x;
    uint8[2] memory n = m;

    // Align most significant bit
    while (compa(x, n) == 1 && n[n.length-1] & 0x80 != 1)
        n = shift(n, 1);
    if (compa(n, x) == 1)
        n = shift(n, -1);

    // Subtract
    while (compa(r, m) != -1)
    {
        (r,) =  sub(r, n);
        n =     shift(n, -1);
    }
    return r;
}

Complete contract here. Addition and subtract is add() and sub(); shift() is bitwise-shift with positive values being right and negative values being left. Compa() is a comparison function that returns 1 if greater, 0 if equal, and -1 if less than.

The end goal is to handle 1024-bit integers as four 256-bit integers. I am using two 8-bit integers currently as it is much easier to debug.

For both cases, with a sufficiently large difference between the input and modulo (i.e. 255 % 4), the online compiler hangs and crashes.

The second implementation scales a bit better than the first one, but it seems to have a lot of overhead.

I was wondering if this was an issue with the online complier. Or if my code is just really slow? Even if I am using naive implementations, I didn't think the code would take this long to run or crash.

Update: Optimized the bitwise-shifts, 255 % 4 no longer crashes. Still quite slow though.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.