Talk

The Power of a Look-up Table

Watch Now

52:55

EOC 2024

Login to Watch

Nathan Jones

Nathan Jones is an embedded systems engineer and educator focused on understanding how low-level systems behave — and how they fail. His work explores the boundary between hardware and firmware, including debugging, firmware development, and practical embedded security considerations. He is a frequent contributor to DigiKey and EmbeddedRelated, where he writes on topics including microcontroller architecture, debugging techniques, and practical embedded system design. Nathan earned a Bachelor of Engineering from Harvey Mudd College in 2010 and a Master of Computer Engineering from North Carolina State University in 2020. He has taught digital logic, computer architecture, electrical engineering, and physics at the United States Military Academy at West Point, where he developed entire courses and delivered hands-on laboratory instruction for future Army officers. Nathan has been invited to speak at the Embedded Online Conference, CppCon, Hackaday Superconference, the Embedded Systems Summit, JawnCon, and Teardown. He lives in Tennessee with his wife, two children, and one black cat.

View full profile

Topics Covered

C C++Software Design

Talk

The Power of a Look-up Table

Nathan Jones

52:55 EOC 2024

Nathan Jones

52:55

Look-up tables have been speeding up math operations for time immemorial, but there's more to this simple programming "idiom" than just numbers in an array. Join me in this talk as we discover and categorize the different ways we can store and retrieve data from arrays in ways that enable all sorts of fun and useful things, from creating digital music to building jump tables that drive command parsers or finite state machines.

1 / 5

Please log in or create an account to test your knowledge and see the answers.

What is the primary trade-off Nathan emphasizes when picking or tuning a lookup-table implementation (for example, a sine table)?

A Balancing speed, memory usage, and accuracy to find the right spot for your application.

B Always choose a lookup table because it provides maximum accuracy compared to library functions.

C Minimize table size at all costs because lookup tables are always slower than computing functions.

D Use lookup tables to avoid any bounds checking or safety checks in code.

E Prefer polynomial approximations because lookup tables cannot be tuned for performance.

Why does Nathan recommend using static and const for a function-local lookup table that doesn't change at runtime?

A Because const helps the linker store the table in flash (not RAM) and static prevents the table from being copied onto the stack each call.

B Because static const forces the CPU to keep the table permanently in the L1 cache.

C Because static const makes the table writable at runtime so you can update its values freely.

D Because static const automatically encrypts the table contents to protect intellectual property.

E Because static const creates multiple copies of the table to improve reentrancy.

What benefit does piecewise linear interpolation and/or a sparse table provide over a simple nearest-sample lookup for a function like sine?

A It significantly reduces lookup error for the same or smaller table size by interpolating between nearby stored samples and concentrating points where the function changes rapidly.

B It always makes lookups faster than direct nearest-sample lookup because interpolation requires no arithmetic.

C It removes the need to consider accuracy because interpolation guarantees exact function values.

D It eliminates the need for bounds checking since interpolation only uses interior samples.

E It forces you to use floating-point math and prevents fixed-point implementations.

When inputs are not contiguous positive integers (e.g., strings, sparse keys, negative numbers), which approaches does Nathan recommend for indexing into a lookup-table?

A Use hashing, indirect indexing (index table → value table), or sparse key–value lists (with search), instead of relying on direct contiguous indexes.

B Require every caller to convert their inputs into consecutive positive integers before calling the lookup function.

C Avoid lookup tables entirely and always use deeply nested if-else chains for such inputs.

D Allocate a table large enough to cover every possible integer including negatives and map inputs by adding a huge offset.

E Use recursion over the table entries rather than hashing or indirect indexing.

Why does Nathan recommend using a two-dimensional array of function pointers (a jump table) to implement a finite state machine?

A Because a state-by-event table of function pointers makes dispatch compact, easy to visualize and modify, and avoids sprawling nested switch/case code for each state/event pair.

B Because function-pointer tables are always faster than any switch-case on all platforms regardless of table size.

C Because using a jump table means you no longer need to write separate handler functions for each transition.

D Because jump tables automatically validate inputs and prevent state-machine bugs without tests.

E Because function-pointer tables eliminate the need for maintaining state variables.

Formatting help

italics	surround text with asterisks
bold	surround text with two asterisks
hyperlink	[hyperlink](https://example.com) or just a bare URL
inline code	surround text with single `backticks`
code block (multi-line)	wrap on its own lines with three backticks: ``` your code here ```
~~strikethrough~~	surround text with ~~two tilde characters~~
quote	prefix with >

Upvotes Newest Oldest

mjlinden

Score: 0 | 2 years ago | no reply

An excellent presentation on an often overlooked aspect of embedded systems design.

Phil_Kasiecki

Score: 0 | 2 years ago | no reply

A great talk on a subject not talked about enough - and thank you for your service, Nathan.

SimonSmith

Score: 0 | 2 years ago | no reply

Good talk. I think you meant 0.5mm accuracy, not 0.5cm at 03:30 in? The library function performance depends on if you have a double or single precision MMU. One major advantage of tables is ensuring all cases/states are covered, easily missed in complex nested if else statements. I’ve used a variation of memoisation, where the tables are.stored in RAM and fully computed once during initialisation when there’s time to do so. I’ve found a good use for them in generic UART configuration and handlers. There are examples of table-based initialisation of tasks in Jacob’s book. I partcularly liked your button metadata and CLI parser.

Carlos.Amaya

Score: 0 | 2 years ago | no reply

Thank you very much Nathan, I am always looking forward to your talks in the conference. I really appreciate your thorough investigation and great delivery. Thanks for the book recommendation.

DaveK

Score: 1 | 2 years ago | no reply

Thanks for that thorough presentation on lookup tables. I think you touched on every way I have used lookup tables over the years and more.. A classic use case is for really fast CRC generation. Thanks for providing the links. Good stuff.

Thomas.Schaertel

Score: 1 | 2 years ago | no reply

Great talk, Nathan! I loved how you applied LUTs in different practical applications and also provided additional links for reading. Thank you so much. I sometimes forget how invaluable and expandable LUTs are.

nathancharlesjonesSpeaker

Score: 0 | 2 years ago | no reply

Slides are now posted. Sorry about the delay, folks!

Partners & Sponsors

STMicroelectronics

Memfault

NXP

Micro Digital, Inc.

MySQL

Become a Sponsor