cresta Я с VC++ все это дело делал, а мелкомягкие всегда своей дорогой идут, тот же файл впринципе можно и в другом компилере скомпилить, только stdafx.h убрать. На чем ты компилишь? Насчет GetTickCount - забыл поменять, на моей только машине и получался правильный результ. В аттаче тот же код, но и с rdtsc - мне его разброс просто не нравиться (в идеале надо вообще время потока использовать). Погрешность измерения GetTickCount вполне укладывается в этот разброс, но надо задавать частоту (сейчас под это дело константа заведена). С VB (как в других HLL) можно обойтись без использования переносов, но это опять же тормоз несусветный, еще бы сильную криптографию на нем писали... Вот пример на Це (поправде не проверял): <font face="fixedsys] void add32 (BYTE* a, const BYTE* b) { QWORD d = 0; for (int n = 0; n < 32; n ++) { d = a [n] + b [n]; a [n] = (BYTE) d; d >>= 8; } } </font><!--face-->
alpet Можно и без них обойтись. Заводишь промежуточное двойное слово (слово тоже знаковое в VB) и всё что не влезло уходит в старший байт (причём не побитно, как в ADC и RCL). Ну а потом "Value AND &HFF00" и перенос у тебя. Хотя "всё", это наверное я прогнал. Больше чем на один бит при сложении никак не получится. cresta Он родимый. Отключение проверки переполнения числа не предлагать, мало ли у кого что. Про то чтобы каждый раз подгружать таблицу в память это ты наверное погорячился. Никто в здравом уме такого делать не станет. Один раз при загрузке грузишь, а потом просто обращаешся по индексу к элементу.
Проверки на переполнение не выполняются, для преобразования числа в 78 цифр требуется где-то 1500 тактов. Цифры собираются по 9 штук(на последней итерации может быть меньше) в регистре edx, а затем содержимое буфера умножается на 1000000000(если это не последняя итерация) и цифры добавляются к нему. Код (Text): atoi256:;(+4 - pu256, +8 - str) push ebp push ebx push esi push edi ;+16 mov edi,[16+esp+4] mov esi,[16+esp+8] xor eax,eax mov ecx,8 rep stosd mov ebx,1 lodsb mov edx,.nop cmp al,'+' jz .plus cmp al,'-' jnz .nosign .minus: mov edx,.neg .plus: inc esi .nosign: dec esi push edx xor edx,edx xor eax,eax mov ebx,1 .loop: lodsb sub al,'0' cmp al,9 ja .eloop lea edx,[edx*5] lea ebx,[ebx*5] lea edx,[edx*2+eax] add ebx,ebx cmp ebx,1000000000 jb .loop call .long_mul xor edx,edx jmp .loop .eloop: cmp ebx,1 jnz .long_mul ret .long_mul: mov ecx,-32 .long_mul_1: mov ebp,edx mov eax,[edi+ecx] mul ebx add eax,ebp adc edx,0 mov [edi+ecx],eax add ecx,4 jnz .long_mul_1 mov ebx,1 xor eax,eax ret .neg: xor eax,eax not dword [edi-32] not dword [edi-28] not dword [edi-24] not dword [edi-20] not dword [edi-16] not dword [edi-12] not dword [edi-8] not dword [edi-4] add dword [edi-32],1 adc dword [edi-28],eax adc dword [edi-24],eax adc dword [edi-20],eax adc dword [edi-16],eax adc dword [edi-12],eax adc dword [edi-8],eax adc dword [edi-4],eax .nop: pop edi pop esi pop ebx pop ebp ret 8
alpet Исправленный тоже вылетает, на malloc В общем переделал его на VirtualAlloc/VirtualFree. И дописал в него нормальный rdtsc, по всем правилам. Можно и как inline его оформить, но на таких значениях (тысячи и десятки тысяч) особого смысла в этом нет. В общем примерно как и предполагал, так и получается. Табличный вариант работает быстро, если многократный вызов в цикле, без перерывов на выполнение каких-то других фрагментов кода: Код (Text): const int loops = 100000; Init_Clock(); //запуск счётчика for (int n = loops; n --;){ Cvts ((PVOID) x, "123456789012345678901234567890123456789012345678901234567890123456789 012345678"); } Stop_Clock(); //останов счётчика dwStartL=dwStartL/loops; //кол-во тиков на 1 проход Для loops = 100000 получается на 1 проход ~5900 тиков. Но если вызывать однократно (loops = 1) то получается на один проход ~47000 тиков. Это плата за подгрузку такого размера таблицы в кэш. Хотя, LZNT1, таблица уже сформирована по WM_CREATE, и её больше никто не освобождает и снова не формирует. При однократных вызовах она только лишь из ОЗУ готовая подгружается в кэш. Ценой 41000 тиков. Тут уж тебе выбирать, будет твоя прога непрерывно тысячи раз конвертировать строку или будет заниматься этим однократно. Если при каждом вызове заниматься ещё и формированием таблицы, (вариант, где предполагалось, что я погорячился то там получается неприличное значение порядка 4500000 тиков на один вызов. В аттаче исходник на c++ и два ехе: один с циклом на 1 проход, другой на 100000 проходов (это если у LZNT1 нет компилятора си). То, что выводит в теле мессаджбокса - младшие 32 бита счётчика, в заголовке мессаджбокса - старшие 32. Обычно они равны 0. В общем без таблицы пока имеется для однократного вызова ~9900 тиков, для многократного - 8800. _836391581__big_str.zip
Black_mirror Ну ты и оптимист сразу по 9. А мы тут по 1 цифре копаемся Похоже, теперь в сторону fpu или xmm надо смотреть, чтобы сделать быстрее.
cresta У Кнута в разделе про быстрое умножение описывается такая идея(это самая понятная из всех, дальше идёт преобразование Фурье, а в конце вывод о том, что умножение и деление можно выполнять за время пропорциональное длине числа, на машине, которая последовательно считывает данные и имеет операцию индексации(как именно я еще не понял), и за log(len) на параллельных схемах): Пусть нужно умножить два числа, длиной 2n бит каждое. Первое число ax+b, а второе cx+d, где a,b,c,d числа меньше 2^n, а x=2^n. Произведение можно представить как ac*x^2+ad*x+bc*x+ad. Здесь четыре умножения чисел длиной n. Их число можно уменьшить до трёх, представив ad+bc как (a-b)(d-c)+ac+bd или (b-a)(c-d)+ac+bd или ac+bd-(a-b)(c-d) или ac+bd-(b-a)(d-c) (для вычислений нужно использовать тот вариант, в котором обе разности входящие в произведение положительны, этот момент доставляет некоторое неудобство при реализации). Что касается применения этой идеи к нашей задаче: Собираем по 9 цифр в слова, получится 8 слов и еще не полное слово, которое будем обрабатывать отдельно. Далее разбиваем числа на пары, умножаем старшее число на 10^9(,10^18,10^36 берём из таблицы) и добавляем младшее. Умножений получается вроде 4+2*3+1*9*9, +8 для обработки не полного слова. Сложений наверно получится где-то около сотни(считать пока лень).
Сделал один вариант, ~800-900 тиков, но он пока для строки, длина которой кратна 8 символам (в частности 72 или 80). Попробую доработать чтобы любую длину принимал.
Black_mirror Э, чёт я не врубился. Значит берём мы 9 десятичных чисел и разбиваем на пары: 12 34 56 78 9?. Или мы сначала их конвертируем в двоичный формат? Дальше что, старшее число умножаем на миллиард(зачем?). Нельзя подробней расписать алгоритм (извини за непонятливость)? И ещё, это что за масштаб lea edx,[edx*5]? Вроде ж бывает только 1,2 и 4.
bogrus Интересный плод фантазии разработчиков языка. Но всё же, имхо, это неправильная запись, т.к. она искажает представление команды (правило SIB).
Вроде родил Правда, несколько длинновато получилось Но вроде быстро. Первый проход (при подгрузке в кэш) ~3400 тиков, последующие проходы ~950 тиков. Преобразуется по 8 символов сразу (для кратности дворду), с умножением на 10^8. Кстати, LZNT1, если у тебя строка фиксированной длины, то можно это дело значительно сократить и ускорить. Наверное, тиков в 700-750 можно уложиться. Процедура в аттаче. Это заморочки фасма )) Блин, аттач забыл
cresta Хоть ты мне скажи что даёт умножение на миллиард. Не могу ж я тупо код перебивать. Кстати, может кому будет интересно. http://www.macro.aaanet.ru/apnd_13.html
На миллиард умножал Black_mirror, у меня 100 миллионов.. Но принцип наверное один. Маленький пример: строка "1234" = ((((0*10)+1)*10+2)*10+3)*10+4 - это если преобразовывать поразрядно. Разряд - это 10 в десятичной системе, поэтому буфер каждый шаг умножается на 10 - один разряд. То же число можно посчитать иначе, например "по-двухразрядно", значит умножая на 2 десятичных разряда(100): "1234" = ((0*100)+12)*100+34. Как видно, оба способа дают одинаковый результат 1234, но второй способ использует всего 2 умножения и 2 сложения, в то время как первый - 4 умножения и 4 сложения. За счет уменьшения количества действий (особенно умножений) и происходит ускорение работы. Чем руководствовался Black_mirror при выборе, сколько разрядов разом обрабатывать (9) - это к нему вопрос. Я выбрал 8 разрядов исходя из соображений уменьшения (исключения) переполнения при умножении и возникающей при этом необходимости коррекции результатов (adc). И второй момент - 8 символов кратны дворду. Взять очередные 8 разрядов для преобразования - это просто взять два дворда из строки. Если было бы 9, то нужно было бы брать три дворда, но третий на 75% был бы взят вхолостую, т.е. потеря времени. Black_mirror берет символы из строки побайтно (lodsb), за счёт этого у него несколько медленней (на одно умножение надо 9 раз грузить из строки, у меня 2 раза). Можно конечно было и сделать по 4 разряда (по одному дворду), но тут увеличивается количество умножений и сложений. Невыгодно. Примерно такой расклад. А ссылка интересная, спасибо.
Ещё вариант на тему по-двордной обработки строки. ~810-820 тактов. Код в аттаче, с кое-какими комментариями. 964220084__s_256 .inc
Я имел в виду что результатом умножения является 64-битное число в двух регистрах (EDX:EAX). MUL - это скорее обходной манёвр для ассемблера, позволяющий за счёт процессора расширить операнд вдвое. На ЯВУ такое не прокатит. Вызов функции из DLL - это не алгоритм. Да и обходной манёвр в принципе тоже.
