LINUX.ORG.RU
Форум — Development  

Перемножение двух чисел в дополнительном коде с обнаружением переполнения

 , , ,


1

3

Вытащу сюда вопрос из темы.

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

Алгоритм, который мне известен:

1. Расширить операнды знаком в 2 раза. 2. Перемножить расширенные операнды алгоритмом беззнакового умножения, получив произведение, которое имеет в 4 раза больше бит, чем исходные операнды. 3. Трактуем произведение как число в дополнительном коде: если полученное значение укладывается в диапазон значений исходного типа, то переполнения нет, если не укладывается — значит переполнение.

Ну то есть, например: для перемножения 256-битных чисел нам придётся оперировать 1024-битным произведением. Что несколько дохрена.

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

(UPD: не, вроде херня какая-то)

★★

Последнее исправление: wandrien (всего исправлений: 1)
← webassembly - пара теоретических вопросов.
Как определить собраны ли исполняемые файлы с реализацией технологии PIE или нет →
  1 2 3
Ответ на: комментарий от COKPOWEHEU

«Умножение в столбик» оправдано если нет аппаратного умножения. А если оно есть

А если оно есть, то для более крупных чисел нам всё равно потребуется «умножение в столбик», где в качестве разрядов будут выступать фрагменты меньшего размера.

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

Там требуется 4 умножения меньшей разрядности. И насколько я понял, угол не срезать. Либо три умножения - в случае, если старшие биты произведения нас не интересуют.

wandrien ★★
() автор топика
Ответ на: комментарий от wandrien

А если оно есть, то для более крупных чисел нам всё равно потребуется «умножение в столбик», где в качестве разрядов будут выступать фрагменты меньшего размера.

Если не изменяет память (нет книг под рукой), у Кнута в TAOCP это очень подробно, в мелких деталях, разжевано.

anonymous
()
Ответ на: комментарий от Loki13

Так ТС же вроде компилятор и пишет(если я его ни с кем не путаю).

дык компилятор же дергает инструкции процессора?

Вообще ТС тут какой то агрессивный, раньше он был добрее;-)

AntonI ★★★★★
()
Ответ на: комментарий от wandrien

для более крупных чисел нам всё равно потребуется «умножение в столбик»

да

угол не срезать

В общем виде пусть есть числа X и Y

X = sum_i x_i<<B*i
Y = sum_j x_j<<B*j

где x_i и y_j их B-битные фрагменты. Тогда если в лоб

Z = X*Y = sum_i sum_j x_i*y_j<<B*(i+j)

И никуда от этого не деться… m*n умножений, сдивгов и сложений. «Математика, бессердечная ты сука!»(c)

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

AntonI ★★★★★
()
Ответ на: комментарий от AntonI

дык компилятор же дергает инструкции процессора?

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

Loki13 ★★★★★
()
Ответ на: комментарий от AntonI

дык компилятор же дергает инструкции процессора?

У процессора на этот счёт ровно одна инструкция, которая нам полезна: mul, который возвращает произведение с удвоенным числом бит. (И то вон на RISC-V её нет, там это две отдельных инструкции.)

От этого и пляшем.

wandrien ★★
() автор топика
Ответ на: комментарий от AntonI

«Математика, бессердечная ты сука!»(c)

Вопрос в том, возможно ли поймать переполнение, не делая полный набор умножений и сложений.

Потому что если переполнение считаем за UB, там код будет короче короче раза в два (минус одно умножение и несколько сложений).

А вот если нужно проверять переполнение, то я вижу только вариант с полным умножением.

wandrien ★★
() автор топика
Ответ на: комментарий от AntonI

Вообще ТС тут какой то агрессивный, раньше он был добрее;-)

Да, чё-т выбесили маленько.

Там на 1-й странице темы чел предложил проверять отсутствие переполнения при умножении через деление числа обратно.

И чел-то не дурак какой-то, занимался портированием Гайки на RISC-V, в железе немножко шарит. Это я без сарказма говорю, если что: реально не дурак.

А потом еще я тут прочитал чудный метод умножения через развёртку в цикл сложений.

