Сплит Умножение целых чисел

Мне нужен алгоритм, который использует два 32-битных целых числа в качестве параметров, и возвращает умножение этих параметров на два других 32-разрядных целых числа: 32-разрядная часть и 32-разрядная часть ,Сплит Умножение целых чисел

Я хотел бы попробовать:

uint32_t p1, p2; // globals to hold the result 

void mult(uint32_t x, uint32_t y){ 
    uint64_t r = (x * y); 

    p1 = r >> 32; 
    p2 = r & 0xFFFFFFFF; 

}

Хотя это работает , это не гарантирует существование 64-разрядных целых чисел в машине, ни является их использование компилятором.

Итак, как наилучшим образом его решить?

^{Примечание 1}: На самом деле, это не сработало, потому что мой компилятор не поддерживает 64-битные целые числа.

Obs: Пожалуйста, избежать с помощью boost.

источник

2013-11-11 Rodrigo Siqueira

Вы можете обрабатывать каждое число и продукт в виде строки и выполнять умножение школы в брутфорсе. Затем разделите продукт на две части соответственно. –

Это действительно так, но я думаю, что может быть более быстрый и довольно умный способ сделать это. Поскольку я имитирую процессор, он должен быть как можно быстрее. –

Вы проверили [эту тему] (http://stackoverflow.com/q/18425513/69809)? – Groo

Просто используйте 16-разрядные разряды.

void multiply(uint32_t a, uint32_t b, uint32_t* h, uint32_t* l) { 
    uint32_t const base = 0x10000; 
    uint32_t al = a%base, ah = a/base, bl = b%base, bh = b/base; 
    *l = al*bl; 
    *h = ah*bh; 
    uint32_t rlh = *l/base + al*bh; 
    *h += rlh/base; 
    rlh = rlh%base + ah*bl; 
    *h += rlh/base; 
    *l = (rlh%base)*base + *l%base; 
}

источник

2013-11-11 09:58:51 AProgrammer

Отлично! Не обнаружено переполнения. –

Возможно, я бы добавил некоторые условные директивы компиляции, чтобы включить «реальное» 32-> 64 умножение на поддерживающих его платформах. –

@MatteoItalia Я слышал, что компиляторы ДОЛЖНЫ предоставить способ выполнить 64-битные операции, даже если они находятся на 32-битной платформе с использованием 'long long'. Я попробую это, и если это не сработает, я сделаю то, что вы сказали. –

Как я заметил, вы можете рассматривать каждый номер в виде бинарной строки длиной 32

Просто перемножить эти числа, используя школьную арифметику. Вы получите строку длиной 64 символа.

Затем просто разделите его.

Если вы хотите быстрое умножение, вы можете изучить алгоритм Karatsuba multiplication.

источник

2013-11-11 07:07:25

На самом деле, я также вручную пробовал этот метод перед вопросом с 4-битными целыми числами: 'x = 0b1111' и' y = 0b1111'. Я разделил его на четыре двухбитовых целых числа: 'x1 = x0 = y1 = y0 = 0b11'. Карацуба переполнена в '((x1 + x0) * (y1 + y0))', поскольку это приведет к ошибке '0b100100', и это не может поместиться в 4-битное целое число. –

@RodrigoSiqueira Вам нужно будет сохранить числа в виде строк, а затем выполнить умножение. –

Ой, да, я забыл эту деталь. –

Если unsigned long тип поддерживается, это должно работать:

void umult32(uint32 a, uint32 b, uint32* c, uint32* d) 
{ 
    unsigned long long x = ((unsigned long long)a)* ((unsigned long long)b); //Thanks to @Толя 
    *c = x&0xffffffff; 
    *d = (x >> 32) & 0xffffffff; 
}

Logic заимствованные из here.

источник

2013-11-11 07:39:42

unsigned long long x = (без знака длинный длинный) (a * b); это неверно, должно быть: unsigned long long x = ((unsigned long long) a) * ((unsigned long long) b); –

Ухм, вы полагаетесь на доступность 'unsigned long long', в то время как OP явно заявляет, что это не гарантируется. –

@ Толя На самом деле, это именно то, что я пробовал перед вопросом. И, как и @MatteoItalia и я сказал, 64-битные целые числа могут быть недоступны. «Unsigned long long» моего компилятора 32-битный, а '* d' всегда будет 0. –

Это объяснение и реализация Karatsubas-Algorithm. Я загрузил код и запускал его несколько раз. Кажется, что все идет хорошо. Вы можете изменить код в соответствии с вашими потребностями.

источник

2013-11-11 09:31:55 David

Я не знаю, не хватает ли чего-то, но этот алгоритм использует строки и слишком важен. –

Сплит Умножение целых чисел

ответ

Смежные вопросы