ホームページ >バックエンド開発 >C++ >C で整数演算を使用して大きな整数を効率的に二乗するにはどうすればよいですか?

C で整数演算を使用して大きな整数を効率的に二乗するにはどうすればよいですか?

Mary-Kate Olsen
Mary-Kate Olsenオリジナル
2024-12-23 07:28:54694ブラウズ

How Can I Efficiently Square Large Integers in C   Using Integer Arithmetic?

高速大数値二乗計算

問題:

y = x^ を計算するにはどうすればよいですか? 2 C および整数演算を使用して、精度を損なうことなく可能な限り高速に実行します。 (32bit with Carry)?

解決策:

この問題は、計算量 O(N^(log2(3)) のカラツバ乗算を使用して解決できます。 )、N は次の数です。

実装:

これは C でのカラツバ乗算の実装です:

void karatsuba(int *a, int *b, int n, int *c) {
  if (n <= 1) {
    c[0] = a[0] * b[0];
    return;
  }
  int half = n / 2;
  int *a0 = new int[half];
  int *a1 = new int[half];
  int *b0 = new int[half];
  int *b1 = new int[half];
  for (int i = 0; i < half; i++) {
    a0[i] = a[i];
    a1[i] = a[i + half];
    b0[i] = b[i];
    b1[i] = b[i + half];
  }
  int *c0 = new int[half];
  int *c1 = new int[half];
  int *c2 = new int[n];
  karatsuba(a0, b0, half, c0);
  karatsuba(a1, b1, half, c1);
  for (int i = 0; i < n; i++)
    c2[i] = 0;
  for (int i = 0; i < half; i++)
    for (int j = 0; j < half; j++)
      c2[i + j] += a0[i] * b1[j];
  for (int i = 0; i < half; i++)
    for (int j = 0; j < half; j++)
      c2[i + j + half] += a1[i] * b0[j];
  for (int i = 0; i < n; i++)
    c[i] = c0[i] + c1[i] + c2[i];
  delete[] a0;
  delete[] a1;
  delete[] b0;
  delete[] b1;
  delete[] c0;
  delete[] c1;
  delete[] c2;
}

この実装の複雑さは O(N ^(log2(3)))。これは単純な O(N^2) よりも大幅に高速です。

結論:

カラツバ乗算を使用すると、単純な O(N^2) アルゴリズムを使用するよりもはるかに高速に y = x^2 を計算できます。

以上がC で整数演算を使用して大きな整数を効率的に二乗するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。