Vector Languages

A little bit of weekend fun (?):

If we plot x mod y in a matrix, we get:

y =     1 2 3 4 5 6 7 
---------------------
x = 1 | 0 1 1 1 1 1 1
x = 2 | 0 0 2 2 2 2 2
x = 3 | 0 1 0 3 3 3 3
x = 4 | 0 0 1 0 4 4 4
x = 5 | 0 1 2 1 0 5 5
x = 6 | 0 0 0 2 1 0 6
x = 7 | 0 1 1 3 2 1 0

You can see that if x % y == 0 only where either y == 1 or y == x, x is prime.

So with that knowledge in hand, you could write a (hugely inefficient) prime-generator in Swift which looks like this:

static func getPrimes(to n: Int) -> [Int] {
    // Generate our n*n matrix.
    // For n = 3, m will be:
    // [
    //     (x: 1, row: [(y: 1, xmody: 0), (y: 2, xmody: 1), (y: 3, xmody: 1)]),
    //     (x: 2, row: [(y: 1, xmody: 0), (y: 2, xmody: 0), (y: 3, xmody: 2)]),
    //     (x: 3, row: [(y: 1, xmody: 0), (y: 2, xmody: 1), (y: 3, xmody: 0)])
    // ]
    let m = (1...n)
        .map { x in
            (x: x, row: (1...n).map { y in
                (y: y, xmody: x % y)
            })
    }
    
    let primes = m
        // Get the divisors of x
        .map { x, row in
            (x,
                // filter out the (y, xmody) pairs where xmody == 0
                row.filter { y, xmody in xmody == 0 }
                    // and only return the y part; we're done with xmody now
                    .map { y, xmody in y }
            )
        }
        // Get the values of x where the divisors are only 1 and x
        .filter { x, zs in
            if case (1?, x?) = (zs.first, zs.last), zs.count <= 2 {
                return true
            } else {
                return false
            }
        }
        .map { x, zs in x }
    
    return primes
}

Ok, so what? You’ve got an inefficient prime generator. Cool, but not ground-breaking.

Check out this implementation in q, an APL-related vector language:

p : {n where 2=sum 0=n mod/: n:1+til x}
rle : {(count;first)@\:/:(where not =‘:[x])_x}
expand : {(),/(#).’x}

It’s tweetable!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s