wandrien ★★
() автор топика
Ответ на: комментарий от wandrien

RISC-V, uint64_t = uint64_t*uint64_t

00000ad4 <test>:
  z = x*y;
 ad4:	1ffff797          	auipc	a5,0x1ffff
 ad8:	53478793          	add	a5,a5,1332 # 20000008 <x>
 adc:	4388                	lw	a0,0(a5)
 ade:	43cc                	lw	a1,4(a5)
 ae0:	1ffff797          	auipc	a5,0x1ffff
 ae4:	52078793          	add	a5,a5,1312 # 20000000 <y>
 ae8:	0007a803          	lw	a6,0(a5)
 aec:	0047a883          	lw	a7,4(a5)
 af0:	030587b3          	mul	a5,a1,a6
 af4:	02a88733          	mul	a4,a7,a0
 af8:	00e786b3          	add	a3,a5,a4
 afc:	030537b3          	mulhu	a5,a0,a6
 b00:	03050733          	mul	a4,a0,a6
 b04:	97b6                	add	a5,a5,a3
 b06:	81818693          	add	a3,gp,-2024 # 20000018 <z>
 b0a:	c298                	sw	a4,0(a3)
 b0c:	c2dc                	sw	a5,4(a3)
}
 b0e:	8082                	ret

3.5 умножения. Жаль, типа int128_t не существует.

COKPOWEHEU ★
()
Ответ на: комментарий от yars068

Ну да, я к тому и веду. Но тут следует сделать поправку, что сдвигать нужно числа по цепочке ячеек в памяти неопределённой длинны и тут могут разные неочевидные приколы возникнуть.

ugoday ★★★★★
()
Ответ на: комментарий от wandrien

чудный метод умножения через развёртку в цикл сложений.

Суммирование со сдвигом - не такой плохой вариант. Если в одном из множителей ненулевых бит мало могу представить то длинных целых это будет работать быстрее чем «в столбик».

От задачи же зависит, длиннная арифметика же не просто так появилась?

AntonI ★★★★★
()
Ответ на: комментарий от wandrien

Ну да. Если бы были int128_t, можно было бы посмотреть как компилятор обрабатывает переполнение. Хотя с него станется никак. Тот редкий случай, когда жаль, что архитектура 32-битная, а не 16 или 8.

Хотя можно еще на AVR посмотреть, там умножение 8-битное.

COKPOWEHEU ★
()

кстати можно совсем просто-просто :-)

перед перемножением разложить числа на простые сомножители, тогда всё их перемножение выливается в сложение степеней при сомножителях.

идеальное решение, ибо можно ли сделать ещё более упорото ?

MKuznetsov ★★★★★
()
Ответ на: комментарий от COKPOWEHEU

Жаль, типа int128_t не существует.

У gcc есть расширение тип __int128. Вот что выдал godbolt.org для RISC-V (64-bits) gcc 14.2.0 с -O2:

__int128 mul128(__int128 a, __int128 b)
{
    return a * b;
}

_Z6mul128nn:
        mul     a3,a3,a0
        mul     a1,a1,a2
        mulhu   a5,a0,a2
        add     a1,a1,a3
        mul     a0,a0,a2
        add     a1,a1,a5
        ret
V1KT0P ★★
()
Ответ на: комментарий от V1KT0P

Вот например для -m32 -march=i586 -O3 то же самое:

mul64:
        push    ebx
        mov     eax, DWORD PTR [esp+8]
        mov     edx, DWORD PTR [esp+16]
        mov     ecx, DWORD PTR [esp+12]
        mov     ebx, DWORD PTR [esp+20]
        imul    ebx, eax
        imul    ecx, edx
        mul     edx
        add     ecx, ebx
        pop     ebx
        add     edx, ecx
        ret
wandrien ★★
() автор топика
Ответ на: комментарий от wandrien

Это не про переполнение.

Ага с переполнение все становится сложнее:

bool mul_128_overflow(unsigned __int128 a, unsigned __int128 b, unsigned __int128 *c)
{
    return __builtin_mul_overflow(a, b, c);
}

