calgorithmarminteger-divisioneabi

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


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


Solution

  • 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.