Сколько битов потребуется для умножения двух 129-значных чисел, если машина имеет 64-разрядные слова?
Итак, я изучал и наткнулся на этот вопрос алгоритмов:
Итак, машина использует 64 бита для слов. Мы можем умножить два числа n слов с определенной сложностью. Если n равно 129, то сколько это бит?
Я немного запутался, как это сделать. Если слово будет 64-битным, то я думал, что 129 * 64 будет ответом, но это кажется очень большим количеством битов. Кто-нибудь может объяснить, как подойти к этой программе?
1 ответ
Умножение N-разрядного числа на M-разрядное число дает N+M-разрядное число. Таким образом, умножение числа из 129 слов (8256 бит) на другое дает результат в 16512 бит или 258 слов. Да, это много битов, но такие умножения появляются, например, в криптографии.