56772


## 前提と質問内容

（前提）3x3の正方行列の掛け算を行うプログラムをC言語で書き、  
[compiler explorer](https://gcc.godbolt.org/)というC言語のアセンブラ出力を確認できるページで  
x86-64 icc 19.0.1とMIPS gcc 5.4のアセンブリ言語に出力しました。

（質問）内側のループにおける代入文とフロー制御の命令回数と、プログラム全体の計算複雑度はC言語からアセンブリ言語に変換すると変わるのでしょうか。

## 現在の見解

C言語のプログラムでは、内側のループにおける代入文とフロー制御(C言語はプログラム上でプログラマーが行う必要がないのかもしれませんが）の命令数は

[code]

    C[i][j] += A[i][k]*B[k][j];
    
[/code]

の１回だと考えています。

またプログラム全体の計算複雑度はO(N^3)だと思います。

（現在の見解）内側のループにおける代入文とフロー制御は、アセンブリ言語の方が明確にアドレスなどを指定しないといけないので、命令数が増えると考えています。一方、プログラム全体の計算複雑度はどのように考えればいいのかアセンブリ言語を見てもわからず困っています。

内側のループにおける代入文とフロー制御について、  
例えばMIPSの場合、compiler explorerで

[code]

    C[i][j] += A[i][k]*B[k][j];
    
[/code]

と対応する以下の部分の命令数を数えれば「内側のループにおける代入文とフロー制御の命令回数」と言えるのでしょうか。

[code]

    lw $3,32($fp)
    nop
    move $2,$3
    sll $2,$2,1
    addu $2,$2,$3
    lw $3,36($fp)
    nop
    addu $2,$2,$3
    sll $2,$2,3
    addiu $3,$fp,32
    addu $2,$3,$2
    lwc1 $f2,164($2)
    nop
    lwc1 $f3,160($2)
    lw $3,32($fp)
    nop
    move $2,$3
    sll $2,$2,1
    addu $2,$2,$3
    lw $3,40($fp)
    nop
    addu $2,$2,$3
    sll $2,$2,3
    addiu $3,$fp,32
    addu $2,$3,$2
    lwc1 $f4,20($2)
    nop
    lwc1 $f5,16($2)
    lw $3,40($fp)
    nop
    move $2,$3
    sll $2,$2,1
    addu $2,$2,$3
    lw $3,36($fp)
    nop
    addu $2,$2,$3
    sll $2,$2,3
    addiu $3,$fp,32
    addu $2,$3,$2
    lwc1 $f0,92($2)
    nop
    lwc1 $f1,88($2)
    nop
    mul.d $f0,$f4,$f0
    add.d $f0,$f2,$f0
    lw $3,32($fp)
    nop
    move $2,$3
    sll $2,$2,1
    addu $2,$2,$3
    lw $3,36($fp)
    nop
    addu $2,$2,$3
    sll $2,$2,3
    addiu $3,$fp,32
    addu $2,$3,$2
    swc1 $f0,164($2)
    swc1 $f1,160($2)
    
[/code]

## 実行中のプログラム

x86-64 icc 19.0.1とMIPS gcc
5.4のアセンブリ言語に出力したプログラムも掲載しましたが、C言語と対応する部分を確認するには、以下のC言語のプログラムを[compiler
explorer](https://gcc.godbolt.org/)に貼り付けて変換いただく方がわかりやすいと思います。

C言語のプログラム

[code]

    #include<stdio.h>
    
    #define N 3
    int 
    main(int argc, char *argv[])
    {
        double A[N][N] = {
            {1.0, 3.0, 1.0},
            {3.0, 1.0, 3.0},
            {1.0, 1.0, 1.0}
        };
    
        double B[N][N] = {
            {6.0, 1.0, 0.0},
            {0.0, 1.0, 6.0},
            {0.0, 1.0, 1.0}
        };
    
        double C[N][N] = {
            {0.0, 0.0, 0.0},
            {0.0, 0.0, 0.0},
            {0.0, 0.0, 0.0}
        };
        int i, j, k;
    
        for(i=0; i<N; i++)
            for(j=0; j<N; j++)
                for(k=0; k<N; k++)
                    C[i][j] += A[i][k]*B[k][j];
    
        for(i=0; i<N; i++)
            for(j=0; j<N; j++)
                printf("C[%d][%d] = %f\n", i, j, C[i][j]);
    }
    
[/code]

MIPSのプログラム

[code]

    $LC2:
            .ascii  "C[%d][%d] = %f\012\000"
    $LC0:
            .word   1072693248
            .word   0
            .word   1074266112
            .word   0
            .word   1072693248
            .word   0
            .word   1074266112
            .word   0
            .word   1072693248
            .word   0
            .word   1074266112
            .word   0
            .word   1072693248
            .word   0
            .word   1072693248
            .word   0
            .word   1072693248
            .word   0
    $LC1:
            .word   1075314688
            .word   0
            .word   1072693248
            .word   0
            .word   0
            .word   0
            .word   0
            .word   0
            .word   1072693248
            .word   0
            .word   1075314688
            .word   0
            .word   0
            .word   0
            .word   1072693248
            .word   0
            .word   1072693248
            .word   0
    main:
            addiu   $sp,$sp,-272
            sw      $31,268($sp)
            sw      $fp,264($sp)
            move    $fp,$sp
            sw      $4,272($fp)
            sw      $5,276($fp)
            lui     $2,%hi($LC0)
            addiu   $3,$fp,48
            addiu   $2,$2,%lo($LC0)
            li      $4,72                 # 0x48
            move    $6,$4
            move    $5,$2
            move    $4,$3
            jal     memcpy
            nop
    
            lui     $2,%hi($LC1)
            addiu   $3,$fp,120
            addiu   $2,$2,%lo($LC1)
            li      $4,72                 # 0x48
            move    $6,$4
            move    $5,$2
            move    $4,$3
            jal     memcpy
            nop
    
            sw      $0,196($fp)
            sw      $0,192($fp)
            sw      $0,204($fp)
            sw      $0,200($fp)
            sw      $0,212($fp)
            sw      $0,208($fp)
            sw      $0,220($fp)
            sw      $0,216($fp)
            sw      $0,228($fp)
            sw      $0,224($fp)
            sw      $0,236($fp)
            sw      $0,232($fp)
            sw      $0,244($fp)
            sw      $0,240($fp)
            sw      $0,252($fp)
            sw      $0,248($fp)
            sw      $0,260($fp)
            sw      $0,256($fp)
            sw      $0,32($fp)
    $L7:
            lw      $2,32($fp)
            nop
            slt     $2,$2,3
            beq     $2,$0,$L2
            nop
    
            sw      $0,36($fp)
    $L6:
            lw      $2,36($fp)
            nop
            slt     $2,$2,3
            beq     $2,$0,$L3
            nop
    
            sw      $0,40($fp)
    $L5:
            lw      $2,40($fp)
            nop
            slt     $2,$2,3
            beq     $2,$0,$L4
            nop
    
            lw      $3,32($fp)
            nop
            move    $2,$3
            sll     $2,$2,1
            addu    $2,$2,$3
            lw      $3,36($fp)
            nop
            addu    $2,$2,$3
            sll     $2,$2,3
            addiu   $3,$fp,32
            addu    $2,$3,$2
            lwc1    $f2,164($2)
            nop
            lwc1    $f3,160($2)
            lw      $3,32($fp)
            nop
            move    $2,$3
            sll     $2,$2,1
            addu    $2,$2,$3
            lw      $3,40($fp)
            nop
            addu    $2,$2,$3
            sll     $2,$2,3
            addiu   $3,$fp,32
            addu    $2,$3,$2
            lwc1    $f4,20($2)
            nop
            lwc1    $f5,16($2)
            lw      $3,40($fp)
            nop
            move    $2,$3
            sll     $2,$2,1
            addu    $2,$2,$3
            lw      $3,36($fp)
            nop
            addu    $2,$2,$3
            sll     $2,$2,3
            addiu   $3,$fp,32
            addu    $2,$3,$2
            lwc1    $f0,92($2)
            nop
            lwc1    $f1,88($2)
            nop
            mul.d   $f0,$f4,$f0
            add.d   $f0,$f2,$f0
            lw      $3,32($fp)
            nop
            move    $2,$3
            sll     $2,$2,1
            addu    $2,$2,$3
            lw      $3,36($fp)
            nop
            addu    $2,$2,$3
            sll     $2,$2,3
            addiu   $3,$fp,32
            addu    $2,$3,$2
            swc1    $f0,164($2)
            swc1    $f1,160($2)
            lw      $2,40($fp)
            nop
            addiu   $2,$2,1
            sw      $2,40($fp)
            b       $L5
            nop
    
    $L4:
            lw      $2,36($fp)
            nop
            addiu   $2,$2,1
            sw      $2,36($fp)
            b       $L6
            nop
    
    $L3:
            lw      $2,32($fp)
            nop
            addiu   $2,$2,1
            sw      $2,32($fp)
            b       $L7
            nop
    
    $L2:
            sw      $0,32($fp)
    $L11:
            lw      $2,32($fp)
            nop
            slt     $2,$2,3
            beq     $2,$0,$L8
            nop
    
            sw      $0,36($fp)
    $L10:
            lw      $2,36($fp)
            nop
            slt     $2,$2,3
            beq     $2,$0,$L9
            nop
    
            lw      $3,32($fp)
            nop
            move    $2,$3
            sll     $2,$2,1
            addu    $2,$2,$3
            lw      $3,36($fp)
            nop
            addu    $2,$2,$3
            sll     $2,$2,3
            addiu   $3,$fp,32
            addu    $2,$3,$2
            lwc1    $f0,164($2)
            nop
            lwc1    $f1,160($2)
            nop
            swc1    $f0,20($sp)
            swc1    $f1,16($sp)
            lw      $6,36($fp)
            lw      $5,32($fp)
            lui     $2,%hi($LC2)
            addiu   $4,$2,%lo($LC2)
            jal     printf
            nop
    
            lw      $2,36($fp)
            nop
            addiu   $2,$2,1
            sw      $2,36($fp)
            b       $L10
            nop
    
    $L9:
            lw      $2,32($fp)
            nop
            addiu   $2,$2,1
            sw      $2,32($fp)
            b       $L11
            nop
    
    $L8:
            move    $2,$0
            move    $sp,$fp
            lw      $31,268($sp)
            lw      $fp,264($sp)
            addiu   $sp,$sp,272
            j       $31
            nop
    
[/code]

x86-64 のプログラム

[code]

    .L_2__STRING.0:
            .long   1680169795
            .long   1680169821
            .long   540876893
            .long   681509
    
    main:
            push      rbp                                           #7.1
            mov       rbp, rsp                                      #7.1
            sub       rsp, 256                                      #7.1
            mov       QWORD PTR [-8+rbp], rbx                       #7.1[spill]
            mov       DWORD PTR [-240+rbp], edi                     #7.1
            mov       QWORD PTR [-232+rbp], rsi                     #7.1
            lea       rax, QWORD PTR [-224+rbp]                     #8.17
            mov       edx, offset flat: A.136.0                     #8.17
            mov       ecx, 72                                       #8.17
            mov       rdi, rax                                      #8.17
            mov       rsi, rdx                                      #8.17
            mov       eax, ecx                                      #8.17
            shr       rcx, 2                                        #8.17
            rep   movsd                                             #8.17
            mov       ecx, eax                                      #8.17
            and       ecx, 3                                        #8.17
            rep   movsb                                             #8.17
            lea       rax, QWORD PTR [-152+rbp]                     #14.17
            mov       edx, offset flat: B.136.0                     #14.17
            mov       ecx, 72                                       #14.17
            mov       rdi, rax                                      #14.17
            mov       rsi, rdx                                      #14.17
            mov       eax, ecx                                      #14.17
            shr       rcx, 2                                        #14.17
            rep   movsd                                             #14.17
            mov       ecx, eax                                      #14.17
            and       ecx, 3                                        #14.17
            rep   movsb                                             #14.17
            lea       rax, QWORD PTR [-80+rbp]                      #20.17
            mov       edx, 0                                        #20.17
            mov       ecx, 72                                       #20.17
            mov       rdi, rax                                      #20.17
            mov       eax, edx                                      #20.17
            and       eax, 65535                                    #20.17
            mov       ah, al                                        #20.17
            mov       edx, eax                                      #20.17
            shl       eax, 16                                       #20.17
            or        eax, edx                                      #20.17
            mov       esi, ecx                                      #20.17
            shr       rcx, 2                                        #20.17
            rep   stosd                                             #20.17
            mov       ecx, esi                                      #20.17
            and       ecx, 3                                        #20.17
            rep   stosb                                             #20.17
            mov       DWORD PTR [-256+rbp], 0                       #27.6
    ..B1.5:                         # Preds ..B1.6 ..B1.4
            mov       eax, DWORD PTR [-256+rbp]                     #27.11
            cmp       eax, 3                                        #27.13
            jl        ..B1.7        # Prob 50%                      #27.13
            jmp       ..B1.13       # Prob 100%                     #27.13
    ..B1.6:                         # Preds ..B1.8
            mov       eax, 1                                        #27.16
            add       eax, DWORD PTR [-256+rbp]                     #27.16
            mov       DWORD PTR [-256+rbp], eax                     #27.16
            jmp       ..B1.5        # Prob 100%                     #27.16
    ..B1.7:                         # Preds ..B1.5
            mov       DWORD PTR [-252+rbp], 0                       #28.7
    ..B1.8:                         # Preds ..B1.9 ..B1.7
            mov       eax, DWORD PTR [-252+rbp]                     #28.12
            cmp       eax, 3                                        #28.14
            jl        ..B1.10       # Prob 50%                      #28.14
            jmp       ..B1.6        # Prob 100%                     #28.14
    ..B1.9:                         # Preds ..B1.11
            mov       eax, 1                                        #28.17
            add       eax, DWORD PTR [-252+rbp]                     #28.17
            mov       DWORD PTR [-252+rbp], eax                     #28.17
            jmp       ..B1.8        # Prob 100%                     #28.17
    ..B1.10:                        # Preds ..B1.8
            mov       DWORD PTR [-248+rbp], 0                       #29.8
    ..B1.11:                        # Preds ..B1.12 ..B1.10
            mov       eax, DWORD PTR [-248+rbp]                     #29.13
            cmp       eax, 3                                        #29.15
            jge       ..B1.9        # Prob 50%                      #29.15
            lea       rax, QWORD PTR [-80+rbp]                      #30.5
            mov       edx, DWORD PTR [-256+rbp]                     #30.7
            movsxd    rdx, edx                                      #30.5
            imul      rdx, rdx, 24                                  #30.5
            add       rax, rdx                                      #30.5
            mov       edx, DWORD PTR [-252+rbp]                     #30.10
            movsxd    rdx, edx                                      #30.5
            imul      rdx, rdx, 8                                   #30.5
            add       rax, rdx                                      #30.5
            lea       rdx, QWORD PTR [-224+rbp]                     #30.16
            mov       ecx, DWORD PTR [-256+rbp]                     #30.18
            movsxd    rcx, ecx                                      #30.16
            imul      rcx, rcx, 24                                  #30.16
            add       rdx, rcx                                      #30.16
            mov       ecx, DWORD PTR [-248+rbp]                     #30.21
            movsxd    rcx, ecx                                      #30.16
            imul      rcx, rcx, 8                                   #30.16
            add       rdx, rcx                                      #30.16
            movsd     xmm0, QWORD PTR [rdx]                         #30.16
            lea       rdx, QWORD PTR [-152+rbp]                     #30.24
            mov       ecx, DWORD PTR [-248+rbp]                     #30.26
            movsxd    rcx, ecx                                      #30.24
            imul      rcx, rcx, 24                                  #30.24
            add       rdx, rcx                                      #30.24
            mov       ecx, DWORD PTR [-252+rbp]                     #30.29
            movsxd    rcx, ecx                                      #30.24
            imul      rcx, rcx, 8                                   #30.24
            add       rdx, rcx                                      #30.24
            movsd     xmm1, QWORD PTR [rdx]                         #30.24
            mulsd     xmm0, xmm1                                    #30.24
            movsd     xmm1, QWORD PTR [rax]                         #30.5
            addsd     xmm1, xmm0                                    #30.5
            lea       rax, QWORD PTR [-80+rbp]                      #30.5
            mov       edx, DWORD PTR [-256+rbp]                     #30.7
            movsxd    rdx, edx                                      #30.5
            imul      rdx, rdx, 24                                  #30.5
            add       rax, rdx                                      #30.5
            mov       edx, DWORD PTR [-252+rbp]                     #30.10
            movsxd    rdx, edx                                      #30.5
            imul      rdx, rdx, 8                                   #30.5
            add       rax, rdx                                      #30.5
            movsd     QWORD PTR [rax], xmm1                         #30.5
            mov       eax, 1                                        #29.18
            add       eax, DWORD PTR [-248+rbp]                     #29.18
            mov       DWORD PTR [-248+rbp], eax                     #29.18
            jmp       ..B1.11       # Prob 100%                     #29.18
    ..B1.13:                        # Preds ..B1.5
            mov       DWORD PTR [-256+rbp], 0                       #32.6
    ..B1.14:                        # Preds ..B1.15 ..B1.13
            mov       eax, DWORD PTR [-256+rbp]                     #32.11
            cmp       eax, 3                                        #32.13
            jl        ..B1.16       # Prob 50%                      #32.13
            jmp       ..B1.20       # Prob 100%                     #32.13
    ..B1.15:                        # Preds ..B1.17
            mov       eax, 1                                        #32.16
            add       eax, DWORD PTR [-256+rbp]                     #32.16
            mov       DWORD PTR [-256+rbp], eax                     #32.16
            jmp       ..B1.14       # Prob 100%                     #32.16
    ..B1.16:                        # Preds ..B1.14
            mov       DWORD PTR [-252+rbp], 0                       #33.7
    ..B1.17:                        # Preds ..B1.18 ..B1.16
            mov       eax, DWORD PTR [-252+rbp]                     #33.12
            cmp       eax, 3                                        #33.14
            jl        ..B1.19       # Prob 50%                      #33.14
            jmp       ..B1.15       # Prob 100%                     #33.14
    ..B1.18:                        # Preds ..B1.23
            mov       eax, 1                                        #33.17
            add       eax, DWORD PTR [-252+rbp]                     #33.17
            mov       DWORD PTR [-252+rbp], eax                     #33.17
            jmp       ..B1.17       # Prob 100%                     #33.17
    ..B1.19:                        # Preds ..B1.17
            mov       eax, offset flat: .L_2__STRING.0              #34.4
            mov       edx, DWORD PTR [-256+rbp]                     #34.4
            mov       ecx, DWORD PTR [-252+rbp]                     #34.4
            lea       rbx, QWORD PTR [-80+rbp]                      #34.4
            mov       esi, DWORD PTR [-256+rbp]                     #34.4
            movsxd    rsi, esi                                      #34.4
            imul      rsi, rsi, 24                                  #34.4
            add       rbx, rsi                                      #34.4
            mov       esi, DWORD PTR [-252+rbp]                     #34.4
            movsxd    rsi, esi                                      #34.4
            imul      rsi, rsi, 8                                   #34.4
            add       rbx, rsi                                      #34.4
            movsd     xmm0, QWORD PTR [rbx]                         #34.4
            mov       rdi, rax                                      #34.4
            mov       esi, edx                                      #34.4
            mov       edx, ecx                                      #34.4
            mov       eax, 1                                        #34.4
            call      printf                                        #34.4
            mov       DWORD PTR [-244+rbp], eax                     #34.4
            jmp       ..B1.18       # Prob 100%                     #34.4
    ..B1.20:                        # Preds ..B1.14
            mov       eax, 0                                        #35.1
            mov       rbx, QWORD PTR [-8+rbp]                       #35.1[spill]
            leave                                                   #35.1
            ret                                                     #35.1
    A.136.0:
            .long   0x00000000,0x3ff00000
            .long   0x00000000,0x40080000
            .long   0x00000000,0x3ff00000
            .long   0x00000000,0x40080000
            .long   0x00000000,0x3ff00000
            .long   0x00000000,0x40080000
            .long   0x00000000,0x3ff00000
            .long   0x00000000,0x3ff00000
            .long   0x00000000,0x3ff00000
    B.136.0:
            .long   0x00000000,0x40180000
            .long   0x00000000,0x3ff00000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x3ff00000
            .long   0x00000000,0x40180000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x3ff00000
            .long   0x00000000,0x3ff00000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x00000000
            .long   0x00000000,0x00000000
    
[/code]


CC BY-SA 4.0
2019-07-20T07:04:12.210
56769
2019-07-20T08:51:30.990
2020-06-17T08:14:45.997
-1
question
c assembly 計算量
C言語からアセンブリ言語に書き出した時の計算量について


> （質問）内側のループにおける代入文とフロー制御の命令回数と、プログラム全体の計算複雑度はC言語からアセンブリ言語に変換すると変わるのでしょうか。

一般論として、あるアルゴリズムの実装言語を機械変換（例: C言語→アセンブリ言語へのコンパイル）しても、ビッグ・オー記法の計算複雑度は変化しません。

というよりも「計算複雑度」はアルゴリズムそれ自身から決まりますから、具体的な実装プログラミング言語には依存しないと解釈すべきです。

> またプログラム全体の計算複雑度はO(N^3)だと思います。

“C言語やアセンブリ言語で記述されたプログラム”の計算複雑度という表現がすでに不正確であり、  
“今はたまたまC言語やアセンブリ言語で記述している行列乗算アルゴリズム”の計算複雑度を議論すべきです。


CC BY-SA 4.0
2019-07-20T08:51:30.990
56772
2019-07-20T08:51:30.990
49
56769
answer