Making a Big Math Library

Introduction

In most of your day to day applications, numbers that fit within 8, 16, 32 and 64 bits are enough. Sometimes you may need to stretch out into your floating point processor to include some more precision and start looking at 80 bit numbers. Today’s post, I want to start on a library in assembly language that works on even bigger numbers. There are going to be some caveats or conditions that we’ll establish up front, but they will be big numbers! The design considerations for this library will be as follows:

• Unsigned integers
• Fixed size

With this information, we can now start to build our library.

The big number data type

Well, it’s not really that special at all. We just need to define an array of quad-words to the length that we want. So, an example would look like this.

bignum_size EQU 10        ; bignums will be 640bits in size
                                            
num_a resq bignum_size    ; make our bignum variable

That’s all pretty simple. A number is just an array of a pre-defined length. With a length to 10, at 64 bits per array index we’ve got ourselves a 640 bit number. Quite large. In fact, we’re talking numbers up to 4.562441e+192. Now that’s impressive.

Lets operate!

We’ve got a very impressive data type that we can declare where ever we want, but how do we use it? We need to define all of the management, arithmetic, logic and printing ourselves. First of all though, we’ll want to be able to zero out our number, which is just continually writing zeros over our memory buffer (much like a memset).

; --------------------------------------------
; bignum_zero                                 
; initialize a bignum to zero                 
;                                             
; input                                       
; rdi - address of the number                 
; --------------------------------------------
                                              
_bignum_zero:                                 
  push  rax               ; save any registers                                  
  push  rcx               ; that we'll mow over                   
  push  rdi                                  
                                              
  xor   rax, rax          ; the value we want to set to                   
  mov   ecx, bignum_size  ; the number of quads to write                   
  rep   stosq             ; clear out our number                   
                                              
  pop   rdi               ; restore any registers that                   
  pop   rcx               ; we saved                   
  pop   rax                                  
                                              
  ret                                        

Excellent. We can initialize our big number now to zero so that we have a starting point. Next, we’ll want to be able to debug any problems that we may have while building this library, so its going to be of great benefit to be able to see what the value is of our number. The following code leans on some assembly I had written in a previous article which displays the value in RAX. Here’s how we’ll print our big number to screen.

; --------------------------------------------
; bignum_print                                
; prints a bignum to the console             
;                                             
; input                                       
; rsi - address of the number                 
; --------------------------------------------
                                              
_bignum_print:                                
  push  rax                 ; save off any values                         
  push  rbx                                  
  push  rcx                                  
                                              
  mov   rcx, bignum_size    ; we'll print all blocks

next_block:                                   

  mov   rbx, rcx            ; setup our base pointer                             
  dec   rbx                 ; to point to the block corresponding                 
  shl   rbx, 3              ; to our counter rcx

  mov   rax, [rsi + rbx]    ; get the value in rax                 
                                              
  call  _print_rax          ; print it                 
                                              
  dec   rcx                 ; move onto the next block                 
  jnz   next_block          ; keep printing                 
                                              
  pop   rcx                 ; restore any saved registers                 
  pop   rbx                                  
  pop   rax                                  
  ret                                        

Most obvious thing to note here is that we’re moving through the bignumber back-to-front so that it’s presented on screen in a human manner. We can test what we have so far is working by writing a small piece of test code.

; zero out our number
mov   rdi, num_a   
call  _bignum_zero  

; print it to screen
mov   rsi, num_a   
call  _bignum_print

Which, rather uninterestingly will just spit out a massive list of zeros.

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

So, lets do something a little more interesting. The smallest pieces of arithmetic that I think we can implement for these numbers is increment and decrement.

Increment

This is straight forward. Add 1 to the lowest part of the number. If that part of the number just “clocked”, or reset to zero - we must carry our value onto a higher block.

; --------------------------------------------
; bignum_inc                                  
; increments a big number by 1                
;                                             
; input                                       
; rdi - address of the number                 
; --------------------------------------------
                                              
