在装配递归中求解Pascal的三角形(nCk) [英] Solving Pascal's Triangle (nCk) in Assembly Recursion
问题描述
我目前无法解决组合问题.我的基本情况很好.我认为问题在于评估组合(n-1，k)，然后评估组合(n-1，k-1).
i am currently stuck with getting the answer from a combination problem. My basecase works just fine. I think the problem is at evaluating combination(n-1,k) and then evaluating combination(n-1,k-1).
这是我的代码:n和k是来自用户的输入.
Here's my code: n and k are inputs from user.
sub esp, 2
push word[n]
push word[k]
call combi
pop word[ans] ;store yung combi value sa ans
;convert to ascii string value
add word[ans], 30h
;print answer
mov eax, 4
mov ebx, 1
mov ecx, ans
mov edx, 2
int 80h
jmp exit
combi:
mov ebp, esp
mov ax, word[ebp+4] ;ax = k
cmp [ebp+6], ax ;if (n==k)
je basecase
cmp word[ebp+4],0 ;cmp k = 0
je basecase
;combi(n-1,k)
mov ax, [ebp+6] ; ax = n
mov bx, [ebp+4] ; bx = k
dec ax ;n-1
;execute again
sub esp, 2
push ax
push bx
call combi
pop cx ;stores to cx popped value combi(n-1,k)
mov ebp, esp ;update pointers
;combi(n-1,k-1)
push ax
dec bx
push bx
call combi
pop dx ;stores to dx popped value combi(n-1,k-1)
mov ebp, esp ;update pointers
add cx, dx ;combi(n-1,k) + combi(n-1,k-1)
mov word[ebp+8], cx
jmp combi_exit
basecase:
mov word[ebp+8], 1
combi_exit:
ret 4
希望您能给出满意的答复和出色的想法！谢谢！
Hoping for your kind responses and brilliant ideas! Thank you!
推荐答案
要解决递归问题，combi:的中间部分存在问题:
To fix your recursion, the middle part of combi: has a problem:
...
call combi
pop cx ;stores to cx popped value combi(n-1,k)
;* ^ this freed the allocated space for result
mov ebp, esp ;update pointers
;* not needed, as you will not use EBP right now, and next call destroys it
;combi(n-1,k-1)
push ax
;* ^ pushing first argument, but no stack space reserved for result
dec bx
push bx
call combi
...
要修复，您可以将该部分调整为:
To fix you can adjust that part to:
这对于2次以上的深度递归将无法正常工作，因为您没有按需保留寄存器，整个递归体系结构需要更多的注意，我首先会选择使用更简单的设计来重写它，而不是解决所有这些小问题.此修复"将至少停止段错误.
this will not work correctly for 2+ deep recursion, as you don't preserve registers as needed, the whole recursion architecture requires more care and I would opt simply to rewrite it with simpler design in the first place, than fixing all these minor problems. This "fix" will at least stop the segfaulting.
...
call combi
mov cx,[esp] ;stores to cx value combi(n-1,k)
;* ^ keeps the stack space reserved (not popping)
;combi(n-1,k-1)
push ax
...
当然还有另一个问题，即您的输出仅对一位数字正确，但仅搜索堆栈溢出和标记[x86 ]信息，在此不再赘述.
There's of course the other problem with your output being correct only for single digit numbers, but just search stack overflow and the tag [x86] info for those, not going to repeat it here.
顺便说一句，此IMO源自不幸的过于复杂的用法堆栈，您是否出于某些特殊原因而遵循这种复杂的调用约定?如何在寄存器中提供一些自定义的类似fastcall的参数和结果?它的性能也要好得多，但是对我个人而言，更容易跟踪事物并正确地处理堆栈.如果可以尝试，我可以稍后在此答案中添加我自己的变体.
BTW, this IMO stems from the unfortunate overcomplicated usage stack, do you have some particular reason why you follow such complex calling convention? How about some custom fastcall-like giving arguments and results in registers? It's also much more performant, but for me personally it's also easier to keep track of things and process stack correctly. I may add my own variant later to this answer, if I will try...
具有注册调用约定的完整工作示例:
full working example with register calling convention:
文件: so_32b_pascal_triangle.asm
file: so_32b_pascal_triangle.asm
section .text
global _start
_start:
mov ecx,5 ; n
mov edx,2 ; k
call combi
; return to linux with sys_exit(result)
mov ebx,eax
mov eax,1
int 80h
; ECX = n, EDX = k, returns result in EAX, no other register modified
; (_msfastcall-like convention, but extended to preserve ECX+EDX)
combi: ; c(n, k) = c(n-1, k-1) + c(n-1, k), c(i, 0) = c(i, i) = 1
test edx,edx ; k == 0
je .basecases ; c(i, 0) = 1
cmp edx,ecx ; k == n
je .basecases ; c(i, i) = 1
; 0 < k < n case:
dec ecx ; n-1
call combi ; EAX = c(n-1, k)
push esi
mov esi,eax ; keep c(n-1, k) in ESI
dec edx ; k-1
call combi ; EAX = c(n-1, k-1)
add eax,esi ; EAX = c(n-1, k-1) + c(n-1, k)
; restore all modified registers
pop esi
inc ecx
inc edx
ret ; return result in EAX
.basecases:
mov eax,1
ret
编译+运行+结果显示:
...$ nasm -f elf32 -F dwarf -g so_32b_pascal_triangle.asm -l so_32b_pascal_triangle.lst -w+all
...$ ld -m elf_i386 -o so_32b_pascal_triangle so_32b_pascal_triangle.o
...$ ./so_32b_pascal_triangle ; echo $?
10
...$
出于好奇，尝试从C-ish C ++代码中调用它(以验证fastcall约定是否按预期工作，即使需要与C/C ++互操作性也是如此):
And for my own curiosity, tried to call it from C-ish C++ code (to verify the fastcall convention is working as expected even when interoperability with C/C++ is required):
so_32b_pascal_triangle.asm文件具有相同的combi:代码，但开始位置已修改(添加了全局内容，已删除_start):
The so_32b_pascal_triangle.asm file has same combi: code, but the beginning is modified (added global, removed _start):
section .text
global combi
; ECX = n, EDX = k, returns result in EAX, no other register modified
; (fastcall-like convention, but extended to preserve ECX+EDX)
combi: ; c(n, k) = c(n-1, k-1) + c(n-1, k), c(i, 0) = c(i, i) = 1
...
文件so_32b_pascal_triangle_Cpp.cpp:
#include <cstdio>
#include <cstdint>
extern "C" __attribute__ ((fastcall)) uint32_t combi(uint32_t n, uint32_t k);
int main()
{
for (uint32_t n = 0; n < 10; ++n) {
printf("%*c", 1+2*(10-n), ' ');
for (uint32_t k = 0; k <= n; ++k) {
printf("%4d", combi(n, k));
// 4-char width formatting - works for 3 digit results max.
}
printf("\n");
}
}
构建+测试:
$ nasm -f elf32 -F dwarf -g so_32b_pascal_triangle.asm -l so_32b_pascal_triangle.lst -w+all
$ g++ -std=c++17 -c -m32 -O3 -Wall -Wpedantic -Wextra so_32b_pascal_triangle_Cpp.cpp
$ g++ -m32 so_32b_pascal_triangle*.o -o so_32b_pascal_triangle
$ ./so_32b_pascal_triangle
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
这篇关于在装配递归中求解Pascal的三角形(nCk)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
