2 ms·
A base 8 or 16 version of this might be useful for calculating products on old CPUs without a multiply instruction, without having unreasonably large tables. O
by jepler 3y ago
A base 8 or 16 version of this might be useful for calculating products on old CPUs without a multiply instruction, without having unreasonably large tables.
One table driven way of accelerating 8×8 bit multiplication with a table of modest size (e.g., 256 words) is https://dercuano.github.io/notes/multiplication-with-squares.html https://dercuano.github.io/notes/multiplication-with-squares... -- however since there are 17578 distinct products of two 8 bit numbers, even a full Irish Logarithm table would probably be infeasible to store in most systems where the technique would be relevant. (you've used over 50% of a 16-bit address space on the table) And 6 table look-ups for 4 bits at a time is likely to be slower than 2 table look-ups for the 8-bit square table, even with the extra bit shifting required.
- IshKebab 3y agoWould it though? The tables have 45 non-zero elements. The zeros aren't all regularly distributed so you're probably looking at storing way more than that. A full table with the answers stored directly is only 55 elements. Maybe I missed something but what's the point? Does it scale better than N^2?
- jepler 3y agoyeah I'd kinda talked myself out of it the idea the end of my own post.