Найти первое число, факториал которого делится на х? - PullRequest
Новая
       104

Найти первое число, факториал которого делится на х?

0 голосов
/ 31 января 2020

Я новичок в ассемблерном кодировании, если какие-то глупые ошибки исправьте меня .....

Учитывая число x, ваша задача состоит в том, чтобы найти первое натуральное число i, факториал которого делится на x .

  • Число x будет сохранено в регистре% rax с помощью инструкции mov.

  • Окончательный результат должен быть сохранен в регистре% 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

1 Ответ

4 голосов
/ 31 января 2020

Давайте поработаем над вопросом:

Учитывая число 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);

Now ...

Предположим, что x выбран таким образом, чтобы переполнение не происходило.

Что это на самом деле означает?

Если человек, запрашивающий код, предполагал, что вы будете использовать алгоритм, который я описал; тогда это, вероятно, будет означать, что x будет меньше квадрата root из 1 << 64); и, следовательно, у вас будут переполнения, если вы будете использовать «алгоритм с большей вероятностью переполнения» (любой алгоритм, который вычисляет значение <code>n!), поэтому вы должны использовать мой алгоритм (или найти лучший алгоритм).

В любом слючае; рекурсия плохая и ненужная.

...