Multiplying two digit numbers

We were chatting at dinner the other day about mental arithmetic and Navid had a neat trick for multiplying numbers in his head.   He’s written it out below.

Mentally multiplying two digit numbers is difficult for the majority of people. This is probably due to our limited working memory overflowing when we try to store the partial products, leading to errors.

In many cases, I use a trick to simplify the problem, which is the subject of this blog post. It requires a bit of investment, but lets us compute products such as 84*78 both accurately and (in due time) quickly.

 

Theory

This trick works for a * b when a + b is even, that is to say either a and b are both even or both odd, for example 65*43 and 88*78. Furthermore, it works best when a and b are close together, but as your proficiency increases this becomes less important.

The essence of the trick is in the difference of two squares, namely, we want to write a * b =       (c + d) * (c – d) = c^2 – d^2                  

We quickly find that. c = (a + b) / 2 and d =|a – b| / 2

In other words c is the average of a and b, whereas d is the difference between the average and a or b. Note that the condition that a + b is even ensures that both c and d are integers.

You are probably wondering what the point of this complication is. Well, in many cases computing c^2 – d^2 is easier than working out a * b. For example, take 43*57, it is easy to see their average is 50 and the difference is 7. Hence, the product reduces to 502 – 72 = 2500 – 49 = 2451. Try it out on the following examples:

a) 66*62                             b) 98*84                             c) 39*33                             d) 44*76

 

Tips and Conclusion

After doing a few problems you will find that most of the time d is small enough to recall d^2 from memory. The trickier part is calculating c^2, fortunately, we can use the fact                 (x + y)^2 = x^2 + 2xy + y^2 to aid us. For example, writing 82 = 80 + 2 we find that 822 = 802 + 2*2*80 + 4 = 6400 + 324 = 6724. Personally, I found that this speedy computation of c^2, removed the major bottleneck from the method.

Some practice is required but soon you will be able to multiply the majority of numbers of this form in under ten seconds.

Queens’ Academic Saturday on “Understanding Intelligence”

Last Saturday we all got invited to talk from Queens’ Computer Science graduate Demis Hassabis who matriculated here in 1994. Under the title ‘Understanding Intelligence’ he talked about his latest startup DeepMind (recently bought by Google), as well as what else he has been up to since graduating from Queens’.

Demis said he had always been interested in Artificial Intelligence. Before he came to Queens’ he created many computer games, most famously Theme Park (1994), which all had a strong foundation of AI built into them. He continued this after graduating from Queens’ with game titles such as Black & White (2001) and Republic: The Revolution (2003) until he in 2005 went to UCL to do a PhD in Cognitive Neuroscience. He told us that doing a degree in Neuroscience was crucial to achieve his in-depth understanding of how the brain works and how he later could use this knowledge to found DeepMind. He referred to the quote:

“What I cannot create, I do not understand.” 

- Richard Feynman (1988)

DeepMind

In 2011 Demis co-founded a company called DeepMind with the idea to create ‘an Apollo programme for artificial intelligence’.  The company was successful in attracting the best AI researches in the world and very impressively, only 3 years later, Google bought the company.

In difference to many others, instead of focussing on a very narrow task, DeepMind aimed to develop ‘General-purpose learning algorithms’ which would have a very broad range of applications. He outlined a sketch of how these works by showing the agent model:

  1. The agent receives perceptions from environment through a set of sensors
  2. The agent interprets these and decides on an what action to take
  3. The agent performs the action and goes back to (1)

While step 1 and 3 are easy to achieve, step 2 is where advanced artificial intelligence is needed and this is what DeepMind has mastered. Demis showed some demos of how their software was able to, only by watching the screen and being able to control the joystick, win any of the old Atari games. Because they had made their learning algorithm as general as possible, it didn’t really matter what games the software was playing, it would quickly learn what optimal strategies to use and become better than any human player. All they had to tell the algorithm was that a high score was good.

Demis finished his talk by answering questions on anything from self-driving cars to how a future with advanced artificial intelligence would look like.

I found the talk very interesting as I’m currently writing my final dissertation (Part II of the Computer Science course) within the field of AI and machine learning. You can read more about that project here.

Part II students’ summers

This week’s meeting of the Queens’ CompSci students focused on what our part II students did over summer (that being the summer between years 2 & 3 of the undergraduate course).A slide from Holly's talk about an internship at Facebook

Many secured a placement for an internship. This lasted about 3 months with a variety of companies including Facebook, Amazon TV and Palantir, taking place in California, London, Russia, Denmark and more. These students gained experience in industry as well as with new toolsets, and enjoyed many of the perks of working with huge companies – Facebook’s food being especially recommended!A slide from Jeppe's talk about an internship with Palentir

One common recommendation from students was to apply early in the year for internships – interviews can start around November, and if places fill up before they process your application you can find it hard to secure something for the summer. Queens’ starts C.V. help early in the year to aid you in this. Cambridge also offers summer projects in the Computer Laboratory to build on skills learnt in the year.

Other students chose to spend their summer on independent learning – Mistral devoted a large part of his time to researching malware and computer security, for instance. Meanwhile, Jake developed an iOS app for his location-based social network company (a joint project with other students), and also worked on his YouTube series (which is featured often on this blog) and web development.

Finally, the part II students held a short panel where other students could ask them questions, followed by a great formal dinner.

Meet the supervisors – Raphaël Proust

One of our new supervisors this term is Raphaël who will be supervising the Semantics course in the second year.  He’s written a short introduction about himself:

Raphaël is a PhD student. His research focuses on automatic memory management and intermediate representations for compilers. Blending these topics together leads to compile-time garbage collection. And once you start down that road you start wondering what is “garbage” and using “fix-point” as a verb and wondering why people even bother writing programs at all. Maybe that’s the road to a PhD… Hopefully.

Before Cambridge, Raphaël studied in ÉNS Cachan at the Université Rennes 1 and, before that, at the Université Paris 7 Denis Diderot. For as long as he has been able to select them on his own, he has always picked courses that try to fill a gap between the theory and the practice. Compilers are a good fit for that: modern compilers are a blend of a lot of theory and various engineering feats.

Welcome back

Welcome back everyone to the new academic year.  We have 6 new freshers who are joining us at Queens’ this year.  We also have a new student in the second year who is with us for one year on the Cambridge-MIT exchange.  Finally, we also have one student returning to us in Part III (fourth year) who has just spent a year away on the Cambridge-MIT exchange.   If you are interested in going on that then the details are on the department web pages – or talk to me.

So a warm welcome to Alex, Adam, Bradley, Rob, Sam, Navid and Tatsiana.  And welcome back Jan.

A Computer Science Supervision

Here’s another video from Jake about supervision in Cambridge.  The video is of the final supervision that I give for the Concepts in Programming Languages course.  Concepts is a really fun course that covers the history of different programming languages.  The idea is that by thinking about how languages have evolved over time you might be better placed to exploit (or invent) new ones.

This has some nice overlap with my research at the moment too in which we are looking at how scientists use Fortran and how the language has evolved over time.  You can see a bit more about this on the New Approaches to Programming in the Sciences (NAPS) webpage.

The supervision took place near to the exams and so you’ll see me at the beginning talking about choosing exam questions.  This is unusual since Cambridge exams take place at the end of each year and so for the rest of the time we are free to focus on learning without worrying about exam strategy.

Note Jake’s comment that the supervisor will try to ask you questions that interpret the course rather than just repeat the facts.  I think this is the whole point of a university education – we don’t want students to just learn the book by rote but instead we want them to be able to link the pieces together and apply them in new ways.  In teaching terms this is called a deep approach to learning.