温馨提示:本文翻译自stackoverflow.com,查看原文请点击:assembly - Find the first number whose factorial is divisible by x?

assembly - 找出第一个因数可被x整除的数字吗?

发布于 2020-03-29 12:56:37

我是汇编代码的新手,如果有任何愚蠢的错误,请纠正我.....

给定数字x,您的任务是找到第一个自然数i,其阶乘数可被x整除。

  • 使用mov指令将数字x存储在寄存器%rax中。

  • 最终结果应存储在寄存器%rdi中。

  • 假设选择x不会发生溢出。

我的尝试:

factorial:  

    pushq %rbp
    movq %rsp, %rbp 
    cmpq $1, %rdi   
    je if           
    jmp else

if:

    movq $1, %rax
    jmp factend

else:

    pushq %rdi      
    subq $1,%rdi    

    call factorial  
    popq %rdi       
    mulq %rdi      

    jmp factend      

factend:

    movq %rbp, %rsp
    popq %rbp
    ret

查看更多

查看更多

提问者
cool_dude_69
被浏览
46
Brendan 2020-01-31 16:52

让我们来研究这个问题:

给定数字x,您的任务是找到第一个自然数i,其阶乘数可被x整除。

也就是说,找到n这样n! % x == 0

如果拆分n!x为他们的主要因素(如像“60 = 2 * 2 * 3 * 5”)你知道,其余的将是零,当所有的主要因素,x也是首要因素n!; 这意味着n必须等于或大于的最大素数x

在最坏的情况下,如果x为素数(只有一个素数),则n必须等于x例如,如果x为61,n则将为61。这很重要,因为它n!很快变大并会溢出(例如,61!不能容纳64位)。

幸好; 如果n大于2;n!与相同(n-1)! * n; 并且((n-1)! * n) % x与相同((n-1)! % x) * n) % x

换一种说法; 为了使其工作(避免溢出),您可以执行以下操作(无需进行任何计算n!):

do {
  i = i + 1;
  remainder = remainder * i;
  remainder = remainder % x;
while(remainder != 0);

现在...

假设选择x不会发生溢出。

这实际上是什么意思?

如果询问代码的人认为您将使用我描述的算法;那么它可能意味着x将小于1 << 64的平方根);因此,如果您使用“更可能发生溢出的算法”(任何会计算的值的算法),那么就会产生溢出,n!因此必须使用我的算法(或找到更好的算法)。

任何状况之下; 递归是不好的,也是不必要的。

发布
问题

分享
好友

手机
浏览

扫码手机浏览