Приветствую. Я, дабы совместить приятное с полезным, пишу библиотеку для работы с длинной арифметикой. Формат данных: 1 dword с длиной числа в байтах, далее само число с обратным порядком байт, доп.код. Задачи(в порядке убывания приоритета) - максимальная скорость работы, разумный расход памяти. Размер кода не критичен. Пока написал сложение, сдвиги и беззнаковое умножение, на знаковом наступил затык. Если умножать 2 числа "столбиком", то потребуется сохранить знаки операндов и перевести их в прямой код, после чего выполнить беззнаковое умножение. Но тогда потребуется или изменять операнды(а они по понятным причинам передаются по ссылке), или на лету создавать буфер под временные переменные, которые могут быть весьма большими. Оба варианта неприемлимы. Если кто работал в этом направлении, поделитесь идеями, пожалуйста. Исходники могу дать, но, имхо, пока бессмысленно.
Насколько отдельно? То, что я выставлю его отдельным байтом, не изменит самого алгоритма. Или предлагаете перейти на прямой код?
Ну, например вот так: typedef struct _LONG_INTEGER { ULONG Length; CHAR Sign; UCHAR Bytes[ 1 ]; } LONG_INTEGER, * PLONG_INTEGER; Для положительных чисел Sign = 1, для отрицательных Sign = -1. Знак произведения = произведению знаков. А вообще советую глянуть код библиотеки GMP (GNU Multiple Presicion). Она вроде одна из самых шустрых. И много чего умеет. К тому же код открытый. Есть и под Windows и под Unix.
Dryu Ну типа как написал Forever или вообще одним битом (как в FPU вроде). Или как packed/unpacked BCD-числа. В любом случае - раз ты написал что приоритетнее скорость - так будет быстрее чем переводить или учитывать знаки в алгоритме.
Dryu Зачем из доп. кода переводить-то? Алгоритмов знакового умножения в доп. коде вагон и тележка: В столбик с учётом знака, в столбик с корректировкой результата, метод Burks-Goldstine-von-Neumann, метод Робертсона, метод Буса.
В принципе, нашёл алгоритм знакового умножения, но будет несколько геморройно. Погляжу в исходники, спасибо.
