Сложение очень-очень длинных чисел

Т.е. сложение беззнаковое?

 

Gray > "вероятность CF или ZF в вышеописанной ситуации крайне мала"

TheSvin > "..разные ситуации с CF, но данные на вход лучше подавать более продуманными"

Собственно, первоначальная идея с использованием перехода и основывалась на предположении о его малой вероятности. Поэтому поиск вариантов с меньшей зависимостью от числа переходов можно считать в некоторой степени развлечением, хотя если такой вариант найдется и будет работать не на одной модели проца, то почему бы и нет. А чередование переходов через цикл - это видимо наихудшая ситуация, т.к. динамическое предсказание работает и на P3, и в текущем цикле заранее начинает выполняться ветка (или готовится ее выполнение), которая выполнялась в предыдущем цикле (может я и не прав, но похоже что так).



А вот на P4 существенно снизить потери за счет ошибок предсказания что-то не удается и наверное это не удивительно, учитывая длину гипер-конвейера. Поэтому остается надеятся на вероятность, а может лучше использовать вариант Gray с SSE2 на тех процах, где это возможно.

 

The Svin > "Т.е. сложение беззнаковое?"



Полагаю, что самым быстрым вариантом будет хранение знака в заголовке числа, а в "теле" хранить лишь абсолютную величину оного. При сложении с отрицательным числом просто делать вычитание. Т.е. беззнаковым я бы называть его не стал, знак есть, но хранится отдельно. Этот тот самый случай, когда главная цель (быстро вычислять) диктует формат хранения данных.

 

Gray

Полагаю, что самым быстрым вариантом будет хранение знака в заголовке числа, а в "теле" хранить лишь абсолютную величину оного

все те либы для работы с длинными числами, которые я видел, именно так и делают.



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

 

Max, создавать всегда интереснее, чем переделывать

 

Gray

нуу, если такими темпами делать сложение, то я представляю, что будет, когда пойдет умножение или деление ))

 

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

Давненько я такого сюрра не слышал.

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

Ты должен показать сам формат и доказать что и при нём это будет работать, чтобы убедить, что не делается мартышкин или Сизифов труд.

 

Gray

Пусть у нас одно число положительное а другое отрицательное, и оба имеют одинаковую длину в битах, как узнать из первого второе нужно вычитать или наоборот, чтобы получить результат в таком же формате?

 

[offtop]

Корень зла - незнание истины. Из этого корня вырастает дерево сомнений со множеством полодов страданий.

Будда.



[/offtop]

 

Black_mirror

Пусть у нас одно число положительное а другое отрицательное...

в аттаче кусок одной из либ на паскале.

если кратко, то процедура сложения вызывается рекурсивно, только числа меняются местами

_2025673999__sample.pas

 

"Да... оказывается мы придумываем сложение чисел с форматом которого не определились..."

Я все-таки понимаю задачу так, как она сформулирована в названии темы, т.е. в общем. И Gray в своих неоднократных пояснениях прямо или косвенно об этом говорил. Если мы хотим не просто быстренько "спихнуть" задачку, а поисследовать проблему, то мы разбиваем ее на этапы. Вполне естественно, что на первом этапе решалась задача сложения длинных чисел, записанных в обычном формате. Здесь, по крайней мере для меня, думаю и для других тоже, выяснилось очень много интересного, связанного с особенностями работы современных процессоров (к сожалению, об особенностях атлонов мы мало чего узнали...). Это и то, что ADC на P3-P4 довольно тормозная инструкция, и что самый компактный код, далеко не всегда оказывается самым быстрым, и что предсказумые переходы в циклах "не так страшны, как их малюют", и насколько важно выравнивание кода и т.д. и т.п. Что-то из этого было известно "теоретически", но тут оно было проверено на практике и подтверждено тестами. Разве можно говорить, что это был мартышкин труд ?

На втором этапе можно поговорить и о формате чисел. В частности разная длина операндов не протеворечит тому, что было сделано. Gray сразу говорил, что y < x. Поэтому под size мы можем понимать длину у и при выходе из цикла добавить перенос в старшие разряды x в дополнительном цикле с выходом по JNC. Что касается изменения формата (прямой код, динамическая длина и т.п.), то я согласен с Max - прежде чем изобретать велосипед, не мешало бы ознакомится с "мировыми достижениями" в этом деле и затем предложить какой-нить вариант для затравки. Иначе все зациклится на уровне беспочвенных рассуждений.



