In his seminal paper Kenneth Iverson described a new mathematical notation which soon became A Programming Language.
Recently, while reading Surely You’re Joking, Mr. Feynman!, I found that Feynman invented his own notation when he was in school.
In his seminal paper Kenneth Iverson described a new mathematical notation which soon became A Programming Language.
Recently, while reading Surely You’re Joking, Mr. Feynman!, I found that Feynman invented his own notation when he was in school.
Cliff Pickover twitted a fun puzzle: Which series is bigger?
The first one is the famous geometric series which sum is equal to 1. The second one seems to be bigger because 1 < n, except for the 0th term, but that 0th term makes a big difference.
While I was working through the chapter 5.3 of SICP, I created small visualization of the stopandcopy garbage collection algorithm.
I start with the following memory structure example.
The content of the root
register is a pointer p4
to the list of registers (x y z)
. The register x
points to address 6 where improper list (1 . 2)
saved. The register y
points to address 8 where list (x x)
starts. Finally, the register z
points to address 10 where list (3 4 5)
starts. Addresses 1, 3, 5, 9, 11, 13, 15 contain garbage.
After we ran the GC algorithm, we got the following memory structure.
root
now points to address 0, x
to 1, y
to 3, and z
to 6.
In the previous post we discussed the discrete Fourier transform (DFT). Its J implementation was pretty straightforward, and the program looked almost identical to its mathematical definition. In this post, I want to explore how to implement fast Fourier transform (FFT), a recursively defined version of DFT that reduces algorithmic complexity from $O(n^2)$ to $O(N\log{N})$.
Recall the DFT formula from the previous post
I use a slightly different notation here to make recursive definition easier to understand.
We assume that N is a power of 2. Using basic arithmetic and properties of complex exponentials, we can derive the formula for the DFT of order 2N in terms of two DFTs of order N
where $m=0,\dots,N1$. The base case, when $N=1$, is
i.e. the identity function.
The Fourier analysis in general and the Fourier transform in particular has always been one of my favourite topics in mathematics. When I started learning the J programming language I thought that implementing the discrete Fourier transform (DFT) in J must be really elegant. One rainy weekend I finally found time to do that, and this post is a result of my experiments.
The definition of onedimensional DFT is pretty simple. It is just a function that maps a given vector f of length N to a vector F of the same length by the following formula
To implement this formula the only thing we need is basic arithmetic for complex numbers. Not only does J provide such an arithmetic, it has special code for complex exponentiation, which makes the implementation much easier than it would be in other languages.
Before we start coding let’s rewrite the formula in terms of matrix multiplication so that we can utilize this feature of J. Let $\omega$ be the primitive Nth root of unity $\omega = e^{2\pi i/N}$, then the DFT formula becomes
where f is an input vector and $\Omega$ is a symmetric matrix $(\omega^{mn})$ with $m,n=0,\dots,N1$.
For the last four months I’ve been actively involved in organizing EFL in Toronto. Now when the conference is over I want to take a few minutes to express my appreciation to all the people who made it happen.
My big thank you goes to (in alphabetical order)
Thank you all! Without you this conference wouldn’t be possible.
I’ve recently hit on a nasty bug in Java. It sits in Date
class and shows up only at noon!
I’m going to demonstrate it using Groovy shell, but you can reproduce it in plain Java environment too.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 

So far so good.
I chose a specific formatter on line 1 to make the bug even more evident. With this formatter lines 5, 8, and 11 must be identical on my machine, and they are in this example. The assertion on line 13 also proves the equality.
Now let’s change the example date to one hour earlier
1 2 3 4 5 6 7 8 

Lines 2, 5, and 8 are not identical any more. The String representation of the date is 12 hours off.
To make sure the problem is in toString
and not in parse
, let’s format the date using formatter
1 2 

Looks good. The problem is in toString
indeed. Or is it?
Let’s parse 13 o’clock date and 12 o’clock date. The difference between them should be 1 hour. In reality
1 2 3 4 5 6 7 8 

Wow, the problem is actually in parse
. Then how come the format
returned the correct value? That’s still a mystery to me.
I’m actually quite surprised that this bug survived through JDK 1.7.0_09, and neither Sun nor Oracle hasn’t fixed it yet.
This is my impressionistic noncanonical irregular ClojuresqueErlangish notes on Lambda Jam conference which took place in Chicago on July 8–10, 2013. These notes are pretty long, and I don’t split them on purpose. If you read them all, you should become overwhelmed and overloaded with the information. Only this way you can feel the same I felt on the last day of the conference :)
After working on Sleeping Barber problem at Coding Dojo I decided to implement it in Erlang. Because Erlang is the perfect language for these sorts of problems, many people have alredy solved it in many different ways. I found at least three groups of solutions: 1) direct implementation using message passing between processes, 2) OTP solution using gen_server, and 3) something resembling objectoriented approach.
Strangely enough, I didn’t see any solution based on FSM. That is odd because this is the first thing coming to my mind when I hear this problem. To fill the gap, I’m going to solve it using gen_fsm, which is a standard OTP behaviour for FSM.
Rod Johnson, creator of Spring, programmer that became entrepreneur:
One thing I think that you really need to be careful of as well, particularly if you, like me, are a programmer, is don’t get carried away writing code. Typically in my experience anyone who is a good programmer is pretty passionate about it, love writing code, get addicted to the process of writing code, fell pretty good about their code basis. As soon as you get down that path you are not thinking straight anymore and now you are increasing your emotional investment, you are having lots of fun writing interesting code and you are no longer in a place mentally where you are going to be trying to find some reason that you shouldn’t write that code. That has been a big lesson for me that the quicker I get to coding, the longer it takes me to ask the kind of questions I should ask upfront.
Linus Torvalds, creator of Linux, programmer that still programs:
I’m interested in programming. When business started happening, I didn’t get into this for the business side. I wanted to do programming. When other people started selling Linux, I said “Yes! Now I can avoid caring about that side too.”
I never had to deal with single business related thing in Linux ever. Seriously, I had to deal with lot of other things but business related things… I got queries and I just said “I don’t care.”