It’s just fun playing around with Stern-Brocot trees and a bit of Haskell…! For any fraction on the Stern-Brocot tree there is just one path to it from the root. That path can written as a sequence of left or right ‘turns’ at each node depending on whether the target node is smaller or larger than the current node. This leads to the Stern Path For example in this small tree the path to, say, 4/5 is, from 1/1, LRRR. The fraction 5/2 has path RRL. To get to 5/8 we go LRLR… and so on. (If you want to Read More
Tag: code
Ford and his Circles.
A Ford circle is a circle derived from a pair of numbers that are co-prime, i.e. they have no common factors. For a pair of co-prime integers p and q the Ford circle has radius r and centre at a point P(x, y) where r = 1/(2q^2) and P = (p/q, r) No matter what co-prime numbers, p and q, are used to create Ford circles the circles never intersect and they are all tangential to the horizontal axis. Now, we could generate ‘random’ Ford circles by picking any old co-prime pair (p, q). However, the Farey Read More
Count the Fractions.
This is the first in a series of posts about sequences of fractions, circles, trees of fractions, binary search trees and ways of representing rational numbers as paths through these trees . The idea is to enjoy a bit of recreational mathematics and to use Haskell to express some of the notions in its own succinct way. One Lot Of Fractions First we’ll look at all unique and simplified fractions between 0 and 1 with a denominator no larger than a given value. For example, with a maximum denominator of 3, 4 and then 5 we have For Read More
Squares and Graphs
Recently I came across this intriguing little puzzle… Take the integers 1..n and, if possible, arrange them in a list in such a way that consecutive numbers in the list add up to a square number. Use each number 1..n once only. In exploring this puzzle I started writing down the numbers and forming a graph where two numbers are connected if they add up to a square. Drawing such graphs is fun but slightly tedious for, for example, [1..300]… Here’s such a graph for numbers 1..15. Starting at 8 then 1 etc. and following the path gives the solution Read More
Continued Fractions, Pell’s Equation and Scary Numbers.
This is Pell’s equation: where n is a positive integer that isn’t a perfect square. Only integer solutions for x and y are sought and if n is not a perfect square then there are infinitely many integer solutions. It can be shown that the convergents of the continued fraction (CF) for the square root of n contains a solution known as the Fundamental Solution (FS). In practice this fundamental solution is the first convergent that satisfies the equation under consideration. Once this solution is known then all other solutions can be calculated from a simple recurrence relationship. i.e. If Read More
More Continued Fractions Continued.
In the post Parsers to Fractions to Square Roots! we looked at continued fractions (CFs) expressed in list format and used that format to calculate the square root of integers. The technique didn’t really explore an effective way of generating the list form for a CF. In this short post we’ll look at how to calculate the CF list format for the square root of an integer. Then, from the list, calculate the convergents, each of which gives a better and better value for the square root. (The details of convergents have been covered in Continued Fractions Continued.) With a Read More
The expressiveness of Haskell – Split a List.
Just recently playing around with one of the excellent Advent of Code problems (specifically 2015 question 6 ) a possible solution involved splitting a list into two parts where the first element goes into the first part, the second element into the second part and so on. For example [1, 2, 3, 4, 5, 6] -> [1, 3, 5], [2, 4, 6] So, in terms of function signatures we can write splitList :: [a] -> ([a], [a]) Notice there’s no constraint on the type in the list, it’s a very general function. One way of doing this is is to make use of pattern matching Read More
Synacor Virtual Machine.
Just recently I came across the ‘Synacor VM’ challenge. The problem is an interesting exercise in implementing a virtual machine using a supplied architecture definition and then running the VM using the given binary file as input. When run the program is an adventure type game which many people have completed but I have, so far, resisted that temptation. So here’s the spec.
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
-- -- == Synacor Challenge == In this challenge, your job is to use this architecture spec to create a virtual machine capable of running the included binary. Along the way, you will find codes; submit these to the challenge website to track your progress. Good luck! == architecture == - three storage regions - memory with 15-bit address space storing 16-bit values - eight registers - an unbounded stack which holds individual 16-bit values - all numbers are unsigned integers 0..32767 (15-bit) - all math is modulo 32768; 32758 + 15 => 5 == binary format == - each number is stored as a 16-bit little-endian pair (low byte, high byte) - numbers 0..32767 mean a literal value - numbers 32768..32775 instead mean registers 0..7 - numbers 32776..65535 are invalid - programs are loaded into memory starting at address 0 - address 0 is the first 16-bit value, address 1 is the second 16-bit value, etc == execution == - After an operation is executed, the next instruction to read is immediately after the last argument of the current operation. If a jump was performed, the next operation is instead the exact destination of the jump. - Encountering a register as an operation argument should be taken as reading from the register or setting into the register as appropriate. == hints == - Start with operations 0, 19, and 21. - Here's a code for the challenge website: mzMXMdUpOZeH - The program "9,32768,32769,4,19,32768" occupies six memory addresses and should: - Store into register 0 the sum of 4 and the value contained in register 1. - Output to the terminal the character with the ascii code contained in register 0. == opcode listing == halt: 0 stop execution and terminate the program set: 1 a b set register <a> to the value of <b> push: 2 a push <a> onto the stack pop: 3 a remove the top element from the stack and write it into <a>; empty stack = error eq: 4 a b c set <a> to 1 if <b> is equal to <c>; set it to 0 otherwise gt: 5 a b c set <a> to 1 if <b> is greater than <c>; set it to 0 otherwise jmp: 6 a jump to <a> jt: 7 a b if <a> is nonzero, jump to <b> jf: 8 a b if <a> is zero, jump to <b> add: 9 a b c assign into <a> the sum of <b> and <c> (modulo 32768) mult: 10 a b c store into <a> the product of <b> and <c> (modulo 32768) mod: 11 a b c store into <a> the remainder of <b> divided by <c> and: 12 a b c stores into <a> the bitwise and of <b> and <c> or: 13 a b c stores into <a> the bitwise or of <b> and <c> not: 14 a b stores 15-bit bitwise inverse of <b> in <a> rmem: 15 a b read memory at address <b> and write it to <a> wmem: 16 a b write the value from <b> into memory at address <a> call: 17 a write the address of the next instruction to the stack and jump to <a> ret: 18 remove the top element from the stack and jump to it; empty stack = halt out: 19 a write the character represented by ascii code <a> to the terminal in: 20 a read a character from the terminal and write its ascii code to <a>; it can be assumed that once input starts, it will continue until a newline is encountered; this means that you can safely read whole lines from the keyboard and trust that they will be fully read noop: 21 no operation |
I had a couple of attempts at this – in Haskell – and the main thing I learnt from this was… Yes, the Haskell type system is very expressive and allows for a sophisticated modelling Read More
Continued Fractions Continued.
It seems to me that continued fractions (CFs) are perhaps too advanced for ‘A’ levels and too elementary for a degree maths course and are perhaps undervalued or ignored in schools and universities? Since my last post about fractions I’ve looked a little more at CFs and found they have applications ranging from factorising large numbers to gear ratio calculations. And they’re really interesting when their layers are peeled away with a bit of Haskell. So, a bit of playing with numbers and a bit of Haskelling- what’s not to like? Let’s start with a fraction, any fraction – say Read More
Parsers to Fractions to Square Roots!
The earlier post Fractions to Phi to Fibonacci! showed a simple structure for Continued Fractions (CF) and used a CF representation of the Golden Ratio to derive the terms of the Fibonacci Sequence. It also alluded to a particular notation to express a CF and here we will describe that notation, create a parser for it and calculate the square roots of some integers from their specific CFs and finally derive a general CF that can be used to find the square root of any integer. CF List Notation Essentially the CF is written as a list of ints Read More