PS: Все-таки не удержусь от замечания насчет "интересной мысли" Gray по поводу ZF. Я ее считаю не особо интересной, поскольку если комбинация 0\0 вещь редкая, то JZ ничего не дает кроме дополнительного проигрыша, когда эта комбинация все-таки встречается. Некоторая польза от нее может быть именно в случае, когда операнды одинаковой длины и 0 < у < x, т.е. когда мы "тупо" складываем старшие дворды x с нулями. Тогда за счет динамического предсказания может удастся что-то сэкономить.

 

Max >"может быть имеет смысл не изобретать велосипед по новой, а взять готовую либу и попытаться прооптимизировать ее?"

Gray >"создавать всегда интереснее, чем переделывать "

Max >"нуу, если такими темпами делать сложение, то я представляю, что будет, когда пойдет умножение или деление ))"



Кстати, алгоритм быстрого умножения Карацубы был создан именно в процессе "изобретения велосипеда"

 

The Svin >"Да... оказывается мы придумываем сложение чисел с форматом которого не определились..."



Смеюсь Классический RTFM. Я ведь не просто так постил в форум свой сишный исходник (См. первую страницу темы. Gray Дата: Окт 7, 2004 12:24:57) Из него мой рабочий формат чисел очевиден

И про свое отношение к формату писал (См. вторую страницу темы. Gray Дата: Окт 7, 2004 18:06:01 )

Формат - не догма! Если удастся придумать формат дающий большее быстродействие, с удовольствием буду его использовать. Как Вам мысль о хранении чисел блоками по 127 или 63 бит с перспективой использования возможностей SSE2?

 

S_T_A_S_ > "Корень зла - незнание истины. Из этого корня вырастает дерево сомнений со множеством полодов страданий.

Будда. "



Червь познания питается плодами сомнений...

Кто-тоМудрый

 

leo >"Все-таки не удержусь от замечания насчет "интересной мысли" Gray по поводу ZF. Я ее считаю не особо интересной, поскольку если комбинация 0\0 вещь редкая, то JZ ничего не дает кроме дополнительного проигрыша, когда эта комбинация все-таки встречается."



Похоже я плохо выразил мысль о ZF. Речь идет лишь о варианте, когда используется комбинация

add eax,edx

jc @@carry2



В этом случае лучше писать

add eax,edx

jz @@carry2



Выигрываем мы на этом конечно очень мало, но все же выигрываем

 

1. Определение обычный формат субъективное, это опять случай, когда никакой сложности нет точно сказать какой формат, но почему то труда ты себе не даёшь и читателям приходится предпологать а что такое для leo обычный формат.

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

У Gray нет никакого формата, он его не придумал, поэтому к сложению его чисел данный топик имеет косвенное отношение.

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



2. По поводу

Предположим что речь идёт о целых числах в дополнительном коде. Тогда вспомним как мы раскладываем слогаемые в алгоритме у нас есть cf который складывается с a и их сумма складывается с b. (a+cf)+b.

Трудно понять из выражения

что имелось ввиду (для меня она выглядит как ноль делённый на ноль) но что имелось ввиду Gray то это случай когда при a+cf a=0=cf

А случай которые я использовал это a=FFFFFFFh cf=1

Так вот таких случаев не больше не меньше а ровно столько же. Возьми все числа где на определённых участках a=FFFFFFFh cf=1, сделать not множества этих чисел, получишь равномощное множество чисел со случаями

a+cf a=0=cf.

3.

Ты видимо не понял вообще о чём речь, тут не может быть проигрыша никак, меняется просто условие в переходе.



Давай по полочкам

Есть два и только два случая когда a+cf=0

Первый случай это тот же что и когда (a+cf) вызывает cf

т.е. а=-1 и cf=1

Другой случай a+cf=0 это a=0 и cf = 0.

Всё! больше случаев быть не может!