_bignum_inc:                                  
  push  rcx                       ; save off any registers                                  
  push  rbx                                  
  push  rax                                  
                                              
  mov   rcx, bignum_size          ; worst case, we'll have to
                                  ; go through all blocks

  xor   rbx, rbx                  ; reset our base to be zero                             
                                              
_bignum_inc_carry:                            
  mov   rax, qword [rdi + rbx]    ; get this block into rax           
  inc   rax                       ; increment it
  mov   qword [rdi + rbx], rax    ; store it back           
  cmp   rax, 0                    ; check if we "clocked"           
  jne   _bignum_inc_done          ; if we didn't, we're finished           
                                              
  add   rbx, 8                    ; move the base onto the next block           
  dec   rcx                       ; 1 less block to process           
  jnz   _bignum_inc_carry         ; continue until we're finished           
                                              
_bignum_inc_done:                             

  pop   rax                       ; restore any of the saved values           
  pop   rbx                                  
  pop   rcx                                  
  ret                                        

Alright, we’ve got incrementation going on here. The most interesting case for us to test is when a block is sitting on the carry boundary or sitting at 0xffffffffffffffff. After we increment that, we should see that clear out to zero and the next block to get a 1.

mov   rdi, num_a                     
call  _bignum_zero                   
mov   qword [rdi], 0xffffffffffffffff   ; setup out number on the boundary
                                     
mov   rsi, num_a                     
call  _bignum_print                     ; print it out
                                     
mov   rdi, num_a                        ; push it over the boundary with
call  _bignum_inc                       ; an increment 
                                     
mov   rsi, num_a                        ; print out the new number
call  _bignum_print                  

Which results in the following.

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFF
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000

Those massive trails of zeros are getting annoying. We can clean them up later by making our print routine a little smarter. But you can see that we’ve successfully incremented over a boundary so that our next higher block gets a one.

Decrement

This is pretty much as straight forward as incrementing, on this time we’re not going to carry to a higher quad-word, we’re going to borrow from it if we do cross a boundary. Here’s the code for a decrement.

; --------------------------------------------
; bignum_dec                                  
; decrements a big number by 1                
;                                             
; input                                       
; rdi - address of the number                 
; --------------------------------------------
                                              
_bignum_dec:                                  
  push  rcx                       ; save off any registers                                  
  push  rbx                                  
  push  rax                                  
                                              
  mov   rcx, bignum_size          ; worst case, we'll need
                                  ; to go through all blocks

  xor   rbx, rbx                  ; clear out the base                             
                                              
_bignum_dec_borrow:                           
  mov   rax, qword [rdi + rbx]    ; get the current quad           
  dec   rax                       ; decrement it           
  mov   qword [rdi + rbx], rax    ; store it back in the number           
  cmp   rax, 0xffffffffffffffff   ; check if we went across a boundary           
  jne   _bignum_dec_done          ; if not, get out now           
                                              
  add   rbx, 8                    ; move onto the next block           
  dec   rcx                       ; not done yet?           
  jnz   _bignum_dec_borrow        ; keep processing borrows           
                                              
_bignum_dec_done:                             
  pop   rax                       ; restore the saved registers           
  pop   rbx                                  
  pop   rcx                                  
  ret                                        

This really is the increment routine just with the numeric direction reversed. Making sure that we are on the right track, we can test out the decrement across a boundary again.

mov   rdi, num_a                        ; setup our number right                     
call  _bignum_zero                      ; on the boundary
mov   qword [rdi], 0xffffffffffffffff
                                     
mov   rsi, num_a                        ; print its current state
call  _bignum_print                  
                                     
mov   rdi, num_a                        ; increment over the boundary
call  _bignum_inc                    
                                     
mov   rsi, num_a                        ; print its state
call  _bignum_print                  
                                     
mov   rdi, num_a                        ; decrement it over the boundary
call  _bignum_dec                    
                                     
mov   rsi, num_a                        ; print its state
call  _bignum_print                  

The output of which looks like this.

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFF
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFF

Again, it’s pretty hideous with the trailing zeros, but you can see this in action now. Back and forth, across boundaries - no sweat.

Conclusion

