Разделение int64 на два int32, выполнение математических расчетов и повторное соединение - PullRequest
Новая
       98

Разделение int64 на два int32, выполнение математических расчетов и повторное соединение

2 голосов
/ 07 августа 2020

Я работаю с ограничениями оборудования, которое имеет ограничение на 64-битное целое число. Не поддерживает плавающую точку. Я имею дело с очень большими целыми числами, которые мне нужно умножать и делить. При умножении я сталкиваюсь с переполнением 64 бит. Я создаю прототип решения в python. Вот что у меня есть в моей функции: 

upper = x >> 32 #x is cast as int64 before being passed to this function
lower = x & 0x00000000FFFFFFFF

temp_upper = upper * y // z #Dividing first is not an option, as this is not the actual equation I am working with. This is just to make sure in my testing I overflow unless I do the splitting.
temp_lower = lower * y // z

return temp_upper << 32 | lower

Это в некоторой степени работает, но в конечном итоге я теряю большую точность (мой результат иногда отличается на несколько миллионов). Глядя на это, кажется, что это происходит из-за разделения. Если достаточно, верхний сдвигается вправо. Затем, когда я перемещаю его обратно на место, у меня появляется пробел из нулей.

К сожалению, этот topi c очень сложно гуглить, поскольку все, что имеет верхнее / нижнее значение, дает результаты о округлении вверх / вниз. И все, что касается разделения целых чисел, возвращает результаты о разделении их на массив символов. Что-нибудь о int arithmeti c поднять основы c алгебры с целочисленной математикой. Может, я просто не умею гуглить. Но не могли бы вы дать мне несколько советов о том, как это сделать?

Такое разделение - это всего лишь то, что я пытаюсь сделать, это не обязательно решение. Все, что мне нужно, это временно go сверх 64-битного целочисленного лимита. Окончательный результат будет под 64bit (после части деления). Я помню, как в колледже учился так разделять, а затем делать математику и повторно комбинировать. Но, к сожалению, как я уже сказал, у меня возникли проблемы с поиском в Интернете чего-либо о том, как на самом деле это вычислить.

Наконец, мои цифры иногда маленькие. Так что я не могу отрезать нужные кусочки. Мне нужно, чтобы результаты были в основном эквивалентны тому, если бы я использовал что-то вроде int128 или что-то в этом роде.

Я полагаю, что другой способ взглянуть на эту проблему заключается в следующем. Поскольку у меня нет проблем с разделением int64, мы можем забыть об этой части. Итак, мы можем представить, что мне скармливают два int64, один верхний, а другой нижний. Я не могу объединить их, потому что они не помещаются в один int64. Поэтому мне нужно сначала разделить их на Z. Объединить шаг легко. Как сделать деление?

Спасибо.

1 Ответ

0 голосов
/ 07 августа 2020

Насколько я понимаю, вы хотите выполнить (x*y)//z.

Ваши числа x,y,z все подходят на 64 бита, за исключением того, что вам нужно 128 бит для промежуточных x*y.

Проблема действительно связана с разделением: у вас есть 

h * y = qh * z + rh
l * y = ql * z + rl

h * y << 32 + l*y = (qh<<32 + ql) * z + (rh<<32 + rl)

, но ничего не говорит о (rh<<32 + rl) < z, и в вашем случае высокие биты l*y перекрывают младшие биты h * y, поэтому вы получаете неправильное частное, отстоящее на потенциально много единиц.

То, что вы должны сделать в качестве второй операции, скорее: 

rh<<32 + l * y = ql' * z + rl'

Затем получите общее частное qh<<32 + ql'

Но конечно, вы должны избегать переполнения при вычислении левого операнда ...

Поскольку вы разделяете только один из операндов x*y, я предполагаю, что промежуточный результат всегда соответствует 96 битам.

Если это верно, то ваша задача состоит в том, чтобы разделить 3 32-битных конечности x*y на 2 32-битных конечности z.
Таким образом, это похоже на алгоритм Бернигеля-Циглера «разделяй и властвуй» для деления.
Алгоритм можно разложить так:

  • получить 3 конечности a2,a1,a0 умножения x*y с помощью, например, карацубы
  • разделить z на 2 конечности z1,z0
  • выполнить div32( (a2,a1,a0) , (z1,z0) )

вот какой-то псевдокод, имеющий дело только с положительными операндами и без гарантии правильности, но вы получаете представление о реализации: 

p = 1<<32;

function (a1,a0) = split(a)
    a1 = a >> 32;
    a0 = a - (a1 * p);

function (a2,a1,a0) = mul22(x,y)
    (x1,x0) = split(x) ;
    (y1,y0) = split(y) ;
    (h1,h0) = split(x1 * y1);
    assert(h1 == 0); -- assume that results fits on 96 bits
    (l1,l0) = split(x0 * y0);
    (m1,m0) = split((x1 - x0) * (y0 - y1));  -- karatsuba trick
    a0 = l0;
    (carry,a1) = split( l1 + l0 + h0 + m0 );
    a2 = l1 + m1 + h0 + carry;
    
function (q,r) = quorem(a,b)
    q = a // b;
    r = a - (b * q);

function (q1,q0,r0) = div21(a1,a0,b0)
   (q1,r1) = quorem(a1,b0);
   (q0,r0) = quorem( r1 * p + a0 , b0 );
   (q1,q0) = split( q1 * p + q0 );
   
function q = div32(a2,a1,a0,b1,b0)
    (q,r) = quorem(a2*p+a1,b1*p+b0);
    q = q * p;
    (a2,a1)=split(r);
    if a2<b1
        (q1,q0,r)=div21(a2,a1,b1);
        assert(q1==0); -- since a2<b1...
    else
        q0=p-1;
        r=(a2-b1)*p+a1+b1;
    (d1,d0) = split(q0*b0);
    r = (r-d1)*p + a0 - d0;
    while(r < 0)
        q = q - 1;
        r = r + b1*p + b0;
   
function t=muldiv(x,y,z)
    (a2,a1,a0) = mul22(x,y);
    (z1,z0) = split(z);
    if z1 == 0
        (q2,q1,r1)=div21(a2,a1,z0);
        assert(q2==0); -- otherwise result will not fit on 64 bits
        t = q1*p + ( ( r1*p + a0 )//z0);
    else
        t = div32(a2,a1,a0,z1,z0);
...