64-битный / 64-битный алгоритм поиска остатка на 32-битном процессоре?

Question

Я знаю, что подобные вопросы задавались в прошлом, но после долгого процесса я реализовал алгоритм правильного нахождения коэффициента, используя метод деления путем повторного вычитания. Но я не могу узнать остаток от этого подхода. Есть ли какой-нибудь быстрый и простой способ узнать остаток в 64-битном /64-битном делении на 32-битном процессоре. Если быть более точным, я пытаюсь реализовать

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

Ссылка в этом документе http://infocenter.arm.com/help/topic/com.arm.doc.ihi0043d/IHI0043D_rtabi.pdf

Answer 1

Какие? Если вы делаете повторное вычитание (что звучит по-настоящему просто), то разве это не так просто, как то, что вы оставили, когда вы не можете сделать другое вычитание, это остаток?

По крайней мере, это наивный интуитивный способ:

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;
}

Или я скучаю по лодке, здесь?

Конечно, это будет фантастически медленно для больших чисел, но это повторное вычитание. Я уверен (даже не глядя!) Есть более продвинутые алгоритмы.

Answer 2

Это алгоритм деления, запускаемый в 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 (частное) можно удалить, если вам нужно только r (остаток). Вы можете реализовать каждую из промежуточных переменных i, q, r как пару uint32_t, например, i_lo, i_hi, q_lo, q_hi..... shift, сложение и вычитание lo и hi - простые операции.

#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;
}

и так далее.

0 как делитель все еще остается нерешенной задачей:-) .