Кто то когда то рано или поздно пытался написать модули для работы с большими числами. Вот и моё время подошло (ну я философ прямо ). Вобщем есть 256-битное число (массив из 32-х байт). Как в него запихнуть соответсвующее его диапазону десятичное число в строчном представлении?
Т.е. надо в число запихнуть строку? Это как??? Может в буфер запихнуть? Или преобразовать строку в число? Что-то задача не очень конкретная. Что на входе есть? Что должно быть на выходе?
Неиначе как требуется шустрый вариант atoi для 256-битных чисел. На входе число в виде строки, порядка 78 символов (целое со знаком, но очень большое), на выходе его двоичный эквивалент. Сразу приходит на ум, насколько удобны шестнадцетиричные числа...
atoi для bigint'ов... Скорость по идее не критична, можно решить проблему в лоб: сделать классическую функцию atoi, но все ариф. операции в ней тоже на bigint'ах.
alpet Не то чтобы они были как то особенно удобны, просто их можно привести к двоичным. Десятичные наверное тоже можно, но как неясно. Единственная закономерность (которую я нашёл) то что предел диапазона десятичных укладывается в границы 0-4-7 бит. 000009 - 0000 0000 0000 0000 1001 - 4 000099 - 0000 0000 0000 0110 0011 - 7 000999 - 0000 0000 0011 1110 0111 - 10 009999 - 0000 0010 0111 0000 1111 - 14 099999 - 0001 1000 0110 1001 1111 - 17 999999 - 1111 0100 0010 0011 1111 - 20 0009999999 - 0000 0000 1001 1000 1001 0110 0111 1111 - 24 0099999999 - 0000 0101 1111 0101 1110 0000 1111 1111 - 27 0999999999 - 0011 1011 1001 1010 1100 1001 1111 1111 - 30 _BC_ Тоже тут порыскал в инете в поисках альтернативных способов пробразования DEC->BIN, но ничего кроме деления с остатком не нашёл. Можно ли такое сделать с помощью булевых операций? Может быть маски какие посоставлять?
По моим прикидкам наиболее простое и производительное решение будет с использованием таблички (порядка 780 256-битных значения: 1,2,3..9,10,20..90,100,200..900 и т.д.), тогда на долю binint математики выпадает только сложение, что конечно не так ресурсоемко, как умножение на 10. Вобщем сначала лучше обозначить общий алгоритм на HLL, а потом реализовать и оптимировать его на асме.
alpet Вроде умножение на 10 не так трудно реализовать: это можно свести к копированию буфера, содержащего число, в новый destination со смещением в 3 бита, и затем к новому буферу дважды добавить исходный.
780*256=199680 - многовато получается. По поводу умножения на 10, это значит конвертировать значение разряда в двоичный формат, а потом возводить в нужную степень? Вроде подходит. cresta Хороший алгоритм, попробую им воспользоваться.
Умножение 256-битного числа на 10. Младшие биты числа - по младшим адресам (в dw_0). Код (Text): .data dw_0 dd 0 ;8 двордов - 256 бит dw_1 dd 1 dw_2 dd 2 dw_3 dd 3 dw_4 dd 4 dw_5 dd 5 dw_6 dd 6 dw_7 dd 7 temp_0 dd 0 ;temp-буфер temp_1 dd 0 temp_2 dd 0 temp_3 dd 0 temp_4 dd 0 temp_5 dd 0 temp_6 dd 0 temp_7 dd 0 temp_t dd 0 .code lea esi,dw_0 lea edi,temp_0 mov edx,7 _copy: ; - копирование 256-битного числа в temp-буфер mov eax,[esi+edx*4] mov [edi+edx*4],eax dec edx jns _copy mov ecx,3 _shift: ; - сдвиг temp-буфера на 3 разряда влево (умножение на 8) shl dword ptr[edi+0],1 rcl dword ptr[edi+4],1 rcl dword ptr[edi+8],1 rcl dword ptr[edi+12],1 rcl dword ptr[edi+16],1 rcl dword ptr[edi+20],1 rcl dword ptr[edi+24],1 rcl dword ptr[edi+28],1 dec ecx jnz _shift mov ecx,2 _adc: ; - добавление дважды к temp-буферу исходного числа clc mov eax,[esi] adc [edi],eax mov eax,[esi+4] adc [edi+4],eax mov eax,[esi+8] adc [edi+8],eax mov eax,[esi+12] adc [edi+12],eax mov eax,[esi+16] adc [edi+16],eax mov eax,[esi+20] adc [edi+20],eax mov eax,[esi+24] adc [edi+24],eax mov eax,[esi+28] adc [edi+28],eax dec ecx jnz _adc mov edx,7 _copy_back: ; - копирование числа из temp-буфера (умноженного на 10) в исходный mov eax,[edi+edx*4] mov [esi+edx*4],eax dec edx jns _copy_back Вроде ничего не напутал Надо конечно потестить. Я проверял только на тех значениях, что прописаны в dw_0 - dw_7. Насчёт скорости - сравнивать пока не с чем.
LZNT1 Ничего не много = 25 Кбайт всего. На многих процессоров это влезет в пределы кэша L1. Вот кстати свойство что поможет в большей упаковке и существенному повышению производительности: 10000 = 0x2710, 20000 = 0x4E20, 30000 = 0x7530, 40000 = 0x9C4... младшие 4 бита = 0 100 млн. = 0x5F5E100, 200 = 0xBEBC200, 300 = 11E1A300... младшие 8 бит = 0 1e12 = E8D4A51000, 2e12 = 1D1A94A2000, 3e12 = 2BA7DEF3000... младшие 12 бит = 0 1e16 = 2386F26FC10000, 2e16 = 470DE4DF820000, 3e16 = 6A94D74F430000... младшие 16 бит = 0 Иными словами дес. числа большие (и кратные при этом) 1e(x) имеют как минимум x нулевых бит. Помере увеличения x конечно будет требоваться все больше и больше байт для сохранения одного числа из таблички, но никогда оно не достигнет 32 байт. Соответственно размер таблички у нас будет существенно меньше 780*32 (25Kb), а все операции сложения также будут проводится над меньшими по разядности числами (т.е. меньше 2500 сложений на 78 значное дес. число).
Громоздковато получается. Это если допустим 100-значное число, получается 5150 умножений на 10, а каждое умножение включает один сдвиг и два сложения. cresta У меня байтовый массив. Лучше я сдвиг сделаю через промежуточное слово. alpet Забыл поделить на 8 Про нулевые биты я чёт не понял к чему это? В принципе сократить табличку можно урезав разрядность чисел меньшего диапазона, но при этом нужно будет задавать с какого элемента он расширяется.
LZNT1 С умножениями несколько проще - ненадо табличку изначально генерить, да и алгоритм настолько просто, что хоть сразу в асме пиши. А сложность у него несколько другая - сколько знаков в числе, столько и умножений. Вот примерный алгоритм с умножениями: Код (Text): char bdig [] = "1234567891284381627175239549165324123647123"; int l = strleng (bdig); char bin [32]; // 256 bit digit memset (bin, 32, 0); // = 0 bin [0] = bdig [0] - 0x30; // set first for (int i = 1; i < l; i ++)} { L256MUL10 (bin); // multiple 10 L256ADD (bin, bdig [i] - 0x30); // add digit } Табличку очень сильно можно урезать, наверное даже до 10Кб - считай первые числа 2 и 4 байта, а последние будут порядка 20 байт.
alpet А почему всего 20? А остальные 12 как? Наверное всё таки сложениями быстрее будет. Меньше вычислений.
Уменьшить таблицу можно, используя только 1,2,4,8 на декаду. Правда, за счёт некоторого усложнения алгоритма. Что в этом массиве? Исходная строка или конечный результат? Пока тут в аттаче преобразование строки в 256 битное число. Тестировал на правильность на разрядности 64 бита, нормально. По идее и дальше будет работать, т.к. переход между двордами отработал нормально. При длине строки 78 символов время получил 18000 тактов. Первый проход (с загрузкой в кэш кода) - 19000. Удастся ли если делать вариант с таблицей, уложиться в это время, чтобы подгрузить таблицу в кэш и выполнить код? _274607943__str_to_256bit.inc
cresta Конечный результат у меня в байтовом массиве. Только байты могут быть беззнаковыми, остальные типы вызывают переполнение. Усложнять алгоритм наверное не нужно. Нужно просто при загрузке таблицы а память расширять сжатые значения до 32-х байт. С таблицей таки быстрее будет. Всего одна операция на порядок. Ведь каждое число есть в таблице. Например 951. Берём из таблицы значения для 900,50 и 1, а затем складываем их вместе.
совсем не факт. А с таблицей такого размера - думаю, наверняка медленнее будет. Хотя это надо мерять. Делать вариант с таблицей и сравнивать. То, что просто сложение (вернее не просто, а с учётом переноса) - это понятно. Я и сам по возможности использую таблицы, но что-то мне подсказывает, что в данном случае таблица - не лучший вариант. Если это преобразование строки будет делаться в цикле многократно (десятки и сотни раз), причем непрерывно, то тогда есть смысл потратить время на то, чтобы сделать таблицу и подгрузить в кэш. Если преобразование будет выполняться периодически (однократно), потери времени на таблицу могут оказаться непомерно высокими. Да и пока не видно, что такого можно сэкономить за счет таблицы. О скорости: данные (как строку, так и принимающий число буфер) желательно выравнять на 16. Я как всегда, об этом забыл Сейчас подравнял буфера на 16 и получил для процедуры в аттаче почти в 2 раза быстрее: 78-символьная строка обрабатывается за 10400 тактов (первый проход - 12000). Как будешь использовать конечный массив - дело твоё, хочешь как байтовый, а то, как он формируется, никак не скажется на том, как его потом использовать. Если конечно не на VB его формировать, а так как предлагается - на асме. Судя по тому, что остальные типы будут вызывать переполнение, использоваться будет в VB?
Приготовил приблизительный вариант с табличкой (не упакованной пока). Результат сначала напугал - 11200 тиков, но потом перекомпилил в релиз (обертка то HLL) - стало нормально - 6000 тиков на строку из 78 символов. Ну естно пример еще можно оптимизировать, переписав целиком на асм. _1005411386__fscan2.zip
cresta В VB есть аналоги ADC и RCL? Что-то я плохо себе представляю без этих операций быструю функцию...
alpet К сожалению, сравнить не получилось Исходник твой у меня не компилится, по причине #include "stdafx.h". Перенес все функции, структуры и переменные в другой свой исходник, скомпилил нормально, но при попытке преобразовать строку в число прога молча вылетает Я вот один момент не пойму: чего ты постоянно GetTickCount'ом пользуешь . Тот коэффициент, на который делится полученное от неё значение, никак не дает количества тактов. Пока немного доработал свой код, заменив rcl mem32,1 на mov reg32,mem32 rcl reg32,1 mov mem32,reg32 В тактах получается 8800. Если мерять GetTickCount'ом, то на 100000 вызовов функции преобразования строки уходит 470-500 мс. Насколько я знаю, в VB аналогов ADC и RCL, позволяющих учитывать перенос, нет. Только по ошибке переполнения реагировать через обработчик ошибок, но это медленно.
