English 中文(简体)
代码高尔夫:莱布尼兹公式求π
原标题:
  • 时间:2009-01-02 17:42:45
  •  标签:
Locked. This question and its answers are locked because the question is off-topic but has historical significance. It is not currently accepting new answers or interactions.

我最近在“你对编程有哪些争议性的看法?”发布了我最喜欢的面试白板编码问题之一,即使用Leibniz公式编写计算Pi的函数。

它可以通过不同的方式来实现,并且退出条件需要经过一些思考,所以我认为它可能会成为一个有趣的代码高尔夫问题。最短的代码赢!

鉴于Pi可以使用函数4 *(1-1 / 3 + 1/5-1/7 + ...)来估计,使用更多项可以提高精确性,请编写一个计算Pi值的函数,精度达到0.00001。

编辑:2008年1月3日。

正如评论所建议的那样,我将退出条件改为在0.00001内,因为这才是我真正想表达的意思(由于四舍五入精确到5位小数非常困难,因此我不想在面试中提出这个问题,而在0.00001内是一个更易于理解和实现的退出条件)。

此外,为了回答评论,我想我的意图是让解决方案计算迭代次数,或检查是否足够,但没有什么可以阻止你预先计算迭代次数并使用该数字。我真的是出于兴趣问这个问题,看看人们能想出什么。

最佳回答

J,14个字符

4*-/%>:+:i.1e6

解释

  • 1e6 is number 1 followed by 6 zeroes (1000000).
  • i.y generates the first y non negative numbers.
  • +: is a function that doubles each element in the list argument.
  • >: is a function that increments by one each element in the list argument.

因此,表达式>:+:i.1e6生成前一百万个奇数:

1 3 5 7 ... translates to "1 3 5 7 ..." in Chinese. It is a numerical sequence and does not have a distinct translation in Chinese.

  • % is the reciprocal operator (numerator "1" can be omitted).
  • -/ does an alternate sum of each element in the list argument.

因此,表达式-/%>:+:i.1e6生成了前一百万个奇数的倒数的交替和:

1 - 1/3 + 1/5 - 1/7 + ... can be translated into Chinese as: 1 - 1/3 + 1/5 - 1/7 + ... 1 - 1/3 + 1/5 - 1/7 + ... (yī jiǎn sān fēn jiā yī dì wǔ fēn jiǎ jiā yī dì wǔ)

  • 4* is multiplication by four. If you multiply by four the previous sum, you have π.

就是这样!J是数学方面有力的语言。


编辑:由于生成9!(362880)个项的交替和足以获得5位小数的精度,而且莱布尼兹公式也可以写成这样:

4 - 4/3 + 4/5 - 4/7 + ... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... 4-4/3+4/5-4/7+... Translated: 4-4/3+4/5-4/7+... translates to 4-4/3+4/5-4/7+...

你可以编写一个更短的,仅包含12个字符的程序:

-/4%>:+:i.9!
问题回答

语言:Brainfuck,字符数:51/59。

这算数吗? =]

因为Brainfuck中没有浮点数,所以让除法正常运行相当困难。咕噜。

不用换行 (51):

+++++++[>+++++++<-]>++.-----.+++.+++.---.++++.++++.

带换行符(59):

+++++++[>+++++++>+<<-]>++.-----.+++.+++.---.++++.++++.>+++.

Perl

26 chars

26 只是函数,27 用来计算,31 用于打印。

sub _{$-++<1e6&&4/$-++-&_}       # just the sub
sub _{$-++<1e6&&4/$-++-&_}_      # compute
sub _{$-++<1e6&&4/$-++-&_}say _  # print

28 chars

28次计算,34次打印。从评论中。注意此版本不能使用声音。

$.=.5;$=2/$.++-$for 1..1e6        # no print
$.=.5;$=2/$.++-$for$...1e6;print  # do print, with bonus obfuscation

36 chars

36只是计算,42打印。这是来自评论中Hudson对dreeves重新排列的看法。

$/++;$+=8/$//($/+2),$/+=4for$/..1e6
$/++;$+=8/$//($/+2),$/+=4for$/..1e6;print

关于迭代次数:就我数学记忆所及,400000已足够证明精确到0.00001。但是一百万(或低至8e5)实际上可以匹配小数点后5位,且字符数相同,因此我将保留一百万的迭代次数。

红宝石,33个字符

(0..1e6).inject{|a,b|2/(0.5-b)-a}

另一个C#版本:

Please provide more context or text to be translated.

4*Enumerable.Range(0, 500000).Sum(x => Math.Pow(-1, x)/(2*x + 1));  // = 3,14159

52个字符的Python:

print 4*sum(((-1.)**i/(2*i+1)for i in xrange(5**8)))

(51从xrange中删除x.) 51从xrange中删除x。

在Octave(或Matlab)中的36个字符:

l=0:5^8;disp((-1).^l*(4./(2.*l+1)) )

执行“format long;”以显示所有有效数字。省略disp,我们达到30个字符:

octave:5> l=0:5^8;(-1).^l*(4./(2.*l+1)) 
ans = 3.14159009359631

Oracle SQL (Oracle 结构化查询语言)

select -4*sum(power(-1,level)/(level*2-1)) from dual connect by level<1e6

Language: C, Char count: 71

float p;main(i){for(i=1;1E6/i>5;i+=2)p-=(i%4-2)*4./i;printf("%g
",p);}

Language: C99, Char count: 97 (including required newline)

#include <stdio.h>
float p;int main(){for(int i=1;1E6/i>5;i+=2)p-=(i%4-2)*4./i;printf("%g
",p);}

I should note that the above versions (which are the same) keep track of whether an extra iteration would affect the result at all. Thus, it performs a minimum number of operations. To add more digits, replace 1E6 with 1E(num_digits+1) or 4E5 with 4E(num_digits) (depending on the version). For the full programs, %g may need to be replaced. float may need to be changed to double as well.

Language: C, Char count: 67 (see notes)

double p,i=1;main(){for(;i<1E6;i+=4)p+=8/i/(i+2);printf("%g
",p);}

This version uses a modified version of posted algorithm, as used by some other answers. Also, it is not as clean/efficient as the first two solutions, as it forces 100 000 iterations instead of detecting when iterations become meaningless.

Language: C, Char count: 24 (cheating)

main(){puts("3.14159");}

Doesn t work with digit counts > 6, though.

Haskell

I got it down to 34 characters:

foldl subtract 4$map(4/)[3,5..9^6]

This expression yields 3.141596416935556 when evaluated.

Edit: here s a somewhat shorter version (at 33 characters) that uses foldl1 instead of foldl:

foldl1 subtract$map(4/)[1,3..9^6]

Edit 2: 9^6 instead of 10^6. One has to be economical ;)

Edit 3: Replaced with foldl and foldl1 with foldl and foldl1 respectively—as a result of Edit 2, it no longer overflows. Thanks to ShreevatsaR for noticing this.

23 chars in MATLAB:

a=1e6;sum(4./(1-a:4:a))

F#:

Attempt #1:

let pi = 3.14159

Cheating? No, its winning with style!

Attempt #2:


let pi =
    seq { 0 .. 100 }
    |> Seq.map (fun x -> float x)
    |> Seq.fold (fun x y -> x + (Math.Pow(-1.0, y)/(2.0 * y + 1.0))) 0.0
    |> (fun x -> x * 4.0)

Its not as compact as it could possibly get, but pretty idiomatic F#.

common lisp, 55 chars.

(loop for i from 1 upto 4e5 by 4 sum (/ 8d0 i (+ i 2)))

Mathematica, 27 chars (arguably as low as 26, or as high as 33)

NSum[8/i/(i+2),{i,1,9^9,4}]

If you remove the initial "N" then it returns the answer as a (huge) fraction.

If it s cheating that Mathematica doesn t need a print statement to output its result then prepend "Print@" for a total of 33 chars.

NB:

If it s cheating to hardcode the number of terms, then I don t think any answer has yet gotten this right. Checking when the current term is below some threshold is no better than hardcoding the number of terms. Just because the current term is only changing the 6th or 7th digit doesn t mean that the sum of enough subsequent terms won t change the 5th digit.

Using the formula for the error term in an alternating series (and thus the necessary number of iterations to achieve the desired accuracy is not hard coded into the program):

public static void Main(string[] args) {
    double tolerance = 0.000001;
    double piApproximation = LeibnizPi(tolerance);
    Console.WriteLine(piApproximation);
}

private static double LeibnizPi(double tolerance) {
    double quarterPiApproximation = 0;

    int index = 1;
    double term;
    int sign = 1;
    do {
        term = 1.0 / (2 * index - 1);
        quarterPiApproximation += ((double)sign) * term;
        index++;
        sign = -sign;
    } while (term > tolerance);

    return 4 * quarterPiApproximation;
}

C#:

public static double Pi()
{
    double pi = 0;
    double sign = 1;
    for (int i = 1; i < 500002; i += 2)
    {
        pi += sign / i;
        sign = -sign;
    }
    return 4 * pi;
}

Perl :

$i+=($_&1?4:-4)/($_*2-1)for 1..1e6;print$i

for a total of 42 chars.

Ruby, 41 chars (using irb):

s=0;(3..3e6).step(4){|i|s+=8.0/i/(i-2)};s

Or this slightly longer, non-irb version:

s=0;(3..3e6).step(4){|i|s+=8.0/i/(i-2)};p s

This is a modified Leibniz:

  1. Combine pairs of terms. This gives you 2/3 + 2/35 + 2/99 + ...
  2. Pi becomes 8 * (1/(1 * 3) + 1/(5 * 7) + 1/(9 * 11) + ...)

F# (Interactive Mode) (59 Chars)

{0.0..1E6}|>Seq.fold(fun a x->a+ -1.**x/(2.*x+1.))0.|>(*)4.

(Yields a warning but omits the casts)

Here s a solution in MUMPS.

pi(N)
 N X,I
 S X=1 F I=3:4:N-2 S X=X-(1/I)+(1/(I+2))
 Q 4*X

Parameter N indicates how many repeated fractions to use. That is, if you pass in 5 it will evaluate 4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11)

Some empirical testing showed that N=272241 is the lowest value that gives a correct value of 3.14159 when truncated to 5 decimal points. You have to go to N=852365 to get a value that rounds to 3.14159.

C# using iterator block:

static IEnumerable<double> Pi()
{
    double i = 4, j = 1, k = 4;
    for (;;)
    {
        yield return k;
        k += (i *= -1) / (j += 2);
    }
}

For the record, this Scheme implementation has 95 characters ignoring unnecessary whitespace.

(define (f)
  (define (p a b)
    (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) (p (+ a 4) b))))
  (* 8 (p 1 1e6)))

Javascript:

a=0,b=-1,d=-4,c=1e6;while(c--)a+=(d=-d)/(b+=2)

In javascript. 51 characters. Obviously not going to win but eh. :P

Edit -- updated to be 46 characters now, thanks to Strager. :)


UPDATE (March 30 2010)

A faster (precise only to 5 decimal places) 43 character version by David Murdoch

for(a=0,b=1,d=4,c=~4e5;++c;d=-d)a-=d/(b-=2)

Here s a recursive answer using C#. It will only work using the x64 JIT in Release mode because that s the only JIT that applies tail-call optimisation, and as the series converges so slowly it will result in a StackOverflowException without it.

It would be nice to have the IteratePi function as an anonymous lambda, but as it s self-recursive we d have to start doing all manner of horrible things with Y-combinators so I ve left it as a separate function.

public static double CalculatePi()
{
    return IteratePi(0.0, 1.0, true);
}

private static double IteratePi(double result, double denom, bool add)
{
    var term = 4.0 / denom;
    if (term < 0.00001) return result;    
    var next = add ? result + term : result - term;
    return IteratePi(next, denom + 2.0, !add);
}

Most of the current answers assume that they ll get 5 digits accuracy within some number of iterations and this number is hardcoded into the program. My understanding of the question was that the program itself is supposed to figure out when it s got an answer accurate to 5 digits and stop there. On that assumption here s my C# solution. I haven t bothered to minimise the number of characters since there s no way it can compete with some of the answers already out there, so I thought I d make it readable instead. :)

    private static double GetPi()
    {
        double acc = 1, sign = -1, lastCheck = 0;

        for (double div = 3; ; div += 2, sign *= -1)
        {
            acc += sign / div;

            double currPi = acc * 4;
            double currCheck = Math.Round(currPi, 5);

            if (currCheck == lastCheck)
                return currPi;

            lastCheck = currCheck;
        }
    }

Language: C99 (implicit return 0), Char count: 99 (95 + 4 required spaces)

exit condition depends on current value, not on a fixed count

#include <stdio.h>

float p, s=4, d=1;
int main(void) {
  for (; 4/d > 1E-5; d += 2)
        p -= (s = -s) / d;
  printf("%g
", p);
}

compacted version

#include<stdio.h>
float
p,s=4,d=1;int
main(void){for(;4/d>1E-5;d+=2)p-=(s=-s)/d;printf("%g
",p);}

Language: dc, Char count: 35

dc -e  9k0 1[d4r/r2+sar-lad274899>b]dsbxrp 

Ruby:

irb(main):031:0> 4*(1..10000).inject {|s,x| s+(-1)**(x+1)*1.0/(2*x-1)}
=> 3.14149265359003

64 chars in AWK:

~# awk  BEGIN {p=1;for(i=3;i<10^6;i+=4){p=p-1/i+1/(i+2)}print p*4} 
3.14159

C# cheating - 50 chars:

static single Pi(){
  return Math.Round(Math.PI, 5));
}

It only says "taking into account the formula write a function..." it doesn t say reproduce the formula programmatically :) Think outside the box...

C# LINQ - 78 chars:

static double pi = 4 * Enumerable.Range(0, 1000000)
               .Sum(n => Math.Pow(-1, n) / (2 * n + 1));

C# Alternate LINQ - 94 chars:

static double pi = return 4 * (from n in Enumerable.Range(0, 1000000)
                               select Math.Pow(-1, n) / (2 * n + 1)).Sum();

And finally - this takes the previously mentioned algorithm and condenses it mathematically so you don t have to worry about keep changing signs.

C# longhand - 89 chars (not counting unrequired spaces):

static double pi()
{
  var t = 0D;
  for (int n = 0; n < 1e6; t += Math.Pow(-1, n) / (2 * n + 1), n++) ;
  return 4 * t;
}
#!/usr/bin/env python
from math import *
denom = 1.0
imm = 0.0
sgn = 1
it = 0
for i in xrange(0, int(1e6)):
    imm += (sgn*1/denom)
    denom += 2
    sgn *= -1    
print str(4*imm)




相关问题
热门标签