1
$\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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
-1
$\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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This does not answer the question. Whether a probabilistic multiplication circuit using $O(n \log n)$ gates has any practical use is irrelevant to the question, which is whether such a circuit exists. Also, a bounded-error probabilistic algorithm by definition will not get any product consistently wrong, but only wrong with a bounded probability over the random bits. $\endgroup$
    – Aaron Rotenberg
    Commented Jan 14, 2020 at 23:37
  • $\begingroup$ Feel free to post a better answer. I'm looking forward to it. If none is forthcoming then I will draw my conclusions. $\endgroup$
    – gnasher729
    Commented Jan 15, 2020 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.