Arc Forum | Arc Programming Assignment

Arc Forum

Arc Programming Assignment

7 points by eds 6049 days ago | 15 comments

I can now say I have used Arc for programming assignments for classes in school! (Since the professor said I could use any language, I figured I should take advantage of the opportunity.)

I'd post the code, but it wasn't really that interesting (just a algorithm for computing Pascal's triangle, mod 2). Although I did enjoy having completed the assignment in about half as much code as anyone else in the class (since everyone else I knew wrote their program in Java).

EDIT: On second thought, here is the code. If anyone has suggestions for improving or shortening it, please post them.

  (def factorial (n)
    (if (> n 0)
        (* n (factorial (- n 1)))
        1))
  
  (def choose (n k)
    (/ (factorial n) (factorial k) (factorial (- n k))))
  
  (def indices (n)
    (map (let n -1 [++ n]) (n-of n nil)))

  (def pascal-triangle (n)
    (for i 0 n
         (apply prs (map [mod (choose i _) 2] (indices (+ i 1))))
         (prn)))
  
  (pascal-triangle 64)

5 points by lacker 6047 days ago | link

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

-----

3 points by jmatt 6047 days ago | link

This is readable and just fine if you are handing it in for a class.

The benefit of the pascal triangle is that through a simple number triangle you can find binomial coefficients. It has since been redefined as the binomial coefficient. But historically it was interesting because it could provide binomial coefficients through simpler math than n choose k.

If you have to calculate the whole triangle, then I would probably recursively define it and calculate it that way. (Pascal's formula shows that each subsequent row is obtained by adding the two entries diagonally above) Instead of constantly calculating it at each position with n choose k.

I guess you could use the binomial coefficient definition and memoize the choose and factorial. Memoization alone is what is saving you here. Luckily arc provides this functionality.

Anyways, this is a fun problem. Much easier to solve elegant and efficiently in arc, thanks to memoize. Try this in an imperative language and you'll definitely have to fall back on the recursive definition because all those factorials and chooses will kill the performance. There is one other benefit to using the recursive definition - you won't use any extra memory memoizing factorials. Instead you'll just have the chooses appearing in the tree.

-----

1 point by lacker 6046 days ago | link

A bit nit picky, but memoization alone won't make the solution optimal, since you are dealing with very large numbers. n! has O(n log n) digits, so in the limit it will take O(n log n) time just to calculate n! from n * (n-1)!.

-----

1 point by jmatt 6045 days ago | link

I agree memoization isn't optimal.

But I don't know about your big-O estimate. Since the triangle is constructive and you are memoizing calculating n! from n * (n - 1)! will take O(1). It'll be the cached (n - 1)! value times n.

-----

1 point by lacker 6040 days ago | link

Doing a single multiplication is not O(1) when the numbers have more than a constant number of digits. I'm not precisely sure how long multiplying large numbers takes, but it's at least linear in the number of digits involved. And (n-1)! has O(n log n) digits.

-----

1 point by eds 6045 days ago | link

I don't follow how n! has O(n log n) digits. Mind explaining?

-----

2 points by lacker 6040 days ago | link

No prob. Sorry if I go on at too much length here ;-)

So a useful formula for counting digits is, a positive integer x has floor(log10(x)) + 1 digits. You can figure this out yourself by thinking, where does the digit-counting function bump up a notch? At 10, 100, 1000, etc. So asymptotically the number of digits in x is O(log x).

So n! has O(log n!) digits. The trickier part is figuring out or knowing that O(n log n) = O(log n!). Using log ab = log a + log b you can expand out the factorial:

  O(log n!) = O(log (n * (n-1) * ... * n * 1))
            = O(log n + log (n-1) + ... + log 2 + log 1)
            = O(n log n)

In case the last step isn't clear, you can do this splitting-in-half bounding trick. Since each element in the sum is less than log n you can bound from above with

  log n + log (n-1) + ... + log 2 + log 1 < n log n

And if you just take the larger half of the list you can bound from below with

  log n + log (n-1) + ... + log 2 + log 2 > log n + log (n-1) + ... + log (n/2)
                                          > (n/2) log (n/2)

which is itself O(n log n). So O(log n!) = O(n log n).

In general the rules of thumb you use to reduce O(log n!) are:

  1. complicated expressions inside factorials are ugly, you should simplify them
  2. O(sum of n things) is usually O(n * the biggest thing)

Make sense?

-----

1 point by kens 6045 days ago | link

You're multiplying O(n) numbers, each of which is O(log n) digits long, so the result is O(n log n) digits long.

-----

1 point by shader 6045 days ago | link

Usually, it seems to be either (n log n) or (n log n) - 1 digits.

And usually in this case I would leave of the O, as that usually refers to the performance of an algorithm in time or space. I suppose you could construe the number of digits to be "space" but multiplying O(n) numbers doesn't make that much sense.

-----

3 points by almkglor 6049 days ago | link

Use:

  (range 0 i)

instead of:

  (indices (+ i 1))

If you're willing to wait for your code to compile, you can even use Anarki, (require "ssyntaxes.arc"), and use:

  0..i

instead of:

  (indices (+ i 1))

Edit: Also, factorial is pure anyway, so you might have some performance improvement by using defmemo instead of plain def.

Edit2: It's also better to use true tail recursion:

  (def factorial (n)
    ((afn (acc n)
      (if (< n 2)
          acc
          (self (* acc n) (- n 1))))
      1 n))

-----

2 points by almkglor 6049 days ago | link

Here's a version that can actually be compiled by arc2c:

  (def prsall (rest)
    (if rest
      (do (pr (car rest) #\space)
          (prsall:cdr rest))))

  (def map (f l)
    (if l
      (cons (f:car l) (map f (cdr l)))))

  (def factorial (n)
    (if (> n 0)
        (* n (factorial (- n 1)))
        1))

  (def choose (n k)
    ; arc2c only supports two-arg forms for math
    (/ (/ (factorial n) (factorial k))
       (factorial (- n k))))

  (def indices (n)
    (let self nil
      ; no support for '= yet
      (set self
        (fn (i)
          (if (isnt i n)
              (cons i (self (+ i 1))))))
      (self 0)))

  (def pascal-triangle (n)
    (let self nil
      (set self
        (fn (i)
          (if (<= i n)
              (do
                ; Anarki make-br-fn not supported yet
                (prsall (map (fn (_) (mod (choose i _) 2)) (indices (+ i 1))))
                (prn)
                (self (+ i 1))))))
      (self 0)))

  (pascal-trangle 4)

If you're feeling particularly nasty, you can get the C output from arc2c and pass that ^^

-----