|
|
| Посл.отвђт | Сообщенiе |
|
|
Дата: Июл 4, 2004 07:37:11 · Поправил: The Svin Понадобилося сабж т.е. выстроить сабж в линейку 1, 1,1, 1,2,1 , 1,3,3,1 и т.д. Вот накидал рыбу. Кажется задачка интересная, так что можно пообсуждать, есть кажется много возможностей улучшения xchg eax,edi movri eax,1 movri ecx,3 rep stosd ; edi=B mov ebx,2 @outer: xor ecx,ecx inc ecx mov dword ptr [edi],1 mov eax,ebx shl eax,2 neg eax ;eax=-G*4 lea esi,[edi][eax][-4] ;esi=R @inner: mov eax,[esi][ecx*4] ;eax = R[i] add eax,[esi][ecx*4][4] ;eax =R[i]+R[i+1] mov [edi][ecx*4],eax ;B[i]=R[i]+R[i+1] inc ecx cmp ecx,ebx jne @inner mov dword ptr [edi][ecx*4],1 lea edi,[edi][ecx*4][4] inc ebx cmp ebx,33 ;на 33и диагонали можно больше если хочется. jne @outer Бляха муха. Ну как исправлять заголовки то?! |
|
|
Дата: Июл 4, 2004 11:38:49 Маленькое улучшение: shl eax,2 neg eax ;eax=-G*4 lea esi,[edi][eax][-4] ;esi=R Заменил на эквивалентный not eax lea esi,[edi][eax*4] |
|
|
Дата: Июл 4, 2004 12:18:29 Оформил процедурой и несколько незначительных улучшений. PascalD proc lpMemory,dCount pusha movri ecx,3 mov edi,lpMemory cmp edx,ecx ;count < 3? sbb eax,eax jc @r movri eax,1 rep stosd ; edi=B lea ebx,[ecx][2] ;ebx = 2 lea edx,[ecx][-2] ;edx = -2 @outer1: xor ecx,ecx inc ecx dec edx ;edx=-ebx-1 mov dword ptr [edi],ecx lea esi,[edi][edx*4] ;esi=R @inner2: mov eax,[esi][ecx*4] ;eax = R[i] add eax,[esi][ecx*4][4] ;eax =R[i]+R[i+1] mov [edi][ecx*4],eax ;B[i]=R[i]+R[i+1] inc ecx cmp ecx,ebx jne @inner2 mov dword ptr [edi][ecx*4],1 lea edi,[edi][ecx*4][4] inc ebx cmp ebx,dCount jne @outer1 @r: popa ret PascalD endp |
|
|
Дата: Июл 4, 2004 13:26:40 |
|
|
Дата: Июл 6, 2004 02:36:35 The Svin Тупизна моя не имент границ. Я для расширения кругозора пытаюсь просветиться (типа новый русский быдла и все такое), треугольник Паскаля - это, то что я пониаю?? 121 12421 1248421 Блин, я конечно не прав, но что пониаеться под диагоналями треугольника Паскаля. Я могу понять диагонали там паралелограма, трапеции и т.д. но диагонали треугольника мое школьное образование мне не объяснило, я кое-как могу понять медины, бессектрисы и высоты, но до диагоналей еще не допер. з.ы. прошу прощения, за орфографию, слегка не в себе, будет интересно если объясните............ |
|
|
Дата: Июл 6, 2004 03:42:43 Треугольник Паскаля: 11111 1234 136 14 1 И т.д. Жирным шрифтом я отобразил одну из диагоналей. В данном случае 4ую (считая с нулевой) Диагонали одно из самых интересных в треугольнике. Пример из бинарных вещей, допустим тебе хочется узнать сколько может быть n битных (разрядных) чисел в которых только х бит установлены в 1. Вот допустим интересно это про четырёх битные числа. Смотришь на 4ю выделенную диагоноль. 4х битных чисел в которых 0 единичных бит (ни одного единичного бита) - одно,1 единичный бит - 4е, 2а единичных бита - 6, 3 единичных бита - 4е, 4е единичных бита (все биты единичные) - одно. Это же ты можешь узнать про любое n разрядное число. Посмотри на энную диагональ. Пример из алгебры, допустим ты хочешь разложить на множетели (X+Y)n (т.е. биноминальное распределение) Опять тут тебе поможет n ая диагональ, допустим опять о четырёх (X+Y)4 Четвёртая диагональ у тебя 1,4,6,4,1 (X+Y)4= =1*X4+4X3Y+6X2Y2+4Y3X+1*Y4 Коэффициент 1 в 1*X4 я специально оставил чтобы показать соответсвие с диагональю его в обычной записью опускают и пишут просто X4 При вычислении искомого колличества n битных с x единичных бит тебе понадобалось бы очень тяжеловесная формула и трудно реализуемая как n!/(n-x)!(x)! Достаточно сказать что максимальный факториал вместимый в 32х битное число это факториал 12и. Представь что нужно делать для нахождения факториала 32х например, если формулу кодировать в прямом виде. Здесь же ты просто находишь n ую диагональ как сумму арифметической прогрессии до n (это всего лишь одно умножение и сдвиг)(это только если треугольник дан в таком компактном виде, можно расположить его в избыточность, тогда диагональ вообще быстрее находить) и смотришь x_ный элемент (вообще просто адресация по смещению, т.е. операция на адрес не требуется). Сама же процедура показывает найденное рекурентное решение когда диагонали заполняются обычными сложение двух найденных предыдущих (отношение не линейное! каким бы простым код не казался! просто найдено удачное решение по рассчёту адресов нужных элементов). |
|
|
Дата: Июл 6, 2004 04:14:14sbb eax,eax jc @r movri eax,1 Как за это меня BlackMirror не поймал с его любовью к отлеживанию CF и adc,sbb? :) можно смело сокращать на 2а байта: sbb eax,eax jc @r inc eax |
|
|
Дата: Июл 6, 2004 04:55:53 Диагональ - действительно некорректное обозначение в контексте треугольника. Но можно посмотреть на это с другой стороны: числа, формирующие треугольник являются прямоугольной матрицей, где недостающие члены - нули. И тогда числа, выделенные жирным, являются одной из диагоналей матрицы. |
|
|
Дата: Июл 6, 2004 06:02:31 · Поправил: The Svin Согласен. Но согласившись с критикой, прошу обратить внимание на факт что "треугольник Паскаля" тоже не треугольник в смысле геометрическом. |
|
|
Дата: Июл 6, 2004 06:14:42 Кстати, не могу не отметить, что сам термин диагональ, был использован самим Паскалем. Он делил (группировал) числа в своём треугольнике по "столбцам, строкам и диагоналям". В частности он писал в мерсеновской переписке, "сумма чисел по диагонали представляет собой два в степени номера строки". |
|
|
Дата: Июл 6, 2004 08:21:52 Другая импровизация на ту же тему, позволяет найти xный элемент n_ой диагонали но без заполнения треугольника Намного медленней, хотя избегает всё же вычислений факториалов на каждой стадии. CF если ошибка (x > n) xPosINnDiag proc x,n ;вставьте сохранение регистров если нужно mov ecx,n test ecx,ecx je @r1 cmp eax,x sbb eax,eax jc @r inc eax mov ebx,eax @@: mul ecx dec ecx div ebx inc ebx dec x jne @r @r: ret @r1: inc eax jmp @r xPosINnDiag endp |
|
|
Дата: Июл 6, 2004 08:23:36 · Поправил: Black_mirror Как за это меня BlackMirror не поймал с его любовью к отлеживанию CF и adc,sbb? :) можно смело сокращать на 2а байта: Смело можно сокращать в два раза: PascalD:;(lpMemory, dCount)
pusha
mov esi,[32+esp+4];lpMemory
mov edi,esi
jmp .l2
.l0:
lodsd
xchg eax,edx
add eax,edx
stosd
cmp esi,ebp
jb .l0
.l2:
xor edx,edx
xor eax,eax
inc eax
stosd
mov ebp,edi
dec dword [32+esp+8];dCount
jnz .l0
popa
ret |
|
|
Дата: Июл 6, 2004 08:39:33 Работает. Здорово. Изучаю. |
|
|
Дата: Июл 6, 2004 08:53:37xchg eax,edx add eax,edx Заменим на> xadd eax,edx? Размер тот же но быстрее по тестам. |
|
|
Дата: Июл 6, 2004 09:36:28 The Svin Поищи серию книг по полям Борисова(хотя за пределами Украины это будет проблематично). Они определяют бесконечные упорядоченные числовые ряды; доказывают многие биноминальные формулы, которые раньше давались как тождество; дают более общие формулы, из которых выводятся многие известные тождества. В первой книжке рассмотрена обобщенная формула биноминальных коэффициентов на примере теугольника Паскаля. |
|
Powered by miniBB 1.6 © 2001-2002
Время загрузки страницы (сек.): 0.056 |