Каков размер ввода, который появляется во время выполнения сложности целого остатка и деления?

Question

Я пытаюсь выяснить сложность выполнения остатка и деления для целых чисел в современных компьютерах. Независимо от используемого алгоритма, я часто нахожу входной размер, определяемый как число битов, используемых для хранения целых чисел, которые делятся. Я считаю это определение неоднозначным. Предположим, что одно из разделяемых чисел равно 10: оно может быть сохранено с 4 битами. Однако, с точки зрения программиста, если 10 хранится в переменной типа int и на используемом языке программирования, целые числа представлены, скажем, 32 битами, 10 будет храниться с использованием 32 битов. В приведенном выше примере, какое значение представляет размер ввода, который появляется в сложности времени выполнения? 4 бита или 32 бита?

Answer 1

В вышеупомянутом примере, какое значение представляет размер ввода, который появляется в сложности времени выполнения? 4 бита или 32 бита?

Входной размер - это количество бит, которые принимает ALU, выполняющий операцию (или, точнее, сколько битов работает в алгоритме в ALU) - он полностью зависит от архитектуры процессора и кода, созданного вами или вашим компилятором.

Технически говоря, ничто не мешает вам разработать процессор с 32-разрядными регистрами и 8-разрядным ALU, способным принимать только 8 младших разрядов регистра в качестве входных данных (при условии, что с таким процессором было бы совершенно невыносимо работать, но это было бы вполне возможно). И если было несколько ALU, скажем, 8-битных и 64-битных, ничто не мешает вам или компилятору использовать то, что вам нравится, если допустить, что архитектура набора команд предоставляет вам такую ​​свободу.

Это невозможно дать универсальный ответ на ваш вопрос, потому что он не привязан к какой-либо конкретной реализации.