Собственно нужен subj.
Задача сама по себе простая с точки зрения алгоритма, есть пирамидальное возведение в квадрат. но!
1) Алгоритм должен оперировать только с 32битными числами, то есть unsigned int.
2) Основание системы 32 бита.
3) Есть функция, которую надо использовать

unsigned int mul(unsigned int a, unsigned int b, unsigned int *high)

которая умеет умножать два 32х битных числа и получать старшие 32 бита и младшие 32 бита, вызывается так:

unsigned int lower;
unsigned int high;
lower = mul(a, b, &high);

4) при сложении двух 32-х ,битных чисел знак переноса теряется, то есть складываются числа по полулю 2^32.

Вот. сложность в том, чтобы грамотно организовать учитывание переносов и так, чтобы не сильно тратить на это время. У кого есть какие идеи?

Здравствуйте, vip_delete, Вы писали:

_>Собственно нужен subj.
_>Задача сама по себе простая с точки зрения алгоритма, есть пирамидальное возведение в квадрат. но!
Речь о длинной арифметике?

_>1) Алгоритм должен оперировать только с 32битными числами, то есть unsigned int.
_>2) Основание системы 32 бита.
_>3) Есть функция, которую надо использовать
_>

_>unsigned int mul(unsigned int a, unsigned int b, unsigned int *high)
_>

_>которая умеет умножать два 32х битных числа и получать старшие 32 бита и младшие 32 бита, вызывается так:
_>

_>unsigned int lower;
_>unsigned int high;
_>lower = mul(a, b, &high);
_>

_>4) при сложении двух 32-х ,битных чисел знак переноса теряется, то есть складываются числа по полулю 2^32.

_>Вот. сложность в том, чтобы грамотно организовать учитывание переносов и так, чтобы не сильно тратить на это время. У кого есть какие идеи?
Можно примерно так сделать:

#define LO16(n) (n & 0xffff)
#define HI16(n) ((n >> 16) & 0xffff)
#define MAKE32(hi, lo) ((hi << 16) | lo);

unsigned add(unsigned a, unsigned b, unsigned * carry)
{
    unsigned lo = LO16(a) + LO16(b);
    unsigned hi = HI16(a) + HI16(b) + HI16(lo);
    *carry = HI16(hi);
    return MAKE32(LO16(hi), LO16(lo));
}

Здравствуйте, vip_delete, Вы писали:

_>3) Есть функция, которую надо использовать
_>

_>unsigned int mul(unsigned int a, unsigned int b, unsigned int *high)

_>которая умеет умножать два 32х битных числа и получать старшие 32 бита и младшие 32 бита, вызывается так:
_>

_>unsigned int lower;
_>unsigned int high;
_>lower = mul(a, b, &high);

_>4) при сложении двух 32-х ,битных чисел знак переноса теряется, то есть складываются числа по полулю 2^32.

_>Вот. сложность в том, чтобы грамотно организовать учитывание переносов и так, чтобы не сильно тратить на это время. У кого есть какие идеи?

А нельзя использовать функцию:

unsigned long long mul(unsigned long a, unsigned long b);

и сложение делать тоже unsigned long long?

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

Так увлекся, что совсем забыл написать, что речь, конечно, о длинной арифметике под WINx32 с основанием системы счисления 32 бита, то есть unsigned long long юзать нельзя ни при каких вычислениях (Есть только один тип — 32бит-число и каждый знак длинного числа — это 32бит-число), два unsigned int умножаются только спец функцией (интрисик функцией), я ее уже писал — mul.

1) Хоть как придется складывать 32бит-числа и результат всегда будет 32бит-число, плюс надо после сложения узнавать был перенос или не был и запоминать его где-то. То есть трудность именно в управлении переносами...+ трудность еще в вычислении удвоенных произведений 2*a*b (там как минимум надо три штуки 32бит-числа)

p.s. p Понятно, что при основании чистемы счисления 16бит все просто...

