An avian carrier's blog – J

Last summer, someone asked on stackoverflow how to factor a positive integer into prime numbers, and give the output on the form of powers at the right position in a sequence. Let us take a simple example: 825 is 3 × 5 × 5 × 11. The first prime numbers are 2, 3, 5, 7, 11. So 825 can be represented uniquely as the sequence (0 1 2 0 1) because it is equal to 2⁰ × 3¹ × 5² × 7⁰ × 11¹.

Like a lot of people there, I could not resist giving an implementation of the requested functionality in one of my favorite programming languages to show how easy it was. In Factor the math.primes and math.primes.factors vocabularies make it a very easy task. Let us describe it step by step.

The Factor implementation

group-factors takes a number to factor and returns a sequence of pairs, each containing a prime factor and the number of times this factor appears, starting with the lowest prime factor and ending with the highest one.

( scratchpad ) 825 group-factors .
{ { 3 1 } { 5 2 } { 11 1 } }

Next, we need the first prime numbers up-to the highest prime factor (11 in our case). Starting from our list, we can extract the first element of the last pair, which is the highest prime factor, and ask for the primes-numbers up to this number using primes-upto:

( scratchpad ) { { 3 1 } { 5 2 } { 11 1 } } last first primes-upto .
V{ 2 3 5 7 11 }

Then, starting again from the original factors list and this new primes number list, we can look up for each prime its corresponding power, or use 0 if it is not present. Easy, no?

Here is the complete implementation with the necessary plumbing added:

USING: assocs kernel math.primes math.primes.factors sequences ;
: count-factors ( n -- seq )
    group-factors [ last first primes-upto ] keep
    [ at 0 or ] curry map ;

Testing it gives, as expected:

( scratchpad ) 825 count-factors .
V{ 0 1 2 0 1 }

Doing it in J

Incidentally, while browsing stackoverflow today, I found this question again and realized that no one had given the obvious answer in J: there exists a built-in operator doing exactly the requested operation.

_ q:825
0 1 2 0 1

The reverse functionality is easy to use as well:

_(q:^:_1) 0 1 2 0 1
825

However, despite the conciseness of the J solution, I will rather use Factor for real work, as I usually expect to be able to decipher the code I wrote the day before.

I'll follow Dave Ray and will try to say something nice about a bunch of programming languages I use or have used seriously:

• Ada – The only language I would trust my life to.

• C – It gets things done easily in a controlled space when resources are scarce. I use it in many embedded situations, often with FreeRTOS.

• C++ – Its templating system with specialization beats everything I know. When I worked on Urbi at Gostai, I had a lot of pleasure using it.

• Erlang – The language to use to develop distributable parallel applications. I wrote many programs for research projects with it.

• Factor – One of the languages I feel the most comfortable with. I really like the reverse polish notation and the powerful combinators. I use it for many personal and teaching projects.

• Forth – Forth is one of the languages that I have been liking since the first time I heard about it. Its conciseness, simplicity, grammar and ease of implementation beats almost everything when it comes to size on very small embedded systems. I used it to write a Forth compiler targetting the Microchip PIC16Fxxx microcontrollers family.

• Haskell – I started using it when I had to send patches for Darcs. I really love monads, and I also love explaining them in class. My window manager configuration is also written in Haskell.

• J – It is unbeatable if you have RSI and need to type as little characters as possible for a task that can be applied to a whole array. I use it mostly to solve Project Euler problems.

• Java – Well, everyone knows it so it may be used to explain a simple concept. Is that nice enough?

• Javascript – Javascript lets us do things in the browser I would not have imagined five years ago. For example, this web page is static but includes Twitter updates and comments, thanks to Javascript. On the server side, I use it within a CouchDB database where I store a whole web application; it dynamically generates iCalendar views for multiple people from data gathered at TVrage.com using their XML API.

• Python – I can hack anything in a few minutes and still be able to read it later. I wrote a Forth compiler for the Microchip PIC18Fxxx microcontrollers family with it.

• Ruby – Feels like Python, only more functional and cleaner. I would use it more if I had not been bitten by threading unstability on Sparc64Linux in the past (for the will-spam-for-food.eu.org service we ran with Pierre Beyssac and Thomas Quinot). Ruby helps me run this blog.

• Scala – There comes a useful, powerful and pleasant to use language targetting the Java virtual machine. I used it to write my HarassMe Android application.

I probably forgot some languages in the list. However, if I use them, I am sure I can tell something nice about them.

This may come as a surprise, but I will today write about a programming language for which no Free Software implementation exists, the J programming language. J does not stand for the J dirty word (Java), but is the full name of the language.

I first heard about J while solving some problems on the Project Euler challenge. One of the problems to be solved was "given that C(n,p) is the number of ways to take p items amongst m items, find the number of C(n,p) greater than one million for n between 1 and 100 inclusive."

This was a very easy problem. I coded my solution using Python and, by curiosity, looked at how other people did it. I saw someone mentionning its J solution:

+/1e6<,!/~>:i.100

Wow, 17 characters! As I was in disbelief, I gave it a try and installed a copy of J on my GNU/Linux laptop. I cut and pasted the expression, and it gave me 4075, the expected solution. Let me describe how it works.

First of all, expressions are evaluated from right to left.

i.100

will generate a list of all integers from 0 to 99 (the 100 first non-negative integers). Then, the increment operator is used, so the part

>:i.100

leads to the list of numbers from 1 to 100. The rank of the increment operator is zero, which means that it operates on individual items, not on lists. Since we give it a list as argument, each member of the list will be incremented, and give the new 1 to 100 list.

The C(n,p) operator in J is written as

p ! n

However, we want to apply it for every p and n in 1 to 100. The tilde (~) modifier means that we want the left argument of the ! function to be the same as the right argument. The slash (/) modifier means that we want to build a table. Without it, the ! operator would be applied to the first item of the left argument and the first item of the right argument, then to the second item of the left argument and the second item of the right argument and so on. Here, it is applied to every combination of its left and right arguments, meaning that the result is a 100x100 table:

!/~>:i.100

Now, the coma (,) transforms the 100x100 table into a 10000 elements flat list:

,!/~>:i.100

Now, we want to select all the elements greater than one million. For that, we will compare each element to 1e6 (one million in scientific notation). Since the left argument is a plain number and the right argument is a list (the 10000 long list we obtained), the result will be a 10000 items list containing either 0 (false) or 1 (true):

1e6<,!/~>:i.100

Ok, so we now have a 10000 items list containing 0 (smaller than one million) or one (greater than one million). To find out the number of ones, we only have to sum up the items. Using the plus (+) operator and the slash (/) modifier, an addition will be inserted between every item of the list:

+/1e6<,!/~>:i.100

That's it.

To the computer literate people, it looks a lot like APL without the special characters and the need for a special keyboard. No surprise, J and APL have both been designed by Kenneth E. Iverson.

J is very efficient while working on large sets of data. Its table operator and its rank analysis almost entirely obviates the need for explicit loops. For example, if you want to multiply the 100 first prime numbers, you can use the p: operator which returns the n-th prime number (starting with 0, which returns 2, 1 returns 3, 2 returns 5, 3 returns 7 and so on):

*/p:i.100x

The x modifier stands for extended (read unlimited) integer precision. You want to know what the solution is? Install your copy of J and try it yourself.