mul_128_overflow(unsigned __int128, unsigned __int128, unsigned __int128*):
        mv      a5,a0
        li      a0,0
        bne     a1,zero,.L4
        bne     a3,zero,.L5
        mulhu   a3,a5,a2
        mul     a2,a5,a2
        mv      a5,a3
.L2:
        sd      a2,0(a4)
        sd      a5,8(a4)
        ret
.L4:
        mv      t1,a1
        mv      a6,a2
        bne     a3,zero,.L12
.L6:
        mul     a7,a6,t1
        mulhu   t3,a5,a2
        mulhu   t1,a6,t1
        add     a6,a7,t3
        sltu    a7,a6,a7
        add     t1,a7,t1
        mul     a7,a5,a2
        bne     t1,zero,.L8
        mv      a2,a7
        mv      a5,a6
        sd      a2,0(a4)
        sd      a5,8(a4)
        ret
.L5:
        mv      t1,a3
        mv      a6,a5
        j       .L6
.L12:
        mul     a7,a5,a2
        mulhu   t3,a5,a2
.L8:
        li      a0,1
        mul     a1,a1,a2
        mv      a2,a7
        mul     a3,a3,a5
        add     a1,a1,a3
        add     a5,a1,t3
        j       .L2
V1KT0P ★★
()
Ответ на: комментарий от wandrien

Едрить!)))

Ага, у меня такое-же впечатление поэтому я решил глянуть а что сгенерирует RISC-V rv64gc clang 19.1.0 с -O2. И вот он уже вроде как нормальный код сгенерировал:

bool mul_128_overflow(unsigned __int128 a, unsigned __int128 b, unsigned __int128 *c)
{
    return __builtin_mul_overflow(a, b, c);
}

mul_128_overflow(unsigned __int128, unsigned __int128, unsigned __int128*):
        mul     a6, a3, a0
        mul     a5, a1, a2
        add     a6, a6, a5
        mulhu   a5, a0, a2
        add     a6, a6, a5
        sltu    a7, a6, a5
        snez    t0, a3
        snez    a5, a1
        and     a5, a5, t0
        mulhu   a1, a1, a2
        snez    a1, a1
        or      a1, a1, a5
        mulhu   a3, a3, a0
        snez    a3, a3
        or      a1, a1, a3
        or      a1, a1, a7
        mul     a0, a0, a2
        sd      a0, 0(a4)
        sd      a6, 8(a4)
        mv      a0, a1
        ret
V1KT0P ★★
() 
typedef struct {
    unsigned __int128 a;
    unsigned __int128 b;
    unsigned __int128 c;
} X_unsigned;

int mul_128_overflow(X_unsigned *x)
{
    return __builtin_mul_overflow(x->a, x->b, &x->c);
}

typedef struct {
    signed __int128 a;
    signed __int128 b;
    signed __int128 c;
} X_signed;

int imul_128_overflow(X_signed *x)
{
    return __builtin_mul_overflow(x->a, x->b, &x->c);
}

mul_128_overflow:
        mov     rcx, qword ptr [rdi]
        mov     rax, qword ptr [rdi + 8]
        mov     r9, qword ptr [rdi + 16]
        mov     rsi, qword ptr [rdi + 24]
        test    rsi, rsi
        setne   dl
        test    rax, rax
        setne   r10b
        and     r10b, dl
        mul     r9
        mov     r8, rax
        seto    r11b
        mov     rax, rsi
        mul     rcx
        seto    sil
        or      sil, r11b
        or      sil, r10b
        add     r8, rax
        mov     rax, rcx
        mul     r9
        add     rdx, r8
        setb    cl
        or      cl, sil
        mov     qword ptr [rdi + 32], rax
        mov     qword ptr [rdi + 40], rdx
        movzx   eax, cl
        ret

