Реализации алгоритмов/Решето Сундарама: различия между версиями
Содержимое удалено Содержимое добавлено
К.Королев (обсуждение | вклад) |
К.Королев (обсуждение | вклад) |
||
Строка 12:
i <sub>m n</sub> = 2mn + m + n , m, n - натуральные (1)
используется как решето простых чисел по принципу «как есть» и это соотношение действительно есть готовый оператор для любого языка программирования высокого уровня. Однако, если рассматривать это соотношение как симметричную матрицу, то решето можно реализовать более эффективно. Но сначала обратимся ко 2-му тому культовой монографии Д.Кнута «Искусство программирования», точнее, к упр.8 раздела 4.5.4. «Разложение на простые множители». В упражнении предлагается найти алгоритм высеивания, использующий только операции сложения и вычитания, а в ответе на него приведены соотношения, непосредственно вытекающие из (1): в оригинальных обозначениях монографии это p = 2j + 1 и q = 2j + 2j<sup>2</sup> соответственно. Сам же Д.Кнут происхождение этих выражений не объясняет, возможно, по причине весьма скромного рейтинга упражнения (задача на 15 – 20 минут), которое имеет, хотя тематически и не совсем логичное, продолжение в упражнении 15 раздела 5.2.3
3-го тома. Приведенное в ответе, цитата, «решение несколько замысловато: в нем пропускаются все числа, кратные 3». Решение предложено Б.Чартресом. Однако, используя (1), можно построить более простой и эффективный алгоритм, пропускающий все числа, кратные 3. Вернее, с точки зрения матрицы (1), этот алгоритм пропускает все строки и столбцы матрицы, кратные 3-м. Приведем этот алгоритм, реализованный на ассемблере. Смысл используемых переменных следующий:
NOdd+1 – количество нечетных чисел, из которых надо отсеять составные;
Строка 41 ⟶ 42 :
; Отсеивание остальных чисел
@@NEXT:
mov eax,12-1
mov ecx,5 ; период второй строки
mov edx,10 ; для исключения столбца второй строки, «кратного» 3-ем
mov bl,2
;======= Движение по строке =======
; Из-за «переопределенности» (1) следующие пересылки выполняются
Строка 52 ⟶ 53 :
@@S1:
mov Byte Ptr Prime[eax],0 ; составное число
add
cmp eax,DWord Ptr NOdd
jnb
@@S2:
mov Byte Ptr Prime[eax],0 ; составное число
add
cmp eax, DWord Ptr NOdd
jb
@@S3:
ja
mov Byte Ptr Prime[eax],0 ; последнее число в строке составное
@@S4:
; ======= Переход к следующей строке =======
mov eax,edi
add
add
add
mov edx,ecx
shl
dec
jnz
; Исключение строки, «кратной» 3-ем
mov bl,2
add
add
add
mov edx,ecx
shl
cmp eax, DWord Ptr NOdd
jb
ja
jz
@@S5:
mov edi,eax
cmp eax, DWord Ptr NOdd
jb
ja
@@S6:
mov Byte Ptr Prime[eax],0 ; последнее нечетное число составное
| |||