How CPUs Do Math(s) - Computerphile

Matt Godbolt continues the story of the CPU and explains how machines do addition
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharanblog.com
Thank you to Jane Street for their support of this channel. Learn more: www.janestreet.com

[@gougify]

The fact that Matt Godbolt can't do simple arithmetic and get 7+4=10 warmed my heart and reminded me that you can be brilliant and still be bad at mental arithmetic

[@MattGodbolt]

My maths is awful which is why I tend to rely on the computer for everything!

[@hdaalpo]

Clearly he accidentally used base 11.

[@Krzysztof_z_Bagien]

At least he got the most significant digit right :D

[@positronalpha]

Off by one, of sorts.

[@RabbitInAHumanWoild]

As someone who has written lots of assembly code I found this to be a lot of fun.

[@cigmorfil4101]

Back in the day (1984) i had to write a program that generated all the digits of a very large number; to know the program was running and not crashed, and to make the most of the 32kb (32,768 bytes) CBM PET I used the screen memory for part of the processing (it also added an extra 1k (1024 bytes) as the 32k PETs actually had 32k plus a separate 1k for the screen. To allow for system buffers, etc (I sent the result to the printer) the normal memory available started at 0x0400 and ran up to 0x7fff - 31k (31738 bytes)! Using the extra screen memory betwenn 0x8000 and 0x83ff I got a full 32k for the data - the program itself, IIRC, was placed in one of the cassette buffers - my program could handle much larger numbers than we were required to process (it had 904 digits).

[@user-lt2rw5nr9s]

I just realized that Matt Godbolt wrote Compiler Explorer

[@MangoJones139]

Ha, I wouldn't even have realized that without your comment. 😅 I really like messing around with compiler explorer. It's such a great tool to understand how compilers interpret and optimize your code and also a great tool for teaching. Matt also seems to be a genuinely nice person. 🙂

[@luketurner314]

Thank you for introducing me to Compiler Explorer

[@Yupppi]

It's not known as Godbolt for no reason!

[@phizc]

I actually knew that, but I didn't know it was him in the video 😅. Cool.

[@aDifferentJT]

I think you mean that Matt Compiler Explorer wrote Godbolt

[@LordElrond8]

Reminds me of the game "Human Resource Machine" which is basically all of this but inside a puzzle game.

[@MattGodbolt]

I was recommended this game after the last video was published...and now I'm addicted to that too :D

[@urgay1992]

There is also the sequel called "7 Billion Humans" which introduces multiple workers collaborating!

[@retop56]

@@MattGodbolt You should check out Turing Complete.

[@KribensaUK]

OMG I had that same book and had totally forgotten about it until this video. Thanks for the memory!

[@VincentZalzal]

Matt Godbolt is so good at explaining things at the right level for the audience! I've seen him describe really low-level stuff at conferences, but he's also able to explain CS basics like this for everybody. Great stuff! Hope to see him again here soon.

[@alexlandherr]

At 4:17, in an effort to solve some problems from Project Euler in C++ I implemented what’s essentially column addition and multiplication on integer number strings. Another was exponentiation where one function argument was the number string and the other was a regular integer type since I used repetitive multiplication. Since my code was purpose-built for specific problems it can’t handle floating point arithmetic, division or subtraction. But I can compute ridiculously large factorials…

[@jeromethiel4323]

An interesting side note is the Z-80 (probably the 8080 as well) could at the metal layer, do BCD math. So saying your "hypothetical robot" could only handle two base 10 numbers in 8 bits is actually what could have been done in the 1980's, at the machine level. I'm betting this was a holdover from the Intel 4004, which was designed to be a calculator chip after all. And a 4 bit processor (which the 4004 was) could handle one BCD digit at a time. While i did a fair bit of Z-80 assembly programming back in the day, i never actually used BCD mode. But it was there if i wanted to! ^-^

[@MattGodbolt]

The 6502 also had BCD mode! I didn't think to talk about it as I figured it was too anachronistic but good point!

[@euromicelli5970]

Very true. For completeness, x86 processors (“Intel-type machines”) also support BCD arithmetic much for the very same reason; however the BCD instructions are no longer available when running 64-bit code (this is because in practice they are never used in modern code, and AMD was not afraid to discard complex instructions that nobody used to make space for more useful features, or for efficiency)

[@cigmorfil4101]

Not quite. The Z80 didn't do BCD arithmetic at the metal level but instead noted when an addition of BCD was done and then a separate instruction DAA (Decimal Adjust A) was subsequently required after each add or subtract to correct the binary result of adding two BCD numbers back to BCD. The 6502 however _did_ have a full BCD mode "at the metal level" whereby setting a flag changed all ADC and SBC instructions to work with BCD and not binary - a real hardware BCD.

[@GeoffryGifari]

Greatly enjoy these low-level computing lectures

[@zzzaphod8507]

Interesting video, clearly laid out, thanks

[@cemlynwaters5457]

Terrific video 🎉

[@muizzmuhammad]

Great stuff

[@jeromethiel4323]

What we need to have on this channel is an in depth video on binary scientific notation, or floating point numbers. Still having a hard time wrapping my head around that. Much more at home with integer math, as it's easy.

[@3rdalbum]

Good video. I never considered before now that carries in addition could only be 1; but as soon as you said it, it all clicked and was obviously true. I also was fascinated by turning conditionals into a mathematical operation that would result in a flag being set or cleared, and the hardware using this as the true branch condition. It makes sense though. Does this still happen on modern CPUs or can they now do numerical comparisons "natively" in hardware?

[@MattGodbolt]

Many CPUs still do it exactly that way. They have a "compare" instruction which is exactly the same as subtracting, keeping the flags afterwards but throwing away the result. Then if equal: the zero flag is set. If the second is greater than the first the result is negative so the negative flag is set. So various combinations of the zero and negative flag can be used to handle >, >=, =, !=, < etc etc. Other cpus might have a dedicated "compare and branch" type instruction, and...deep down inside x86 CPUs a sequence of compare-then-branch instructions are turned into a single micro-operation. But that's definitely another video :-)

[@Yupppi]

Damn he's good at explaining computer stuff.

[@dickybannister5192]

nice explainer. thanks. as an aside, just watched an IAS lecture by a guy called Ian Mertz. think he is from Warwick. some work on the Tree Evaluation problem (with James Cook). he came across well, and a problem that sounds explanable. thx again anyway.

[@ChrisWalshZX]

I'm going to write this in Z80 tonight for my ZX Spectrum!

[@olafurw]

[@MattGodbolt]

❤ right back at you @olafurw

[@GeoffryGifari]

It is mentioned that the "carry flag" is raised whenever there's a carry for the next digit. Is "lower down the carry flag" also a separate command when there is no need to carry? example: 149 22 _____ + 9 + 2 = 1, carry 1 4 + 2 = 6, + carry 1 = 7, no more carry 1 + 0 = 1 and we get 171 In the second step, should there be a command "lower down the carry flag"? In other words, is the carry flag always raised after it has been raised once?

[@cigmorfil4101]

No. Every time an arithmetic operation is done, if a carry flag was raised, the extra 1 is adddd and the flag is lowered. The result of the addition is checked and the carry flag raised or not as appropriate.

[@ThomasGanterPrien]

6502 did have BCD mode in which each byte was *exactly* like in the video representing a two digit base 10 number. So the end of the video could have shown those, no need for hex. (Yes, i am that old to have worked on these machines back in the early 80s)

[@cinderwolf32]

Double dabble :)

