Длинное умножение пары значений uint64

Как я могу безопасно умножить пару значений uint64, чтобы получить результат в виде пары LSB и MSB одного типа?

typedef struct uint128 {
    uint64 lsb;
    uint64 msb;
};

uint128 mul(uint64 x, uint64 y)
{
    uint128 z = {0, 0};
    z.lsb = x * y;
    if (z.lsb / x != y)
    {
        z.msb = ?
    }
    return z;
}
  1. Правильно ли я вычисляю LSB?
  2. Как правильно вычислить MSB?

c integer integer-arithmetic
person goodvibration    schedule 02.10.2020    source источник
comment
Это неудобно делать в портативном C, вам в основном нужно воссоздать длинное умножение начальной школы, которое требует четырех отдельных умножений и нескольких сложений. Однако большинство 64-битных компиляторов предоставляют в качестве расширения стандартного C либо 128-битный целочисленный тип с ограниченной функциональностью (например, unsigned __int128 в gcc), либо встроенный доступ к расширяющей инструкции умножения, которую предоставляет большинство машин.   -  person Nate Eldredge    schedule 02.10.2020
comment
@NateEldredge: Да, это именно то, что я сейчас делаю, разбивая каждое из входных значений на пару uint32. Надеялся получить что-нибудь с полки здесь. Спасибо.   -  person goodvibration    schedule 02.10.2020
comment
Готовы ли вы использовать что-то специфичное для компилятора? Если да, скажите, какой компилятор вы используете.   -  person Nate Eldredge    schedule 02.10.2020
comment
В Интернете должны быть тысячи руководств по выполнению подобных арифметических операций. Вы сами разобрались с алгоритмом, который показываете в коде? Или вы использовали или адаптировали то, что нашли? Если нашли, то где? Что ресурс, который вы использовали, сказал вам об этом? Что заставляет вас в этом сомневаться? Что заставляет вас задуматься о собственном решении? Вы проверили это? Это работает для ваших тестов? Если это школьное или книжное задание/упражнение, работает ли оно с тестами вашей школы или учебника?   -  person Some programmer dude    schedule 02.10.2020
comment
@NateEldredge: Солидность. И фактические типы uint256. Я разместил вопрос и в C, потому что я надеялся получить быстрый ответ. Я разместил его без указания платформы, потому что ищу чисто арифметическое решение (потому что я, очевидно, не могу полагаться на какое-либо аппаратное обеспечение и/или компилятор).   -  person goodvibration    schedule 02.10.2020
comment
@Someprogrammerdude: Конечно, но я не смог найти способ сформулировать это в простом запросе Google, поэтому я разместил его здесь (если честно, в надежде получить «повторяющееся» предложение). И, главное, не для школы (Солидити родилась лет через 20 после того, как я уже закончил школу).   -  person goodvibration    schedule 02.10.2020
comment
Я вижу, это важное отличие. Честно говоря, я думаю, что наиболее распространенным решением является использование GMP или чего-то подобного вместо того, чтобы изобретать велосипед.   -  person Nate Eldredge    schedule 02.10.2020
comment
Я согласен с @NateEldredge, используйте любые доступные библиотеки. Если, конечно, это не школьное задание, в таком случае оно должно было быть выполнено в классе. :)   -  person Some programmer dude    schedule 02.10.2020
comment
Кажется, я припоминаю довольно недавний вопрос об умножении 256-битных целых чисел, но не могу его найти.   -  person Nate Eldredge    schedule 02.10.2020
comment
Совет: Разделите их на 32-битные числа, умножьте 2 32-битных числа и разделите 64-битный результат на 2 32-битных числа. Делайте то же самое, что и в начальной школе, без калькулятора, но в момент однозначных чисел используйте 32-битное число в качестве цифры.   -  person 12431234123412341234123    schedule 02.10.2020
comment
Странно изобретать велосипед. Я считаю, что на github будет много готовых к использованию библиотек (особенно на C++, которые вы можете портировать на C). Я нашел это, это, это.   -  person KamilCuk    schedule 02.10.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

Когда мы учились в школе и нам приходилось умножать 2 числа без калькулятора, мы умножали 2 цифры, получали результат с 1-2 цифрами, записывали их и в конце концов складывали. Мы назло умножили, поэтому нам нужно было вычислить только однозначное умножение за раз. Аналогичная вещь возможна с более высокими числами на ЦП. Но там мы не используем десятичные разряды, мы используем в качестве разряда половину размера регистра. При этом мы можем умножить 2 цифры и получить 2 цифры в одном регистре. В десятичном виде 13*42 можно рассчитать как:

  3* 2 =     0 6
 10* 2 =     2 0
  3*40 =   1 2 0
 10*40 = 0 4 0 0
        --------
         0 5 4 6

То же самое можно сделать и с целыми числами. Чтобы упростить задачу, я умножаю 2 8-битных числа на 16-битное число на 8-битном процессоре, для этого я умножаю только 4 бита на 4 бита за раз. Давайте умножим 0x73 на 0x4F.

0x03*0x0F = 0x002D
0x70*0x0F = 0x0690 
0x03*0x40 = 0x00C0 
0x70*0x40 = 0x1C00
            -------
            0x22BD

Вы в основном создаете массив с 4 элементами, в вашем случае каждый элемент имеет тип uint32_t, сохраняете или добавляете результат одного умножения в правильный элемент (ы) массива, если результат одного умножения слишком велик для один элемент, сохраните старшие биты в старшем элементе. Если дополнение переполняется, перенос 1 к следующему элементу. В итоге можно объединить 2 элемента массива, в вашем случае до двух uint64_t.

person 12431234123412341234123    schedule 02.10.2020