Multiplication of two n-bit integers

Yo yo yo sup I’m back! – and ready to rock and roll. If you’re reading this, some general advice is to stop now and go do something useful, this post was not written with you in mind. Truth be told, you’ve probs arrived here by accident. If you’re not reading this, congrats! You’ve come to the right place.

To multiply A and B

To multiply integers

You want to divide,

Split into two or three parts,

Or four or more, you decide.

 

First put them in binary

Then make even splits:

A1 and B1 are easy,

Just write each as it is;

 

Now we must consider

What powers of 2

We must divide the other parts by

So they’re integers size n/(2^p)

 

Now multiply all out

A, B rewritten as above

Replace opposite multiplications

With pairs and minuses to spread da love.

 

Now all is done

We can find T(n) w.r.t. n/p

And solve the recursive relationship:

It’s quicker, you see!

Advertisements

Maths is awesome… EVERYWHERE!

To the elusive and almightily invisible crowd that is an Internet readership,

Tomorrow is the day Cambridge decision letters are due to arrive for 2016 undergraduate applicants, and I am seriously freaking out. Every five minutes I stop and Google (only realised the subtle mathsy pun on words after typing that – and yes, the magnitude of my freaking out is on the level of 10100)  Churchill College, where I applied, because I realise that I potentially only have a day left in which to daydream about going there before my dreams are crushed, and then I go on the websites of the other uni’s I’ve applied to to remind myself that it’s ok, they’re all awesome too, and by that time I’ve got nothing much done and so I realise that I need to do some more work if I’m ever going to get in ANYWHERE…

And so I decided to make a list of the reasons why maths (which is what I’ve applied to do because I like it – hence the name of this blog) is awesome EVERYWHERE:

  1. There are right answers and wrong answers: sometimes there are more than one right answer, so you can be creative, but there is a clean line between the correct and the incorrect, so you can aactually tell whether what you’re doing is any good.
  2. It stretches across centuries and the world in general, whether it’s the triangles of Pythagoras or the vectors of Stefan Banach
  3. It makes sense.
  4. The fundamental truths of mathematics stand alone, uninfluenced by public opinion and so on.
  5. It is abstract so even if the world blew up mathematics would remain intact.
  6. It stretches across cultures because it’s universal, like love, except it’s easier to understand.
  7. You can explore it yourself without any specialist equipment, just your mind.

There, that took my mind of Cambridge for 10 minutes or so. What shall we do for the 16 hours until the postlady comes?!

*Photo of Churchill from https://www.cambridgenetwork.co.uk/news/churchill-college-partners-with-onespacemedia-for-integrated3582/

 

**UPDATE** I’VE GOT AN OFFER FROM CAMBRIDGE!!!

The Museum of Curiosity

This BBC Radio 4 special is too good to miss. This particular episode was recorded as part of the BBC “Make It Digital” season, and the “museum” has brought in three brilliant guests – Matt Parker (mathematician and comedian), Eben Upton (creator of the Raspberry Pi) and Sydney Padua (writer and illustrator of The Thrilling Adventures of Lovelace and Babbage) – along with “curators” John Lloyd and Sarah Millican to discuss how computers came to be whilst squeezing in as many laughs as possible.

Continue reading