Обрати внимание что в первом случае cf и до и после сложения равен будет 1 а во втором и до и после cf будет равен 0, иначе говоря cf не изменится.

Пусть у нас переменная cf ={1,0}

Определим функцию CF(a,cf) которая будет возвращать тоже

{1,0} если будет CF при сложении текущего cf и a,

тогда можно так записать идею про ZF

(a+cf=0)&(CF(0,0)=0)&(CF(-1,1)=1)->

->(a=-1 & cf=1)|(a=0&cf=0)->

->(CF(-1,cf)=1=cf)|(CF(a,cf)=0=cf)->

->CF(a,cf)=cf&(a+cf=0)

CF это carry после операции cf - до.

Если установился ZF - то ни cf ни надо проверять, ни 0 ни надо прибавлять.

Мы просто

Код (Text):

1.  
2. jc @@carry2
3.     add [edi],eax
4.     setc dl
5. @@carry2:
6.  

меняем на

Код (Text):

1.  
2. je @@carry2
3.     add [edi],eax
4.     setc dl
5. @@carry2:
6.  

Ты меня в сомнения ввёл своей фразой, я уже не уверен это ли имел ввиду Gray, но так я понял и из того, что я понял никак это ухудшить или увеличить код не может, меняется tttn короткого перехода и теперь оно покрывает оба случая когда CF не меняется и a после сложения равно 0.



4. По поводу поста о худшем случае с переходами.

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

Возможно оно верно, но пока бездоказательно.

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

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

Например ты хочешь сравнить а что ты можешь купить в местном ларьке и в местном супермаркете (в смысле ассортимента а не возможностей финансовых) худший случай - оба они закрыты и ничего ты не купишь там. Лучший - полный возможный ассортимент для каждого из них. Так как средний то вычислять? Пополам что-ли делить лучший?

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

Короче нужно искать модель для вычисления "среднего" случая, она тут важнее.

 

Gray & TheSvin еще раз о JZ

Все что вы оба говорите я прекрасно понимаю, это вы меня понять не хотите.

Я тестировал на P3 и P4 несколько вариантов переходов: 1) нет переходов вообще, 2) в каждом цикле кроме первого есть переход, 3) переход в каждом нечетном цикле, 3) переходы в каждом 4, 8 и 16 цикле (дальше не было смысла т.к. тенденция стала ясна). При этом вариант 2) давал несколько лучшие результаты чем 1). Вариант 3) давал наихудшие и намного худшие результаты. Дальше с уменьшением числа переходов ситуация улучшается. Цифры для P4 приведены на стр.5, leo 16 окт 12:17, аналогичная тенденция наблюдается и для P3, поэтому в начале стр.6 я уже не приводил все варианты, а только 1 и 3 (если нужно могу привести все).

Какой из всего этого напрашивается вывод. Очень простой: и в P3 и в P4 рулит предсказание переходов (в первом цикле статическое, в последующих динамическое). В варианте 1) и статическое и динамическое предсказание совпадают и jc занимает максимум один такт, а если доверять интелам то 0. В варианте 2) один раз получается промах, но зато проц пропускает неисполняемые инструкции и в итоге получается несколько лучше. В остальных же случаях возникают НЕПРЕДСКАЗУЕМЫЕ переходы и связанные с этим penalty, т.к. проц должен выбросить из конвейера ненужные микроопы и\или отменить результат, если он уже успел его "сощелкать". На P4 ес-но результаты хуже за счет более длинного конвейера (см.IA-32 optimization).

Теперь что касается ZF. Если считать, что комбинации (у=1,cf=1) и (y=0,cf=0) появляются случайно и равновероятно, но не идут пачками, то мы при замене jc на jz будем иметь в среднем в два раза больше НЕПРЕДСКАЗАННЫХ длительных переходов. Вы считаете это хорошо и "интересно" ?

Все-таки переходы никогда не считались быстрыми операциями, и в доках по i486 приводились задержки jcc: 1 такт при отсутствии перехода и не менее 3 тактов при наличии. В P3 и P4 ситуация изменилась - здесь важно не то есть прыжок или нет, а то что проц правильно угадал куда пойдет выполнение. Если угадал, то задержки практически нет, если не угадал то говорить о задержке просто "not applicable", ребята из интел только говорят что она может быть большой, сравнимой с длиной конвейера и что ветвление следует избегать где только возможно.

