Предположим, что у вас есть 2 целых числа без знака из n цифр, заданных в двух массивах a, b, и у вас есть p процессоров, где каждый может добавить 2 цифры и вычислить перенос, если существует. Можно ли вычислить a + b за время O (p + n/p)? Я пытался разделить входные данные на p интервалов (n/p) каждый, но я не знаю, как обрабатывать перенос.Добавление двух целых чисел равно
ответ
Я считаю, что это возможно. Я собираюсь принять n >= p
и что ваши процессоры p расположены в архитектуре без общего доступа, где процессоры обмениваются данными посредством передачи сообщений.
Если ваши цифры еще не распределены между процессорами p, но собраны на одном ведущем процессоре, не участвующем в вычислении, вы просто разделите a и b, чтобы создать p блоков смежных цифр, и отправить их на каждый из процессоров. Это требует сложности сообщений O(p)
.
Затем каждый процессор вычисляет две суммы для своего блока цифр, одну сумму в предположении, что он получит перенос 1 от своего предшественника, то есть процессор, у которого следующий блок менее значительных цифр, а другой, предполагающий, что перенос будет равно 0. Он также рассчитает свой исходящий перенос для каждого из двух сценариев. Вычисление имеет временную сложность O(ceil(n/p))
, поскольку каждый процессор должен иметь целое число цифр.
Конечно, процессор, который имеет блок наименее значимых цифр, должен будет вычислить только одну сумму. Как только он выполнил свои вычисления, он отправляет свою долю возвращаемых цифр обратно хозяину и его исходящий перенос в процессор, содержащий следующий блок более значимых цифр. Следующий процессор решает, какой из двух сценариев результата стал истинным, отправляет соответствующие итоговые цифры главному и его исходящему переносу на следующий процессор. И так далее.
Это потребует дополнительных сообщений p для результатов и сообщений p-1 для переносов. Таким образом, сложность сообщений остается O(p)
. Сложность времени будет O(p + ceil(n/p))
, так как последнему процессору придется ждать, пока p-2
своих предшественников не решит, какой из двух результатов переслать. Если вы предполагаете, что n цифр могут быть равномерно распределены между p-процессорами (т. Е. N кратно p), вы в порядке со своей предлагаемой временной сложностью O(p + n/p)
.
Этот метод добавления с вычислением двух возможных результатов спекулятивно очень похож на то, как работает Carry-select adder.
- 1. Добавление двух целых чисел
- 2. Добавление двух целых чисел, представленных связанными списками
- 3. Добавление двух нулевых целых чисел, не работающих
- 4. Добавление двух целых массивов
- 5. Расчет двух целых чисел
- 6. Печать двух целых чисел
- 7. Признать силу двух целых чисел
- 8. Добавление целых чисел
- 9. Добавление двух целых JavaScript
- 10. Добавление двух чисел в c
- 11. Сравнение двух пар целых чисел
- 12. [InterviewBit] Сила двух целых чисел
- 13. Сравнение частного двух целых чисел
- 14. Модуля произведения двух целых чисел
- 15. , сравнивая значения двух целых чисел
- 16. среднего значения двух целых чисел
- 17. Модифицированное деление двух целых чисел
- 18. Сортировка двух массивных целых чисел
- 19. Псевдослучайный хэш двух целых чисел
- 20. XOR двух коротких целых чисел
- 21. Исправить GCD двух целых чисел
- 22. Добавление целых чисел в список
- 23. Добавление целых чисел в HashMap
- 24. Добавление целых чисел без longs
- 25. Добавление двух чисел с функцией
- 26. Добавление двух целых чисел в индекс массива без их суммирования
- 27. Добавление двух целых чисел в отладчик дает неожиданный вывод
- 28. Добавление двух целых чисел без использования оператора plus
- 29. добавление двух целых чисел в метод ввода пользователем
- 30. Добавление строк как целых чисел из двух списков
Awesome, спасибо! – Shmoopy
Добро пожаловать! Спасибо за репутацию :) – Marcellus