[@Computerphile]

kzbin.info/www/bejne/m4msl41nrrB5oqM

[@cinderwolf32]

@@Computerphile I think I vaguely remember referencing this video when I was trying to learn Z80 asm. It was around about this time!

[@trevinbeattie4888]

When I came in I thought it was going to be about how the ALU performs addition; turns out this is more about how a programmer would add arbitrary size integers in machine language. Still enjoyable though; brings back memories. :) I’d also like to point out that the carry flag is something I’ve _only_ seen in machine language. High-level languages tend to just throw away any overflow, so the programmer has to write extra complicated code to handle it if necessary.

[@MattGodbolt]

A very fair point there! It is indeed rare to use the carry on high level languages, it's hard to access in C or C++ without vendor extensions even. So, this tale of how 8bit machine do maths was more a stepping stone to show how the earlier video can be made "real" with numbers that fit in the pigeon holes more than really about ALUs. I hope to get there eventually though! We have a long way up, and down, to go to explain how everything really works :-)

[@casperes0912]

Yeah. Though on optimizing compiler can recognize the patterns and simplify the produced assembly. Higher level languages intentionally hide that sort of thing for compatibility reasons. Then they can run on machines that don’t have carry flags

[@klfjoat]

Yeah, they're computer scientists, not computer engineers.