Well, this is just the tip of the iceberg for this particular library. I’d hope to demonstrate logical testing, addition, subtraction, multiplication and division as well shortly. The best part about these routines is that if you wanted to operate on 6400 bit numbers, all you have to do is change the constant bignum_size that I’d set earlier to 100.

Monoids and Associativity

Introduction

Associativity is a property of a function which has an output equivalent no matter what order the function is applied. Addition and product are examples of mathematical functions that are associative as opposed to subtraction and division which are not. Today’s post will focus on associative functions and their definitions through Monoids in Haskell.

Associative functions

In the introduction to this post, I spoke about associative functions and gave a few examples. Here are those examples again, but demonstrated mathematically.

(5 * 7) * 9 == 5 * (7 * 9)
(5 + 7) + 9 == 5 + (7 + 9)
(5 - 7) - 9 != 5 - (7 - 9)
(5 / 7) / 9 != 5 / (7 / 9)

These examples are pretty straight forward in their reading. You can see clearly that the product and addition operators are associative, subtraction and division not. String concatenation (or array concatenation) is also associative such that:

"Hello " ++ ("World" ++ "!") == ("Hello " ++ "World") ++ "!"

These proofs are pretty straight forward. I think that you should have the idea of what associative functions are by now.

Monoids

Monoids are Haskell’s way of decorating a type that is functionally associative. The definition of a Monoid is as follows.

class Monoid m where
  mempty :: m
  mappend :: m -> m -> m
  mconcat :: [m] -> m
  mconcat = foldr mappend mempty

You can find more information specifically about the type up on the Haskell Wiki. From the definition above, we can see that there are 3 functions to be defined.

mempty

mempty is the identity value for the monoid. It acts more like a constant rather than a function.

mappend

mappend is the binary function that can be used between two of these typed Monoids.

mconcat

mconcat folds the mappend function between the elements of an array of Monoids.

Monoid Laws

Above, I have gone through the basic principals of associative functions which by-and-large cover off on the laws that a Monoid must abide by. There are some explicit ways of writing this concept, there are as follows.

