線形補間の区間計算　対数で割る理由を知りたいです。

線形補間を行うサンプルコードの中にわからない部分があります。
補間する区間を算出する関数内で既知点の総数を対数で割る処理をしているのですが、
その理由がよくわかりません。

もしかしてピボット的な位置を探しているのかと思いましたが、いまいち確信を得られませんでした。

もしかしたらすごく初歩的な内容を質問しているのかもしれませんが、
ご教授いただけないでしょうか？　よろしくお願いします。

int Sagasu(double xx[], double x, int n)
/*
  該当区間を探す
 */
{
    int i, l, r, m, kaisuu;

    l = 0;
    r = n;

　　//この部分です。
    kaisuu = (int)(log(n)/log(2)+1);


    for (i=1; i<=kaisuu; i++){
        m = (l+r)/2;
        if (xx[m] <= x) l = m;
        else r = m;
        if (xx[l+1] > x) break;
    }
    return l;
}

double Hokan(double xx[], double yy[], double x, int k)
/*
  線形補間
 */
{
    int k1;

    k1 = k+1;
    return yy[k]+(x-xx[k])*(yy[k1]-yy[k])/(xx[k1]-xx[k]);
}

int Datain(double xx[], double yy[])
/*
  テストデータ作成
  y = sin(x) (x=0,10,...,360)
 */
{
    int i, n, deg;
    double rad;

    n = 36;
    for (i=0; i<=n; i++) {
        deg = 10*i;
        rad = 3.14159265*deg/180.0;
        xx[i] = deg;
        yy[i] = sin(rad);
    }
    return n;
}

/*    ------------------    Main    ------------------    */
int main()
{
    int i, k, n;
    double x, y, xx[ND+1], yy[ND+1];
    char s[135];

    n = Datain(xx, yy);
    for (i=1; i<=4; i++) {
        printf(" x= "); gets(s); sscanf(s,"%lf",&x);
        k = Sagasu(xx, x, n);
        y = Hokan(xx, yy, x, k);
        printf(" y= %e\n", y);
    }
    return 0;
}
/* -- 実行例:戸川隼人「数値計算」岩波書店 p.148 プログラム7.1 -- */
/*
Z:\src\C>Hokan
 x= 45
 y= 7.044160e-01
 x= 135
 y= 7.044160e-01
 x= 225
 y= -7.044160e-01
 x= 315
 y= -7.044160e-01
*/

行動規範の内容に同意します

回答2件

    for (i=1; i<=kaisuu; i++){
        m = (l+r)/2;
        if (xx[m] <= x) l = m;
        else r = m;
        if (xx[l+1] > x) break;
    }

このloopを一回まわるたびに lとr間の距離が1/2になるから、
lとrを十分近づける(収束する)ためにloopを回る回数は (2底での)nの対数、すなわちlog(n)/log(2)。

投稿2021/05/07 11:16

編集2021/05/07 11:18

episteme

総合スコア16614

siusus

2021/05/07 12:27

回答ありがとうございます。恥ずかしい話なのですが、私には高校数学的な素養がほとんどありません・・。反復法？で解を求めようとしているのはなんとなくわかるのですが・・。高校数学からやり直した方がいいとは思うのですが、収束条件（？）とかの分野を勉強するのに適した検索ワードだったり、WEBページとかがあったら教えていただけないでしょうか？厚かましいお願いかもしれませんが、よろしくお願いします。