除算演算子を持たないプロセッサでのアセンブリモーションアルゴリズム

Question

除算演算子を持たないプロセッサ（ARMと考える）に2つの数値のモジュロを求める簡単なマクロを実装する必要があります。私は除算を繰り返すことで除算を使用することができましたが、これが最も効果的か、最も簡単なものかどうかはわかりません。

提案がありますか？コードがさらに役立つでしょう。この特定のクラスでは、SPARCのサブセットを使用しているので、ほとんどの操作はadd r1, r2, rdestのようになります。

この特定の割り当てでは、a mod b == 0、または除算の残りの部分がゼロであることを確認する必要があります。だから、効率的な実装のためのヒントや提案は、大歓迎です。

Answer 1

あなたがに制限されている正確な操作はありませんアイデアは、私はあなたが長い間分裂、このような何か、擬似コードでやると思うだろう：実際に商（またはでを計算するには

dividend = abs(dividend) 
divisor = abs(divisor) 
if divisor == 0, 
    barf 
remainder = dividend 
next_multiple = divisor 

do 
    multiple = next_multiple 
    next_multiple = left_shift(multiple, 1) 
while next_multiple <= remainder && next_multiple > multiple 

while multiple >= divisor, 
    if multiple <= remainder, 
     remainder = remainder - multiple 
    multiple = right_shift(multiple, 1) 

を少なくとも絶対値）、最後の部分は次のようになります。

quotient = 0 
while multiple >= divisor, 
    quotient = left_shift(quotient, 1); 
    if multiple <= remainder, 
     remainder = remainder - multiple 
     quotient = quotient + 1 
    multiple = right_shift(multiple, 1) 

これはテストされておらず、おそらくエラーが発生しています。

Answer 2

Jweede、私はあなたの問題を解決する方法がわかりませんでしたが、一見関連性の高い投稿が見つかったhere。

Answer 3

私は考えられる2つのアプローチが考えられます。これは宿題ですので、私はちょうどそれらに言及し、それらが実現可能である場合は、操作できますし、それらを実装する方法：

1. A/B = 2 ^（LOG2（A）-log2（B））：もしあなた値の対数を取得することができます、あなたは密接に部門を近似することができます。

2. バイナリロングディビジョン：ディビジョンを行う前に小数点の長いディビジョンを行う方法を学んだ、そうですか？だからバイナリの長い分割を行うようにコンピュータを教えてください。

（編集：＃1を修正し、ログ分割式）を

Answer 4

これは直接あなたの質問に答えるが、それでも興味深いケースではありません。数が2のべき乗でmodulo'dされている場合の操作は通常は、1つのまたは2つのサイクル動作である、単一のAND演算を使用する

x % 2^n = x & (2^n - 1) 

ように行うことができます。

At Wikipedia

Answer 5

はあなたがヒットするかほぼ確実に、最も効率的ではないとはいえ簡単な実装になります0を越えるまで減算（または負の場合の追加）bでのように思えるの詳しい情報。

Answer 6

アドバイスありがとうございました！

これを実行するために繰り返し減算アルゴリズムによる単純除算を使い始めました。しかし、ysthによって指摘されているように、はるかに簡単な方法があります。ここで最初のアルゴリズムがあります：

 .macro mod a, b, r 
     mov a, r 
divlp: sub r, b, r 
     cmp r, b 
     bge divlp 
     .endmacro 

これは密接に似ている：

mod(a, b){ 
    int r = a 
    while(r >= b){ 
     r = r - b 
    } 
    return r 
} 

Answer 7

A/B = Q、したがって、A = Bの* Qを。 Q = 0 & Q = 1と バイナリ検索Q.スタートを、おそらくベースの例として：私たちはQ.

私の考えはミックスに追加したい、& Bの両方を知っています。 B * Q> Aになるまで倍増し、2つの境界（QとQ/2）を持っているので、それらの2つの間に正しいQを見つけてください。 O（（A/B）のログ）が、実装が少しトリッキー：

#include <stdio.h> 
#include <limits.h> 
#include <time.h> 

// Signs were too much work. 
// A helper for signs is easy from this func, too. 
unsigned int div(unsigned int n, unsigned int d) 
{ 
    unsigned int q_top, q_bottom, q_mid; 
    if(d == 0) 
    { 
     // Ouch 
     return 0; 
    } 

    q_top = 1; 
    while(q_top * d < n && q_top < (1 << ((sizeof(unsigned int) << 3) - 1))) 
    { 
     q_top <<= 1; 
    } 
    if(q_top * d < n) 
    { 
     q_bottom = q_top; 
     q_top = INT_MAX; 
    } 
    else if(q_top * d == n) 
    { 
     // Lucky. 
     return q_top; 
    } 
    else 
    { 
     q_bottom = q_top >> 1; 
    } 

    while(q_top != q_bottom) 
    { 
     q_mid = q_bottom + ((q_top - q_bottom) >> 1); 
     if(q_mid == q_bottom) 
      break; 

     if(d * q_mid == n) 
      return q_mid; 
     if(d * q_mid > n) 
      q_top = q_mid; 
     else 
      q_bottom = q_mid; 
    } 
    return q_bottom; 
} 

int single_test(int n, int d) 
{ 
    int a = div(n, d); 
    printf("Single test: %u/%u = %u\n", n, d, n/d); 
    printf(" --> %u\n", a); 
    printf(" --> %s\n", a == n/d ? "PASSED" : "\x1b[1;31mFAILED\x1b[0m"); 
} 

int main() 
{ 
    unsigned int checked = 0; 
    unsigned int n, d, a; 

    single_test(1389797028, 347449257); 
    single_test(887858028, 443929014); 
    single_test(15, 5); 
    single_test(16, 4); 
    single_test(17, 4); 
    single_test(0xFFFFFFFF, 1); 

    srand(time(NULL)); 

    while(1) 
    { 
     n = rand(); 
     d = rand(); 

     if(d == 0) 
      continue; 

     a = div(n, d); 
     if(n/d == a) 
      ++checked; 
     else 
     { 
      printf("\n"); 
      printf("DIVISION FAILED.\n"); 
      printf("%u/%u = %u, but we got %u.\n", n, d, n/d, a); 
     } 

     if((checked & 0xFFFF) == 0) 
     { 
      printf("\r\x1b[2K%u checked.", checked); 
      fflush(stdout); 
     } 
    } 

    return 0; 
} 

また、あなたはまた、B * Q < = Aがtrueの場合は1にそれぞれ1を設定し、ビットを反復処理することができ、ビットを1のままにしてください。それ以外の場合は0にしてください。 MSB→LSBを進めます。 （ただし、B * Qがオーバーフローすることを検出することができるようにする必要があります

Answer 8

MODが少しずつ計算することができます。あなたの残りの部分を与える

int r = 0; 
int q = 0; 
for (int i = sizeof(n) * 8 - 1; i >= 0; --i) { 
    r <<= 1; 
    r |= (n >> i) & 1; 
    if (r > d) { 
    r -= d; 
    q |= 1 << i; 
    } 
} 
return r; 

は、qは商だろう もしあなたがbsrl命令を持っていれば、最上位ビットから始めることができるので、より良い上限を設定することができます。