imul_128_overflow:
        push    r15
        push    r14
        push    rbx
        mov     r9, qword ptr [rdi]
        mov     rcx, qword ptr [rdi + 8]
        mov     r11, qword ptr [rdi + 16]
        mov     r15, qword ptr [rdi + 24]
        mov     r8, rcx
        sar     r8, 63
        mov     r10, r15
        mov     rax, r11
        mul     r8
        mov     rsi, rax
        mov     rbx, rdx
        imul    r10, r8
        add     rbx, r10
        add     rbx, rax
        mov     rax, r15
        sar     rax, 63
        mov     r14, rax
        imul    r14, rcx
        mul     r9
        mov     r10, rax
        mov     r8, rdx
        add     r8, r14
        add     r8, rax
        add     r10, rsi
        adc     r8, rbx
        mov     rax, r9
        mul     r11
        mov     rbx, rdx
        mov     rsi, rax
        mov     rax, rcx
        mul     r11
        mov     r11, rdx
        mov     r14, rax
        add     r14, rbx
        adc     r11, 0
        mov     rax, r9
        mul     r15
        mov     rbx, rdx
        mov     r9, rax
        add     r9, r14
        adc     rbx, r11
        setb    al
        movzx   r11d, al
        mov     rax, rcx
        mul     r15
        add     rax, rbx
        adc     rdx, r11
        add     rax, r10
        adc     rdx, r8
        mov     qword ptr [rdi + 40], r9
        sar     r9, 63
        xor     rdx, r9
        xor     r9, rax
        xor     eax, eax
        or      r9, rdx
        setne   al
        mov     qword ptr [rdi + 32], rsi
        pop     rbx
        pop     r14
        pop     r15
        ret
wandrien ★★
() автор топика
Ответ на: комментарий от MKuznetsov

ибо можно ли сделать ещё более упорото ?

Логарифм произведения есть сумма логарифмов сомножителей. Соответственно:

x * y = e(ln x + ln y)

Как видите, мы вообще избавились от умножений.

ugoday ★★★★★
()
Ответ на: комментарий от wandrien

Заинтересовался какой код сгенерировд clang под RISC-V. Решил привести результат компиляции в псевдокод:

Для понимания того что происходит в коде накидал себе визуально процесс умножения столбиком:

D*B=EF
D*A=GH
C*B=IJ
C*A=KL
                    A       B
                    C       D
-----------------------------
            G       H+E     F
    K       L+I     J
_____________________________
    K       G+L+I   H+E+J   F

Упрощенный псевдокод (стало интересно почему нету умножения L = C * A, это переполнение как-то косвенно определяется?):

A = a.h
B = a.l
C = b.h
D = b.l

struct {
  uint64 h;
  uint64 l;
} u128

bool mul_128_overflow(u128 a, u128 b, u128* c)
{
    u64 A = a.h;
    u64 B = a.l;
    u64 C = b.h;
    u64 D = b.l

    u64 F = D * B;
    u64 H = D * A;
    u64 E = D * B;
    u64 J = C * B;

    u64 G = D * A;
    u64 I = C * B;

    u64 HEJ = H + J + E;
    u64 E_overflow = HEJ < E;
    u64 C_exists = C != 0;
    u64 A_exists = A != 0;
    u64 C_A_exists = A_exists & C_exists;
    u64 G_exists = G != 0;
    u64 I_exists = I != 0;

    u64 overflow = E_overflow | C_A_exists | G_exists | I_exists;
    
    c->l = F;
    c->h = HEJ;
    return overflow;
}

Полный псевдокод соответствующий ассемблеру:

bool mul_128_overflow(u128 a, u128 b, u128* c)
{
    u64 A = a.h;
    u64 B = a.l;
    u64 C = b.h;
    u64 D = b.l

    u64 J = C * B;                                  //mul a6, a3, a0
    u64 H = D * A;                                  //mul a5, a1, a2
    u64 HJ = H + J;                                 //add a6, a6, a5
    u64 E = D * B;                                  //mulhu a5, a0, a2
    u64 HEJ = HJ + E;                               //add a6, a6, a5
    u64 E_overflow = HEJ < E;                       //sltu a7, a6, a5
    u64 C_exists = C != 0;                          //snez t0, a3
    u64 A_exists = A != 0;                          //snez a5, a1
    u64 C_A_exists = A_exists & C_exists;           //and a5, a5, t0
    u64 G = D * A;                                  //mulhu a1, a1, a2
    u64 G_exists = G != 0;                          //snez a1, a1
    u64 G_C_A_exists = G_exists | C_A_exists;       //or a1, a1, a5
    u64 I = C * B;                                  //mulhu a3, a3, a0
    u64 I_exists = I != 0;                          //snez a3, a3
    u64 G_I_C_A_exists = G_C_A_exists | I_exists;   //or a1, a1, a3
    u64 overflow = G_I_C_A_exists | E_overflow;     //or a1, a1, a7
    u64 F = D * B;                                  //mul a0, a0, a2
    c->l = F;                                       //sd a0, 0(a4)
    c->h = HEJ;                                     //sd a6, 8(a4)
    return overflow;                                //mv a0, a1     //ret
}
V1KT0P ★★
()
Последнее исправление: V1KT0P (всего исправлений: 1)
Ответ на: комментарий от V1KT0P

