Far2, русский: F9, К, У, Del (меню -> Команды -> список hotplug-Устройств -> удалить). Как вариант, Alt+F1/F2 (выбор дисков) -> Shift+Del на нужном диске.
Теория чисел — большая наука, там фактов и теорем много… Про распределение простых чисел с картинками на русском хорошо написано здесь: ega-math.narod.ru/Liv/Zagier.htm.
Вы путаете области применимости алгоритмов: решето Эратосфена ищет все простые числа до некоторой границы, и именно эта задача обсуждается в посте; умные слова типа «псевдопростые числа» относятся к проблеме тестирования заданного числа на простоту.
Формулируйте чётче, в математике, равно как и в программировании, небольшое изменение слов может диаметрально изменить смысл и верность утверждения. Многочлен, выдающий в точности все простые числа, существует, с поправкой на то, что рассматривать нужно только положительные его значения; только такой многочлен зависит от 26 переменных.
«Для любого n можно найти такие C_1 и C_2, что ...» — это не нуждается в доказательстве. Чебышёв доказал, что можно найти такие C_1 и C_2, что для любого (достаточно большого) n выполнены неравенства C_1*n/log(n) < pi(n) < C_2*n/log(n) — почувствуйте разницу. Чебышёву не удалось доказать, что предел существует; это сделали уже после него с использованием тяжёлого матана ТФКП.
Поправка: указанная версия занимала целых 0D0h байт, но тем не менее на четверть ужать можно. Версия на 191 байт, правда, с использованием одной инструкции, появившейся в i386, и в которой спираль по умолчанию вращается: pastebin.com/eJSVzF5L
diff с файлом из поста:
7c7,8
< mov si, 100
---
> mov si, 0A000h
> mov es, si
8a10
> mov bp, 13 ; kruch
18,25c20
< push cx
<
< ; ??????? ES ????????? ?? ???????????
< mov ax, 0A000h
< mov es, ax
<
< mov bh, 0FAh ;mov bx, 320*200
< mov ax, si
---
> mov bh, 0FAh
27,43c22,27
<
< mov cx, 160
< lp2:
< ; ?????? ? DX ????? ??????? ?? K1
<
< pusha
< mul ax
< xchg ax, cx
< mul ax
< add ax, cx
< xor dx, dx
< mov bx, [kruch] ;mov bx, 40 ; K1 = 40
< div bx
< mov bx, sp
< mov word [bx+10], ax
< popa
<
---
> mov ax, bx
> xor dx, dx
> div word [_320+di-RRR]
> sub ax, 100
> sub dx, 160
>
49c33
< mov word [si], cx ; SIN
---
> mov word [si], dx ; SIN
52,55c36,45
< fimul word [vnum]
< fmul dword [glad]
< fist word [si]
< add dx, [si]
---
> fimul word [vnum+di-RRR]
> fmul dword [glad+di-RRR]
> fistp word [si]
>
> imul ax, ax
> imul dx, dx
> add ax, dx
> xor dx, dx
> div bp
> add ax, [si]
59,69c49,50
< mov byte [es:bx], dl
<
< dec cx
< cmp cx, -160
< jg lp2
<
< dec ax
< cmp al, -100
< jg lp1
<
< pop cx
---
> mov byte [es:bx], al
> jnz lp1
77c58
< add cl, ch ; [DELTA]
---
> add ch, cl ; [DELTA]
88,92d68
< cmp al, 0 ; was ah!!
< jl no_inv
< not ah
< no_inv:
<
94d69
< add al, cl ; + ??????
102a78
> add al, ch ; + ??????
108,109d83
< mov bx, di
< mov cx, 3
112c86
< and al, [bx]
---
> and al, [di+bx]
115c89
< loop mmm
---
> jnp mmm
118a93,94
> xor al, 0xFF
> js setColor
121,122d96
< sub al, cl ; - ??????
<
124c98
< jnz setPalette_loop
---
> jns setPalette_loop
138a113,126
> label_push_down:
> cmp al, 80
> jne label_push_up
> dec bp
> jnz paint_me
> inc_kruch_paint_me:
> inc bp
> paint_me:
> jmp paint
>
> label_push_up:
> cmp al, 72
> je inc_kruch_paint_me
>
142c130
< mov ch, 0
---
> mov cl, 0
147c135
< dec ch
---
> dec cx
151,164d138
< jne label_push_down
< inc ch
<
< label_push_down:
< cmp al, 80
< jne label_push_up
< dec [kruch]
< jnz paint_me
< inc [kruch]
< paint_me:
< jmp paint
<
< label_push_up:
< cmp al, 72
166,167c140
< inc [kruch]
< jmp paint
---
> inc cx
171,174c144,145
< jne label_push_G
< not byte [di]
<
< label_push_G:
---
> je change_color
> inc bx
176,179c147,148
< jne label_push_B
< not byte [di+1]
<
< label_push_B:
---
> je change_color
> inc bx
182c151,152
< not byte [di+2]
---
> change_color:
> not byte [di+bx]
184a155
> xor bx, bx
189c160
< jmp paint
---
> jmp paint_me
203c174
< kruch dw 13
---
> _320 dw 320
205c176
< sign db 'Dedicated to my wife 9'
\ No newline at end of file
---
> ;sign db 'Dedicated to my wife 9'
\ No newline at end of file
За вычетом сигнатуры получаем экономию в 234 — 191 = 43 байта.
В части изменений вы уже разобрались, дополнительно:
— есть свободный регистр bp, самую частую переменную выгоднее засунуть туда, тем более что команды inc/dec word [di] двухбайтовые, а новые inc/dec bp однобайтовые; после этой правки звание самой частой переменной восстанавливается за RRR, на которую и указывает di;
— двойной цикл по координатам точки (ax,cx) выгоднее заменить одним циклом по bx — тем более что это цикл до нуля, такие проще — а координаты восстанавливать делением;
— cl и ch выгоднее переставить, тогда вместо двухбайтовых inc/dec ch можно использовать однобайтовые inc/dec cx; в качестве побочного эффекта при этом спираль начинает вращаться при запуске;
— цикл длины 3 можно записать не только как убывающий по cx от 3 до 0, но и как возрастающий по bx от 0 до 3; нетипичные команды jp/jnp проверяют флаг чётности числа бит в младшем байте результата PF, который для 1 и 2 имеет одно значение, а для 3 — другое; поскольку bx=0 от цикла по точкам, это экономит на инициализации; popa благополучно восстанавливает bx=0;
— можно убрать отдельные действия для al>=0 и al<0 за счёт «цикла» длины 2 (действия) / xor al, 0xFF / js (начало);
— ветку с безусловным переходом назад jmp paint лучше переместить повыше, чтобы jmp стал коротким;
— три команды not byte [di+xxx] можно объединить в одну not byte [di+bx]; после неё надо не забыть сбросить bx.
Очевидно, вы никогда не пробовали на практике сравнивать по размеру ассемблерный и эквивалентный скомпилированный код. Компиляторы по скорости ещё могут сравниться с человеком, а по размеру откровенно сливают — тем более, что сегодня и задачи-то такой не ставится.
Наоборот, Вы использовали di для адресации RRR,GGG,BBB и si для адреса временной переменной сопроцессора. У меня все обращения к глобальным переменным идут через di, кроме одного mov [...],al, где это не имеет смысла, а сам di указывает на наиболее часто используемую переменную.
47,50c41,42 — это часть изменения: pusha / запись в сохранённую копию на стеке / popa / операция с ax и cx через временную переменную -> push ax cx / операция с сохранённой копией на стеке / pop cx ax.
Поправка: нужно ещё не забыть умножить на площадь большого квадрата S0, так что после подстановки s=S/S0 окончательная формула выглядит так:
InverseErf(0.995)*sqrt(S(S0-S)/N).
Считаем, что генератор случайных чисел идеален — точки равномерно распределены по квадратам и независимы друг от друга.
Пусть площадь фигуры S, площадь большого квадрата, в который бросаются точки, S0, и s = S/S0. С вероятностью s точка попадает внутрь фигуры, с вероятностью 1-s — вовне. Рассмотрим случайную величину, равную 1, если точка попала внутрь фигуры, и 0 иначе; по определению её матожидание равно s, а дисперсия s(1-s).
Пусть бросается N точек. Алгоритм выдаёт в качестве оценки площади среднее значение N независимых случайных величин, описанных в предыдущем абзаце. По центральной предельной теореме при больших N это среднее значение распределено примерно как нормальная случайная величина с матожиданием s и дисперсией s(1-s)/N.
Ясно, что поскольку алгоритм случайный, ему в принципе может фатально не повезти, если все точки случайно окажутся в странных местах, но такое событие исключительно маловероятно. Будем для определённости считать, что события с вероятностью <1% на практике не происходят; число, естественно, можно менять. По формуле вероятности для нормальной случайной величины при больших N отклонение результата, выданного алгоритмом, от правильного значения s по модулю не превосходит
InverseErf(0.995)*sqrt(s(1-s)/N)
в синтаксисе Mathematica, который можно использовать на wolframalpha.com; 0.995, потому что с вероятностью 0.005 отклонение будет больше по модулю и положительно и с вероятностью 0.005 отклонение будет больше по модулю и отрицательно — в сумме получается 1%, на который мы договорились забить. Учитывая, что InverseErf(0.995) примерно равно 2, это даёт возможную абсолютную погрешность метода.
Между прочим, нет ли в коде, помеченном "???", опечатки?
Весь код
push eax
push ebx
mov eax,[cur_task_num];в этой dword’овой переменной будем хранить номер тек. задачи
mov ebx,100h
mul ebx
pop ebx
mov edi,eax;EDI – начало TSS_struct
pop eax
Это некоторая путаница в терминах. Пусть h — хеш-функция. Есть разные задачи:
1. Поиск коллизий. Ищутся такие x,y, что h(x) = h(y).
2. Поиск прообраза. Дано a, ищется такое x, что h(x) = a.
3. Поиск второго прообраза. Дано a, ищется такое y, не равное a, что h(y) = h(a).
Из-за парадокса дней рождения сложность первой задачи для абстрактной хеш-функции пропорциональна квадратному корню из числа значений хеш-функции, что существенно проще остальных задач. Поэтому в первую очередь ищут коллизии, и именно для них построена табличка из поста. В комментариях речь идёт о поиске второго прообраза, и это значительно более сложная задача.
В криптографии слова «хеш-функция скомпрометирована» означают «для хотя бы одной задачи найдено решение существенно быстрее, чем в случае абстрактной хеш-функции». Отсюда отнюдь не следует, что есть решения других задач.
Да, всё правильно, в этих случаях mov'ом обойтись нельзя. Я ещё добавлю, что lea любят использовать в качестве длинных nop'ов, типа lea esi, [esi+0], что в 32-битном режиме имеет 2-, 3- и 6-байтную формы.
Не надо скромничать, написание этого поста само по себе доказывает знание ассемблера. У меня, по-видимому, просто опыта больше, а опыт — дело наживное.
Код вполне может быть на fasm или nasm, где offset нет. BareMetal, к слову, использует nasm. lea вообще имеет смысл только когда mov'ом обойтись нельзя. Выход по ret из COM-программ совершенно законен, 4C — это расширенный вариант, в нагрузку заполняющий код завершения программы.
тяжёлого матанаТФКП.diff с файлом из поста:
За вычетом сигнатуры получаем экономию в 234 — 191 = 43 байта.
В части изменений вы уже разобрались, дополнительно:
— есть свободный регистр bp, самую частую переменную выгоднее засунуть туда, тем более что команды inc/dec word [di] двухбайтовые, а новые inc/dec bp однобайтовые; после этой правки звание самой частой переменной восстанавливается за RRR, на которую и указывает di;
— двойной цикл по координатам точки (ax,cx) выгоднее заменить одним циклом по bx — тем более что это цикл до нуля, такие проще — а координаты восстанавливать делением;
— cl и ch выгоднее переставить, тогда вместо двухбайтовых inc/dec ch можно использовать однобайтовые inc/dec cx; в качестве побочного эффекта при этом спираль начинает вращаться при запуске;
— цикл длины 3 можно записать не только как убывающий по cx от 3 до 0, но и как возрастающий по bx от 0 до 3; нетипичные команды jp/jnp проверяют флаг чётности числа бит в младшем байте результата PF, который для 1 и 2 имеет одно значение, а для 3 — другое; поскольку bx=0 от цикла по точкам, это экономит на инициализации; popa благополучно восстанавливает bx=0;
— можно убрать отдельные действия для al>=0 и al<0 за счёт «цикла» длины 2 (действия) / xor al, 0xFF / js (начало);
— ветку с безусловным переходом назад jmp paint лучше переместить повыше, чтобы jmp стал коротким;
— три команды not byte [di+xxx] можно объединить в одну not byte [di+bx]; после неё надо не забыть сбросить bx.
47,50c41,42 — это часть изменения: pusha / запись в сохранённую копию на стеке / popa / операция с ax и cx через временную переменную -> push ax cx / операция с сохранённой копией на стеке / pop cx ax.
Код длинный, поэтому ссылка: pastebin.com/2CXf8EWJ
InverseErf(0.995)*sqrt(S(S0-S)/N).
Пусть площадь фигуры S, площадь большого квадрата, в который бросаются точки, S0, и s = S/S0. С вероятностью s точка попадает внутрь фигуры, с вероятностью 1-s — вовне. Рассмотрим случайную величину, равную 1, если точка попала внутрь фигуры, и 0 иначе; по определению её матожидание равно s, а дисперсия s(1-s).
Пусть бросается N точек. Алгоритм выдаёт в качестве оценки площади среднее значение N независимых случайных величин, описанных в предыдущем абзаце. По центральной предельной теореме при больших N это среднее значение распределено примерно как нормальная случайная величина с матожиданием s и дисперсией s(1-s)/N.
Ясно, что поскольку алгоритм случайный, ему в принципе может фатально не повезти, если все точки случайно окажутся в странных местах, но такое событие исключительно маловероятно. Будем для определённости считать, что события с вероятностью <1% на практике не происходят; число, естественно, можно менять. По формуле вероятности для нормальной случайной величины при больших N отклонение результата, выданного алгоритмом, от правильного значения s по модулю не превосходит
InverseErf(0.995)*sqrt(s(1-s)/N)
в синтаксисе Mathematica, который можно использовать на wolframalpha.com; 0.995, потому что с вероятностью 0.005 отклонение будет больше по модулю и положительно и с вероятностью 0.005 отклонение будет больше по модулю и отрицательно — в сумме получается 1%, на который мы договорились забить. Учитывая, что InverseErf(0.995) примерно равно 2, это даёт возможную абсолютную погрешность метода.
смотрится более естественно — разве что за исключением особой fasm'овской магии с virtual, — чем
Между прочим, нет ли в коде, помеченном "???", опечатки?
Весь код
можно заменить одной командой
но ещё лучше двумя
1. Поиск коллизий. Ищутся такие x,y, что h(x) = h(y).
2. Поиск прообраза. Дано a, ищется такое x, что h(x) = a.
3. Поиск второго прообраза. Дано a, ищется такое y, не равное a, что h(y) = h(a).
Из-за парадокса дней рождения сложность первой задачи для абстрактной хеш-функции пропорциональна квадратному корню из числа значений хеш-функции, что существенно проще остальных задач. Поэтому в первую очередь ищут коллизии, и именно для них построена табличка из поста. В комментариях речь идёт о поиске второго прообраза, и это значительно более сложная задача.
В криптографии слова «хеш-функция скомпрометирована» означают «для хотя бы одной задачи найдено решение существенно быстрее, чем в случае абстрактной хеш-функции». Отсюда отнюдь не следует, что есть решения других задач.