Data, Knowledge & Life

Weiwei Cheng's blog

Archive for 一月 2010

How to compute the soft maximum

leave a comment »

by John D. Cook(博主注:John Cook最近在他的个人博客The Endeavour上撰写的关于计算soft maximum的文章非常值得一读。转载在这里,大家一起学习一下。文后附带的几个相关的链接,包括如何避免计算程序数值溢出的讨论,都是极有价值的文章。)

The most obvious way to compute the soft maximum can easily fail due to overflow or underflow.

The soft maximum of x and y is defined by

g(x, y) = log( exp(x) + exp(y) ).

The most obvious way to turn the definition above into C code would be

double SoftMaximum(double x, double y){
return log( exp(x) + exp(y) );
}

This works for some values of x and y, but fails if x or y is large. For example, if we use this to compute the soft maximum of 1000 and 200, the result is numerical infinity. The value of exp(1000) is too big to represent in a floating point number, so it is computed as infinity. exp(200) is finite, but the sum of an infinity and a finite number is infinity. Then the log function applied to infinity returns infinity.

We have the opposite problem if we try to compute the soft maximum of -1000 and -1200. In this computation exp(-1000) and exp(-1200) both underflow to zero, and the log function returns negative infinity for the logarithm of zero.

Fortunately it’s not hard to fix the function SoftMaximum to avoid overflow and underflow. Look what happens when we shift both arguments by a constant.

log( exp(x–k) + exp(y–k) ) = log( exp(x) + exp(y) ) – k.

This says

log( exp(x) + exp(y) ) = log( exp(x-k) + exp(y-k) ) + k.

If we pick k to be the maximum of x and y, then one of the calls to exp has argument 0 (and so it returns 1) and the other has a negative argument. This means the follow code cannot overflow.

double SoftMaximum(double x, double y)
{
double maximum = max(x, y);
double minimum = min(x, y);
return maximum + log( 1.0 + exp(minimum-maximum) );
}

The call to exp(minimum – maximum) could possibly underflow to zero, but in that case the code returns maximum. And in that case the return value is very accurate: if maximum is much larger than minimum, then the soft maximum is essentially equal to maximum.

The equation for the soft maximum implemented above has a few advantages in addition to avoiding overflow. It makes it clear that the soft maximum is always greater than the maximum. Also, it shows that the difference between the hard maximum and the soft maximum is controlled by the spread of the arguments. The soft maximum is nearest the hard maximum when the two arguments are very different and furthest from the hard maximum when the two arguments are equal.

Thanks to Andrew Dalke for suggesting the topic of this post by his comment.

Related links:
Soft maximum
Anatomy of a floating point number
Avoiding overflow, underflow, and loss of precision

Advertisements

Written by Weiwei

24/01/2010 at 15:18

发表在 转贴

给大家推荐一款办公键盘

leave a comment »

MS Comfort Curve Keyboard

  办公室的键盘(Cherry eVolution Stream Corded Multimedia Tastatur silber)用了一年多,打算换个新的。个把礼拜前在Media Markt闲逛,偶然看到Microsoft的一款人体工程键盘(Microsoft Comfort Curve Keyboard 2000),小试了一下,手感很不错,价格又便宜(19.9€),于是便买回来了。难怪Microsoft硬件的口碑比软件的好:用了这个键盘一段时间,感觉非常好:按键触感柔合,功能键简约实用,在办公场所尤其值得推荐。不过经常玩模拟器的朋友最好不要买这款键盘。我用它打街霸的时候,经常会有出招失灵的现象。貌似它同时能接受的键位不超过3个。

  这款键盘还有一个升级版,Microsoft Natural Ergonomic Keyboard 4000,有兴趣的朋友也可以试试。在德国的朋友如果近期想要购入电脑输入设备,Microsoft目前正在做活动:购买微软的硬件产品,凡价格超过30€的,返19%的增值税

Written by Weiwei

21/01/2010 at 23:05

发表在 杂话

Ten surprises from numerical linear algebra

leave a comment »

from The Endeavour by John

Here are ten things about numerical linear algebra that you may find surprising if you’re not familiar with the field.

  1. Numerical linear algebra applies very advanced mathematics to solve problems that can be stated with high school mathematics.
  2. Practical applications often require solving enormous systems of equations, millions or even billions of variables.
  3. The heart of Google is an enormous linear algebra problem. PageRank is essentially an eigenvalue problem.
  4. The efficiency of solving very large systems of equations has benefited at least as much from advances in algorithms as from Moore’s law.
  5. Many practical problems — optimization, differential equations, signal processing, etc. — boil down to solving linear systems, even when the original problems are non-linear. Finite element software, for example, spends nearly all its time solving linear equations.
  6. A system of a million equations can sometimes be solved on an ordinary PC in under a millisecond, depending on the structure of the equations.
  7. Iterative methods, methods that in theory require an infinite number of steps to solve a problem, are often faster and more accurate than direct methods, methods that in theory produce an exact answer in a finite number of steps.
  8. There are many theorems bounding the error in solutions produced on real computers. That is, the theorems don’t just bound the error from hypothetical calculations carried out in exact arithmetic but bound the error from arithmetic as carried out in floating point arithmetic on computer hardware.
  9. It is hardly ever necessary to compute the inverse of a matrix.
  10. There is remarkably mature software for numerical linear algebra. Brilliant people have worked on this software for many years.

Written by Weiwei

21/01/2010 at 02:37

发表在 转贴

史上最贵建站:中国工会网招标

leave a comment »

我们多捐点,不如你们少贪点~
资料来源:万景新闻

Written by Weiwei

20/01/2010 at 23:56

发表在 杂话

好壮观的眼镜群

leave a comment »


安徽合肥,戴着3D眼镜看Avatar的观众们。
图片来自纽约时报

Written by Weiwei

20/01/2010 at 23:45

发表在 杂话

24 Season 8 is on air!

leave a comment »

Written by Weiwei

19/01/2010 at 01:33

发表在 娱乐

屏蔽Live Messenger底部的广告

leave a comment »

  微软的Windows Live Messenger,也就是之前的MSN Messenger,是我最常用的即时通讯工具。上网的时候,我喜欢把它开着放在一边。Messenger一个很令人烦的毛病就是其底部的广告条:它不是一个静态的广告条,经常会莫名闪烁,播放动画之类。如果鼠标悬停到它上边,甚至会弹出一个巨幅的广告画面(这里严重鄙视微软一下)。这里介绍一种可以屏蔽Messenger底部广告的方法。(更多技巧可以参见MakeUseOf.com

  1、打开Windows控制面板,进入Internet Options,选择Security标签,再选择Restricted,点击Sites按钮;

internet_options_restricted_sites

  2、在弹出的对话框中添加http://rad.msn.com。这样,通过将微软广告服务器的地址放到受限网站列表里,我们屏蔽了其发送的广告信息。

  完成以上的操作之后,Messenger底部的广告条变成了一个白框。恭喜你,讨厌的广告已经被你成功屏蔽了。

msn_window_ad

Written by Weiwei

17/01/2010 at 19:15

发表在 杂话