для RISC-V (64-bits)

Так интересно-то когда разрядность результата умножения в 4 раза больше разрядности ядра. То есть для 64-битного уже int256_t нужен. Но проще скомпилировать для 32-битного ядра ваш int128

gcc 14.2.0

В моем 12.2.0 видать не завезли.

COKPOWEHEU ★
()
Ответ на: комментарий от ugoday

Как видите, мы вообще избавились от умножений.

а вот кстати, да

можно без MUL считать :-) ln(x) exp(x) вроде как можно считать поразрядно, только сложения и сдвиги..и загнать в GPU, упарываться так упарываться :-)

MKuznetsov ★★★★★
()
Ответ на: комментарий от COKPOWEHEU

Так интересно-то когда разрядность результата умножения в 4 раза больше разрядности ядра.

Решил чутка повелосипедить и запилить умножение uint512 с определением переполнения, а для понимания нужно сравнить с GMP и Boost. В результате сделал бенчмарк на скорую руку(вроде нигде не ошибся), если нет нужды в определении переполнения то Boost довольно близко по производительности (на треть медленее) к GMP. А вот при определении переполнения Boost в 33 раза медленее GMP.

Для Boost переполнение реализовал через исключение(из-за этого и проседает производительность при переполнении), по другому похоже нельзя. При исключении в результате будет мусор.

Для GMP переполнение реализовал через проверку размера результата, он динамически выделяет память до нужного количества байт при необходимости (если есть переполнение, то привет аллокация памяти).

Тестировал на Core i7-3770 в один поток:

Count of numbers: 3000000
Count of tests: 10
Overflow numbers: Yes
Count of numbers with overflow: 1475896
Count of numbers without overflow: 1524104

GMP checked: 140 ms
GMP: 134 ms
Boost checked: 4709 ms
Boost: 196 ms

Check Boost overflow detect: True
Check Boost checked_uint512_t overflow numbers: False
Check Boost checked_uint512_t not overflow numbers: True
Check Boost uint512_t overflow numbers: False
Check Boost uint512_t not overflow numbers: True

========================================================

Count of numbers: 3000000
Count of tests: 10
Overflow numbers: No
Count of numbers with overflow: 0
Count of numbers without overflow: 3000000

GMP checked: 99 ms
GMP: 93 ms
Boost checked: 133 ms
Boost: 128 ms

Check Boost overflow detect: True
Check Boost checked_uint512_t overflow numbers: True
Check Boost checked_uint512_t not overflow numbers: True
Check Boost uint512_t overflow numbers: True
Check Boost uint512_t not overflow numbers: True
V1KT0P ★★
()
Ответ на: комментарий от MKuznetsov

Не каждый обладает мощной видеокартой. Нам понадобится логарифмический и экспоненциальный операционные усилители. Благодаря чему мы избавимся даже и от сложений!

ugoday ★★★★★
()
Ответ на: комментарий от ugoday

Нам понадобится логарифмический и экспоненциальный операционные усилители. Благодаря чему мы избавимся даже и от сложений!

от сложений ненадо избавляться - можем ОУ впараллелить, результаты потом сложить, ошибка накопится только в младших разрядах а их мы доподлинно другими методами быстро знаем :-)

