Comments / Profile of alexeibs / Habr

alexeibs Jul 31 2012 at 09:21

А после выполнения mpz_mul в mpz_t хранится число, готовое к выводу в файл, или коэффициенты многочленов?

alexeibs Jul 31 2012 at 08:30

При использовании деления (а оно сейчас быстрое, как выяснилось) получается вот такой код умножения по модулю 64-битных чисел:

; a = RAX
; b = RBX
; c = RCX
MUL RBX
DIV RCX
; в RDX у нас модуль (a * b) % c

alexeibs Jul 31 2012 at 08:16

В x86/x64 на вход операции деления подается частное 2 регистрах и делитель в одном регистре. Для x64 как раз получаем 128-битное частное и 64-битный делитель

alexeibs Jul 31 2012 at 08:05

Хотя в том же руководстве написано, что для семейства 12h такая замена неактуальна, т.к. деление и так выполняется быстро

alexeibs Jul 31 2012 at 08:02

по сути это замена N / C = N * (1 / C). Поскольку C — константа, то 1 / C можно вычислить заранее

alexeibs Jul 31 2012 at 07:57

Сначала вычисляем a * b, а затем находим остаток от деления на константу. Деление на константу можно заменить умножением. В руководстве по оптимизации для процессоров AMD описан алгоритм такой замены.
support.amd.com/us/Processor_TechDocs/40546.pdf
раздел «8.1 Replacing Division with Multiplication»

alexeibs Jul 31 2012 at 06:45

Умножение по константному модулю вряд ли выполняется медленно. Это моно сделать за 2 команды целочисленного умножения, которые на Core i7 и AMD K10 выполняются за 3 такта каждая

alexeibs Jul 31 2012 at 06:42

Можно посмотреть исходники GMP

alexeibs Jul 29 2012 at 19:17

Это уже вопрос к разработчикам GMP.

alexeibs Jul 29 2012 at 17:02

Логарифмический масштаб:
habrastorage.org/storage2/67a/b64/5e6/67ab645e6b8a42f956b4d1b3d36500fb.png

alexeibs Jul 29 2012 at 16:53

Функцию dump я написал, чтобы убедиться, что второй алгоритм возвращает те же результаты, что и первый. Вывод там выполняется в шестнадцатеричном виде, что, в принципе, не должно занять много времени. Но сама запись данных на жесткий диск будет узким местом для второго алгоритма.

alexeibs Jul 29 2012 at 14:27

Добавил совмещенный график

alexeibs Jul 29 2012 at 08:49

Они построены на разных данных, т.к. там где алгоритм №1 в состоянии посчитать число Фибоначчи за разумное количество времени, алгоритм №2 отрабатывает менее, чем за секунду. Если вы посмотрите на таблицу, то увидите, что самое большое число, обработанное алгоритмом №1, равно 3.000.000, а самое маленькое, обработанное алгоритмом №2, — 50.000.000. При том, что число в 16 раз больше, затрачиваемое время — в 50 раз меньше.

alexeibs Jul 28 2012 at 22:00

>> В вашем коде это 2^32 -1.
База в данном случае 2^32
>> Допустим ваш код заработал, после того как в нем поменялось add edi, 1 на add edi, 4
Писал в торопях, допустил ошибку
>> Если уж вы решили написать его на асме
Тут нужен именно ассемблер либо intrinsic'и, которые позволяют получить доступ к старшей части результата умножения.
Код вывода в шестнадцатеричном виде элементарен. Если нужна десятичная форма, то код усложнится и, да, понадобится деление.

void print_number(unsigned int* number, unsigned int number_size, int leading_zeros)
{
	for(; number_size--;) {
		if (!number[number_size]) {
			if (leading_zeros)
				printf("%08x", 0);
		} else {
			if (leading_zeros)
				printf("%08x", number[number_size]);
			else
				printf("%x", number[number_size]);
			for(; number_size--;)
				printf("%08x", number[number_size]);
			break;
		}
	}
}

В этой функции и функции из предыдущего комментария предполагается порядок байтов little-endian, принятый в x86.

alexeibs Jul 28 2012 at 19:37

И все-таки деление в явном виде для реализации «длинного» умножения не нужно. Вот простейшая реализация умножения «длинного» числа на беззнаковое целое.

unsigned multiply(unsigned* big_number, unsigned number_size, unsigned multiplier)
{
    unsigned overflow;
    __asm {
        mov edi, big_number
        mov ebx, multiplier
        mov ecx, number_size
        xor esi, esi
    begin_loop:
        mov eax, [edi]
        mul ebx
        add eax, esi
        mov esi, edx
        mov [edi], eax
        add edi, 1
        sub ecx, 1
        jnz begin_loop
        mov overflow, esi
    }
    return overflow;
}

Перемножение 2 «длинных» чисел выполняется аналогично умножению столбиком.
>> Если при умножении Вы будете использовать основание со степенью двойки
А в каком виде по-вашему хранятся числа в оперативной памяти компьютера? Вывод — это уже отдельная история. Если на то пошло, то можно и в шестнадцатеричном виде вывести данные. Несколько тысяч цифр человек все равно не в состоянии воспринять, поэтому это будет не сильно хуже, чем десятичное представление.
>> Да и сама операция умножения (короткого на короткое) дороже чем сложение
Дороже, но на современных процессорах оно выполняется относительно быстро.

alexeibs Jul 27 2012 at 20:53

По вашей логике и для выполнения сложения требуется операция деления — для вычисления переноса.

alexeibs Jul 27 2012 at 20:50

Как работает длинная арифметика я понимаю. Непонятно мне ваше стремление включить операции деления в асимптотику умножения. Да, неявно деление выполняется, но деление на степени двойки выполняется за констатное время простым сдвигом. Я уже писал, что результатом выполнения команд умножения в x86-процессорах является пара числел, одно из которых — перенос в старшие разряды. На скорость умножения это никак не влияет.

alexeibs Jul 27 2012 at 14:57

Не пойму, зачем нужна операция деления для реализации «длинного» умножения? Перенос разрядов легко реализуется на уровне ассемблера. По крайней мере в x86 команды умножения возвращают результат в 2 регистрах. Старшая часть результата в этом случае — это и есть перенос.
>>Почему же вы не исправили ошибку, допущенную предыдущим автором в оценке асимптотики, и на которую ему указали в первом же комментарии?
Я не считаю оценку автора предыдущей статьи ошибочной. «Длинная арифметика» нужна далеко не всегда. Чаще всего разрядность операндов фиксирована.

alexeibs Jul 26 2012 at 23:10

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

(где k — порядковый номер числа фибоначчи на текущей итерации), то сложность итерации будет равна

. Сложность всех итераций равна

. Асимптотика получается

, что все равно лучше, чем ваша оценка

. К тому же для умножения можно использовать более эффективные алгоритмы.