# Gas cost for bigInt library

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 x, uint8 m) returns(uint8)
{
// 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 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 x, uint8 m) returns(uint8)
{
// 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 memory r = x;
uint8 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.