c言語で

Question

c言語初心者です、下記の条件を満たすプログラムの書き方がよくわからないのですがどのようにしたらいいのでしょうか？

１・倍精度浮動小数点数のn×n正方行列2つの積を計算するプログラム
２・計算時間は1秒以内
３・nをどこまで大きくできるかチャレンジ

n×n正方行列2つの積を計算するプログラム,計算時間は1秒以内
という条件は満たしているのですが、nをどこまで大きくできるかがうまくできません。

Answer 1

退会済のようですが・・・今時の環境で１秒に計算できる正方行列のサイズは１０万を超えると思います（以下のプログラムで１０００までは試しましたが時間が短すぎて計測できませんでした）。１０万だとdoubleが８バイトとして約２４０GBのメモリが必要です。環境依存と言えばそうなのですが・・・いまいち出題者の意図が分かりません。
(FreeBSD 10.3-RELEASE-p11 clang version 3.8.1)

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

#define MAXSIZ (10000)

void init(double m[MAXSIZ][MAXSIZ], int siz);
void mClear(double m[MAXSIZ][MAXSIZ], int siz);
void multiply(const double mA[MAXSIZ][MAXSIZ],const double mB[MAXSIZ][MAXSIZ],double mC[MAXSIZ][MAXSIZ],int siz);
void print(const double m[MAXSIZ][MAXSIZ], int siz);
//
double mA[MAXSIZ][MAXSIZ];
double mB[MAXSIZ][MAXSIZ];
double mC[MAXSIZ][MAXSIZ];
//
int main(int agc, char *agv[])
{
    if( agc != 2 ){
        fputs("Error agc!=2\n",stderr);
        exit(1);
    }
    //
    int matSiz= atoi(agv[1]);
    //
    if( matSiz < 1 || MAXSIZ < matSiz){
        fputs("Error matSiz\n",stderr);
        exit(2);
    }
    //
    init(mA,matSiz);
    init(mB,matSiz);
    mClear(mC,matSiz);
    //
    clock_t st= clock();
    multiply(mA, mB, mC, matSiz);
    clock_t et= clock();
    //
    print(mC,matSiz);
    printf("MatSiz= %d %f msec\n",matSiz, ((et-st)*1000.0)/CLOCKS_PER_SEC);
    //
    return 0;
}
//
void init(double m[MAXSIZ][MAXSIZ], int siz)
{
    for( int i= 0; i < siz; i++){
        for( int j= 0; j < siz; j++){
            m[i][j]= (double)rand()/(double)RAND_MAX;
        }
    }
}
//
void mClear(double m[MAXSIZ][MAXSIZ], int siz)
{
    for( int i= 0; i < siz; i++){
        for( int j= 0; j < siz; j++){
            m[i][j]= 0.0;
        }
    }
}
//
void multiply(const double mA[MAXSIZ][MAXSIZ],const double mB[MAXSIZ][MAXSIZ],double mC[MAXSIZ][MAXSIZ],int siz)
{
    for( int i= 0; i < siz; i++){
        for( int j= 0; j < siz; j++){
            for( int k= 0; k < siz; k++){
                mC[i][j] += mA[i][k]*mB[k][j];
            }
        }
    }
}
//
void print(const double m[MAXSIZ][MAXSIZ], int siz)
{
    for( int i= 0; i < siz; i++){
        for( int j= 0; j < siz; j++){
            printf("%2.4f ",m[i][j]);
        }
        putc('\n',stdout);
    }
}

Comments

[raccy]

mC[i][j]= mA[i][k]*mB[k][j];
は
mC[i][j]+= mA[i][k]*mB[k][j];
だと思います(その前にも0.0で初期化が要りますが)。Clangの最適化は恐ろしいほど優秀なので、for( int k= 0; k < siz; k++){...}の部分は最適化で最後のmC[i][j]= mA[i][siz-1]*mB[siz-1][j];しか計算されていないのでは無いかと思われます。

なお、手元(macOS)で同じような実装をした物で試したところ、GCC 6.2.0だと564個までしかできませんでした。でも、Clangだと6001個ぐらいと10倍以上も違う…。私のはVLAでスタックに積んだ実装なのでで、mallocでヒープに割り当てた場合も最適化のされ方が何か違ってきそうな気がします。

[cateye]

ご指摘ありがとうございます。ソース修正して差し替えました。１０万というのは私の思い違いでですね＾＾；・・・結果は以下の通り・・・私の環境では７００～８００のあたりにありそうです。
MatSiz= 500 382.812500 msec
MatSiz= 600 750.000000 msec
MatSiz= 700 898.437500 msec
MatSiz= 800 1359.375000 msec
　CPU：AMD　A10-6800K　4.1～4.4G

Answer 2

こんにちは。

推測ですが、nを#defineすることはできても、int n;にできなくて困っているのですよね?
であれば、malloc()で獲得すると良いです。1次元配列になりますが、2次元的にアクセスすることは可能です。

double* array=(double*)malloc(sizeof(array)*n*n);   // nxn個の領域を確保する

// とりあえず初期化
for (int i=0; i < n; ++i)
    for (int j=0; j < n; ++j)
        array[j*n+i]=0;   // array[i][j]と同等なアクセス

// 必要な処理はここへ

free(array);   // 開放を忘れずに

arrayは1次元なのでarray[i][j]とは書けません。
でも、array[j*n+i]ならば、n x n正方配列の(i, j)要素へアクセスしているのと同等です。

Answer 3

「n×n正方行列2つの積を計算するプログラム,計算時間は1秒以内」ができているというのであれば、まず、その部分を下記のような関数にします。@detailの内容は適当なので実際の実装にあわせてください。

#include <stdbool.h>
/**
 * n x n 正方行列2つの積を計算し、計算時間が1秒以内かを判断する。
 * @brief 要約説明
 * @param (int n) 行列のサイズ。n x n 正方行列で計算される。
 * @return 1秒以内なら true、でなければ false を返す。
 * @detail 行列の各要素は double (通常はIEEE 754 倍精度浮動小数点数)である。
 *   行列の各要素は[0, 1)の乱数(randを使用)を用いる。乱数の生成時間は計算時間に含まれない。
 *   計算時間は clock() を用いてプログラムが使用した時間である。実際に経過した時間ではない。
 *   メモリを確保できない場合は false を返し、errno に ENOMEM をセットする。
 */
bool matrix_product_onesec(int n)
{
  // 実装を書く
}

あとは、nを増やしながら、上の関数で確認していくだけです。どこまで確認するかは指定できるようにするといいでしょう。

int max_calcable(int m)
{
  for (int i = 1; i <= m; i++) {
    if (!matrix_product_onesec(i)) return i - 1;
  }
  return m;
}

false が返ってきたとき、それまで成功していた数、つまり、i - 1を返すことがコツになります。最大まで達していれば、最大を返します。

Answer 4

課題の意図はこういうことではないでしょうか。（計測処理は端折りました）

double n = 0;

while(１秒内)
{
    pow(n,2.0); // math.h
    n++;
}
printf("n=%f",n);