0

問題: 「大きな整数は (小さな) 整数のリストとして表されます。」

次があるとします。

type reg = string;;   (* "$0" models register set to constant 0 *)
type label = string;; (* empty string models no label *)

type asmistr =
   AsmHalt
 | AsmNop
 | AsmAdd of reg * reg * reg
 | AsmAddi of reg * int * reg
 | AsmSub of reg * reg * reg
 | AsmMul of reg * reg * reg
 | AsmLoad of reg * reg * reg
 | AsmStore of reg * reg * reg
 | AsmJmp of label
 | AsmBne of reg * reg * label
 | AsmBeq of reg * reg * label
 | AsmSlt of reg * reg * reg
;;

type asmprog = AsmProg of (label * asmistr) list;;

type asmline = 
    AsmIstr of label * asmistr 
  | AsmComment of string 
  | AsmDebugReg of reg 
  | AsmDebugMem of int * int
;;

この一連の定義は、レジスタ、命令、およびラベル (ジャンプで使用) を使用して、アセンブリのような言語を定義するために使用されます。

次に、命令型言語 (「while」「if」などの命令を含む) から ASM へのコンパイラを実装する必要があります。

私の先生が提案した実装は、11000 が [1, 1, 0, 0, 0] のように、各要素が指定された数字の数字 (数字は整数のみ) であるリストを使用することです。

最初のギャップは次のとおりです: 一般的な O'Caml プログラムを考慮して、これをどのように実装できますか? 大きな整数を挿入する必要があるとします。「計算」を許可するために使用できるロジックは何ですか? 最後に、ASM プログラムは add、sub mul、およびその他の大きな整数を含む可能性のある命令も実行できるため、レジスタ、大きな整数、および命令でこれを処理する方法がわかりません。

私が必要としているのは、おそらく O'Caml 言語で大きな整数を実装する方法と、アセンブリに似た言語 (この場合は ASM) を考慮してこれを実現する方法の一般的なスキームです。

事前に感謝します。明確でない場合は、私の英語で申し訳ありません。誰かが私を助けることができれば、必要に応じて詳細を追加します

4

2 に答える 2

1

あなたの質問に対する私の理解は次のとおりです。アセンブリする無限の整数を持つ単純な命令型言語をコンパイルする必要があり、コンパイラは OCaml で記述されます。そうですか？あなたの質問は、「無制限の整数の算術演算をどのようにコンパイルすればよいですか?」です。

それが実際に問題である場合、最初に OCaml でこれらの大きな数の演算を実装することをお勧めします ( のリストを使用します。各要素がorでintある必要はないことに注意してください。加算がオーバーフローしない、より大きな基数を使用できます)。あなたのネイティブな OCaml 整数、そしてそれは操作をより速くします)、そしてそれをネイティブアセンブリプログラムにどのように移植するのか疑問に思います. まず、どのようにリストをコンパイルしますか?01

于 2013-02-06T23:18:02.293 に答える
0

まず、数字には底があることを理解する必要があります。通常、人々は 10 進数 (基数 10) を使用しますが、プログラマーは 16 進数 (基数 16) とバイナリー (基数 2) も使用します。あなたの先生は正しいです (各要素が与えられた数字の数字であるリストを使用してください)。しかし、これらの数値が任意の基数であることに言及していない可能性があります。パフォーマンス/効率のために、おそらく基数 256 (各桁は 8 ビット整数)、または基数 65536 (各桁は 16 ビット整数)、基数 2^32、または基数 2^64 を使用する必要があります。選択は、基礎となるハードウェアが処理できると予想されるものに依存します (たとえば、コードが 16 ビット CPU で実行されることを意図している場合は、base 65536 を使用します)。

次に決定することは、数値の格納方法です。通常、桁数、いくつかのフラグ、および桁のリストを追跡する何かが必要です。フラグについては、数値が正か負かを示すフラグが 1 つ必要ですが、数値が無限大の場合、数値に桁落ちがある場合などには、より多くのフラグを使用できます。たとえば、"5/(- 6)" は、"桁数" がゼロの数値になる可能性があります。負のフラグと精度のフラグが設定されています。

これが決定されたら、正の数の加算を実装する必要があります。これはほとんどの場合、キャリーを使用して数字を追加するだけであり、結果は最大のソース番号よりも (最大で) 1 桁多い場合があります。たとえば、2 桁の数字と 4 桁の数字を加算する場合、5 桁の結果用にメモリを割り当ててから、次のような方法で 1 つずつ数字を追加します。

for(n = 0; n < result_digits; n++) {
    digit = source1[n] + source2[n] + carry;
        if(digit > DIGIT_MAX) {
            carry = 1;
            digit &= DIGIT_MASK;
        } else {
            carry = 0;
        }
        result[n] = digit;
    }
}

次のステップは、より大きな正の数からより小さな正の数の減算を処理するコードを作成することです。これは、最上位の桁から始めて、キャリーを使用してある桁から別の桁を減算するだけです。これが機能したら、小さな正の数から大きな正の数の減算を処理するように拡張します。これには、事前に数値を交換し、後で結果を否定することが含まれます。たとえば、「3 - 10 = -( 10 - 3)」です。

正の数の加算と減算が機能したら、負の数のサポートに取り掛かることができます。これはほとんどの場合、符号フラグをいじって、加算するか減算するかを選択するだけです。たとえば、「8 + (-3) = 8 - 3」の場合、「8 - (-3) = 8 + 3」、「-8 + 3 = 3 - 8」、「-8 + -3 = -( 8 + 3)」など。すべての場合において、正の数の加算または減算として再配置および実行できます。

次のステップは、正の数の乗算です。これは、各桁を乗算し、前の桁からのオーバーフローを追加するだけです。

for(n = 0; n < result_digits; n++) {
    digit = source1[n] * source2[n] + temp;
    temp = digit >> DIGIT_BITS;
    digit &= DIGIT_MASK;
    result[n] = digit;
}

次に、負の数の乗算について心配します。ここでは、元の数値を正にして正の数値の乗算を行い、その後結果の符号を設定します。

于 2013-02-07T03:51:26.310 に答える