Find the first number whose factorial is divisible by x?

Question

I am new to assembly coding if any silly mistakes please correct me.....

Given a number x, your task is to find first natural number i whose factorial is divisible by x.

• The number x will be stored in register %rax using the mov instruction.

• The final result should be stored in register %rdi.

• Assume x is chosen such that overflow does not occur.

My attempt:

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

Answer 1

Let's work on the question:

Given a number x, your task is to find first natural number i whose factorial is divisible by x.

That is, find n such that n! % x == 0.

If you split n! and x into their prime factors (e.g. like "60 = 2*2*3*5") you know the remainder will be zero when all the prime factors in x are also prime factors in n!; which means that n must be equal to or larger than the largest prime factor of x.

For a worst case, if x is a prime number (only one prime factor) then n will have to be equal to x. For example, if x is 61, then n will be 61. This is important because n! becomes large quickly and will overflow (e.g. 61! won't fit in 64 bits).

Fortunately; if n is larger than 2; n! is the same as (n-1)! * n; and ((n-1)! * n) % x is the same as ((n-1)! % x) * n) % x.

In other words; to make it work (to avoid overflows) you can do something like this (without every calculating n! itself):

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

Now...

Assume x is chosen such that overflow does not occur.

What does that actually mean?

If the person asking for the code assumed you'd be using the algorithm I've described; then it would probably mean that x will be less than the square root of 1 << 64); and therefore you will have overflows if you use a "more likely to overflow algorithm" (any algorithm that does calculate the value of n!) so you must use my algorithm (or find a better algorithm).

In any case; recursion is bad and unnecessary.