[@somedooby]

It's extra convenient if you don't need the overflow though. With cryptography code, where reallocating dynamically sized BigUints can leave some sensitive data in memory, it is particularly useful to use fixed size numbers such as a [u64; 6] for some arbitrary operations. But there are probably a lot more use cases where the overflow is necessary

[@SlideRSB]

It never occurred to me that 1 is the the most you'll ever carry in addition in bases other than binary.

[@ipadista]

hm if you multiply 99 * 99 you would get 9801, so if your cpu/robot does multiplication, the "only need to carry 1" analogy doesn't work

[@SlideRSB]

@@ipadista My comment was referring to addition, not multiplication. Also, I believe the ALU usually performs multiplication through addition.

[@cigmorfil4101]

​@@ipadista To multiply on a 6502 for example, you have to write your own routine. You basically loop over all the bits of one of the multiplicands whilst doubling the other. Whenever there is a one bit you add that doubled value of the other to the result. Each addition can create at most 1 bit of carry during the processing. So to calculate: result := 0 num1:= 99 num2 := 99 loop if num1 mod 2 = 1 then result := result + num2 num2 := num2 + num2 num1 := int(num1 ÷ 2) until num1 = 0 In the addition stage there will be a carry of at most 1. The additions carried out are: 0 + 99 = 99 99 + 198 = 297 297 + 3168 = 3475 3465 + 6336 = 9801 Similarly in each doubling there will be a carry of at most 1. The CPU has instructions that multiply and divide by 2 in binary. The checking for the number being odd and dividing by two are combined into a single instruction that divides by 2 and results in a remainder (in the carry flag) if the original number was odd.

[@richardtwyning]

I was really lucky to grow up with the best processor of its time aged 12 in 1982. The Texas Instruments TMS9900, 16-bit, and it was big endian

[@GeoffryGifari]

A bit further from the topic, but if I have the number 0 in the integer data type and the number 0 in the float data type, would the memory space those two take up be different?

[@geeempee]

There are different sizes of integers and floats to choose from when coding, so it depends. One of the common sizes for integers is 32 bits, and floats can also be 32 bits, so in that case they would be the same, but they could be different. In general, each data type has a fixed memory size no matter what value it's currently representing.

[@Elena-gs2bv]

Excellent🎉❤🎉❤🎉❤🎉❤🎉

[@lostwizard]

Wouldn't 10's complement work just fine for signed numbers in your decimal scheme?

[@MattGodbolt]

They would; but I felt it was complex and abstract enough without going in to it! If/when I do binary here, then pointing at the 'top bit' as being negative is sort of easier and more intuitive than "if the first digit is 5 or above, then ..." etc

[@lostwizard]

@@MattGodbolt Indeed. Perhaps as an "extra" for people to watch after the binary 2's complement stuff. Then again, it was only in my head because I was doing BCD floating point on a CPU without "Decimal Adjust After Subtraction". There's a great way to asplode heads.

