Writing a Compiler for Verilog – part 1

February 9, 2010 Mithrandir 2 comments

This year, I took a class named Numerical Computers II (I had Numerical Computers I last year). The course was about Computer Architecture and things like this. However, I ended up with a very fascinating homework: to write a compiler for Verilog in a team of 2 to 4 people. The deadline is coming soon (I have to finish it by Friday) but I need a break so I’ll post here my story.

Read more…

Segmented Sieve Of Eratosthenes

February 5, 2010 Mithrandir Leave a comment

Today’s Programming Praxis problem describes an algorithm which may be used to find the prime numbers in a large interval, so large that it cannot be kept in memory at once. See their description there, I’ll only give the code in Haskell.

First, some utility functions:

firstQ :: Int -> Int -> Int
firstQ l pk = (-(1+l+pk) `div` 2) `mod` pk
 
nextQ :: Int -> Int -> Int -> Int
nextQ b pk qk = (qk - b) `mod` pk

Then we sieve one block and convert the values to the primes:

sieveBlock :: [Int] -> [Int] -> [Int] -> [Int]
sieveBlock [] [] blk = blk
sieveBlock (p:ps) (o:ofs) blk = filter f (sieveBlock ps ofs blk)
  where
    f x = (x < o) || ((x - o) `mod` p /= 0)
 
getValsfromBlock :: Int -> [Int] -> [Int]
getValsfromBlock l bl = map (\x->l+1+2*x) bl

Now, it’s time to obtain all the numbers. This post will make use of the until function which is very similar to what some will use for the `for` construct in C.

sieve :: Int -> Int -> Int -> [Int] -> [Int]
sieve l r b primes = middle $ until stop incr start
  where
    middle (_, v, _) = v
    stop (sb, _, _) = sb == r
    start = (l, [], map (firstQ l) primes)
    incr (startblock, primessofar, q) = (nextblock, nextprimes, nextq)
      where
        array = [0 .. b-1]
        nextblock = startblock + 2 * b
        nextprimes = primessofar ++ (getValsfromBlock startblock bl)
        nextq = zipWith (nextQ b) primes q
        bl = sieveBlock primes q array

The main is very simple after we know about the print function and that it is a monadic one

main = print $ sieve 100 20000 10 [3, 5, 7, 11, 13]

That’s all for now.

Formal Languages and Books

February 4, 2010 Mithrandir 1 comment

I’ve read two books in the last days. Both are related to Formal Languages, Automata Theory and Compilers. This will be another review article.

Read more…

A Strange Machine

February 2, 2010 Mithrandir 2 comments

Another Haskell puzzle. This time, we have a 2D square matrix. Each cell can contain a number. We have a cursor which always resides in one cell of the matrix. Let s be the sum of values contained in the 8 neighbouring cells and the cursor’s cell. At each update step, we will modify the cell under cursor by using a bijective function of s. After this, we change the cursor location by moving it to a neighbouring cell or leaving it as it is, depending on the value of its cell.

We have to simulate such a machine, assuming that the matrix wraps at the boundary.

Read more…

Learn the Tools of Open Trade

February 1, 2010 Mithrandir Leave a comment

Today, we (members from ROSEdu) started accepting applications for the second edition of CDL. I’ll be back soon with another Haskell puzzle.

The Monad Reader – Issue 15

January 26, 2010 Mithrandir Leave a comment

Today, Brent Yorgey announced a new issue of «The Monad Reader». The waiting of 10 days since submission deadline and today was worth it: a project from Google Summer of Code (Gergely Patai – a new profiler for Haskell), 3 useful monads (Edward Z. Yang – Logic, Prompt and Failure) – of which the Prompt Monad will be used in a personal project, hopefully before April -, a new way to write monads (Heinrich Apfelmus – an operational view of monads) and a nice implementation of STM in pure Haskell (Andrew Coppin).

I’ll be back shortly.

Categories: Reviews Tags:

A General Network Module

January 25, 2010 Mithrandir 1 comment

Let’s say we need to solve a problem involving a graph-like structure, possibly containing cycles. We want to do this in a functional way (Haskell) but we are stuck when we deal with the cycles.

Read more…

Numbers, exponents and cycles

January 16, 2010 Mithrandir 9 comments

Suppose we have a number N_0. We apply the following procedure to N_0 in order to obtain a new number N_1: we take N_0’s digits and raise them alternatively to 2 and 4, summing the results. Thus, N_0=2435 will become N_1=2^4+4^2+3^4+5^2=138. We don’t stop here. Instead, we apply the same procedure to N_1 obtaining N_2=1^2+3^4+8^2=146.

Of course, and someone can prove it, this procedure will quickly lead either to a number already seen or to 1. For now, we are only interested in the number of iterations required for this.

Read more…

Categories: Puzzles Tags:

A New Kind of Science

January 10, 2010 Mithrandir 1 comment

I’ve managed to read Stephen Wolfram’s book (pdf version, 20 to 30 pages in a week due to a busy schedule). I can say that it was a new kind of experience.

Read more…

Categories: Reviews

A Puzzle and a Solution (2)

January 1, 2010 Mithrandir Leave a comment

Last post was ended with a problem: our solution exhausted the memory before it could give an answer to N=1000, P=42. There were three comments trying to solve them and the last two of them are working. However, the solution involving the lcm of cycles is faster and I will post it here (the other one is posted as a comment there).

Read more…