When I first understood git, after dedicating some hours to watching a video and reading long articles, it was like I finally had power over time. I can find out who changed what, and when. I can move branches to point right where I want. I can rewrite history!

# Tag: math

# Brains, computers, and problem solutions

Programmers tell the computer what to do.

The computer has a processor, it has some memory, and it follows a set of instructions. The instructions say what to load into memory, what to do with the values in memory, how to change that memory, and when to store it off somewhere else. There is an instruction pointer that shows the next instruction to execute. There are tests that can change where the instruction pointer goes next.

Assembly language is the closest to pure computer programming, to telling the computer exactly what to do. Imperative languages like C are an abstraction above that. We still tell the computer what to do, in what order, and how to change the values in memory. Code is in one place, data in another. Object oriented languages like Java offer a few more abstractions, organizing relevant code with data, hiding memory management. These languages are still imperative: we tell the processor what to do and in what order.

Now that we don’t program business software in assembler, do programmers still tell the computer what to do? We tell the compiler what to do, and that tells the runtime what to do, and that tells the computer what to do. What do we really do?

Programmers solve problems.

When we learn to code we learn to think like the computer. But what if that is not the optimal way to think? what if we think instead of how the problem looks, what the solution looks like?

Programming in a declarative style means stating solutions, not steps. State what is true, or state what we’re doing – don’t describe how the computer goes about it. That’s an implementation detail for the compiler to optimize. (I’m talking business software here, not embedded systems.) Code in a language suited to the problem. This gives us more ways to solve problems, and cleaner ways to solve problems.

We’re not limited to what comes naturally to a computer, or what comes naturally to our brains.

Abstraction is key. The right abstractions make our code easy to read and faster to write and maintain. Don’t limit abstractions to the ones that fit the computer. Don’t limit them to objects that model business entities. This is why learning math is useful, and it’s why functional programming is useful: the more abstractions we know how to hold in our head — abstractions with no analog in either the real world or the computer world — the more tools we have for solving problems.

# Finding Primes in Haskell

I’m currently distracted from life, immersed in Concepts of Modern Mathematics.

Did you know that you can find out whether a number is prime by multiplying all the integers before it, adding one, and then dividing by the number of interest? Me neither! it’s like this:

a number p is prime if and only if: (1*2*3*...*(p-1) + 1) mod p = 0

So, if the product of all positive integers less than p is one short of dividing evenly by p, then p is prime. Otherwise, not prime.

As the book points out, this is not a practical way to determine primeness, because if p is 17, that product is fourteen digits long. However, there’s a sneaky way to make this more practical.

This formula came out of the concept of arithmetic modulus p, which is a strange sort of arithmetic that considers only the numbers 0 through p-1. Any higher or lower numbers circle around. Any number above p-1 reduces to its remainder when divided by p. It’s a bit like when a two-year old is counting: “One, two, three, four, one, two, three…”

Since this equation came out of arithmetic modulus p, we can use this property to shrink the product as we do the multiplication. While we multiply 1 times 2 times 3 times 4, etc, we can stop after each multiplication and mod p. That way the product never gets crazy high — at most (p-1)*(p-1) — because at each step it drops to something less than p.

To simplify this equation, we take out the “mod p” because in arithmetic modulus p, “mod p” is free. Also, 0 and p are the same number. (yes, that’s weird.)

We can knock a few steps off this procedure:

1*2*...*(p-1) + 1 = 0 = p

1*2*...*(p-1) = p - 1

1*2*...*(p-2) = (p-1)/(p-1) = 1

1*2*3*...*(p-2) = 1

In Haskell, we can write this as: for a list of numbers from 1 to p-2, accumulate a product, modding the product by 17 at each step; see whether the end result is 1.

let isPrime p = foldl (\acc x -> acc * x `mod` p) 1 [2..(p-2)] == 1

This says start with 1, accumulate the product-then-mod, and see whether we come out with 1.

Let’s check all the numbers up to 100 and see which ones are prime.

>filter isPrime [2..100]

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

That’s pretty much instantaneous. Finding every prime between 2 and 10000 — there are 1229 — takes about thirty seconds on Swirlybob in GHCi. It was twenty seconds on Carolyn, my work laptop.

A future goal: use monads to time the operation precisely. I wonder whether implementing it as a recursive function and explicitly checking for 0 in the accumulator will be faster. (This happens early in the process for all non-primes except perfect squares.)