[@bertblankenstein3738]

Going back to the 6809 flags: carry, equal, zero? hmm that's what I can remember. I seem to gobo there is a interrupt flag, and a total of 8 flag, to make an even byte.

[@MattGodbolt]

Equal is usually the same flags as 'zero', and then there's negative. Overflow is usually in there too, and maybe a parity flag. 6502 had a couple of bits that were essentially unused in its 8-byte flag register

[@bertblankenstein3738]

@@MattGodbolt I looked online. There is a half carry, and you are right, a zero flag. I'm not sure why I remember BNE mnemonic. Some other ones.

[@MattGodbolt]

@@bertblankenstein3738 there definitely a BNE which checks the zero flag. All the comparisons voilo down to zero and/or other flags like negative :)

[@klfjoat]

I just found out that the presenter has a whole compiler explainer website. But can we get the bite sized basics of compiling C to assembly/machine code explained in a Computerphile? I have done hand machine coding of a 6502, but aside from "compiler turns C into machine code", never learned anything about compiling. Like, what's the object file & linking about? Why is GCC's default compilation target named a.out, is that an interesting thing? Etc.

[@MattGodbolt]

If I get time and Sean has the patience to let me do it, I'd love to get there :). I have some long form conference talks on some of these topics but they're aimed at folks already with a decent understanding of compiling. Bite size would be ace if we can find the right way to do it!

[@cigmorfil4101]

The a.out default comes from way-way back when Unix was first developed. It stands, I believe, for assembler output as it was the result of assembling the C processed code into machine code. Put simply, linking is the dragging in of the code for the library functions you've used (eg the library containing the code for printf) and linking in the calls to that function. To learn C I used a book which created a small (reduced function) C compiler. It converted the C into an abstract machine, ie compiled the code into an intermediary pseudo assembler code, parsing the C syntax, etc. This intermediary code was then translated into the actual code of the processor used to run the program. It seems an odd way of doing things, but means that to get the compiler running on different processors only required the rewrite of this final assembler and not having to rewrite the whole code. For example the C statement x += a

[@andyh7152]

Smashing the stack for fun nd profit :)

[@JerehmiaBoaz]

