Посмотрим на начало нашей isprime:
mov ECX,[num] ;Проверяемое число
mov EAX,0 ;Флаг что число не простое
cmp ECX,2
jc .ret ;Числа меньше 2 все не простые
cmp ECX,4
jc .yes ;Числа 2 и 3 простые
test ECX,1
jz .ret ;Остальные чётные числа все не простые
cmp ECX,max_prime
jc .low ;Число меньше размера таблицы простых, возьмём бит простоты напрямую
Вот зачем здесь cmp ECX,4? Раз дальше будет проверка на чётность нам надо её обойти для числа 2, но сравнение с двойкой уже есть выше! Да, там стоит jc для 0 и 1, но ведь cmp выдаёт и флаг нуля (ZF), кто нам мешает его проверить и не сравнивать с 4? Никто. А что будет с тройкой? А она как нечётная меньшая размера таблицы возьмётся напрямую из последней. Да и 0 с 1 тоже можно не проверять командой jc .ret, им в таблице всё равно стоит 0 как не простым и можно смело лезть в таблицу. Больше ничего не изменится. Числа 0, 1, 3 будут проверяться на наносекунду (реально нс, не гипербола) дольше - да и пофиг.
mov ECX,[num] ;Проверяемое число
mov EAX,0 ;Флаг что число не простое
cmp ECX,2
je .yes ;Число 2 простое
test ECX,1
jz .ret ;Остальные чётные числа все не простые
cmp ECX,max_prime
jc .low ;Число меньше размера таблицы простых, возьмём бит простоты напрямую
Скорость замерять не буду, очевидно она не изменилась от одной команды.
Это пример что после одного сравнения можно уйти не только по ДА/НЕТ (истина/ложь), но и в большее количество путей. В каком-то языке (и процессоре) даже есть специальный оператор if с тремя альтернативами после сравнения: меньше, равно, больше. Не считая команду
ftst в FPU, она всё же не ветвится, лишь флаги выдаёт. А мы выходит легко можем двумя командами сделать тройное ветвление (три альтернативы). А можем и больше ... Если условия придумаем.
UPD. Вот ведь, так заоптимизировался что потерял пример. В этом абзаце речь про пару команд подряд после cmp ECX,2:
Первую из которых "оптимизировал" удалением.
А теперь вернёмся к главной программе и посмотрим на вот этот цикл подсчёта количества простых в ней:
mov EDX,EAX
mov ECX,0 ;Количество простых по указанное число
mov EBX,0 ;Текущее проверяемое число
.count: stdcall isprime, EBX ;Проверим на простоту
add ECX,EAX
inc EBX
cmp EBX,EDX
jbe .count
Зачем мы перебираем чётные? Мы же знаем что они все составные кроме 2. А ведь на каждое из них тратится время, вызов функции, штук 10 команд в ней, возврат, здесь вон 4 команды. Давайте начнём с числа 3, а двойку посчитаем "в уме", мы же уже отладили isprime, она двойку считает правильно:
mov EDX,EAX
mov ECX,1 ;Количество простых по указанное число
mov EBX,3 ;Текущее проверяемое число
.count: stdcall isprime, EBX ;Проверим на простоту
add ECX,EAX
add EBX,2
cmp EBX,EDX
jbe .count
Запускаем:
C:\>prog3.exe 100000000
5761455 primes up to 100000000
time: 75.334s
Количество правильное, но время, как так? Мы же ускоряли программу, куча команд (половина вызовов функции) перестала выполняться - и вдруг медленнее?! Ладно, пусть не вдвое быстрее (половину же чисел не проверяем), понятно что все чётные проверяются почти моментально и на общее время влияют не сильно, но чтобы вообще медленнее ...
А вот и так бывает. Честно скажу, понятия не имею почему медленнее. Обычно такие странности случаются из-за предсказателя переходов в процессоре, когда при изменении программы условные переходы становятся или более случайными, или какой-то переход перестаёт быть намного более вероятным (чаще срабатывает чем нет). Но здесь вроде бы ничего такого нет. А скорость падает. Незначительно, но ожидали то рост. Возможно это всего лишь такие флуктуации, но замерять точнее лень.
Потому так важны реальные тесты, практика нередко не сходится с теорией (видимо из-за недостаточного знания последней).
В последнем варианте одна мелкая засада:
C:\>for /l %n in (1,1,10) do @prog3.exe %n |find "up"
2 primes up to 1
2 primes up to 2
2 primes up to 3
2 primes up to 4
3 primes up to 5
3 primes up to 6
4 primes up to 7
4 primes up to 8
4 primes up to 9
4 primes up to 10
Первые две строки неправильные. Т.е. для не проверяемых 1 и 2. Можно "грубой силой" заставить показывать правильно, а можно вернуть проверку двойки (а до неё простых нет) и заодно ещё один финт:
mov EDX,EAX
mov ECX,0 ;Количество простых по указанное число
mov EBX,2 ;Текущее проверяемое число
cmp EDX,EBX
jb .disp1
.count: stdcall isprime, EBX ;Проверим на простоту
add ECX,EAX
inc EBX
jz .disp1
or EBX,1
cmp EBX,EDX
jbe .count
.disp1: cinvoke wsprintf, buf, .fmt3, ECX, EDX
Финт в команде or EBX,1 после увеличения EBX на 1. Как мы помним 0 в младшем бите только у чётных чисел, если после увеличения полчился ноль, т.е. чётное, то or уствновит младший бит в 1 и превратит число в нечётное на 1 больше. А если вдруг после увеличения младший бит уже 1, то 1 or 1 = 1 и ничего неправиьлного or не сделает. Т.е. числа будут перебираться только по нечётным за исключением самого первого, которое двойка.
Время практически то же. Тесты оставляю читателям.
Ещё здесь добавлен переход jz .disp1 - зачем? А вот предположим найдётся маньяк пожелавший узнать сколько таки простых по
, вот запустит он программу без этой команды с числом 4294967295 (0xFFFFFFFF), подождёт час, два, три, когда-нибудь inc EBX (с or или без, всё равно) досчитает до этого числа, cmp EBX,EDX выдаст флаг равенства, jbe пойдёт обратно на цикл, это число проверится isprime, снова дойдёт до inc EBX и выдаст ... 0! Ну или 1 с or. Команда cmp невозмутимо снова выдаст C=1, jbe обрадуется и снова на цикл. И снова, и снова ... до посинения.
Потому если уж зашли за границу чисел, то командой jz (напомню, inc не выдаёт флаг переноса CF который сюда просится вместе с jc) выйдем из замкнутого круга и покажем что насчитали до границы. Проверить оставляю желающим, мне дважды по несколько часов жаль.
На этом собственно про хитрости всё сказал что хотел и вспомнил.
Прежде чем переходить к тесту Ферма жду вопросов и предложений.
Например придумать какую-нибудь промежуточную по сложности программу между Фибоначчи и этим тестом на простоту выше. Для тренировки. Или освоиться с отладчиком. Или про отличия в x64 рассказать (но это удобно после теста Ферма, он хорошо ложится на числа до 2^64). Или рассказать об возможном ускорении написанной isprime заменой части делений на меньшее количество или вообще на умножения (причём это пригодится и в тесте Ферма). Или сунуться краем носа в модулярную арифметику (с расчётом выйти на поиск простых по паттерну). Или ещё что.
Думаю, может мне к более простому коду вернуться, к Фибоначчи и его посмотреть в отладчике.
да и основные структуры управления и данных должны знать, и по истории многих вопросов и так в курсе. Видел бы раньше - не стал бы так распинаться, может по другому что-то объяснил бы.