Code and Bugs

Coding things

Category: Questions of a Beginner

Writing a Compiler for Verilog – part 2

As previously stated, I am working on a Verilog Compiler in Python using PLY. The last article talked in a generic way about the project, from now on we will talk about specific parts of the compiler.

Today, we begain with the first part of any compiler: the lexing part.

Read the rest of this entry »

Writing a Compiler for Verilog – part 1

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 the rest of this entry »

Segmented Sieve Of Eratosthenes

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.

A Strange Machine

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 the rest of this entry »

Learn the Tools of Open Trade

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

A General Network Module

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 the rest of this entry »

A Puzzle and a Solution (2)

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 the rest of this entry »

A Puzzle and a Solution

Let’s say we have a number N of children placed in a circle and playing the following simple game: proceeding around the circle they kick out every Pth of them (of course, P < N).

Of course, what we will obtain is a permutation of the first N natural numbers. The puzzle asks for the order of this permutation (that is the number of times it must be applied to itself to get back to an ordered list.

Read the rest of this entry »

Verilog and VHDL on Linux (Ubuntu)

For those interested in programming electronic components there is always the possibility to use Xilinx if you are on Windows. Of course, there is a Xilinx port for Linux but it is buggy application and a very large download. This article aims to give an alternative to this application. One that will need only a few KB of download from an apt-get source.

Read the rest of this entry »

Uniformity

Suppose we have to make a quiz. The questions have different degrees of difficulty and come from several different chapters. We have the following problem:How can we ensure that we select the questions uniformly from both domains?

Read the rest of this entry »

Follow

Get every new post delivered to your Inbox.