対数についてどこで学べますか?[閉まっている]

https://stackoverflow.com/questions/121847

02-07-2019
|

質問

プログラミングの文脈では対数がよく言われると聞きます。これらは多くの問題の解決策であるように見えますが、現実世界でそれらを活用する方法が見つからないようです。を読みましたウィキペディアの項目そして率直に言って、それは私にとって賢明なことではないのです。

では、対数が解決する現実世界のプログラミング問題についてはどこで学べるのでしょうか? 対数を実装することで解決した、直面した問題の例を知っている人はいますか?

解決

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

新しいラップトップを買うのに 2000 ドルを手に入れるまで何年待たなければなりませんか?

1000 × 1.024^バツ = 2000

1.024^バツ = 2

x = ログ _1.024 2 = 29.23 年

他のヒント

プログラミングにおける対数は、アルゴリズムの効率を説明する際にも頻繁に使用されます。ビッグオー表記.

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

私自身の調査で、いくつかの有用なリソースを発見しました。

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

これは対数に関する素晴らしい一連のレッスンです。6年生のこのコメントがそれをうまく要約しています。

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

Ruby クイズ #105:トーナメントの組み合わせ

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

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

(タイトルからご想像のとおり) 優れた直感的なガイドです。 e, 、自然対数の底。豊富なイラストと例により、これは貴重な記事になります。

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

これは、次の記事の続編です。 e そして、 自然対数 (ln) この記事で与えられた直感的な説明を使えば、これは「一定の成長レベルに達するのに必要な時間を与える」ということです。

実際、良いコンテンツがたくさんあります より適切な説明 サイト。本当に、素晴らしいリソースです。

私が実際に以前に出会ったもう 1 つのツールですが、すっかり忘れていました。 インスタカルク. 。これは、Better Explained サイトの著者である Kalid Azad と同じ人物によるもののようです。これは、数学をハックするときに非常に便利なツールです。

ログはメタ演算の一種です。これは、すべての数値を (おそらく固定された) 基数を指数化したものとして考える方法です。演算は指数のみで実行されます。これは、ログの加算と減算を行うことで乗算と除算ができることを意味します。言い換えれば、データをログ領域に配置し、一連の演算を実行して、非ログ領域に戻します。浮動小数点精度の損失と、ログ空間への変換またはログ空間からの変換のオーバーヘッドが低ければ、やがて全体的な勝利が得られる可能性があります。

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

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

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

時間の消費に関連した対数について聞いたことがあると思います。

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

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

16 個の値の場合、最大 4 回の検索が必要です。32 個の値の場合は最大 5 回、64 個の値の場合は最大 6 回検索します。1048576 個の値を 20 ステップで検索します。これは、配列内の各項目を個別に比較するよりもはるかに高速です。もちろん、これは並べ替えられたデータのコレクションに対してのみ機能します。

お勧めします e:数字の物語対数の重要性、対数の発見、自然現象との関連性についての優れた基礎が得られます。

もう 1 つの見方は、数値内の基本乗数の数を見ることです。次の例で、これがどのように関係しているかがわかると思います。

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

変数で考えたい場合:

ログ N (バツ) = Y
(N^Y) = バツ

現実世界の多くの (多くの!) 関係は対数です。たとえば、Stack Overflow のレピュテーションスコアの分布が次のようになったとしても驚かないでしょう。正規のログ. 。大多数のユーザーの評判スコアは 1 ですが、少数のユーザーは達成できないほど高い評判を持つことになります。その分布に対数変換を適用すると、ほぼ線形の関係になる可能性があります。クイックスキャン https://stackoverflow.com/users?page=667 これが真実であることを示しています。

あなたはもっとよく知っているかもしれませんロングテール対数分布を応用した概念です。

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

すべてのプログラミング例で最も明らかな使用法は精度です。簡単に言うと、符号なし整数を保存することを考えてみましょう。Xを保存するには何ビット必要ですか?n ビットに格納できる最大値は 2^n - 1 なので、X を格納するには log_2 X + 1 ビットが必要になります。short、int、word、long などを簡単に選択できるようになりました。

たくさんあるうちの一例:多数の期間を使用して、非常に小さいレートで複利を計算します。

高速累乗を使用する最も簡単な方法でも実行できますが、浮動小数点数の格納方法と s * r power n の計算に依然として O(ln(n)) 演算が必要なため、精度が低下する可能性があります。

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

A = ln( s * r 乗 n ) = ln(s) + n * ln(r)
対数データベースの2つのルックアップはLN（S）とLN（R）を提供し、LN（R）が非常に小さく開始され、フロートは結果= Exp（a）の近くで最高の精度で機能します。

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

MIT のオープンコースウェアをチェックしてください。アルゴリズムの概要. 。無料の教育。素晴らしい。

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

約30年前にG社から出版されました。N.N.マーティンについては、彼が発明したという事実以外にはあまり学ぶことができませんでした。範囲エンコーディング. 。賢い人のようですね！私は彼のオリジナルの論文のコピーを入手できませんでしたが、Per-Åke Larson の論文は「動的ハッシュテーブル」には非常に明確な説明があります。

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

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

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

指数 (したがって対数) の別の日常的な例は、次の形式です。 IEEE 浮動小数点数.

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

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.

自然対数の謎を解く (ln) BetterExplained は私が見つけた中で最高のものです。基礎から概念を明確にし、基礎となる概念を理解するのに役立ちます。その後はすべてが楽勝のように思えます。

私が使用したサイトをいくつか紹介します。

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

住宅評価の方程式

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

以前の価格 = 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

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow