我听说在编程上下文中提到了很多对数。它们似乎是许多问题的解决方案，但我似乎无法找到一种在现实世界中使用它们的方法。我已经阅读了Wikipedia 条目，坦率地说，这让我一点也不聪明。
那么，我在哪里可以了解对数解决的实际编程问题？有没有人有任何通过实施对数解决的问题的例子？
Charles Roper
问问题
4898 次
19 回答
13
编程中的对数也经常用于描述使用大 O 表示法的算法的效率。
例如，二分搜索算法的最坏情况是 O(log(n))（在排序集上），而线性搜索的最坏情况是 O(n)
于 2008-09-23T15:52:33.923 回答
12
假设你有 1000 美元，它存在于一个利息为 2.4% 的储蓄账户中。
你要等多少年才能有 2000 美元才能购买一台新笔记本电脑？
1000 × 1.024 x = 2000
1.024 x = 2
x = log 1.024 2 = 29.23 年
于 2008-09-23T15:52:07.527 回答
10
在我自己的研究中，我发现了一些有用的资源：
可汗学院对数部分
这是一套很棒的对数课程。一位六年级学生的评论很好地总结了这一点：
非常感谢。这周，我的数学老师告诉我要挑战自己，所以我尝试了对数。起初我想，“我做不到，这太难了”。然后我看了视频，现在他们甚至很有趣！我在六年级，我的数学老师给我留下了深刻的印象。我不能感谢你。
Ruby 测验 #105：锦标赛对决
本文包含一个很好的示例，该示例使用以 2 为底的对数来确定在给定x支球队的情况下完成淘汰赛所需的回合数。
指数函数和 E 的直观指南
一个优秀的、直观的（正如你所期望的那样，给定标题）指南e，自然对数的底。大量插图和示例使其成为文章的瑰宝。
揭秘自然对数 (ln)
这是一篇关于e的文章的后续文章，讨论了自然对数 (ln)，使用文章中给出的直观解释，“给你达到一定增长水平所需的时间”。
Better Explained网站上实际上有很多好的内容。确实，很棒的资源。
我之前实际上遇到过但后来完全忘记的另一个工具是Instacalc。似乎是同一个人 - Kalid Azad - 创建了 Better Explained 网站。它是一个非常有用的工具，用于破解数学。
于 2008-09-24T17:52:10.587 回答
5
日志是一种元算术。这是一种将每个数字视为（可能是固定的）基数提高到指数的方式。仅对指数执行操作。这意味着您可以通过对日志进行加法和减法来进行乘法和除法。换句话说，您将数据放入日志空间，执行一套算术，然后将其拉回非日志空间。如果浮点精度损失和转换进出日志空间的开销很便宜，那么您可能会在时间上取得整体胜利。
你可以用日志做的一个巧妙的技巧是计算一个数字在打印时将占用的字符数，方法是将数字的 log-base-2 除以 log-base-10(2)，这是常数时间与一组乘法相比。
于 2008-09-23T15:59:07.400 回答
4
我见过用于显示标签云的对数。这是一个解释它的页面：
于 2008-09-23T15:52:40.817 回答
4
我假设您已经听说过带有时间消耗上下文的对数。
一个具体的例子是搜索算法。给定一组有序数据（想想一个有序的 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 次，依此类推。1048576 个值在 20 步中搜索。这比必须单独比较数组中的每个项目要快得多。当然，这仅适用于已排序的数据集合。
于 2008-09-23T16:05:00.447 回答
4
我推荐e: The Story of a Number为对数的重要性、它们的发现以及与自然现象的相关性打下良好的基础。
于 2008-09-23T16:16:35.160 回答
3
另一种看待它的方法是查看一个数字中基数乘数的数量。我相信您可以在以下示例中看到这一切的关系。
十进制（以 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 为基数）：
- 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 ( X ) = Y
- ( N ^ Y ) = X
于 2008-09-23T16:18:23.457 回答
3
现实世界中的许多（许多！）关系是对数的。例如，如果 Stack Overflow 上的声誉分数分布是log normal ，我不会感到惊讶。绝大多数用户的声誉得分为 1，少数人的声誉很高。如果您对该分布应用对数变换，它可能几乎是线性关系。快速浏览https://stackoverflow.com/users?page=667表明这是真的。
您可能更熟悉长尾概念，它是对数分布的应用。
于 2008-09-23T16:27:40.907 回答
2
我能回忆起的唯一问题是必须在 SQL 中计算列的乘积。SQL Server 没有 PRODUCT() 聚合函数，因此这是使用每个值的对数之和（使用 LOG10() 函数）来完成的。主要缺点是列中的所有数字都必须是正数且非零（您无法计算负数或零的对数）。
于 2008-09-23T15:49:36.253 回答
2
每个编程示例中最明显的用法是精度。简而言之，考虑存储无符号整数。你需要多少位来存储 X？嗯，您可以存储在 n 位中的最大值是 2^n - 1，因此您可能需要 log_2 X + 1 位来存储 X。现在您可以轻松选择 short、int、word、long 等。
于 2008-09-23T15:53:22.720 回答
2
举一个例子：以非常小的利率和大量的周期计算复利。
您可以使用最直接的方式进行操作，即使使用快速求幂，但准确性可能会受到影响，因为浮点数的存储方式和计算 s * r 幂 n 仍然需要 O(ln(n)) 操作。
使用对数，它会更准确一些。
A = ln( s * r power n ) = ln(s) + n * ln(r)
对数数据库中的两次查找给出了 ln(s) 和 ln(r)，其中 ln(r) 开始非常小，并且浮点数在 0 result = exp(A) 附近以最佳精度工作，此处为反向查找。
如果您使用非整数指数，这也是唯一真正有效的方法，例如提取三次根。
于 2008-09-23T16:08:38.407 回答
2
查看 MIT 的开放课件：算法简介。免费教育。惊人的。
于 2008-09-23T16:11:43.953 回答
2
我发现的对数更“酷”的应用之一是Spiral Storage。这是一个哈希表，允许您随着表的增长一次拆分一个存储桶，将该存储桶中不到一半的记录重新定位到相同的新存储桶。与线性散列不同，线性散列的性能会周期性地变化，并且所有的桶往往会在同一时间被拆分，而螺旋散列允许表的良好、平滑的增长。
它是大约 30 年前由 GNN Martin 出版的，除了他还发明了Range Encoding之外，我对他的了解不多。看来是个聪明人！我一直无法得到他的原始论文的副本，但是 Per-Åke Larson 的论文“动态哈希表”有一个非常清晰的描述。
于 2008-09-23T16:41:25.583 回答
1
对数函数只是指数函数的逆函数，就像减法是加法的逆函数一样。就像这个等式：
a = b + c
陈述与这个等式相同的事实：
a - c = b
这个等式：
b ** p = x
(where **is raise to an power) 陈述了与这个等式相同的事实：
log [base b] (x) = p
虽然b可以是任何数字（例如log [base 10] (10,000) = 4），但数学的“自然”基数是e(2.718281828...)，请参见此处。
在工程中使用较多的“常用”对数以 10 为底。对某个数字的常用（以 10 为底）对数的一种简单粗暴（强调脏）的解释x是它比十进制数小一表示大小为 的数字所需的数字x。
于 2008-09-24T02:14:03.913 回答
0
在 BetterExplained揭秘自然对数 (ln) 是我发现的最好的。它从基础中清除概念并帮助您理解底层概念。在那之后，一切似乎都是小菜一碟。
于 2009-01-17T13:12:42.770 回答
0
以下是我使用过的一些网站：
- http://www.helpalgebra.com/articles/propertiesoflogarithms.htm
- http://www.math.unc.edu/Faculty/mccombs/web/alg/classnotes/logs/lognotation.html
- http://www.math.unc.edu/Faculty/mccombs/web/alg/classnotes/logs/logprops.html
- http://abacus.bates.edu/acad/acad_support/msw/exps_and_logs.pdf
- http://people.hofstra.edu/Stefan_Waner/Realworld/calctopic1/logs.html
我用对数来计算房子的年升值，以确定卖方是否公平。
房屋升值方程
这是基本方程：
- 以前的价格 = p
- 新价格 = n
- 升值率 = r
- 升值年限 = y
p * (1 + r)^y = n
那么，如果 6 年前的价格是 191,000 美元（通过查看您的审计师的网站），而要价是 284,000 美元，那么升值率是多少（不考虑任何一次性改进成本）？
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% 并考虑他们所做的任何改进（应该在他们主要的网络 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
于 2009-01-29T15:24:46.050 回答