Перевести натуральное число в буквенный вид, используемый программами электронных таблиц для обозначения столбцов. То, есть, для натуральных чисел 1, 2,... 26, 27, 28,... 702, 703, 704,... программа должна возвращать A, B,... Z, AA, AB,... ZZ, AAA, AAB,... Программа должна правильно обрабатывать все положительные значения из диапазона unsigned dword. Эта задача чем-то похожа на вычисление записи числа в позиционной системе счисления. Но чем-то и отличается.
А по-моему, это - задача о переходе от десятичной системы счисления к двадцатишестиричной. Хмм.. почему нельзя удалить сообщение? Не учёл того, что если A=1, то AA=11... Но, тем не менее, задача именно такова, с небольшенькой поправкой.
Можно попробовать начать с этого, если работает правильно (0xFFFFFFFF='MWLQKWU'), то потом избавится от деления, переходов и т.д. Код (Text): ;========================================== buffer rb 8 ;========================================== mov eax,-1 ; unsigned dword mov edi,buffer+7 ;========================================== mov ecx,26 excel: xor edx,edx div ecx test edx,edx jnz @F add edx,ecx dec eax @@: dec edi add edx,64 mov byte [edi],dl test eax,eax jnz excel ;========================================== edi = offset 'MWLQKWU'
Что-то мне подсказывает, что не должно быть так просто видимо "правильное" решение будет вообще без цикла... пока переделал: в edi адрес начала буфера (22 байта с учётом cld) но здесь строка исскуственно разворачивается.. интересно бы это селать без стэка... Код (Text): ; mov edi, buffer ;========================================== cld push -'A' push 'Z'-'A'+1 pop ecx @@: dec eax xor edx,edx div ecx push edx test eax,eax jnz @b @@: pop eax add al,'A' stos byte [edi] jnz @b
Сократил ещё на байт. вообще cld imho можно и не делать... Код (Text): 00401010 . FC cld 00401011 . 6A BF push -41 00401013 . 6A 1A push 1A 00401015 . 59 pop ecx 00401016 . 48 dec eax 00401017 > 31D2 xor edx, edx 00401019 . F7F1 div ecx 0040101B . 52 push edx 0040101C . 48 dec eax 0040101D .^ 79 F8 jns 00401017 0040101F > 58 pop eax 00401020 . 04 41 add al, 41 00401022 . AA stos [byte edi] 00401023 .^ 75 FA jnz 0040101F
S_T_A_S_ Свиснул у тебя идею, сократилось ещё на пару тактов Код (Text): ;========================================== buffer rb 8 ;========================================== mov eax,0xFFFFFFFF mov edi,buffer+7 ;========================================== mov ecx,26 excel: dec eax xor edx,edx div ecx dec edi add edx,'A' mov byte [edi],dl test eax,eax jnz excel ;========================================== edi = offset 'MWLQKWU' В общем, из 40 тактов на PIII, 38 приходится на деление. Есть мысль повозится с делением на константу (26), у Уоррена есть соотв. глава, нужно только в ней разобратся
Похоже на тебя оказывают дурное влияние любители Фога . Нужно ли это оптимизировать по скорости? IMHO нет: - в условии задачи про это не сказано; - как много (в %) времени будет тратить програ на этот код? ну может где-то 0.05 % =) По поводу деления на константу (26) - на сайте лежит MagicNumber by The Svin Эта прога показывает вот что: Код (Text): MagicNumber = 2643056798 mov eax,X mov edx, MagicNumber mul edx SHR edx, 4 Но мне почему-то кажется, что задача не в этом - может нужно какой-нибудь хитрый логарифм посчитать ???
Значит надо делать с компромисом по скорости\размеру И вообще, в первую очередь, меня интересует не сделать задачу для кого-то одного, а научится для себя (и чтобы польза была всем) Классная вещь, но для беззнакового деления с остатком не подойдет? Интересно бы разобрать возможность деления на 26, например как это умножение Код (Text): eax = x lea ecx,[eax*8+eax] ; eax*9 lea ecx,[eax*8+ecx] ; eax*9 + eax*8 lea ecx,[eax*8+ecx] ; eax*9 + eax*8 + eax*8 add eax,ecx ; eax*9 + eax*8 + eax*8 + eax*1 eax = x*26
bogrus > Остаток есть - в eax и младших битах edx. Только он кратен magic number'у Быстрее вычитанием его вычислить - "быстрое" умножение на 26 уже есть Хотя думаю лучше будет imul А вот раздельть на 13 посредством кучи lea imho будет дольше чем обычный div - посмотри, сколько единичек в двоичном представлении числа 2643056798 :-(
Вычисление остатка от деления на 13 для uint32 при помощи маленькой таблички(в 104 байта) примерно за 11-12 тактов на атлоне: Код (Text): ;eax = eax mod 13 mod13: mov ebx,eax ;A*2^18+B < 2^32 and eax,3FFFFh ;B < 2^18 shr ebx,18 ;A < 2^14 add eax,40001h ;0 mod 13 > A sub eax,ebx ;A*2^18+B = B-A mod 13 mov ebx,eax ;A*2^10+B < 2^19 and eax,3FFh ;B < 2^10 shr ebx,10 ;A < 2^9 add eax,60Bh ;0 mod 13 > 3*A lea ebx,[ebx*3] ;3*A sub eax,ebx ;A*2^10+B = B-3*A mod 13 mov ebx,eax ;A*2^6+B < 2^12 and eax,3Fh ;B < 2^6 shr ebx,6 ;A <= 40 < 2^6 sub eax,ebx ;A*2^6+B = B-A mod 13, -40<=B-A<64 movzx eax,byte [.rest+eax];0 <= eax < 13 ret times 40 db (%+11) mod 13 label .rest byte times 64 db (%+12) mod 13 У кого есть идеи как избавиться от таблички?
NANO Мысль интересная, но 128/5 = 25.6, а не точно 26. Поэтому вблизи чисел кратных 26 (77,128,129,154,155 и т.д.) результат завышен на 1. Хотя можно дополнительно проверять знак остатка и прибавлять 26, пока он не станет > 0.
Мысль -заменять деления на умножения обратному числу. Подбор числителя и знаменателя дроби - решение уравнения k/2^n -1 =0, где к =1,3,5,9(ограничения наложенны на числитель и знаменатель для оптимального решения в коде) -для данного варианта. Понятно, что можно добиться большей точности если понизить эти ограничения, допустим искать решения- k0*k1/2^n -1 =0 -> lea eax, [...] ; eax=eax*k0 lea eax, [...] ; eax=eax*k1 sar eax, n; eax =eax/2^n или решения для k0*(k1+1)/2^n -1 =0 -> lea edx, [...]; edx=eax*k0 lea eax, [edx+k1*eax]; eax=k0*(k1+1) sar eax, n; eax =eax/2^n или для (k0*k1+1)/2^n -1 =0 -> lea edx, [...]; edx=eax*k0 lea eax, [eax+k1*edx]; eax=(k0*k1+1) sar eax, n; eax =eax/2^n ... проще говоря вариантов масса, можно перебрать все(програмно естественно), для поиска наиболее точного. т.е. можно и умножать(выше) на 26(и другие) и делить быстро потенциально -ВСЕГДА. Потери точности... лечимы(только не проверкой
http://www.hackersdelight.org/divcMore.pdf Наткнулся на доку по делению, есть примеры для таких констант 3,5,6,7,10,11,12,13,100,1000 (в русской версии Уоррена этих примеров нет) Код (Text): unsigned divu13(unsigned n) { unsigned q, r; q = (n>>1) + (n>>4); q = q + (q>>4) + (q>>5); q = q + (q>>12) + (q>>24); q = q >> 3; r = n - q*13; return q + ((r + 3) >> 4); // return q + (r > 12); } Только понял, что можно было сделать так (собрать все мысли воедино: Код (Text): ;========================================== buffer rb 8 ;========================================== mov eax,0xFFFFFFFF mov edi,buffer+7 ;========================================== excel: dec eax mov ecx,eax mov edx,2643056798 mul edx shr edx,4 mov eax,edx lea edx,[edx+2*edx] lea edx,[eax+4*edx] add edx,edx sub ecx,edx dec edi add ecx,'A' mov byte [edi],cl test edx,edx jnz excel ;========================================== edi = offset 'MWLQKWU'