понижаем разрядность и паралеллим : A*B=(A0+A1+A2+A3)*(B0+B1+B2+B3); A0=A&0x11111..<<0 A1=A&(0x1111..<<1) A2=A&(0x1111..<<2) A3=A&(0x1111..<<3)

16 паралелльных мультипликаторов и 1 сумматор-reduce на их выходе

сводится к перемножению на отдельных ядрах чисел вида [{000x}n] где бит 1 может быть только в позициях кратных 4, остальное нули..

остаётся только распаять цифро-аналоговый комп :-)

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

Кажется, на Хабре была статья. Человек пытался обучить нейронку то ли складывать, то ли перемножать числа, а потом по получившимся весам восстановил алгоритм. Оказалось, нейронка переводит «цифровой» вход в «аналоговое» внутреннее представление, проводит с ним нужную операцию, и «оцифровывает» обратно.

COKPOWEHEU ★
()
Ответ на: комментарий от COKPOWEHEU

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

нейронку нельзя такому научить..можно сделать вид, но не научить. Для неё область определений - это подаваемое в обучении. Всё что вне области определений случайный результат к сожалению. Сама экстраполировать она не может.

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

Напротив. Прелесть нейронок именно в том, что они ищут закономерности, там нет строгого алгоритма. И по этой же причине результатам их работы нельзя доверять на 100%.

COKPOWEHEU ★
()
Ответ на: комментарий от COKPOWEHEU

Напротив. Прелесть нейронок именно в том, что они ищут закономерности, там нет строгого алгоритма. И по этой же причине результатам их работы нельзя доверять на 100%.

вашими устами, да к медку присосаться :-)

к сожалению нейронки не ищут закономерности..они выполняют интерполяцию. Экстраполяция им недоступна, всё что вне области обучения/определения - пальцем в небо. Ровно так-же как с полиномами. Можно поставить краевые условия что ответ вне области обучения будет более-менее верным, но это будет твой заранее заданный ответ, а не нейронки.

вообще все методы модных NN & DL занимаются именно этим - обобщением(сжатием), интерполяцией, довесью шума и обратным «расжатием» не противоречащим интерполяции. ZIP на стероидах, замкнутая система и ничего нового оно ни придумать ни найти не может.

MKuznetsov ★★★★★
()
Ответ на: комментарий от COKPOWEHEU

Напротив. Прелесть нейронок именно в том, что они ищут закономерности, там нет строгого алгоритма. И по этой же причине результатам их работы нельзя доверять на 100%.

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

V1KT0P ★★
()

Завелосипедил самый простой алгоритм умножения 512 битных чисел, пока без проверки переполнения. В тесте оказался всего лишь в 2 раза медленее GMP и в 1.5 раза медленее Boost. А я ведь даже сложение не оптимизировал, просто самый дубовый вариант сделал. Можно еще через алгоритм Карацубы сделать, тогда наверно можно будет приблизиться к GMP.

GMP: 93 ms
Boost: 127 ms
Naive: 194 ms
V1KT0P ★★
()
Ответ на: комментарий от MKuznetsov

можно ли сделать ещё более упорото ?

Умножение чисел - это задача класса P, поэтому доступна нейронкам. Естественно, проще самому расставить весы, чем обучать. Проверить точность обучения можно по лемме Шварца — Зиппеля.

ratvier ★★
()

Нашел у себя ошибку, все-же Boost checked_uint512_t нормально умножает при переполнении.

Глянул дизасм функции умножения а gcc вместо того чтоб заинлайнить функцию умножения делал по вызову на каждое умножение а это 36 вызовов. Благо __attribute__((always_inline)) решил эту проблему. Надо будет подумать еще сложения оптимизировать можно еще чуть выжать.

В результате у меня получилось:

Если числа не приводят к переполнению то наивный велосипед на 5% быстрее Boost и всего на 24% медленее GMP.

Если половина чисел приводят к переполнению то наивный велосипед на 65% быстрее Boost (не могу понять почему это приводит к замедлению) и на 10% быстрее GMP (так как он при переполнении вызывает аллокацию памяти и продолжает умножение даже если нам все за пределами 512 бит не нужно).

