math - 対数についてどこで学べますか?

Question

プログラミングの文脈で対数がかなり言及されているのを耳にします。それらは多くの問題の解決策のように見えますが、実際にそれらを利用する方法を見つけることができないようです. ウィキペディアのエントリを読んだことがありますが、率直に言って、それほど賢明ではありません。

では、対数が解決する実際のプログラミングの問題についてどこで学ぶことができるでしょうか? 対数を実装することで解決された、直面した問題の例を誰かが持っていますか?

score 13 · Accepted Answer

プログラミングにおける対数は、 Big O 記法を使用してアルゴリズムの効率を記述する際にも頻繁に使用されます。

たとえば、二分探索アルゴリズムの最悪のシナリオは O(log(n)) (ソート済みセット上) ですが、線形探索の最悪のシナリオは O(n) です。

score 12 · Accepted Answer

1000 ドルを持っていて、それが 2.4% の利率の普通預金口座にあるとします。

新しいラップトップを購入するために 2000 ドルが手に入るまで、何年待たなければなりませんか?

1000 × 1.024 ^× = 2000

1.024 ^× =2

x = ログ_1.024 2 = 29.23 年

score 10 · Accepted Answer

私自身の調査で、いくつかの有用なリソースに出会いました。

カーンアカデミーの対数セクション

これは、対数に関するすばらしい一連のレッスンです。6 年生のコメントは次のようにまとめています。

どうもありがとう。今週、数学の先生に自分に挑戦するように言われたので、対数に挑戦しました。最初は「無理だ、難しすぎる」と思っていました。それから私はビデオを見ました、そして今、彼らはさらに楽しいです！私は 6 年生で、数学の先生に感銘を受けました。感謝してもしきれません。

ルビークイズ #105: トーナメントマッチアップ

この記事には、基数 2 のログを使用して、 xチームが指定されたノックアウトトーナメントを完了するために必要なラウンド数を決定する良い例が含まれています。

指数関数と E の直感的なガイド

自然対数の底であるeの優れた直感的なガイド (タイトルから想像できるとおり) 。多くのイラストと例がこれを記事の宝石にしています.

自然対数 (ln) の謎を解く

これはeについての記事のフォローアップであり、記事で与えられた直感的な説明を使用して、「特定のレベルの成長に到達するのに必要な時間を与える」自然対数 (ln)について説明します。

実際、Better Explainedサイトには優れたコンテンツがたくさんあります。本当に、素晴らしいリソースです。

私が実際に以前に遭遇した別のツールは、完全に忘れられていたのでInstacalcです。それは、Better Explained サイトの作成者である Kalid Azad によるものと思われます。数学をハックするとき、これは本当に便利なツールです。

score 5 · Accepted Answer

ログは一種のメタ演算です。これは、指数に累乗した (おそらく固定された) 基数としてすべての数値を考える方法です。演算は指数のみで実行されます。これは、ログの足し算と引き算を行うことで、掛け算と割り算を行うことができることを意味します。つまり、データを対数空間に配置し、一連の演算を実行して、非対数空間に引き戻します。浮動小数点の精度の低下と、ログ領域への変換またはログ領域からの変換のオーバーヘッドが少ない場合は、時間内に全体的に勝つ可能性があります。

ログでできる巧妙なトリックの 1 つは、数値の対数ベース 2 を取得して、定数時間である対数ベース 10(2) で割ることによって、数値が印刷されるときに使用される文字数を計算することです。乗算のセットと比較。

score 4 · Accepted Answer

タグクラウドの表示に使用される対数を見てきました。これはそれを説明するページです：

タグクラウドフォント配布アルゴリズム

score 4 · Accepted Answer

時間消費のコンテキストを持つ対数について聞いたことがあると思います。

具体的な例は、検索アルゴリズムです。順序付けられたデータのセット (ソートされた int の配列を考えてください) が与えられた場合、そのデータ内の値へのインデックスキーを見つけたいとします。配列がソートされているという事実から恩恵を受けることができます (たとえば、1、2、6、192、404、9595、50000)。値 2 のインデックスを見つけたいとしましょう。各ステップで配列の半分をカリング (無視) することで、検索スペースを最小限に抑えることができます。この検索は、配列の中央にある値をテストすることから始めます。配列には 7 つの値があり、インデックス 7/2 = 3.5 = 3 を int にします。array[3] は 192 です。探している値は 2 であるため、検索スペースの下半分で検索を続けたいと考えています。インデックス 4、5、6 はすべて 192 より大きく、2 よりも大きいため、完全に無視します。これで、(1, 2, 6) のような検索スペースができました。次に、再び中央にインデックスを付けると (プロセスを繰り返します)、すぐに 2 が見つかります。検索が完了しました。2 へのインデックスは 1 です。