The bcc to a clc instruction pains my heart. (If you branch only if the carry is clear, you don't have to clear the carry after branching.)

[@MattGodbolt]

Yeah, I should perhaps not have done that. But I. General if you're doing a multibyte add you need to clear and so I just went with the simple but I could have easily saved a few cycles there, and made a good point about how optimising code can be like this, sometimes.

[@boberickson9887]

Message to Matt Godbolt: GO PACK GO!

[@Quarky_]

Anyone interested in software engineering should really listen to Matt's podcast "Two's Complement"

[@ytnoo]

6502 forever!

[@mytech6779]

The reason little endian is difficult is because you (and most programs) are dispaying the memory reversed. The normal custom is to display the least significant bit/digit of a number on the right, (because numerals came through arabic and that is written from right to left). Memory may be externally addressed at the word or byte level but internally it is just an array of bits. When you are displaying the content of memory as shown in the video, you have placed the least significant address to the left while displaying the content of that address with the least significant bit on the right. When using little endian; If you sensibly coordinate the display of addresses and contents with the least significant both right or both left, the stream of bits makes a lot more sense and even large multibyte numbers are unbroken in-order sets of bits. This is how the machine actually works with the data.

[@lorensims4846]

Little-endian addressing only makes sense in the context of eight-bit computers. It's ridiculous for modern computers to continue to use little-endian addressing. It's not like compatibility with the 8088 is still a thing.

[@jursamaj]

Your 2 solutions do indeed makes large numbers "flow". One solution (little bit to left) has the number backwards to what to what we use in all other numbers, and so would be no more clear than the current mess. The other solution would reverse the flow of bytes that *aren't* numbers (ascii text, instructions, etc.) which would also be worse than the current mess. So both "solutions" are no solution at all. OTOH, big-endian storage eliminates the problem altogether. Since it makes no difference to the computer, but makes things clearer to programmers, that would be the better solution.

[@mytech6779]

​@@lorensims4846 Even 64bit machines do multi-word arbitrary precision math. How can I clarify what I wrote? Little endian puts the bits in order in the memory array from least to most significant. Big endian is like taking sleeping pills to counteract excess stimulant use, it would be better to avoid the stimulants in the first place. The underlying problem is how people insist on displaying raw memory data reversed. Or on a larger [less practically useful] social scale the way we write numbers backward [decending order] relative to normal english. If we were consistant with normal ascending counting and writing (eg zero, one, two , three, four...) we would say two thirty fivehundred(0.235), not fivehundred thirty two(532.0) The reasoning is because the normal left to right flow of the language makes it very difficult to display a reversed stream of bytes, you can only do this if you know the highest address in advance, and step through in decending order. (Internally reversing fixed size blocks is another option, but the blocks as a group will end up out of order. So not a complete solution.)

[@DrGreenGiant]

Don't forget that machines work in words and not bytes. The whole right to left vs left to right issue is only a thing when representing something smaller or larger than a word.

[@mytech6779]

​@@DrGreenGiant That's about 60 years out of date. amd64 machines work on bytes, cache lines, and several register(word) sizes from 8bit to 512bit.

[@RiscTerilia]

Professor Brailsford when he hears someone say Fibonacci grows quickly "hold my beer"

[@Pepespizzeria1]

Depends how accurately you calculate it

[@gavmckee1]

Are you wearing a bears hoodie @matt 😂, surely this is Vegim’s influence 😂

[@TheKingScrod]

I think the term would be Andro-pomorphized

[@jursamaj]

Except andro- and anthro- both mean 'man'.

[@PasqualItizzz]

That poor tea, just sat there going cold 🥶

[@MattGodbolt]

Waste of a good tea bag! And the ones I like aren't cheap to get in the USA either! 😂

[@ristopoho824]

I have a hard time explaining pigeon holes to people. The word itself translates to Finnish badly, and i'm sorta young and hang out with people mostly younger than me. So. Yea some people imagine pigeon post being only the aristocrat with one bird in a cage they see in movies. But. Well postal services did use them. And. Yea. I don't really know how they worked either, should probably find a documentary about it, could be interesting. Anyway. My favourite logical reasoning trick is to first of all see if a problem is a pigeonhole problem. Because that may make a hugely difficult problem borderline trivial. And that feels good. So, i tend to quite often have the need to explain people why it is named for pigeons.

[@cyberneticqualanaut7207]

A very important point about respecting rules to keep a cohesiveness to a society or culture. In contrast to the US at this point in time, we are fracturing, because some political factions think they are above the law or that the rulings of the Supreme Court are not binding or that experts are not to be respected because we have so many merchants of doubt sowing dissent. We are in a very dangerous juncture of history.

[@guilherme5094]

👍

[@StephenDix]

That is not the accent I associate with that sweatshirt. Daaaaa Bearssss

[@pierreabbat6157]

Why do you do CLC and then ADC instead of just ADD?

[@MattGodbolt]

I'm slowly morphing into real actual 6502 assembly (which I show at the end); and that doesn't have an ADD instruction, only ADC. I should perhaps have glossed over this and had both in my toy CPU, I'm sure the point would have been similar, but it was also useful to show that the CPU sometimes has to change its own flags directly too. Thanks for the feedback!

[@gradientO]

First time I'm seeing the man behind the voice 😂

[@ZT1ST]

About the "Carry" flag being only 1 or 0 - I take it that there's a different flag for carrying with multiplication?

[@ryan0io]

For the 6502, which seems to be the targeted processor here, it can't do multiplication, not in hardware at least. It can only add / subtract, and other instructions like bitshift. Multiplication / division, needs to be coded in assembly using available hardware instructions.

[@scrambledmandible]

​@@ryan0ioIn addition, for x86_64 at least, if you DO have multiplication, it'll typically use register pairs to handle the result, storing the high half of the result in one register and the low half in another

[@fllthdcrb]

@@scrambledmandible Okay, but I thought we were talking about old 8-bit CPUs. Neither the 6502 nor the Z80 have multiply instructions (left bit shift/rotate notwithstanding). Therefore, flags relating specifically to multiplication are a non-issue.

[@navalenigma]

Looks like Matt is a 6502 guy, least the mnemonics hint that way.

[@kevmccarthy8311]

I can’t take this seriously from a Chicago Bears fan. 😂

[@RonJohn63]

Why is Matt wearing a *Chicago Bears* hoodie?

[@MattGodbolt]

I've lived in Chicago now for 13 years and some stuff just kinda seeps into you after a while :)

[@RonJohn63]

@@MattGodbolt 👍

[@qugart.]

Learn that stuff and beat Human Ressource Machine in a jiffy

[@rakshithgowda5384]

❤

[@guillermotorres6376]

Almost anything is human readable if you have enough patience

[@DrGreenGiant]

You should try reading my doctors handwriting lol

[@christophermoran7570]

🐻⬇️

[@ecavero1]

7:49 I finally understand what all this endianness is all about!

[@BongoBaggins]

It's just maths, cheers.

[@TjaMeu]

I completely agree with @JustFamilyPlaytime. I love Computerphile but these videos remind me of my math teacher in high school: incoherent and condescending. With a bit more effort and going a bit deeper, you could actually teach something. But this video just confuses things.. Explaining some things in too much detail and skipping over other details.. and come on: pigeon holes and abacuses??

[@SyntheticFuture]

I know what a pigeonhole is thanks to Taskmaster 😂

[@metalhos]

i guess that's the reason i never had any interest in learning assembler. even the simplest things have to be programmed in the most complicated way.

[@JaspervanStijn]

I think the PC designations are 'little-native-american' and 'big-native-american' ;-)