Count of numbers: 3000000
Count of tests: 10
Overflow numbers: Yes
Count of numbers with overflow: 1475896
Count of numbers without overflow: 1524104

GMP checked: 140 ms
GMP: 134 ms
Boost checked: 4616 ms
Boost: 197 ms
Naive: 118 ms

========================================================

Count of numbers: 3000000
Count of tests: 10
Overflow numbers: No
Count of numbers with overflow: 0
Count of numbers without overflow: 3000000

GMP checked: 102 ms
GMP: 95 ms
Boost checked: 130 ms
Boost: 127 ms
Naive: 118 ms
V1KT0P ★★
()
Ответ на: комментарий от V1KT0P

Вот что бывает, когда человек загорелся идеей =)

А я вечер потратил на переделку парсера, до реализации длинных целых не добрался. https://github.com/wandrien/qod/commit/ff002afb4cf015b24899ffaa1db7b3499991a5e4

wandrien ★★
() автор топика
Ответ на: комментарий от dataman

В копилку: https://github.com/ckormanyos/wide-integer.

Что-то не впечатлило, шаблон на шаблоне шаблоном погоняет. В итоге умножение 512 бит в 3 раза медленее чем простая функция на 200 простых строк кода без шаблонов. Там по умолачнию limb стоит 32 битный, но при попытке выставить 64 битный начинается поток непонятных ошибок шаблонов. Никакого желания нету лезть в лапшу из шаблонов.

Count of numbers: 3000000
Count of tests: 10
Overflow numbers: Yes
Count of numbers with overflow: 1475896
Count of numbers without overflow: 1524104

GMP checked: 140 ms
GMP: 136 ms
Boost checked: 4698 ms
Boost: 199 ms
Wide-integer: 392 ms
Naive: 119 ms

========================================================

Count of numbers: 3000000
Count of tests: 10
Overflow numbers: No
Count of numbers with overflow: 0
Count of numbers without overflow: 3000000

GMP checked: 98 ms
GMP: 94 ms
Boost checked: 132 ms
Boost: 128 ms
Wide-integer: 341 ms
Naive: 119 ms
V1KT0P ★★
()
Ответ на: комментарий от V1KT0P

Никакого желания нету лезть в лапшу из шаблонов.

Кстати, а _BitInt(N) из C2X тут ещё не вспоминали?

$ cat bitint.c

// $ gcc -std=c2x bitint.c

#include <stdio.h>
#include <limits.h>

int main()
{
    typedef _BitInt(512) int512_t;

    int512_t a = 1;
    int512_t b = 2;
    int512_t c = a + b;

    printf("The 512-bit uses %lu bytes in memory\n", sizeof(int512_t));

    printf("_BitInt(%d) uses %lu bytes in memory\n",
            BITINT_MAXWIDTH,
            sizeof(_BitInt(BITINT_MAXWIDTH))
          );

    return 0;
}
dataman ★★★★★
()
Ответ на: комментарий от wandrien

чел предложил проверять отсутствие переполнения при умножении через деление числа обратно.

реально не дурак

Во первых, мопед не мой. Во вторых, делить может только дурак? Библиотека арифметических операций с проверкой переполнения, на которую я дал ссылку, покрыта тестами и по идее должна работать правильно.

X512 ★★★★★
()
Ответ на: комментарий от wandrien

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

Да, но навряд ли это имеет смысл:

>>> def mul_ovf(a, b, word_size=8):
...     return log2(a) + log2(b) >= word_size
... 
>>> mul_ovf(128, 2)
True
>>> mul_ovf(127, 2)
False

Перемножить числа может быть гораздо быстрее, чем найти их вещественные логарифмы. Особенно если использовать SIMD.

anonymous
()
Ответ на: комментарий от anonymous

Перемножить числа может быть гораздо быстрее

Если только не таскать логарифмы в своей структуре рядом с числами. Тогда да — улетишь в космос на такой скорости определения переполнения.

anonymous
()
  1 2 3
← webassembly - пара теоретических вопросов.
Development
Как определить собраны ли исполняемые файлы с реализацией технологии PIE или нет →