これは非常に小さな例ですが、このようなアルゴリズムがどのように機能するかを示しています。

16 個の値の場合、最大 4 回検索する必要があります。値が 32 の場合は最大 5 回、値が 64 の場合は 6 回、というように、20 段階で 1048576 個の値が検索されます。これは、配列内の各項目を個別に比較するよりもはるかに高速です。もちろん、これはソートされたデータのコレクションに対してのみ機能します。

score 4 · Accepted Answer

対数の重要性、その発見、および自然現象との関連性を理解するには、e: The Story of a Numberをお勧めします。

score 3 · Accepted Answer

現実世界の多くの (多くの!) 関係は対数的です。たとえば、スタックオーバーフローのレピュテーションスコアの分布がlog normalであっても驚かないでしょう。大多数のユーザーのレピュテーションスコアは 1 で、少数の人々のレピュテーションは非常に高くなります。その分布に対数変換を適用すると、ほぼ線形の関係になる可能性があります。https://stackoverflow.com/users?page=667をすばやくスキャンすると、これが正しいことがわかります。

対数分布のアプリケーションであるロングテールの概念については、よく知っているかもしれません。

score 3 · Accepted Answer

それを見る別の方法は、数の基本乗数の数を見ることです。次の例で、これらすべてがどのように関連しているかを確認できると確信しています。

10 進数 (基数 10):

log10 (1) = 0、(10^0) = 1
log10 (10) = 1、(10^1) = 10
log10 (100) = 2、(10^2) = 100
log10 (1000) = 3、(10^3) = 1000
log10 (10000) = 4、(10^4) = 10000
log10 (100000) = 5、(10^5) = 100000

バイナリ (基数 2):

log2 (1) = 0、(2^0) = 1
log2 (2) = 1、(2^1) = 2
log2 (4) = 2、(2^2) = 4
log2 (8) = 3、(2^3) = 8
log2 (16) = 4、(2^4) = 16
log2 (32) = 5、(2^5) = 32
log2 (64) = 6、(2^6) = 64
log2 (128) = 7、(2^7) = 128

16 進数 (基数 16):

log16 (1) = 0、(16^0) = 1
log16 (16) = 1、(16^1) = 16
log16 (256) = 2、(16^2) = 256
log16 (4096) = 3、(16^3) = 4096
log16 (65536) = 4、(16^4) = 65536

変数で考えたい場合：

log N ( X ) = Y
( N ^ Y ) = X

score 2 · Accepted Answer

多くの例のうちの 1 つ: 多数の期間で非常に小さなレートで複利を計算する。

高速な累乗を使用しても、最も簡単な方法で実行できますが、精度が低下する可能性があります。これは、フロートの格納方法と s * r 乗 n の計算に O(ln(n)) 操作が必要なためです。

対数を使用すると、多少正確になります。

A = ln( s * r power n ) = ln(s) + n * ln(r)
対数データベースを 2 回検索すると、ln(s) と ln(r) が得られます。ln(r) は非常に小さく始まり、 float は、ここでは逆ルックアップである 0 result = exp(A) 付近で最高の精度で動作します。

たとえば、立方根を抽出するために、整数以外の指数を扱う場合、これは唯一の本当に効率的な方法でもあります。

score 2 · Accepted Answer

私が見つけた対数のより「クールな」アプリケーションの 1 つは、Spiral Storageです。これは、テーブルが大きくなるにつれて一度に 1 つのバケットを分割し、そのバケット内のレコードの半分未満を同じ新しいバケットに再配置できるハッシュテーブルです。パフォーマンスが周期的に変化し、すべてのバケットがほぼ同時に分割される傾向があるリニアハッシュとは異なり、スパイラルハッシュでは、テーブルを適切かつスムーズに拡張できます。

これは約 30 年前に GNN Martin によって公開されました。GNN Martin については、彼がRange Encodingも発明したという事実以外にはあまり学ぶことができませんでした。賢い人みたい！彼の元の論文のコピーを入手することはできませんでしたが、Per-Åke Larson の論文「Dynamic hash tables」には非常に明確な説明があります。