[@lorensims4846]

Actually, the terms "little-endian" and "big-endian" come from Gulliver's Travels to explain the dispute between the Lilliputians and the Blefescuians.

[@pierreabbat6157]

One little, two little, three little endians... What are high-heels and low-heels in computers? And what are the Mac designations?

[@davt8355]

My advice to kids out there (students). Computer science is not going to pay your bills or give you a job but IT does!

[@finna1121]

some of worst advice I've seen in years. amazing.

[@Skittles20p]

what's a abacus?

[@kellerkind6169]

As I understand that might have been a joke, if it's not then let me ask "what's google" ;-)

[@IceMetalPunk]

It's when you make out with a famous Swedish pop group.

[@Nope-w3c]

@@IceMetalPunk Is it Europe? :p

[@cinderwolf32]

This is either a joke making fun of Apple or a genuine question and I cannot tell which

[@IceMetalPunk]

@@Nope-w3c No, that would be a Europecus 😜

[@kappa2454]

😮

[@aesthetesw8159]

Umm actually... Big Endian and Little Endian is from Gulliver's Travels. Look it up 🙄

[@SynthSoundscapes23]

First

[@JustFamilyPlaytime]

Title - "How do CPU's do maths". Content - "I'm not going to talk about binary". Dumbing down ain't in it. Grow up and stop with the condescension.

[@MattGodbolt]

Thanks for the feedback; I was trying to get to the part where I show the code running on a real CPU. It's always tricky to know which parts to simplify and which to go in depth, and trying to fit it in a short enough video can be a challenge. Hoping to do more and go into more depth in future though!

[@cigmorfil4101]

​@@MattGodbolt With the 6502 you could have gone full BCD with the additions for the fibonacci and seen 01 00 01 00 02 00 03 00 05 00 08 00 13 00 21 00 ... in memory (encase your loop within SED and CLD).