3 ms·
The post mentioned that they want low (preferably constant) memory use to support embedded use. Unfortunately, the faster you get, the more memory you use when
by sobellian 8y ago
The post mentioned that they want low (preferably constant) memory use to support embedded use. Unfortunately, the faster you get, the more memory you use when it comes to multiplication. For this reason, they don't even use Karatsuba or Toom-Cook multiplication.
- stephencanon 8y agoThere’s been some nice recent work on time and space efficient integer and polynomial multiplication. Of particular note in this case, you can do karatsuba with only O(log(n)) workspace, at the cost of some additional bookkeeping. See, e.g., https://www.usna.edu/Users/cs/roche/research/papers/lsmul.pdf https://www.usna.edu/Users/cs/roche/research/papers/lsmul.pd...