Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspxBinomial coefficients, for example. Taylor series, for another.en-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10418786Wed, 15 May 2013 06:15:57 GMT91d46819-8472-40ad-a661-2c78acb4018c:10418786James<p>About changing the order of addition: first make sure the series is absolutely convergent. There's a theorem: given a series that's convergent but not absolutely convergent, you can shuffle it to make it converge to anything you want.</p>
<div class="post">[<em>You can freely shuffle a finite series. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10418786" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417905Sun, 12 May 2013 03:26:05 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417905Stallman Torvalds<p>I bet if it were under MsPL you'd be all over it. Stop spreading FUD, you shill.</p>
<div class="post">[<em>Presumably the Microsoft legal department reviewed the MS-PL license. But my content management system doesn't support it so even if all the legal hurdles were cleared, I probably still wouldn't use it. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417905" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417536Fri, 10 May 2013 06:56:13 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417536Raphael<p>MathJax? Isn't that the thing on Wikipedia you can use to increase the loading time of a page by about 10 seconds?</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417536" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417526Fri, 10 May 2013 05:42:24 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417526mikeb<p>Way back when I was in college, I had to take a 1 credit numerical analysis course (taught in Basic, no less) that was supposed to be really easy. It was only one credit, after all.</p>
<p>But it was the hardest course I had that semester.</p>
<p>Math is generally elegant and beautiful, as Raymond says. Arithmetic on computers is an ugly hack.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417526" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417506Fri, 10 May 2013 01:45:57 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417506Maurits [MSFT]<p>Calculate C(50, 7) using C(n, k) = C(n - 1, k - 1) * n / k</p>
<p>Subtract k from both n and k to get the starting point: C(50 - 7, 7 - 7) = C(43, 0)</p>
<p>C(43, 0) = 1 by definition</p>
<p>C(44, 1) = C(43, 0) * 44 / 1 = 1 * 44 / 1 = 44</p>
<p>C(45, 2) = C(44, 1) * 45 / 2 = 44 * 45 / 2 = 990</p>
<p>C(46, 3) = C(45, 2) * 46 / 3 = 990 * 46 / 3 = 15180</p>
<p>C(47, 4) = C(46, 3) * 47 / 4 = 15180 * 47 / 4 = 178365</p>
<p>C(48, 5) = C(47, 4) * 48 / 5 = 178365 * 48 / 5 = 1712304</p>
<p>C(49, 6) = C(48, 5) * 49 / 6 = 1712304 * 49 / 6 = 13983816</p>
<p>C(50, 7) = C(49, 6) * 50 / 7 = 13983816 * 50 / 7 = 99884400</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417506" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417481Thu, 09 May 2013 23:21:29 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417481Neil<p>C(n, k) = C(n - 1, k - 1) × n ÷ k, although true, isn't the relation C(n, k) = C(n, k - 1) × (n + 1 - k) ÷ k that you actually demonstrated.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417481" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417478Thu, 09 May 2013 23:03:12 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417478Anonymous Coward<p>The Apache 2.0 licence is strange (in my opinion) but also short, devoid of hidden gotchas and well understood.</p>
<p>However, I personally wouldn't bet on a math system that results in broken output on the #1 rendering engine while at the same time claiming that it brings beautiful math to all browsers.</p>
<p>Plus, this isn't the kind of site where formulæ are a big necessity. I don't think it's going to be worth it.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417478" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417435Thu, 09 May 2013 20:16:35 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417435Pomax<p>Then it's time to lawyer up, you're using other "free to use on a website" libraries already ;) MathJax is just as free as jQuery etc. it's a CDN-hosted library for the web, not something you pay for to put on your website.</p>
<div class="post">[<em>And I'll have to add MathJax support to my content management system. Given that my content management system doesn't even support images, you can imagine how likely MathJax support is going to show up. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417435" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417391Thu, 09 May 2013 17:55:56 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417391Dem<p>Re: Great, now I have to hire a lawyer to read the licensing agreement. -Raymond</p>
<p>Err, it's open source and licensed under the Apache 2.0 license, why would you need a lawyer to read that?</p>
<div class="post">[<em>Because I don't trust myself to read the license and understand its consequences fully. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417391" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417346Thu, 09 May 2013 15:34:15 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417346Pomax<p>Just use MathJax and typeset it as \[{n \choose k} = \frac{n!}{k!(n-k)!]\], and magic: now your formulae look pretty in pretty much any browser. It's somewhat the defacto library for actually putting math, rather than horrible ascii, on a page these days =)</p>
<div class="post">[<em>Great, now I have to hire a lawyer to read the licensing agreement. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417346" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417277Thu, 09 May 2013 10:23:24 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417277Neil<p>@Veltas I always thought that the standard way to describe a computation whose time depends on the number of bits in n was O(log n).</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417277" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417268Thu, 09 May 2013 09:53:33 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417268Azarien<p>Ah, I remember from high school, when the task was to "simplify the formula". The "simplified" form usually only looked more pretty, but required MORE computation. And some of the transformations were completely pointless (at least their point was never convincingly explained), like "rationalizing the denominator".</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417268" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417221Thu, 09 May 2013 04:30:18 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417221Jon<p>Talking about the gamma function is a good point - if you're happy with using floating point numbers and don't need an exact result, you can calculate binomial coefficients as follows:</p>
<p>n_c_k = exp(lgamma(n+1)-lgamma(k+1)-lgamma(n-k+1));</p>
<p>Not sure how the performance compares to the integer implementation. It's definitely slower for small inputs and maybe faster for large inputs. The lgamma calls can cause extreme numerical errors depending on n and k, so if anyone wants to use this, be careful.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417221" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417173Thu, 09 May 2013 00:40:29 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417173foo<p>> That took forever to format. I will use the traditional notation from now on purely for typographical expediency</p>
<p>Seems like pretty mathematical formulas aren't designed to be suitable for general-purpose blog entries either.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417173" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417148Wed, 08 May 2013 22:11:46 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417148meangrape<p>You need to ask the mathematician for an analytic form of the equation. <a href="http://en.wikipedia.org/wiki/Analytic_expression" rel="nofollow" target="_new">en.wikipedia.org/.../Analytic_expression</a></p>
<div class="post">[<em>The article says that the gamma function (generalized factorial) and infinite series are permitted in analytic expressions, so the formulas given in the article are already analytic. But they are not suitable for computation. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417148" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417145Wed, 08 May 2013 21:52:45 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417145Sven2<p>I'd say formulas aren't necessarily designed to look pretty, but they're designed to work well for stuff that mathematicians do (e.g.: Derive other formulas). And for that, the definition as a series is usually less usable than the definition using factorials.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417145" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417141Wed, 08 May 2013 21:36:10 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417141Craig<p>"(Am I the only person who calculated binomial coefficients by hand?)"</p>
<p>I have a degree in computer engineering and had to go look up what a binomial coefficient *is*, let alone calculate them by hand.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417141" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417102Wed, 08 May 2013 18:10:01 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417102Anoniempje<p>Adam Rosenfield, Google seems to intend to drop any plans for future MathML support in their ‘new’ Blink engine.</p>
<p>Weiqi Goa, I just looked at the demoes on the web page you mention and something goes horribly wrong for me. I just see unformatted Tex (using Chromium 28.something).</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417102" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417093Wed, 08 May 2013 17:37:10 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417093Weiqi Gao<p>Take a look at MathJax (<a href="http://www.mathjax.org/" rel="nofollow" target="_new">http://www.mathjax.org/</a>) for serving mathmatics on the Web. Detailed instructions for enabling it in various blogging software/sites can be found here: <a href="http://checkmyworking.com/2012/01/how-to-get-beautifully-typeset-maths-on-your-blog/" rel="nofollow" target="_new">checkmyworking.com/.../how-to-get-beautifully-typeset-maths-on-your-blog</a>.</p>
<div class="post">[<em>Great, now I have to go talk to a lawyer. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417093" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417083Wed, 08 May 2013 17:15:22 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417083Veltas<p>I'm not sure I understand, as the time complexity would probably be of the form O(2^k) or something similar, so if one were to roughly add 1 to k (i.e. go from 1024 to 2047), the time should roughly double.</p>
<p>Although I'm starting to rethink this convention, it doesn't really make it easier to understand.</p>
<div class="post">[<em>While it's true that it tells you that doubling the second parameter to C(n,k) also doubles cost, it misleads you into thinking that all values of the second parameter from 1024 to 2047 cost the same. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417083" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417079Wed, 08 May 2013 17:01:03 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417079Veltas<p>I was just taught to do it like that.</p>
<p>I suppose it means you're considering the 'size' of the input, rather than the magnitude of a single number given.</p>
<div class="post">[<em>It depends on the nature of the problem. If you used bit sizes, then you would conclude that calculating C(n,1024) and C(n,2047) were roughly equivalent in cost, when in fact the second costs nearly twice as much. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417079" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417076Wed, 08 May 2013 16:55:55 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417076Veltas<p>I feel like I should ask now if it's faster for small n, because the Pascal's triangle identity allows you to find the coefficients through addition, whereas the better complexity method uses multiplication and division.</p>
<p>I personally wouldn't know, I don't know much about performance at all.</p>
<p>Also, wouldn't it be more appropriate to measure algorithmic time complexity with respect to bitsize of n and k, rather than the actual values?</p>
<div class="post">[<em>Not sure what the benefit of measuring in bit size is. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417076" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417065Wed, 08 May 2013 16:16:39 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417065Maurits [MSFT]<p>Yes, the time is quadratic, but the memory requirements are only O(n); you can get away with storing only two rows of the triangle.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417065" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417060Wed, 08 May 2013 16:07:59 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417060GWO<p>[Exercise: Discuss why this is a bad way to calculate binomial coefficents. -Raymond]</p>
<p>Because the number of calculations grows quadratically with n. It is, however the way I do them by hand when n < 10 (i.e. write down Pascal's triangle). Of course, it helps that 1,5,10,10,5,1 is easy to remember, so you can start half way down.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417060" width="1" height="1">re: Mathematical formulas are designed to be pretty, not to be suitable for computationhttp://blogs.msdn.com/b/oldnewthing/archive/2013/05/08/10416823.aspx#10417055Wed, 08 May 2013 15:56:36 GMT91d46819-8472-40ad-a661-2c78acb4018c:10417055John Costello<p>Maurits -- that doesn't work unless you memoize, because it has exponential running time.</p>
<div class="post">[<em>Even if you memoize, it requires quadratic space and time. -Raymond</em>]</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10417055" width="1" height="1">