Arc Forumnew | comments | leaders | submitlogin
2 points by lacker 6044 days ago | link | parent

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 6044 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 6044 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_ 6044 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.

-----