0
$\begingroup$

Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. This algorithm is theoretically interesting, but in practice completely silly because you only start to see advantages on numbers with an absurd number of digits.

But suppose that we only wanted a probabilistic multiplication circuit, which returned the wrong result with probability at most epsilon. Then maybe certain shortcuts could be taken, in order to avoid the most inconvenient parts of multiplying two numbers.

For a fixed acceptable failure rate epsilon, is there an O(n log n) multiplication algorithm that achieves this failure rate without being horrendously inefficient in practice?

$\endgroup$
0
$\begingroup$

There is no acceptable failure rate. There are cryptographic systems that can be cracked if the 64x64 but multiplication of your processor gets one single product consistently wrong.

Unless your eps is so small that my computer being destroyed by a meteorite is more likely than getting a product wrong.

$\endgroup$

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.