Comments 20
Затем вычитаем 1 из n. Таким образом, n будет возрастать на каждом прогоне цикла.
Боюсь, что если из n вычитать 1, n будет скорее уменьшаться, чем возрастать...
Нет, это общее названии категории языков программирования. Никаких обид или пренебрежений, никаких психологических мотивов. См. хотя бы тут: https://ru.m.wikipedia.org/wiki/Императивное_программирование
Для посчитать факториал не нужен не С ни Ассемблер ни Хаскель. Вы вполне можете посчитать его в тетрадке столбиком и осчастливить человечество таблицей значений факториала навсегда. Это не программирование!
Программирование это когда вам надо посчитать квадрат числа каждую микросекунду, а у вас нет инструкции умножения в Ассемблере.
Вы вполне можете посчитать его в тетрадке столбиком и осчастливить человечество таблицей значений факториала навсегда.
Смелое утверждение :) Хотя факториал определен на множестве натуральных чисел и хотя это множество счетно (т.н.алеф-нуль), но это множество, увы, бесконечно. Вы же не пользуетесь таблицами Брадиса, чтобы узнать синус или логарифм? Я, по крайней мере лет 40 этого не делаю и другие, сдается мне, тоже. Так с какой стати кому-то нужны таблицы факториалов, тем более, что их полнота невозможна физически? Рано или поздно кому-то понадобится факториал, которого в такой таблице нет
Так с какой стати кому-то нужны таблицы факториалов, тем более, что их полнота невозможна физически?
А вы не видите предела до которого приведенная функция будет работать на х86 архитектуре? Достаточно таблицы на 15 максимум до 20 значений!
Это так, но, ещё раз — это же просто простая демка к командам ассемблера, к примеру, написать на чистом асме функцию, которая посчитает и напечатает все цифры, скажем 1000! — тоже хорошее упражнение. На самом деле такие функции в продакшене или при реальных расчётах не пишет никто — есть же библиотеки, скажем в Матлабе я просто возьму Symbolic Math Toolbox, и там вроде вообще лимита нет (за исключением памяти компа).
Это же учебный пример. Ещё Фибоначчи берут иногда. Из таких вот маленьких кирпичиков как раз и складывается программирование. А Хаскель тут слегка избыточен, я согласен, просто автор оригинала (это перевод) судя по всему хорошо им владеет, а вот Си и Ассемблером чуть менее уверенно, судя по терминологии и опущенным важным деталям о механизме возврата из функции.
Соглашусь! И добавлю: нахождение НОД по методу Евклида тоже часто рассматривается как пример алгоритма
Мне, в конце 80-х, тоже тоже давали учебный пример про факториал посчитать, и вывести число в десятичном виде неограниченной длины (тоже конечно условно неограниченного, но с пределом который не так просто определить, хотя бы). Эта задача решается на компьютере, но тем же столбиком, как ни странно! И это по моему действительно погружает в проблемы программирования, в понимание применения базовых элементов для понимания программирования, таких как массивы, циклы, чем отличается машинное представление чисел от десятичного человеческого... А самое интересное, этот пример демонстрирует что ручные методы "в лоб" при использовании компьютера, зачастую, оказываются самыми эффективными.
Кажется с годами обучающие задачи несколько поизмельчали, что ли. Грустно это.
самый топ по обучению это плотная работа с текстом(редактирование, вставка, взятие текста, открыть/закрыть файл, и там число дробилок не меньше кстати ))
например текстовый буффер(сама структура его функции, и вторая его часть его рисование )
при желании углубления обучения, можно углубиться в формат текста(ttf например, тут можно познакомиться зачем нужна математика в текстовом буффере в полной мере)
просто факториал или 1 алгоритм это часть от стандарта, который предоставляет точность расчета, по началу это не интересно и не понятно зачем надо, а с текстом всё нагляднее
да и чтобы дойти до этих алгоритмов надо реализовывать всю математическую библиотеку(почитывая стандарт)
Для обучения ассемблера, кстати, могу смело порекомендовать Евро Ассемблер (euroassembler.eu). Это на самом деле офигенная, хотя и мало известная игрушка, причём написанная одним человеком из Чехии, который охотно отвечает на вопросы. Что удобно, это ассемблер и компоновщик в одном флаконе, написанный на себе самом.
Если хочется сделать минимальное консольное приложение под Windows для вычисления факториала, то кода будет всего ничего:
EUROASM AutoSegment=Yes, CPU=X64
fact PROGRAM Format=PE, Width=64, Model=Flat, ListMap=Yes, IconFile=, Entry=Start:
INCLUDE winscon.htm, winabi.htm, cpuext64.htm
Msg1 D "Enter Number:",0
Msg2 D "Factorial is ",0
Buffer DB 80 * B
Start: nop
StdOutput Msg1, Console=Yes
StdInput Buffer ; Input Number
LodD Buffer ; https://euroassembler.eu/maclib/cpuext64.htm#LodD (rax <- Num)
mov rbx, 1 ; Initialize result to 1
.loop:
imul rbx, rax ; Multiply rbx by rax
dec rax ; Decrement rax
cmp rax, 1 ; Check if rax <= 1
jg .loop ; If rax > 1, repeat loop
mov rax, rbx ; Move result to rax
StoD Buffer ; https://euroassembler.eu/maclib/cpuext64.htm#StoD (from rax)
StdOutput Msg2, Buffer, Console=Yes
TerminateProgram
ENDPROGRAM factЯ код чутка поправил, так как два перехода тут не нужны совершенно.
Ассемблируется командой
euroasm.exe fact.asmПоходу генерит листинг, в котором все ходы расписаны
| |EUROASM AutoSegment=Yes, CPU=X64
| |fact PROGRAM Format=PE, Width=64, Model=Flat, ListMap=Yes, IconFile=, Entry=Start:
|[.text] ::::Section changed.
|00000000: |
|00000000: |INCLUDE winscon.htm, winabi.htm, cpuext64.htm
|00000000: * INCLUDE "./maclib/winscon.htm"
|[.text] ::::Section changed.
|00000000: * INCLUDE "./maclib/winabi.htm"
|00000000: * INCLUDE "./maclib/cpuext64.htm"
|00000000: |
|[.data] ::::Section changed.
|00000000:456E746572204E75~|Msg1 D "Enter Number:",0
|0000000E:466163746F726961~|Msg2 D "Factorial is ",0
|[.bss] ::::Section changed.
|00000000:................~|Buffer DB 80 * B
|00000050: |
|[.text] ::::Section changed.
|00000000:90 |Start: nop
|00000001: | StdOutput Msg1, Console=Yes
|00000018: | StdInput Buffer ; Input Number
|0000002F: | LodD Buffer ; https://euroassembler.eu/maclib/cpuext64.htm#LodD (rax <- Num)
|0000003B: |
|0000003B:BB01000000 | mov rbx, 1 ; Initialize result to 1
|00000040: |.loop:
|00000040:480FAFD8 | imul rbx, rax ; Multiply rbx by rax
|00000044:48FFC8 | dec rax ; Decrement rax
|00000047:4883F801 | cmp rax, 1 ; Check if rax <= 1
|0000004B:7FF3 | jg .loop ; If rax > 1, repeat loop
|0000004D:4889D8 | mov rax, rbx ; Move result to rax
|00000050: |
|00000050: | StoD Buffer ; https://euroassembler.eu/maclib/cpuext64.htm#StoD
|0000005E: | StdOutput Msg2, Console=Yes
|00000075: | StdOutput Buffer, Console=Yes
|0000008C: | TerminateProgram
|0000009A: |
| |ENDPROGRAM fact
| **** ListMap "fact.exe",model=FLAT,groups=0,segments=5,entry=Start:,stack=
| [.text],FA=00000400h,VA=00401000h,size=00000479h=1145,width=64,align=0010h,purpose=CODE+LITERAL
| [.data],FA=00000A00h,VA=00402000h,size=0000001Ch=28,width=64,align=0010h,purpose=DATA
| [.bss],FA=00000C00h,VA=00403000h,size=00000050h=80,width=64,align=0010h,purpose=BSS
| [.idata],FA=00000C00h,VA=00404000h,size=00000173h=371,width=64,align=8,purpose=IMPORT+IAT
| [.reloc],FA=00000E00h,VA=00405000h,size=00000030h=48,width=32,align=4,purpose=BASERELOC
| **** ListGlobals "fact.exe",Global=0,Public=3,Extern=0,eXport=0,Import=8
| ExitProcess,[.idata]:0000016Ch,VA=0040416Ch,scope='I',lib="kernel32.dll"
| GetStdHandle,[.idata]:00000150h,VA=00404150h,scope='I',lib="kernel32.dll"
| LodD64@RT,[.text]:0000023Eh,VA=0040123Eh,scope='P'
| ReadConsoleA,[.idata]:00000165h,VA=00404165h,scope='I',lib="kernel32.dll"
| ReadConsoleW,[.idata]:0000015Eh,VA=0040415Eh,scope='I',lib="kernel32.dll"
| ReadFile,[.idata]:00000157h,VA=00404157h,scope='I',lib="kernel32.dll"
| Start,[.text]:00000000h,VA=00401000h,scope='P'
| StoD64@RT,[.text]:000002CDh,VA=004012CDh,scope='P'
| WriteConsoleA,[.idata]:00000142h,VA=00404142h,scope='I',lib="kernel32.dll"
| WriteConsoleW,[.idata]:00000149h,VA=00404149h,scope='I',lib="kernel32.dll"
| WriteFile,[.idata]:0000013Bh,VA=0040413Bh,scope='I',lib="kernel32.dll"
На выходе исполняемый файл в три с половиной килобайта и работает:
>fact.exe
Enter Number:6
Factorial is 720Умеет в AVX512, можно сделать DLL вместо консольного приложения. Использую время от времени для небольших набросков и тонкой настройки и бенчмаркинга узких мест в коде (после интрисиков). Эх, надо будет статью как-нибудь написать.
Из современных книжек могу порекомендовать Даниэль Куссвюрм — Профессиональное программирование на ассемблере x64 с расширениями AVX, AVX2 и AVX-512:
Либо, лучше последнее издание на английском. Она не идеальна, но основы там даны про регистры, стек и всё такое.
Я код чутка поправил, так как два перехода тут не нужны совершенно.
По моим смутным воспоминаниям оригинальная версия более удобна для блока предсказания переходов. Впрочем для учебного примера и небольшого числа итераций это не особенно важно. Да и сам блок предсказания переходов умнеет от поколения к поколению.
Да, разные конструкции могут быть более или менее удобнее для предсказателя переходов, но в данном случае код формально будет работать максимум до 20 итераций.
Впрочем давайте проверим навскидку, пофиг на переполнение, тут работы на десять минут:
EUROASM AutoSegment=Yes, CPU=X64
benchm PROGRAM Format=PE, Width=64, Model=Flat, ListMap=Yes, IconFile=, Entry=Start:
INCLUDE winscon.htm, winabi.htm, cpuext64.htm
Msg0 D "Two Loops Benchmark",13,10,0
Msg1 D "Single Branch Ticks: ",0
Msg2 D "; Dual Branch Ticks: ",0
Buffer DB 80 * B
N DQ 1_000_000_000 ; Amount of Iterations
StartBench %MACRO
cpuid ; force all previous instructions to complete (rax...rdx reset)
rdtsc ; read time stamp counter
mov edi, eax ; save EAX for later
mov esi, edx ; save EDX for later
%ENDMACRO StartBench
EndBench %MACRO
cpuid ; wait to complete before RDTSC
rdtsc ; read time stamp counter again
sub eax, edi ; subtract the most recent CPU ticks from the original CPU ticks
sbb edx, esi ; now, subtract with borrow
shl rax, 32
shrd rax, rdx, 32 ; ticks are in rax
%ENDMACRO EndBench
Start: nop
StdOutput Msg0, Console=Yes
; ======== Single Branch Test ========
StartBench
mov rbx, 1 ; Initialize result to 1
mov rax, [N] ; Amount of interations
.loop1:
imul rbx, rax ; Multiply rbx by rax
dec rax ; Decrement rax
cmp rax, 1 ; Check if rax <= 1
jg .loop1 ; If rax > 1, repeat loop
EndBench
StoD Buffer
StdOutput Msg1, Buffer, Console=Yes
; ======== Dual Branch Test ========
StartBench
mov rbx, 1
mov rax, [N]
.loop2:
cmp rax, 1
jle .done
imul rbx, rax
dec rax
jmp .loop2
.done:
EndBench
StoD Buffer
StdOutput Msg2, Buffer, Console=Yes
TerminateProgram
ENDPROGRAM benchmРезультат примерно такой:
>benchm.exe
Two Loops Benchmark
Single Branch Ticks: 1914967186; Dual Branch Ticks: 1894910657В общем да, небольшая разница есть, но почти гомеопатическая (если прогоны местами поменять, то тенденция та же, я проверил).
На самом деле тут можно от явного сравнения избавиться, так тоже будет работать, потому что декремент устанавливает флаг, который можно сразу использовать для условного перехода:
mov rbx, 1 ; Initialize result to 1
.loop1:
imul rbx, rax ; Multiply rbx by rax
dec rax ; Decrement rax
jnz .loop1 ; If rax > 1, repeat loop
mov rax, rbx ; Move result to rax
Однако в современных реалиях времена, когда перестановкой команд можно было улучшить конвейеризацию или там помочь предсказателю переходов постепенно канули в лету, в основном производительность вытягивается векторизацией и многоядерностью. Я в прошлом году положил довольно много времени на то, чтобы сделать рабочий пример, показывающий эффект предвыборки (ну тот что PREFETCH) на XEON камушке да так и не смог явно и уверенно это продемонстрировать.
Думаю, что в 2025 году учить систему команд Intel – пустая трата времени. Притом, что она сама по себе очень громоздкая и запутанная.
Определение факториала в математике имеет совершенно другой смысл (семантику), чем программа для вычисления факториала в машинном коде. Это становится явно заметным для невычислимых функций, а также для тождеств вида
Само по себе математическое определение не подразумевает никаких вычислений или даже их потенциальной возможности.
На этапе рассуждений о Хаскеле автор обходит это обстоятельство, незаметно подменяя определение функции
factorial n = product [1..n]её применением
factorial 5Либо эту статью написал LLM, либо автор находится на его уровне разумности.
От математики к машине: преобразуем функцию в машинный код