9

I am try to compute the baby step giant step algorithm to find the discrete logarithm. But because of the warning I can't compile the code. It appears at the uint256[] storage A and uint256[] storage B

Here is the code:

function squareRoot(uint256 x) public returns (uint256 y) {
    uint256 z = (x + 1) / 2;
    y = x;
    while (z < y) {
        y = z;
        z = (x / z + z) / 2;
    }
}

function ceiling(uint256 a) constant returns (uint256) {
    return (a / 1) * 1;
}

function proofOfWorkOptimized() onlyOwner public {
    uint256 base = 19;
    uint256 exponent;
    uint256 modulo = 221;
    uint256 valueAtIndexi;
    uint256 valueAtIndexj;

    uint256 rootCeiling = ceiling(squareRoot(modulo));

    uint256[] storage A;
    uint256[] storage B;

    for (uint256 i = 1; i <= rootCeiling; i++){
        uint256 result = base**i % modulo;
        A.push(result);
    }
    for (uint256 j = 0; j < rootCeiling; j++){
        result = base**(rootCeiling*j) % modulo;
        B.push(result);
    }
    for (i = 1; i <= A.length-1; i++){
        for (j = 1; j <= B.length-1; j++){
            if (i == j){
                valueAtIndexi = A[i];
                valueAtIndexj = B[j];
                break;
            }
        }
    }
    exponent = ((valueAtIndexj + 1)*rootCeiling - valueAtIndexi) % modulo;

How can I fix it?

8

This is a little tricky. Unless you have a genuine reason not to, then you should declare A and B as memory, not storage. As it stands, your code writes 28 times to storage, which would cost 28 * 20,000 = 560,000 gas, a huge amount. Putting the arrays in memory would be substantially more efficient.

Declare A and B thus:

uint256[] memory A = new uint256[](rootCeiling);
uint256[] memory B = new uint256[](rootCeiling);

To write to A and B as memory arrays, you can't use push. Just do this:

A[i-1] = result;
....
B[j] = result;

Incidentally, the nested loop doesn't use the [0] indices of the arrays; you probably don't need to compute them if that's correct.

Disclaimer: the above is untested (but it does compile), so E&OE.

P.S. If you genuinely want A and B to be in storage, just move the declarations outside of function scope into the main body of the contract and drop the storage declaration (it is implied):

Contract Foo {
    uint256[] A;
    uint256[] B;
    ...
4
  • Thank you very much! I tried both versions you recommended, using storage costs indeed a huge amount of gas, so i'll go with memory! Thanks again!
    – Slevin
    Nov 14 '17 at 7:14
  • Hi may I know why I got extreme high gas 500k after using your suggestion? Please have a look. Thank you: bool[] memory boolArray; for (uint i = 0; i < toArray.length; i++) { if (getBool(toArray[i])) { boolArray[i] = transfer(toArray[i], amountArray[i], data);}}
    – Russo
    Aug 5 '18 at 6:24
  • @Russo, how long is your array length? Aug 26 '18 at 18:05
  • I think it was about 7 or so...
    – Russo
    Aug 28 '18 at 14:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.