mempty `mappend` x = x
x `mappend` mempty = x
(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

That’s Monoids for you. Take a look as some example implementations on the Wiki and around the web.

Applying Applicative

Introduction

In a previous post, I had pretty much got the textbook definition down for an Applicative Functor and shown some of its pre-existing uses. Today’s post, I want to walk through some code that I’ve written that implements Applicative.

Put it in context!

Right on! It’s all about context. When making instances of the Functor typeclass, it’s all about defining fmap appropriately to “operate” on the data that sits in a context. What’s a context then? The books and articles that I’ve read use pre-existing types as examples. A list for instance is a context, Either is a context, Maybe is a context. All of these things wrap data. So, let’s make our own context to put something in.

data CustomContext a = CustomContext a
                       deriving (Show)

There’s our context, CustomContext. It just wraps around something .. anything. We can apply a functor instance to this with the following.

instance Functor CustomContext where             
  fmap f (CustomContext x) = CustomContext (f x)

fmap allows a function to get inside the context and operate on the inner data - alright, I’ve said this already. Proof that all of this is working is as follows.

λ> let x = CustomContext 10
λ> x                       
CustomContext 10           
λ> fmap (+5) x             
CustomContext 15           

We wrapped 10 in a context. We applied the function (+5) to the value inside our context. We got back a 15 wrapped in a context. Moving into Applicative territory now, it’s not only the value that we operate on that has the context this time - it’s also the function that we apply. We use the pure function to lift a value inside a context and we use <*> to apply a function to a value (both being inside their respective contexts). Here’s how we’ll define Applicative for our type.

instance Applicative CustomContext where                    
  pure                                = CustomContext      
  CustomContext f <*> CustomContext x = CustomContext (f x)

The implementation of pure is straight forward, we’re just going to pop the value in a CustomContext context. The sequential application function <*> is implemented very much how fmap was implemented, in fact it’s the same. The difference comes in with how the parameters are supplied. We’re taking the function out of the context, we take the value out of the context - we apply the function and wrap the result in the context. Here it is in action.

λ> CustomContext (+5) <*> CustomContext 10
CustomContext 15                          

Also, with the use of pure lifting our values or functions into the context.

λ> pure (+5) <*> CustomContext 10
CustomContext 15                 
λ> CustomContext (+5) <*> pure 10
CustomContext 15                 

Excellent. We’ve done it.

Conclusion

This may not be the most feature-rich example, but it should give you good insight into the implementation and workings of Applicative.

type, newtype & data

Introduction

This post is just a small write up on the differences between these three keywords and their uses within Haskell.

type

Using the type keyword is the same as just referring to the actual type that you’ve declared. In other words, type just lets you make a synonym for the original type.

-- a deck is an array of cards
type Deck = [Card]

-- an array of crows would be a murder
type Murder = [Crow]

Using these, we’ll be able to refer to a Card list as a Deck. They can be used interchangeably as they’ll directly cast. All this really does for us, is gives a pre-existing type a more meaningful name to our code.

newtype

Using the newtype keyword, we make a thin wrapper around an existing type. Something that will be treated differently at compile time, but will be directly translatable (and not subject to conversion) at runtime.

-- declare the data type
newtype Word = Word { getWord :: String }
  derives (Show, Eq)

-- using the data type
let helloWord = Word "Hello"
let byeWord = Word "Bye"
let greetingWord = Word "Hello"

newtype only allows you one constructor and one field. It’s important that its used when you’re creating data entries that have these constraints on them. These attributes make newtype a great candidate for when you just want to add a typeclass instance to an existing type.

data

The data keyword allows you to build much more complex types. With the data keyword, you can have as many constructors and fields as you like.

-- create a person data type
data Person = Person String String Int deriving (Show)
let john = (Person "John" "Smith" 35)

-- create a more complex employee type
data Employee = Employee Int Person deriving (Show)
let john = (Employee 6 (Person "John" "Smith" 35))

Of course, it would make more sense to use “record syntax” when defining these datatypes above.

-- define a person
data Person = Person {firstName :: String
                     ,lastName :: String
                     ,age :: Int} deriving (Show)

-- define an employee
data Employee = Employee {employeeId :: Int
                         ,person :: Person} deriving (Show)

-- define "john"
let john = Employee {employeeId = 6
                    ,person = (Person {firstName = "John"
                                      ,lastName = "Smith"
                                      , age = 35}) 
                    }

Wrapping up

• Use type to give your types more meaningful names
• Use newtype if you just want to take an existing type and add a typeclass instance to it
• Use data if you want to create your own datatype

Applicative Functors in Haskell

Introduction

As a follow up to my previous post on Functors, it’s a natural progression for me to do a post on the more advanced version, the Applicative Functor. In a normal functor, you’ll map a function over a functor and applicative functor is a reverse view of this where it’ll allow you to map many functor values over a single function.

What is an Applicative Functor?

At the code level, an Applicative Functor is any type that is in instance of the Applicative typeclass. At a concept level, the Applicative Functor has not only the values in “a context” but also the function that we’ll apply is in a context. This differs from just a normal Functor where it’s only the value that’s wrapped in a context. An Applicative Functor has 2 functions that require implementation. pure and <*>. This typeclass and functions are defined as follows.

class (Functor f) => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

The definition for pure on Hoogle suggests that it will

Lift a value

“Lifting” is very well described in articles all over the web. Here’s the Haskell Wiki’s article on Lifting. pure takes in a value and returns an applicative value around that value. It’s actually quite a simple definition when you read it. The other function defined here is <*>. The definition for <*> on Hoolgle suggests that it will perform

Sequential application

The definition of sequential application here can be expanded such that <*> takes a function (a -> b) wrapped up in a functor f and another functor value f a. It’ll extract the function from the first parameter (a -> b), map it over the functor value f a to produce a result f b. The concept is very similar to what we’ve seen before in mapping scenarios, it’s just that we “map” with different “things”. Today we’re mapping with functor values over a function.

pure

Here’s some examples of pure in action. You’ll see that when we’re casting to a type, we receive the appropriate value back

> pure "Hey" :: Maybe String
Just "Hey"
> pure "Should be in a List" :: [String]
["Should be in a List"]

You can see here that the value is “lifted” by pure into the container (in this case either a Maybe or a List).

<*>

For the next set of examples, I’ll show you some usages of <*>. You’ll need to keep in the front of your mind that all functions on the left hand side are applied to all values on the right hand side, so we end up with a Cartesian effect.

> [sin, cos, tan] <*> [pi, pi, pi]
[1.2246467991473532e-16,1.2246467991473532e-16,1.2246467991473532e-16,-1.0,-1.0,-1.0,-1.2246467991473532e-16,-1.2246467991473532e-16,-1.2246467991473532e-16]

The <*> function is left associable, so when you start chaining calls together it’s the leftmost that is evaluated first.

> [(+),(*)] <*> [1,2] <*> [3,4]
[4,5,5,6,3,4,6,8]

(which is really)
[1+3,1+4,2+3,2+4,1*3,1*4,2*3,2*4]

Applicative Style

You can see how using this “applicative style” in code can often be swapped 1-for-1 with list comprehensions as you achieve the same permuted or Cartesian effect. Take this for example.

> [salutation ++ name | salutation <- ["Hello ", "Goodbye ", "Yo! "], name <- ["John", "Mary", "Anne"]]
["Hello John","Hello Mary","Hello Anne","Goodbye John","Goodbye Mary","Goodbye Anne","Yo! John","Yo! Mary","Yo! Anne"]

> (++) <$> ["Hello ", "GoodBye ", "Yo! "] <*> ["John", "Mary", "Anne"]
["Hello John","Hello Mary","Hello Anne","Goodbye John","Goodbye Mary","Goodbye Anne","Yo! John","Yo! Mary","Yo! Anne"]

You can see that when dealing with lists, the following is true:

pure f <*>; xs == fmap f xs

In this context, pure f is putting f into a list. [f] <*> xs just applies each function in the left list to the right. Another implementation of the Applicative Functor that doesn’t follow the same notion of a List is its use with IO. The idea of the applicative functor still holds, but when dealing with IO its the actions that are operated on. This can be thought of in the same way as sequencing and mapping in one.

ZipList

Another type that is an instance of Applicative is the ZipList. The ZipList type is defined as follows.

instance Applicative ZipList where
  pure x = ZipList (repeat x)
  ZipList fs <*> ZipList xs = ZipList (zipWith id fs xs)

When we use applicative style on a normal list, we end up with a Cartesian product of the two lists involved. A ZipList differs here by operating on indicies in either list that are the same. Index [0] on the left gets applied to Index [0] on the right. Index [1] on the left gets applied to Index [1] on the right, and so on.

Applicative Functor Laws

Finally, there are a few laws that applicative functors must abide by, they are as follows.

• pure id <*> v = v
• pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
• pure f <*> pure x = pure (f x)
• u <> pure y = pure ($ y) <> u

Applying applicative functors for yourself

This has been a very difficult topic that I’ve burnt some time on as late. There are plenty of examples of how this knowledge has been applied for a List or Maybe, but I’ve struggled to apply this to a type of my own. So far though, I’ve come across this article on Applicative Functors on the Hakell Wiki and most notably this sentence:

Anytime you feel the need to define different higher order functions to accommodate for function-arguments with a different number of arguments, think about how defining a proper instance of Applicative can make your life easier.

That to me makes sense. So, if you have a function that operates on a particular type and you’d like to apply that function to “n” arguments - you’d normally create an fmap clone that would cater for that many arguments. Using an applicative functor, the re-creation of the fmap instance goes away as your higher-order function can expect any number of arguments. Because of this, the following is true.

fmap2 f a b = f `fmap` a <*> b
fmap3 f a b c = f `fmap` a <*> b <*> c
fmap4 f a b c d = f `fmap` a <*> b <*> c <*> d

That’s it for today’s post. I hope to update this post with some more examples and information as I discover it!