1

I need a 110-length lookup table that stores numbers from 1 to 20.

I think the solution might be to move the instruction pointer forward by the index, and then return. Is something like this possible? For example:

JumpForward index
return 1
return 2
return 2
etc...

Following are what I've tried so far, compiling with optimizations on:

A table in memory - 3086 gas

function lookup(uint256 index) private pure returns (uint256) {

    uint8[110] memory bellCurveTable = [
         1,
         2, 2,
         3, 3, 3,
         4, 4, 4, 4,
         5, 5, 5, 5, 5,
         6, 6, 6, 6, 6, 6,
         7, 7, 7, 7, 7, 7, 7,
         8, 8, 8, 8, 8, 8, 8, 8,
         9, 9, 9, 9, 9, 9, 9, 9, 9,
        10,10,10,10,10,10,10,10,10,10,
        11,11,11,11,11,11,11,11,11,11,
        12,12,12,12,12,12,12,12,12,
        13,13,13,13,13,13,13,13,
        14,14,14,14,14,14,14,
        15,15,15,15,15,15,
        16,16,16,16,16,
        17,17,17,17,
        18,18,18,
        19,19,
        20
    ];

    return bellCurveTable[index];
}

An if-else chain - 45 to 449 gas

function lookup(uint256 index) private pure returns (uint256) {
    if      (index <=   0) return  0;
    else if (index <=   2) return  1;
    else if (index <=   5) return  2;
    else if (index <=   9) return  3;
    else if (index <=  14) return  4;
    else if (index <=  20) return  5;
    else if (index <=  27) return  6;
    else if (index <=  35) return  7;
    else if (index <=  44) return  8;
    else if (index <=  54) return  9;
    else if (index <=  65) return 10;
    else if (index <=  76) return 11;
    else if (index <=  86) return 12;
    else if (index <=  95) return 13;
    else if (index <= 103) return 14;
    else if (index <= 110) return 15;
    else if (index <= 116) return 16;
    else if (index <= 121) return 17;
    else if (index <= 125) return 18;
    else if (index <= 128) return 19;
    else                   return 20;
}

An assembly switch statement - 94 to 2445 gas (estimated)

function lookup(uint256 index) private pure returns (uint256 stat) {
    assembly {
        switch index
        case   0 { stat :=  0 }
        case   1 { stat :=  1 }
        case   2 { stat :=  1 }
        case   3 { stat :=  2 }
        case   4 { stat :=  2 }
        case   5 { stat :=  2 }
        case   6 { stat :=  3 }
        case   7 { stat :=  3 }
        case   8 { stat :=  3 }
        case   9 { stat :=  3 }
        case  10 { stat :=  4 }
        case  11 { stat :=  4 }
        case  12 { stat :=  4 }
        case  13 { stat :=  4 }
        case  14 { stat :=  4 }
        case  15 { stat :=  5 }
        case  16 { stat :=  5 }
        case  17 { stat :=  5 }
        case  18 { stat :=  5 }
        case  19 { stat :=  5 }
        // etc...
        default  { stat := 20 }
    }
}
1

Answering my own question, I found a decent way. But I'm sure there are methods that cost less gas. I'd still appreciate further help.

Using a string constant - 139 gas

string constant bellCurveTable = "\
A\
BB\
CCC\
DDDD\
EEEEE\
FFFFFF\
GGGGGGG\
HHHHHHHH\
IIIIIIIII\
JJJJJJJJJJ\
KKKKKKKKKK\
LLLLLLLLLL\
MMMMMMMMM\
NNNNNNNN\
OOOOOOO\
PPPPPP\
QQQQQ\
RRRR\
SSS\
TT\
U\
";

function lookupString(uint256 index) public pure returns (uint256) {
    bytes memory bellCurveTableBytes = bytes(bellCurveTable);
    return uint256(bellCurveTableBytes[index]) - 64;
}
3
  • I think is not gonna be better than this. Also, from a practical point of view 139 gas is nothing.
    – Jaime
    Jun 18 '18 at 14:37
  • 1
    An option is to store the curve data as bytes directly (ie bytes constant bellCurveTable = hex"00010202030303...";), but you will only save the subtraction of 64 at the end.
    – Ismael
    Jun 21 '18 at 3:04
  • Thanks, Ismael. That lowered the gas cost down to 83, from 139.
    – abtree
    Jun 22 '18 at 6:33
1

I would do it this way:

function lookup (uint256 index) public pure returns (uint256) {
    return uint8 (bytes (hex"0102020303030404040405050505050606060606060707070707070708080808080808080909090909090909090a0a0a0a0a0a0a0a0a0a0b0b0b0b0b0b0b0b0b0b0c0c0c0c0c0c0c0c0c0d0d0d0d0d0d0d0d0e0e0e0e0e0e0e0f0f0f0f0f0f101010101011111111121212131314") [index]);
}

** note the [index] at the end of this long line.*

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.