Chewing The Cud

I have been working on Project Euler problems for a while now and many of them have centered around prime numbers. I’ve referenced my work with the sieve in other posts but found with a particular problem that some of my functions could benefit from some state being saved (namely the sieve being saved and not re-computed each time).

The problem called to count prime factors of numbers and find consecutive numbers that had the same count of prime factors. My primes module had a prime_factors/1 function that would compute the prime factors and the exponents of those factors (so 644 = 2² * 7 * 23, and primes:prime_factors(644) would return [{2,2},{7,1},{23,1}]. The prime_factors/1 looked something like this:

prime_factors(N) ->
    CandidatePrimes = prime_factors(N, primes:queue(N div 2)),
    PrimeFactors = [ X || X < - CandidatePrimes, N rem X =:= 0 ],
    find_factors(PrimeFactors, N, 0, []).

The call to find_factors/4 takes the factors and finds the exponents and can be ignored for now. The time sink, then, is in generating the CandidatePrimes list. I think my primes:queue/1 function is pretty fast at generating the sieve, and dividing N by two eliminates a lot of unnecessary computation, but when you’re calling prime_factors/1 thousands of times, the call to queue/1 begins to add up. This is where I needed to save some state (the sieve) in between calls. Erlang, fortunately enough, has a module behavior called gen_server that abstracts away a lot of the server internals and lets you focus on the business bits of the server. I won’t discuss it much here as I’m not an authority on it, but Joe Armstrong’s book and the Erlang docs have been a great help in understanding what’s happening behind the scene. You can view the prime_server module to see what its current state is code-wise.

To speed up prime_factors/1, I split it into two functions prime_factors/1 and prime_factors/2. The functions look like this:

prime_factors(N, CandidatePrimes) ->
    PrimeFactors = [ X || X < - CandidatePrimes, N rem X =:= 0 ],
    find_factors(PrimeFactors, N, 0, []).
 
prime_factors(N) ->
    prime_factors(N, primes:queue(N div 2)).

Now, if we don't need to save the queue between calls you can still call prime_factors/1 as usual. The prime_server module utilizes the prime_factors/2 function because it initializes its state to contain a primes sieve (either all primes under 1,000,000 if no arg is passed to start_link, or all primes =< N when using start_link/1) and the current upper bound. Now when the server handles the call for getting the factors, we pass a pared down list of primes to prime_factors/2 and get a nice speed boost.

Well, the heavy lifting is front-loaded in the initialization of the server (generating the sieve) and in calls that increase the sieve's size. One improvement there might be to save the Table generated during the initial sieve creation and start the loop back up from where it left off (when N > UpTo) but that is for another time. If you choose your initial value for start_link right, regenerating the sieve should be unnecessary.

The last speed boost was noticing that calculating the exponents was an unnecessary step so I wrote a count_factors/1 and count_factors/2 that skips the call to find_factors/4 and returns the length of the list comprehension.

With these changes complete, problem 47 went from taking well over 5 minutes to just under 20 seconds to solve brute force.

I am posting this short message from emacs using the weblogger.el package.

Cool!

Working through the Project Euler again and using Erlang to do so, there are quite a few problems that deal with primes. It is important, then, to have a library of functions that make generating and validating primes easy. A typical method for generating primes is using the Sieve of Eratosthenes. As discussed in the wiki article, Melissa O’Neill has shown the given Haskell implementation is not a true implementation, and shows a couple versions that are more true to the algorithm and more performant. I took the implementation she described using a priority queue on page 7 of the pdf. I used a skew heap implementation I found as the priority queue, modified it slightly to handle a Key and a Value parameter, and away I went.

Here’s the implementation I came up with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

%% primes.erl
-module(primes).
 
-export([queue/1]).
 
queue(N) ->
    sieve_queue(lists:seq(2, N)).
 
sieve_queue([]) ->
    [];
sieve_queue([X|XS]) ->
    Table = insert_prime(X, skew_kv:empty()),
    [X | sieve_queue(XS, Table)].
 
insert_prime(P, Table) ->
    skew_kv:insert(P*P, from(P*P, P), Table).
 
sieve_queue([], _Table) ->
    [];
sieve_queue([X|XS], Table) ->
    {NextComposite, _Value} = skew_kv:min(Table),
    case  NextComposite =< X of
        true -> sieve_queue(XS, adjust(Table, X));
        _Else -> [X | sieve_queue(XS, insert_prime(X, Table))]
    end.
 
adjust(Table, X) ->
    {N, [Nprime | NS]} = skew_kv:min(Table),
    case N =< X of
        true ->
            T = skew_kv:delete_min(Table),
            T2 = skew_kv:insert(Nprime, NS(), T),
            adjust(T2, X);
        _Else -> Table
    end.
 
%% from http://www.erlang.org/cgi-bin/ezmlm-cgi?4:mss:177:khdaceipfabbicmifdhf
%% a lazy list that starts at K and increments by Inc
from(K, Inc) ->
    [K|fun()-> from(K+Inc, Inc) end].

I tried to keep variable names similar to the O’Neill implementation, but I have modified it a bit to use lazy lists, Erlang-style. Not being familiar with Haskell, I think lists there are defined lazily by default, but Erlang needs an explicit construct to do lazy lists. Fortunately, it isn’t terribly hard. So, the code!

I named the function queue because I was implementing prime number generators using other methods from the paper (the unfaithful sieve and a sieve with a map instead of a queue), hence why you need to call the function with:

1> primes:queue(10).

I don’t think I’ll expound on the why, as O’Neill does a nice job explaining it in her paper, so I’ll focus on the how and leave it to the reader to learn the why.

My insert_prime function differs from the O’Neill insertprime because mine has to account for Erlang-style lazy lists. My assumption is that the map call in O’Neill’s creates a lazy list and so all the mappings are not computed, since XS is a potentially huge list of numbers. Instead, I observed that those lists are created by the map call are arithmetic progressions that start at p*p and increase by p. My simple lazy list that accomplishes this is called from/2, which I got from a Joe Armstrong suggestion and adapted to my needs.

Let’s take a quick look at from/2. We pass in a number K and an increment Inc and return a list with K at the head and a fun as the tail. The fun wraps a call to from/2, which acts as the iterator for the lazy list. So evaluating

1> primes:from(2, 2).
[2|#Fun<primes .1.47942561>]
</primes>

Here’s an example showing the iterator in action:

57> [K|F1] = primes:from(2, 2).
[2|#Fun<primes .1.47942561>]
58> [K2|F2] = F1().
[4|#Fun</primes><primes .1.47942561>]
59> [K3|F3] = F2().
[6|#Fun</primes><primes .1.47942561>]
60> 
</primes>

This lazy list is stored in the queue as the value (line 16) for the key P*P. The lazy list is then used in the adjust/2 function when we want to compare the smallest key of the queue to the current number we’re evaluating. Line 28 extracts the K into Nprime, and the fun into NS, from the from/2 call earlier. Line 32 shows how to get the next number in the lazy list, NS(), which returns [K+Inc | fun()], and inserts it as the value into the queue. Again, for the why, consult the O’Neill paper.

Otherwise, the implementation is roughly the same. There are some improvements and optimizations that could be made, I’m sure, but for a rough draft, it is fairly speedy, minimal memory usage, and for Project Euler, it is more than adequate in producing the primes I need to solve the problems.

I want to learn Spanish, and while I wish I could just move somewhere and be immersed, that is not feasible at this juncture. So I am reaching out to the open source world to help me along.

The first step was to get a flashcard-like system that would provide me with a way to test my vocabulary and keep track of my progress. To that end, I have installed Mnemosyne. Read all about it because it is a pretty groovy program for flashcard learning. I then downloaded and installed the four Spanish card packages available through the site. As you can see on the left, the site has many languages supported, as well as a variety of other topics to study (including Swedish road signs).

This gives me my base of vocabulary and expressions. Second on the list of tools is the Firefox plugin ImTranslator. This is a great plugin for doing on the fly translations. So when I browse a site in Spanish, or come across something I want to know how to say in Spanish, this plugin gets me going in the right direction.

Using the default media player in Ubuntu, Rhythmbox and its ability to play online radio stations, I’ve searched for and subscribed to several Spanish music and news sites. So now I get to hear music, news, and commercials in several different Spanish cities (Madrid and Barcelona stations currently, though I plan to get some Central and South American stations since that’s where I’ll likely travel to first).

And, for some extra vocab, I signed up with the Spanish Word-a-Day mailing list. I’ve really enjoyed the emails as they have a word, pronunciation guide, synonyms, the word in a sentence, and usually some Spanish trivia, like a joke, expression, or conjugation table for a verb/tense.

The most important piece, however, is actually conversing with native speakers, and I am lucky to have a Mexican restaurant across the street with several native speakers who I’ve gotten to know.

Any other tools you suggest? I think my next one will be finding folks who speak both English and Spanish and chatting with them via GChat or Skype.

A template for a resolution for you to send to your state legislature requiring the Federal Government to reign itself back into it’s Constitutional constraints and cease imposing its will on the States. Remember, the Federal Government is an agent of the States, not the other way around.

• WHEREAS, the Tenth Amendment to the Constitution of the United States reads as follows: “The powers not delegated to the United States by the Constitution, nor prohibited by it to the States, are reserved to the States respectively, or to the people”; and
• WHEREAS, the Tenth Amendment defines the total scope of federal power as being that specifically granted by the Constitution of the United States and no more; and
• WHEREAS, the scope of power defined by the Tenth Amendment means that the federal government was created by the states specifically to be an agent of the states; and
• WHEREAS, today, in 2009, the states are demonstrably treated as agents of the federal government; and
• WHEREAS, many federal laws are directly in violation of the Tenth Amendment to the Constitution of the United States; and
• WHEREAS, the Tenth Amendment assures that we, the people of the United States of America and each sovereign state in the Union of States, now have, and have always had, rights the federal government may not usurp; and
• WHEREAS, Article IV, section 4, United States Constitution, says in part, “The United States shall guarantee to every State in this Union a Republican Form of Government”, and the Ninth Amendment states that “The enumeration in the Constitution, of certain rights, shall not be construed to deny or disparage others retained by the people”; and
• WHEREAS, the United States Supreme Court has ruled in New York v. United States, 112 S. Ct. 2408 (1992), that Congress may not simply commandeer the legislative and regulatory processes of the states; and
• WHEREAS, a number of proposals from previous administrations and some now pending from the present administration and from Congress may further violate the Constitution of the United States.

THEREFORE – Be it resolved by the House of Representatives of the State of <STATE>, the Senate concurring, that:

1. That the State of <STATE> hereby claims sovereignty under the Tenth Amendment to the Constitution of the United States over all powers not otherwise enumerated and granted to the federal government by the Constitution of the United States.
2. That this Resolution serves as notice and demand to the federal government, as our agent, to cease and desist, effective immediately, mandates that are beyond the scope of these constitutionally delegated powers.
3. That all compulsory federal legislation that directs states to comply under threat of civil or criminal penalties or sanctions or requires states to pass legislation or lose federal funding be prohibited or repealed.
4. That the Secretary of State of the State of <STATE> transmit copies of this resolution to the President of the United States, the President of the United States Senate, the Speaker of the United States House of Representatives, the Speaker of the House and the President of the Senate of each state’s legislature and each Member of Congress from the State of <STATE>.

Replace “State of <STATE>” with your state or commonwealth and send it away. Or create this as a petition, gather signatures, then present it to your legislators. Take back your state from the Federal bureaucrats.