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, либо автор находится на его уровне разумности.
От математики к машине: преобразуем функцию в машинный код