# How do I make an efficient lookup table?

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

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;
}
``````
• I think is not gonna be better than this. Also, from a practical point of view 139 gas is nothing. Jun 18 '18 at 14:37
• 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. Jun 22 '18 at 6:33

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.*