В нашем случае jc - это необходимость (т.к. иначе нужен еще один setc, а это уже хуже, чем просто adc), а вот зачем сюда еще jz навешивать, я не очень понимаю. Вот если числа фиксированного формата и старшие дворды y= 0 и мы продолжаем складывать х с нулями, тогда за счет повторяемости ситуации jz не будет давать задержки на этих нулях.

Впрочем, я ничего не советую и тем более не навязываю, а просто поясняю ситуацию так как ее понимаю.

 

[flood]

Ох и не хочется мне снова возвращаться в этот топик, поскольку всё что я здесь пишу больше похоже на флуд =)

Но всёже напишу, повторюсь.



НЕЛЬЗЯ РЕШИТЬ ЗАДАЧУ "В ОБЩЕМ" !!!



Решать - можно, будет приобретён опыт, может ещё что..



Но универсального решения не существует. Нет такого алгоритма, который бы работал одинаково эффективно для

любых данных.



Что такое "очень-очень длинное число"? Может пара мегабайт? Тогда увеличения скорости нужно добиваться другими методами



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



И IMHO

здесь не уместен. Ещё STFW напишите "Найди условия задачи в гугле" .

Ну из того сишного исходника очевидно-то?

Да, можно сделать некоторые предположения, как делал я. Потом оказывается, что они не верны для задачи в целом, а являются лишь частным случаем (что и не удивительно).





Для сомневающихся в важности знания не только формата данных, но и контекста, в котором эти самые данные используются, простой вопрс на засыпку:

даны строки ascii символов, нужно производить их сравнение на равентсво. Как лучше эти строки представить, что бы получить максимально быстрое сравнение? (в формате asciiz или Pascal или..)



ЗЫ: учитывая вышесказанное и то, что у меня athlon, можно делать догадки, почему

ЗЫЫ: Не принимайте всё это близко к сердцу, просто вспомнил, как пришел как-то на Θорум человек, тоже числа складывать быстро хотел. А потом оказалось, что большие числа нужны, что бы отображать счёт в игре %)



[/flood]

 

S_T_A_S_

Чего-то тебя тоже на пространные изложения потянуло, а намек с атлономами ты понял правильно и, надеюсь, без обид

Ты бы высказал свое мнение по поводу условных переходов в цикле (см.предыдущий пост leo) - как по твоему, правильно я понимаю и интерпретирую результаты в том плане, что в P6 и NetBurst штраф за неверное предсказание ветвления может превышать "выигрыш", который можно было бы получить перескочив пару инструкций (для данного случая это add m32,r32 и setc r8 - довольно много микроопов).



PS:

S_T_A_S_ & TheSvin

А в этом топике я тоже чувствую себя неуютно - уж больно много любителей цепляться к словам. Похоже тут собрались юристы и дипломаты - одно невыверенное слово - и жди международного скандала. И зачем я написал "в общем", когда нужно было "в частном". Посмотрите самый первый вопрос Gray - приведен код с инструкцией ADC и вопрос "Как бы сделать это еще быстрее?" Но тут появляется "невыспавшийся" Arvensis и задает вопрос о формате, за который тут же сам и извиняется. Gray ему конкретно отвечает "числа хранятся двойными словами, но можно формат хранения и поменять, если это позволит складывать быстрее". Я конечно не дипломат и понял это так, что числа хранятся в обычном виде, т.е. в дополнительном коде (иначе причем здесь ADC) и от того, что мы увеличиваем разрядность чисел ничего принципиально не изменяется, кроме того что нужно производить сложение по частям с учетом переноса (ага, вот вам еще возможность прицепиться, считая собеседника идиотом, и в сотый раз доказывать, что может быть лучше изменить формат, а что если мегабайты, гигабайты, террабайты и т.д. и т.п.)

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

 

leo >"при замене jc на jz будем иметь в среднем в два раза больше НЕПРЕДСКАЗАННЫХ длительных переходов."



Вот теперь то до меня дошло Интересная мысль. Появилось желание написать что-то совсем без переходов.

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