Arc Forumnew | comments | leaders | submitlogin
5 points by lacker 5989 days ago | link | parent

Hmm, this solution is not big-O-optimal. The solution you give is O(n^3) if you assume O(1) multiplies and divides, and since you are taking factorials that's probably not that great of an assumption either.

You can improve this by using the recursive formula for Pascal's triangle rather than the closed form. Specifically, n choose k equals (n-1) choose (k-1) + (n-1) choose k. Memoize and you can do (pascal-triangle n) in O(n^2), optimal since that's the amount of prints you have to do.

There is also probably an quicker formula for n choose k mod 2, if you don't have to print the entire triangle. Perhaps try using Legendre's formula for the largest power of a prime that divides a factorial.

see: http://mathworld.wolfram.com/Factorial.html

Also you might be able to find some useful recursive formula based on the fact that Pascal's triangle mod 2 looks like a Sierpinski triangle.



2 points by lacker 5989 days ago | link

Yeah here's a faster formula for n choose k mod 2 based on the sierpinski triangle interpretation. In pseudocode:

  def f(n, k):
    if n and k are both 0:
      return 1
    if n is even and k is odd:
      return 0
    return f(floor(n/2), floor(k/2))
Should be able to reduce this to bit operations if you really cared.

-----

3 points by almkglor 5989 days ago | link

  (def f (n k)
    (if
      (is n k 0)
        1
      (and (even n) (odd k))
        0
      ; else
        (f (round:/ n 2) (round:/ k 2)))) ; works if n and k are ints

-----

3 points by eds 5989 days ago | link

Not quite, since 'round returns the nearest even integer on halves. s/round/trunc/g gives the correct solution.

  arc> (round 4.5)
  4
  arc> (round 5.5)
  6
  arc> (trunc 4.5)
  4
  arc> (trunc 5.5)
  5

-----

2 points by bOR_ 5989 days ago | link

Ah.. I remember reading about the reasoning behind that (Round-to-even)

from: http://en.wikipedia.org/wiki/Rounding

  Although it is customary to round the number 4.5 up to 5, 
  in fact 4.5 is no nearer to 5 than it is to 4 (it is 0.5 
  away from both). When dealing with large sets of 
  scientific or statistical data, where trends are 
  important, traditional rounding on average biases the data
  upwards slightly. Over a large set of data, or when many 
  subsequent rounding operations are performed as in digital
  signal processing, the round-to-even rule tends to reduce 
  the total rounding error, with (on average) an equal 
  portion of numbers rounding up as rounding down. This 
  generally reduces upwards skewing of the result.

-----