Fast On-line Integer Multiplication
A Turing machine multiplies binary integers on-line if it receives its inputs low-order digits first and produces the jth digit of the product before reading in the (j+l)st digits of the two inputs. We present a general method for converting any off-line multiplication algorithm which forms the prod...
| Principais autores: | , |
|---|---|
| Publicado em: |
2023
|
| Acesso em linha: | https://hdl.handle.net/1721.1/148874 |
| Resumo: | A Turing machine multiplies binary integers on-line if it receives its inputs low-order digits first and produces the jth digit of the product before reading in the (j+l)st digits of the two inputs. We present a general method for converting any off-line multiplication algorithm which forms the product of two n-digit binary numbers in time F(n) into an on-line method which uses time only O(F(n) log n ), assuming that F is monotone and satisfies n F(n) F(2n)/2 ! kF(n) for some constant k. |
|---|