score 2 · Accepted Answer

私が覚えている唯一の問題は、SQL で列の積を計算しなければならないことです。SQL Server には PRODUCT() 集計関数がないため、これは各値の対数の合計 (LOG10() 関数を使用) を使用して達成されました。主な欠点は、列内のすべての数値が正でゼロ以外でなければならないことです (負の数値またはゼロで対数を計算することはできません)。

score 2 · Accepted Answer

すべてのプログラミング例で最も明白な使用法は精度です。簡単に言えば、符号なし整数の格納を検討してください。X を格納するには何ビットが必要ですか? n ビットに格納できる最大値は 2^n - 1 なので、X を格納するには log_2 X + 1 ビットが必要です。これで、short、int、word、long などを簡単に選択できます。

score 2 · Accepted Answer

MIT の Open Courseware: Introduction to Algorithms を確認してください。無料の教育。素晴らしい。

score 1 · Accepted Answer

クリスが話していることの例として、値のビット数に基づいて複雑さを変更するアルゴリズムは、（おそらく）O（log（n））で記述される効率を持つことになります。

指数（したがって対数）のもう1つの日常的な例は、IEEE浮動小数点数の形式です。

score 1 · Accepted Answer

対数は、1 つまたは両方の軸が広い範囲の値をカバーする場合に、チャートやグラフで非常に頻繁に使用されます。

一部の自然現象は、対数スケールで表現するのが最適です。いくつかの例は、音圧レベル ( dB 単位のSPL ) と地震のマグニチュード (リヒタースケール) です。

score 1 · Accepted Answer

対数関数は単に指数関数の逆であり、減算が加算の逆であるのと同じ意味です。この方程式のように：

a = b + c

は、次の式と同じ事実を述べています。

a - c = b

この式:

b ** p = x

(ここで**は累乗) は、次の方程式と同じ事実を述べています。

log [base b] (x) = p

b任意の数 (例: ) を指定できますが、log [base 10] (10,000) = 4数学の「自然な」基数はe(2.718281828...)です。これについては、こちらを参照してください。

工学でより多く使用される「常用」対数は、10 の底を使用します。ある数値の常用 (10 を底とする) 対数のクイックアンドダーティ (汚いことに重点を置いた) 解釈はx、それが 10 進数よりも 1 小さいことです。のサイズの数を表すのに必要な桁数x。

score 0 · Accepted Answer

BetterExplainedで自然対数（ln） をわかりやすく説明することは、私が見つけた最高のものです。基礎から概念を明確にし、根底にある概念を理解するのに役立ちます。その後、すべてが楽勝のようです。

score 0 · Accepted Answer

ここに私が使用したいくつかのサイトがあります：

私は対数を使用して家の年間評価額を計算し、売り手が公正であるかどうかを判断しました。

家の感謝の式

基本的な式は次のとおりです。

以前の価格 = p
新価格 = n
評価率 = r
感謝の年数 = y

p * (1 + r)^y = n

では、6 年前の価格が 191,000 ドル (郡の監査人のサイトをチェックして) で、提示価格が 284,000 ドルである場合、上昇率はいくらになるでしょうか (1 回限りの改善費用は考慮されていません)。

191,000 * (1 + r)^6 = 284,000

(1 + r)^6 = 284,000 / 191,000 = 1.486

Using a property of exponents and logarithms…

6 ( log (1 + r) ) = log 1.486
log (1 + r) = (log 1.486) / 6 = 0.02866

Using another property of exponents and logarithms…

10 0.02866 = 1 + r
1.068 = 1 + r
r = 1.068 – 1 = 0.068 = 6.8%  (kind of high!)

妥当な価格を決定するには、4% を使用し、彼らが行ったあらゆる改善を考慮します (これは、彼らが主だった Web ID に記載されている必要がありますが、バスルーム/キッチンの改造などは含まれません)。

191,000 * (1 + 0.04)^6 = n
n = 241,675 + reasonable cost of improvement 
which of course will depreciate over time 
and should not represent 100% of the 
cost of the improvement

math - 対数についてどこで学べますか?

19 に答える 19

カーン アカデミーの対数セクション

ルビークイズ #105: トーナメントマッチアップ

指数関数と E の直感的なガイド

自然対数 (ln) の謎を解く

Related

Reference

カーンアカデミーの対数セクション