Здравствуйте, vip_delete, Вы писали:

_>p.s. p Понятно, что при основании чистемы счисления 16бит все просто...
Ну а чудес-то не бывает Либо система отдает тебе флаг переноса, либо будь добр найти его ручками. А если ты думаешь, что складывать побитно будет быстрее, чем пословно...

Здравствуйте, Рома Мик, Вы писали:

РМ>Здравствуйте, vip_delete, Вы писали:

_>>p.s. p Понятно, что при основании чистемы счисления 16бит все просто...
РМ>Ну а чудес-то не бывает Либо система отдает тебе флаг переноса, либо будь добр найти его ручками. А если ты думаешь, что складывать побитно будет быстрее, чем пословно...

сейчас находится флаг так:

r[i] += a;
k = r[i] < a;

В докупентации по флагам проца написано, что знак переноса теряется. но дело именно в управлении переносами. есть как вариант на sse складывать, но там тоже надо управлять переносами. короче в итоге все время на переносы и уходит. Просто может кто-нибудь уже реализовывал подобное? Хотелось бы именно оптимизированный вариант. хоть какой-то уже есть

время в попугаях

sumTime: 0.096287 (время сложения)
mulTime: 2.5289 (время умножения)
sqrTime: 1.66162 (время возведения в квадрат) <- из-за переносов слишком долго по отношению к умножению.

Здравствуйте, vip_delete, Вы писали:

_>В докупентации по флагам проца написано, что знак переноса теряется. но дело именно в управлении переносами. есть как вариант на sse складывать, но там тоже надо управлять переносами.
Слушай, если у тебя есть sse, то у тебя однозначно есть и 64-битное умножение и сложение, нет таких процов с sse и без 64-битной арифметики.

_>короче в итоге все время на переносы и уходит. Просто может кто-нибудь уже реализовывал подобное? Хотелось бы именно оптимизированный вариант. хоть какой-то уже есть
Не буду ничего утверждать, но я бы попробовал с 16-битным вариантом, может оказаться и быстрее, хотя конечно может и не оказаться.

_>sumTime: 0.096287 (время сложения)
_>mulTime: 2.5289 (время умножения)
А тут как без переносов обходишься?

_>sqrTime: 1.66162 (время возведения в квадрат) <- из-за переносов слишком долго по отношению к умножению.
Вообще-то это быстрее умножения

Я бы рекомендовал-таки использовать ассемблер. По крайней мере для сложения/вычитания (лично я реализовывал на нём также и несколько алгоритмов умножения, в том числе и этот самый "столбик").

Здравствуйте, vip_delete, Вы писали:

_>Собственно нужен subj.
_>Задача сама по себе простая с точки зрения алгоритма, есть пирамидальное возведение в квадрат. но!
_>1) Алгоритм должен оперировать только с 32битными числами, то есть unsigned int.
_>2) Основание системы 32 бита.
_>3) Есть функция, которую надо использовать
_>

_>unsigned int mul(unsigned int a, unsigned int b, unsigned int *high)
_>

_>которая умеет умножать два 32х битных числа и получать старшие 32 бита и младшие 32 бита, вызывается так:
_>

_>unsigned int lower;
_>unsigned int high;
_>lower = mul(a, b, &high);
_>

_>4) при сложении двух 32-х ,битных чисел знак переноса теряется, то есть складываются числа по полулю 2^32.

_>Вот. сложность в том, чтобы грамотно организовать учитывание переносов и так, чтобы не сильно тратить на это время. У кого есть какие идеи?

Насколько длинные числа предполагается перемножать? Ведь есть куда более экономные метод Карацубы (O(n^1.5)) и алгоритм перемножения с помощью преобразования Фурье в кольце многочленов (O(n ln(n)lnln(n)). Они более сложны в реализации (т.е. исчезнут преимущества реализации на ассемблере), но при перемножении чисел порядка 1024 бит и более дадут ощутимый выигрыш.