Recursive atoi in Haskell

A friend of mine suggested, during a conversation, that it would be difficult to write a recursive implementation of atoi which could handle all real numbers (i.e. not just non-negative integers). Well, I decided I had to do it anyway. I will freely admit that most of my time was spent remembering how Haskell works.

import Data.Char
import Data.List.Split
myatoi :: [Char] -> Float
myatoi ""       = fromIntegral 0
myatoi ('-':xs) = - myatoi xs
myatoi ('.':xs) = (myatoi xs) / 10^(fromIntegral$length(xs))
myatoi (x:xs)   = fromIntegral((ord(x)-ord('0'))*10^length(head(splitOn "." xs))) + (myatoi xs)

It will fail amusingly if you feed it anything other than a number as a string, but otherwise it works pretty well. That is, of course, despite it being ugly and mildly indecipherable.

Posted in haskell, programming

Primality Testing

I spent the past week working on implementing the Baillie-PSW probable prime test, and it’s been a lot of fun. It’s pushed my abilities in interesting ways, and I’ve had a lot of fun working on the code. I’ve learnt about profiling code in Python, as well as fast modular exponentiation.

On that last one: finding out that Python has a three argument form of pow() where the third argument is an integer to perform the exponentiation modulo to – that sped my code up ~10,000 times. Yep, ten thousand.

The interesting thing about the Baillie-PSW test is that it’s not deterministic. It can only tell you that a number is probably prime. There are a fair few probabilistic tests, and they all share the same flaw: pseudoprimes. A pseudoprime is a composite (non-prime) number which a probabilistic test reports as being prime. This is obviously quite a problem with probabilistic tests – you can be sure that any number reported as composite is composite, but you can’t be sure that any number reported as prime is prime.

This area is where the Baillie-PSW test is very good though. It combines two simpler probabilistic tests (Miller-Rabin and a strong Lucas test). There are no known numbers which are pseudoprimes to both tests. There may be some out there, but there are definitely none below 2^64, and no-one has found any higher than that, either. This means that, for many purposes, the Baillie-PSW test can be regarded as deterministic. It certainly is below 2^64.

If you need to check numbers above 2^64, Baillie-PSW can still be useful. It can weed out definitely composite numbers, leaving you with a smaller list of probable primes with which to check with a slower, deterministic method.

If you’re interested in the code I wrote, it’s available on GitHub.

Posted in mathematics, primes, programming, python

Reference Implementations

Recently I’ve been playing around with a Lisp dialect called Scheme. It’s an absolutely tiny language designed to be very easy to implement. The very first problem I had with Scheme is that it’s very easy to implement; consequently, there are a lot of implementations. This is great when you have a good grasp of the language – you know which features of different implementations will suit you best, and you can choose the right implementation for you and your projects. When you’re just starting out, however, it can be a tricky – and daunting – task to choose from a list of so many different implementations with differences you don’t grasp.

Contrast this approach with, say, Python. Python has a canonical reference implementation called CPython (yes, it is written in C). I’m certain that most beginning Python programmers aren’t even aware that there are other implementations; if they are it’s in a fuzzy ‘I don’t need to care about that’ kind of way. When you Google Python, you find which hosts the CPython implementation as well as the Python documentation and more. After you become more familiar with the Python language, you might want to branch out and use a different Python implementation because it offers something you need – that’s fine. But CPython’s prevalence makes it easy for beginners to jump in. They don’t have to make decisions they don’t understand.

That’s not to say that Scheme’s way of doing things is necessarily wrong. But it does mean that people without an amount of programming experience behind them need a little more hand-holding when getting started with Scheme. Because seriously, there are a lot of implementations to choose from. For what it’s worth: I went with Mit-Scheme because I’m working through _Structure and Interpretation of Computer Programs_.

Posted in lisp, programming, python, scheme

Recent Comments