64 bit / 64 bit remainder finding algorithm on a 32 bit processor?

Question

I know that similar questions has been asked in the past, but I have implemented after a long process the algorithm to find the quotient correctly using the division by repeated subtraction method. But I am not able to find out the remainder from this approach. Is there any quick and easy way for finding out remainder in 64bit/64bit division on 32bit processor. To be more precise I am trying to implement

ulldiv_t __aeabi_uldivmod(  
 unsigned long long n, unsigned long long d)  

Referenced in this document http://infocenter.arm.com/help/topic/com.arm.doc.ihi0043d/IHI0043D_rtabi.pdf

Purpurin

Doing division by repeated subtraction is very slow. Anyway if you have the quotient it's always easy to get a remainder a % b = a - (a/b)*b. The implementation will be similar to doing 128/128 bit division on 64-bit processor that you can find somewhere over here https://mcmap.net/q/590996/-unsigned-128-bit-division-on-64-bit-machine/995714 https://mcmap.net/q/833185/-fastest-way-to-calculate-a-128-bit-integer-modulo-a-64-bit-integer – Boffin

Answer 1

What? If you do repeated subtraction (which sounds really basic), then isn't it as simple as whatever you have left when you can't do another subtraction is the remainder?

At least that's the naïve intuitive way:

uint64_t simple_divmod(uint64_t n, uint64_t d)
{
  if (n == 0 || d == 0)
    return 0;
  uint64_t q = 0;
  while (n >= d)
  {
    ++q;
    n -= d;
  }
  return n;
}

Or am I missing the boat, here?

Of course this will be fantastically slow for large numbers, but this is repeated subtraction. I'm sure (even without looking!) there are more advanced algorithms.

Scarabaeus

Practical aspects, such as worst case execution time (even when ignoring the d==0 case)? – Ramie

Thanks a lot , I was overwhelmed by looking at repeated bit shifting required and getting the correct result. I am doing robustness and My input Numerator "18446744073709551615" and was not fitting to the calculator and its being rounded off as 18446744073709551611,my results were also going wrong because of this. This didn't cross my mind. – Purpurin

while (n >= d) is more correct, still unpractical implementation – Miliaria

Answer 2

This is a division algorithm, run in O(log(n/d))

uint64_t slow_division(uint64_t n, uint64_t d)
{
   uint64_t i = d;
   uint64_t q = 0;
   uint64_t r = n;
   while (n > i && (i >> 63) == 0) i <<= 1;
   while (i >= d) {
      q <<= 1;
      if (r >= i) { r -= i; q += 1; }
      i >>= 1;
   }
   // quotient is q, remainder is r 
   return q;    // return r 
}

q (quotient) can be removed if you need only r (remainder). You can implement each of the intermediate variables i,q,r as a pair of uint32_t, e.g. i_lo, i_hi, q_lo, q_hi ..... shift, add and subtract lo and hi are simple operations.

#define left_shift1 (a_hi, a_lo)          // a <<= 1    
{
    a_hi = (a_hi << 1) | (a_lo  >> 31)
    a_lo = (a_lo << 1) 
}

#define subtraction (a_hi, a_lo, b_hi, b_lo)    // a-= b    
{
    uint32_t t = a_lo
    a_lo -= b_lo
    t = (a_lo > t)        // borrow
    a_hi -= b_hi + t
}   

#define right_shift63 (a_hi, a_lo)      // a >> 63
{
   a_lo = a_hi >> 31;
   a_hi = 0;
}

and so on.

0 as divisor is still an unresolved challenge :-) .

Miliaria