I also love vulkan for having to write 1000 lines of code to render single triangle Yeach, I know, you can write everything in a single line of C/C++ code
In the real early days of computers, doing anything at all on them was a long series of hard problems that had to be solved one at a time. As we (humans in general) got better and better at it, we built up libraries of routines that we knew how to call. You want to know why Linux and related operating systems have so many small command line programs in them that you string together on the command line to accomplish a larger job? This is why. Every single task was viewed as a problem that needed a solution. You would write a program that did that one task as well as it could possible be done. Then when you have a big job requiring many different tasks to be strung together, you just call into all the little task programs, passing the inputs and outputs of each task in a big line. That kind of logic can be extended to solve a great many different kinds of jobs, all while using tested and time honored code to do small tasks, one at a time, as well as possible. As computers matured, and different philosophies were developed about how computers should work, new ways doing things were invented. Linux kept its model of small tasks strung together into big jobs. Other environments like Windows decided to go with a more user friendly approach. In the early days, if you wanted to write a book, you would use a program to type in text, and save it to a file. Then you can run a program on that file to output spelling errors (any word not in a dictionary). Then you run that into a formatting program to paginate, format, etc. your text, and save it as a new file on the computer. Then you can send that formatted file to the printer and it will physically print the document. On Windows, you open a program specially written to allow you to enter text, format it as you go, check for spelling errors on the fly, allow pagination and printing, all in one program. The downside? What happens if you want to do combine two documents into one? In Linux, you can just concatenate the text files right on the command line with a pre-written tool. In Windows, you have to hope your "does everything" program has this functionality built in, or use a different program to combine them. What is you want to print different kinds of files? In Linux, the same program that sends data to the printer can take any pre-formatted input and send it to the printer. No need to reinvent the wheel for printing, just write a utility to convert your existing file into a language the printer understands, and use the already existing print program to finish. In Windows, every program that needs a print function has to implement their own logic for how to handle this. Different programs can end up with different printing features because they implemented it differently. In more modern times, converting a file into something the printer can handle is usually accomplished by the printer driver. Your program just converts whatever it needs to print into effectively a big image, and then the print driver turns that into directions for the printer. This varies of course). I'm just scratching the surface of an enormous amount of complexity, of course, but hopefully you get a sense of how difficult those early days were, and how different philosophies dictated different platform designs.
Things were just different back then. Life was simpler and programs less sophisticated. I once had to take the square root of a 96bit binary number which took a bit of research and then a couple of days to program in assembler. Great fun and very satisfying. We never wasted clock cycles because processing power was precious. These days it's squandered in the most appalling way.
@@rogerfroud300 I think the largest waste of processing power we face today is the myriad of interpreted languages. Since nearly every web site used at least a little JavaScript, basically all of us are affected by it at least a little, but I'm thinking more along the lines of python used for heavy data manipulation, or PHP and all those myriad of interpreted web hosting languages running in data centers. Relatively few modern applications are actually compiled down to machine language. Most of them only compile to an intermediate language of some sort, like C# and VB to, and I think that includes Java (but I haven't used it personally). I wouldn't be surprised to find out that huge sections of our operating systems were written this way. Those extra clock cycles get turned directly into wasted energy and increased CO2 in our atmosphere. It's not a big deal performance-wise today because our modern computers are thousands of times faster and more efficient than anything we had back then. But still, it seems like a waste. As a C# programmer myself, I'm not going out of my way to change, because these levels of abstraction really help us get our work done and hold costs down.
@ For the record, I started programming about 5 years years before I was first able to dial in to my university's VAX. I learned to program from books and magazines in the early 80's. What amazes me is the early programmers didn't have ANY references, just their brains and the basic tools the hardware provided.
@@yarik12341 That's only when it tries to substract 1010 from 1000 (not 10001), and since 1000 is smaller than 1010, it ends up with negative numbers. It's all 1 at the beginning because it rolls over, and incidentally that's how negative numbers are stored, by beginning by 1.
I started out on the 6502 almost 40 years ago. Beyond the nostalgia, it’s great to see, in the comments here, new generations experience the joy and wonder as I did so many years ago. Awesome job, Ben.
6502 isn't just for nostalgia. It's incredibly elegant for what it is, and can be used for countless everyday tasks. Using more complicated systems for simple tasks is asking for trouble
To me, this is the most magical part of technology. It’s not AI, Machine Learning or front end web development frameworks. There is no place I’d rather be than circuitry, processors and low level code :-)
Man, I've been struggling how to do that without Decimal Mode for months. I'm working on a calculator program on the NES and have been running into that program again and again. Every time I looked up how to do it on 6502, they always said "Use Decimal Mode". But the NES's 2A03 doesn't have a decimal mode! I could hug you!
Fun fact: the NES got away with using a 6502 without paying for the patent by doing away with decimal mode. Without decimal mode, the 2A03 no longer fell under the patent protection for 6502 so MOS couldn't stop them. The funny part? The silicon for decimal mode is still on the chip, just with the proper wires cut off to prevent you using it!
To do it efficiently, I'd suggest focusing on a routine which, if A is in the range 0 to 9, will perform a div-mod operation with a value whose upper byte is in A and whose lower byte is fetched via (someZP),Y addressing mode, storing the quotient in (someZP),Y and the remainder in A. If after doing that one decrements Y and loops if it's non-negative, one can easily perform a div-mod by ten for any size of binary number.
And this is why I think he did it this way, vs. using BCD as others suggested.. The concepts here go beyond the 6502. I "grew up" doing 6809 assembly, and was able to follow this, even if the opcodes are different to me. Explaining it with the simplified BCD mode makes it specific to only this processor, and you lose a lot of value IMHO.. THis video was awesome!
@@flatfingertuning727 Yeah, there are lots of ways to do it. (Using tables can really speed things up!). However I like the way this video elegantly describes the concept, and it's quite impressive that the whole thing only uses a few bytes..
8:20 - When you keep leveling up your computer engineering skills, eventually you get the power to infinitely unfold paper with the next calculations already written on it. :)
I remember when this algorithm was first present in a computer architecture course I took. I was in awe of how they managed to take such a complex process and turn it into something so elegant. Your thorough explanation of it here is top notch, and if/when I need a refresher, I'll be sure to come back here!
@@ggldmrd5583 I am not sure about that. First of all, how do you defined "better"? Shorter code or faster execution time? In terms of execution time, it of course all depends on the excact number of instructions and the number of cycles each instruction takes. Here is a high level analysis for a 16-bit number: the long division takes shift 16 loops per decimal digit found, so the worst case runtime is 16x5=80 loops. Double Dabble takes 16 shift loops plus 5 loops within each shift loop to check whether each power of 10 digit is >4 and then add 3 to it. So Double Dabble always takes 16x5 loops, whereas long division can finish in 16 loops for a number 4, add 3 (in the correct position) if necessary - sounds like a lot of instructions and cycles to me.
@@ryanhaart Well, what I defined as "better" was the shortest one in terms of ROM usage (shorter code). To be honest i didn't really check, but i think that i don't take too much risks saying that double dabble implies shorter code, cause the algorithm for the division seems long enough to me for that sort of task, but i might say something false when i say that, cause i didn't check and it's just an intuition. If you prefer the one with the shortest execution time, then i think that it would be more interesting to determine the complexity at worst case depending on the size of the number to convert (instead of the complexity at worst case for a given number of digits). It's not difficult to determine it anyway, the quetion is to know wether it's linear, exponential, quadratic, ...depending on the size of the number.
A few years ago in my first year at university I wrote a 6502 emulator for fun in C#. I only ever got around to testing each instruction individually before I got bored. Your 6502 videos have re-inspired me and now I want to test this program on my emulator!
Another method of extracting the digits is performing repeated subtraction (until it is the last number before going negative) left to right: 255 -> 155 -> 55, this takes 2 subtractions by 100 to get the hundreds digit, then 55 -> 45 -> 35 -> 25 -> 15 -> 5 which takes 5 subtractions by 10 to get the tens, and we now have the ones place which is already there. Its like counting bills but starting at the highest denomination without exceeding the price of a product.
Yeah, I got the same idea. I would love to know what are the advantages on each method. This method seem simpler. But I think that for bigger numbers you may do more iterations. The number of opcodes seem very similar. It would highly depend on the language. It doesnt use ROR but does need increment (to count the number of subtractions) and a conditional jump on borrow. And it looks like you use the same number of registers.
This method is much faster, because it uses at most 9 subtractions per digit, whereas the division method used as many as there are bits. Also you get the result in the right order. Only downside might me larger code size because you need all the powers of 10 as constants in ROM. For 32 bit numbers that would be an extra 36 bytes.
More complex ISA that actually have a div instruction _still_ do this algortihm underneath automatically in hardware. That's why if you check the datasheet for them, the div instruction takes ~16x cycles to complete than a normal instruction (for the appropriate word size)
There is a huge literature on the design of divider circuits and they get much more complicated than bitwise long division. The tradeoffs to consider are mainly how often does a user need to divide integers vs the energy/space the architecture is willing to spend on it.
I think for me the hard part of binary maths is the cascading carry or borrow. The rotating of the number automatically pushing the answer into the "memory" spot was elegant as fuck. Nice.
The joy I'm feeling being able to witness a demonstration of how a computer does math at the machine level is indescribable! (At least somewhere between machine level and assembly ;p ) I am a visual learner who once seeing a demonstration can picture what a written document is describing. Sort of like needing a Rosetta Stone to understand the syntax of a text. This video series has welcomed me back to an electronics hobby I abandoned some 25 years ago as a teen. Thank you for posting these!
That's not praiseworthy. He's dramatically over-complicated things. This video should have been around 10 minutes. At least I remember why I avoid this channel. Ugh.
@@recompile he goes over everything in great detail so everybody can understand it and it also gives a massively deeper understanding of what he's trying to teach
@@recompile You sound like that edgy kid who thinks he's better than everyone else. He makes introductory videos on electronics, and is a good teacher. He's not like those channels who are like "So I coded everything off-camera, here's 500 lines of code, good luck understanding that crap". You must be in a happy relationship with that attitude.
Instead of reversing the string with code so it appears "correctly" ordered in RAM, why not just write the values into RAM as you go, and use the Y register to count how many results you get. Then when you're done, just decrement trough the Y index and print each character, thereby removing the need for a code to iterate trough the string to insert a character. Just a suggestion.
Alternatively, push values onto the stack, and then when you pull they'll come out in the reverse order which is exactly what you need. You'll need to know when to stop pulling from the stack, for that you can either use the Y register as suggested above, or just put a special marker value first, which would indicate that the sequence has ended. Given that the only possible values are 0..9, any other value will work. Maybe even better, use zero as a marker value, and put all values onto the stack shifted by one, just don't forget to decrement them back by one when you pull them from the stack.
"So we're going to do this rotate left, right?" It's like talking to my dad "So we go left, right?" "Wait, left, then right?" "No, left, right?" "Right?" "No, left" "Left?" "Right!" 🤯
Yes - I'm amazed I can still remember all the mnemonics and hex opcode values. I was only about 15 when I moved out of 6502 asm and into x86 and ARM2 asm.
@@gorgikalamernikov3260 Just reserve like 4 bits to decide the amount it moves from the center and 1 bit to decide if it's left or right. There's probably problems with it but my original comment was just sarcasm.
@@puppergump4117 Yeah, that's pretty much how it's done actually, there's 8 reserved bits for a float32 to tell where the dot is... But nuance arises which is what the original commenter was excited about i guess.
I have a degree in IT so I have a pretty good understanding of how to USE computers and some of the basics on how they work, but this channel is awesome because it really makes the ultra low-level stuff click to explain how they work on a physical level. Never ceases to fascinate me, I really appreciate the effort that goes into sharing this stuff.
Being a software developer really like your videos for the insights they provide how things work under the hood. Would have been really helpful if u had a playlist for microprocessors and assembly language in general. I can vouch a lot of software folks would be having a blast if you had such a playlist and then would find a video like this much more understandable and enticing.
There's a much easier way to convert binary numbers to decimal on the 6502. Essentially, you left-shift the value out of the input 16-bit word (MSB→LSB) and left-shift the carry flag from that into the output 16-bit word. Mathematically, this just copies the value bit-by-bit from one word to another. Except that instead of using ROL:ROL to rotate the bit into the output word, you ADC the value in the output word to itself plus the carry from the first word, and instead of doing a normal binary addition, you do a Decimal-Mode addition (SED). The result will be in Binary Coded Decimal instead of binary, which is easy to convert into ASCII, and the output word will need to be three bytes in size to hold results over 9999.
I really hope @eaterbc sees this that was impressive sir ... might be a vid for much later in the series as Ben has not even TOUCHED Decimal mode nor 60% of the ASM calls on the 6502 but I'd love to see Ben keep going into a 6502 master class type of series .. Not that making vid for YT is easy ... Just wish it was a bit faster This is one of my little joys each month so far :D
Good plan, but perhaps Ben did it the long way to demonstrate the basic method, instead of using the decimal feature on the 6502, which hides/avoids the basics.
Very good video! You have no idea how good you explain stuff. I have literally never seen anything related to assembly other than the fact that its a very low level machine language and I was able to follow along! The visual representation of the algorithm was excellent. It shows that you really have a passion for teaching which I wholefully appreciate as a comsci student! Thank you for making this. I will definitely look into your other stuff :D
Ben, where were you back in 1982 when I was learning about binary math. This is some very elegant coding and apart form the print routine there is not one sign of a nasty little jmp instruction, everything is relative calls using bne or beq. You explanation of the math is very clear and my past teachers could learn a lot from your presentation style. Thanks for producing this video, I am sure that a lot of viewers who need to learn the concepts of binary math will benefit greatly from this video ;)
I'm envious of your 6502 computer! It knows the meaning of life. Great video BTW, about half way through now but had to stop and write a comment before I forget. I am very familiar with everything you covered already but I really enjoy a refresher and just to listen to your explanation of things.
Thanks for not skipping things, it really helps to understand the CPU cycles it's gonna take. I have whole new level of respect for long division method now.
And the first example was 42 - The Answer to the Ultimate Question of Life, the Universe, and Everything (in The Hitchhiker's Guide to the Galaxy by Douglas Adams).
I just wanted to say thank for explaining a filed that seems so intimidating in a such understandable way. You helped decide what I'm going to do in university
If you understand this video you should have no problems with CS courses for couple of semesters. I recommend watching linear algebra and calculus series on 3blue1brown channel and that's basicly first year done :D
@@igornoga5362 What you say is completely true. Damn there are lots of Ben Eater subscribers that are also 3Blue1Brown subs lol, and im also part of them.
*_Binary to decimal can't be that hard, right?_* Me: *There is probably a little twist to it* _sees video length_ me: *Oh yes, there definitely is a twist to it*
This is why I've subscribed to you long ago: Step-by-step instructions, simple but thorough explanations and no funny background music. Simply brilliant!
Brilliant stuff! Highly educational for all those new to understanding binary arithmetic and machine coding. For the rest of us old-school coders, I think it’s the first time I’ve ever seen someone fully demonstrate long-hand binary division. Certainly the first time I’ve seen someone who appears to have also written an iPad App in order to help demonstrate it? Awesome work Ben! 😊
Nearly 30 years I learnt electronics including most of the digital stuff going on in this channel. I did stuff on Z80, 6502, 8085 and 8086; I used Karnaugh maps for logic chips anf the 555 timer. I don't do this anymore but this channel is such a great trip down memory lane. Thanks so much for it.
Ben, thank you. I have been coding in ASM (6502) for YEARS... I always had trouble converting from binary to decimal (understanding it). You explained it so that my non-technical wife would get it. That is quite a feat.
Ben, this is an excellent channel. I am aspiring to learn about electronics, and I spend a lot of time browsing videos on the topic- your explanations are clear, you include examples of the relevant circuits, and you provide schematics for those circuits. Few channels tick all of those boxes, please keep up the good work. It' blows my mind how many channels that claim to be about learning about electronics and do not bother with a basic schematic, with the expectation that I reverse engineer that schematic by looking at parts on a breadboard.
Thanks! I found a few 16 bit divide routines and wanted to expand them to handle 32 bits. I had no luck. The clear walk thru of this 16 bit divide routine gave me the deeper understanding I needed to easily make it into 32 bits.
Thank you Ben and thank you to all the wicked-smart people contributing comments here! I’ve really enjoyed reading them and learning from ppls input and stories. This is pure gold!
Back in the 80s, I'd always try to avoid writing a division algorithm because of the time it takes to run and the time to debug. For printing a 16 bit number, to avoid a division algorithm, I would count the number of times I need to subtract 10000, add back 10000 at the end of the loop, then repeat the process with 1000, 100 and 10 (at the last step you are left with the units). You'll get the digits out in the order we want (with leading zeros unless you suppress them). It all depends on how much effort you want to go to, and how efficient you want your code.
@Mickey Farley It's not a general division algorithm is what they meant. It's more specialised for a 5 digit base 10 number, where as eater's algorithm can work for any base and any length just by changing the sub 10 to a different base and adding more bytes to the division "register".
Remember when the decimal to binary conversion took up the majority of the mainframe? People sure managed to find some really clever solutions to the problem especially given the constraints of that time.
If speed isn't important, the hardware required to perform integer binary to decimal conversion can be amazingly compact. To convert an N bit binary number to a D digit decimal number in NxD steps requires counters that can count from 0 to D and 0 to N, along with an Nx1 shift register for the input and a Dx4 shift register for the output, and a little bit of circuitry which could bit in a 20x5-bit ROM and a 1-bit register, or a modest number of gates.
Alternatives for reversing the string of digits: - push to head of string in memory, shuffling remaining bytes along string (as shown in video) - just use stack directly instead of memory, to store digits until output (risks stack overflow, but not in this simple case) - push digits onto end of string in memory, but then output string from end to start (so reverse as output) - push first digit to end of string in memory and build it backwards in memory, then output it forwards from start of string - just output digits to LCD from right to left using cursor control, as seen on a calculator (probably the easiest)
@@PewnyPL Actually the algorithm works fine without the second byte for mod10. The carry bit is set correctly after the first sbc #10 from the low byte and nothing is done with the high byte after the sbc #0.
That is fine if you only ever want to divide by 10... which is great for specifically decimal... but stops working if you need to divide by anything over 255... like say 1000? I know the first argument will be that we are not going that high however, the next steps in decimal is hundreds and then thousands, working the opposite direction and jumping to thousandths is where we enter the realms of engineering where that type of precision becomes a huge necessity. The other variation of that is dealing with fractions where it can get a bit strange as well.
Dear Ben Eater, just would like to say that your channel is fantastic! The tutorials are very instructive and I love to see them because it brings back memories, my days using a Apple ][ and programing in assembly language. Thank you for your great job. Good days I had in the 80's. I still have the Apple manuals, books, a few addon boards, DOS and ProDOS 5 1/4" floppy diskettes.
There are 3 points I want to make: 1) The left 16 bit was unnecessary I think. We only used first 8 bit of it. 2) There is a more efficient algorithm to convert binary to binary coded decimal(BCD) that shifts left each time and adds 3 if a BCD digit is more than or equal to 5. An example run is 4 bit binary 1111 which is 15 needs 2 digit BCD so 8 bits 0000 0000 | 1111 0000 0001 | 1110 0000 0011 | 1100 0000 0111 | 1000 0000 1010 | 1000 (since 0111 = 7 >= 5 we added 3 to this number before the shift happens) 0001 0101 | 0000 its the end we have 1 and 5 which are the digits we wanted. Shift only by the number of bits you have at your initial inputs. To know more about this algorithm check out double dabble 3) You could have used a stack structure to invert bits. Push all of them to stack and pop all of them at the end . But you can not use pha and pla since return from subroutine will read the return address from the stack and if you push something it tries to return to another address. You have to implement your own stack in the RAM.
I don’t think you want to skip out learning a generic integer divide algorithm, and jump straight to the bcd edge case. And the stack is available here if you want to use it, no need to try emulating your own.
Watched this video and compared it with my AVR assembly code for 40-bit conversion. The same and different. But that is how it goes with code. You find the algorithm, convert it in assembly, make it work, after that is has an input and an output. Now I remember I did double dabble. Nice refresher. Up to the next thing I forgot.
The double dabble is quite clever. It is effectively the "double" operation on an extra-wide register that is binary in the bottom and BCD on the top, repeated the exact number of times required to shift all the bits from the bottom register into the top one. It works well in hardware too as the dabbling step is parallelizable. I presume it can run backwards to convert BCD to binary too, again parallelizable
Doesn't the adjust have to be made to every BCD digit? Consider an 8 bit number: 1101 1110 ($DE) to BCD; it requires 3 BCD digits as the result (packed into 2 bytes): 0000 0000 0000 | 1101 1110 0000 0000 0001 | 1011 110- 0000 0000 0011 | 0111 10-- 0000 0000 0110 | 1111 0--- 0000 0000 1001 | 1111 0--- 0000 0001 0011 | 1110 ---- 0000 0010 0111 | 110- ---- 0000 0010 1010 | 110- ----- 0000 0101 0101 | 10-- ----- 0000 0101 1000 | 10-- ----- 0000 1011 0001 | 0--- ----- [oops] 0001 0110 0010 = 162 Adjusting all BCD digits: ... 0000 0101 0101 | 10-- ----- 0000 1000 1000 | 10-- ----- 0001 0001 0001 | 0--- ----- 0010 0010 0010 = 222 as it should be. The check needs to be made to every BCD digit which means two checks for each byte containing a packed BCD which rather wrecks the efficiency of doing the Decimal Adjust before the shift?
Maybe, after going through all these videos, some people of the "Oh, you can make just one little change, how long can it take?" variety will realize that even the slightest change can involve "little" unanticipated things that make almost any change to hardware or software not a "little change". Thanks for the videos - after 47 years of system development, it brought back some memories (my first EPROM programmer was a 6502 and peripheral chips - then I added RAM and ported CP/M to the 6502).
Dude I recently discovered this channel... I've always wondered what the LOGIC is behind all the stuff in computers. Seems like nobody is able to properly explain it to me! Then FINALLY after months of searching I see a vid "sums in binary" and this dude just explains it all with logic gates!! YEESSS FINALLY!! I'm hooked on this channel! Definitely subbed!
When I did this in the 80s I used a table with the binary representation of decimal values 10000, 1000, 100, 10 and 1. (Talking about 16 bits unsigned numbers here) Then I compared the number first with 10000 and if it was greater/equal subtracted it until it was smaller than 10000. Counting the subtractions I got the first (most significant) decimal digit. Same for 1000, 100, 10 and 1 to get all five decimal digits.
I challenged myself to create a solution before watching this video and this is exactly what I came up with too. But instead of doing comparisons I just kept subtracting and checking the carry flag. When the carry shows an overflow (i.e I've subtracted too much) I add one lot back on and then continue to the next decimal digit. Interested to watch the video now and see how Ben solves it.
I think it would be fun to create a BCD doubler circuit, then use it to double each digit and add in the next highest bit from the original number, until the entire set has been processed. A generalized BCD adder with carry in/out is pretty complex, but restricting it to doubling the current digit greatly simplifies it and makes it more practical to create a pure discrete circuit to perform the conversion.
You could do it in even fewer steps by trying to subtract in turn 40000, 20000, 10000 for the leftmost digit, 8000, 4000, 2000, 1000 for the next, 800, 400, 200, 100 for the next, 80, 40, 20, 10 for the next, 8, 4, 2, 1 for the last You still only need a lookup table for 40000, 8000, 800, 80, 8; you can get the rest by shifting those right. This would mean 19 trial subtractions, compared to up to 16*5 = 80 with the method in the video. Of course, the method in the video goes faster if the result has fewer digits. If you want that, you can start with e.g. comparing if the input is < 10, 100, 1000, 10000, to see how many decimal digits the result should have.
@@possible-realities Looks like it, mostly. My idea was to add 6 on carry rather than add 3 before shift on >=5. And an alternative noted in the article I read, a small ROM could be turned into a lookup table to calculate the double with carry.
A few notes: 1. You only need 1 byte for the "10" divisor, no need for mod10+1. This means you can take out TAY/LDA mod10+1/SBC#0 and the subsequent STA mod10+1. With those 4 commands gone, it will save you 192 cycles per digit. 2. I suggest writing it as a function, something like "show_readable:" and pass in a reference to a 2 byte number. At the beginning, you can LDA #0/PHA and then for each digit just ADC #"0"/PHA, when it's finished, you can then pull the values off the stack until you reach the #0 and return. A 2 byte number has a maximum of 5 digits to display, I think the stack can handle it lol.
Others have mentioned it, but I wanted to say just how thankful I am that you take the time. It took me a very long time to find "the right" presentation on how to solve the various cube puzzles and I have definitely found the right person to help me understand circuits and assembly language. It really is all about finding the presentation that works well for you.
Since we never used the stack on the conversion problem, at the start of the subroutine we could have stored a null character in the stack, called the function and instead of printing, we could have pushed the ascii to the stack, and then, when the subroutine of bin2dec conversion ends, we just instead of using index register, we could just popped values from the stack to the A register, and printed them until we read a null.
A simpler approach would be to push a zero onto the stack at the start, then have the outer loop push each digit of the result onto the stack. At the end you just pop the digits off the stack and print them until you hit that initial zero.
@@silaspoulson9935 It could be that he's looking ahead to a library of string processing functions which wouldn't work very well with a result on the stack. The stack-based algorithm could always copy the popped result into memory and still be more efficient, but I can see that once you've started down the road of passing strings around in memory it could be difficult to spot those situations where the stack can simplify things.
Also, I should note that a stack based option only works here because we know the result will be quite small, no more than 6 bytes. It's not an appropriate option for more general string handling, particularly on the 6502 with it's tiny stack.
I learned this alhorithm in school as well as many others for dealing with binary numbers in a computer friendly way, but our professor of computer architecture never explained to us why these algorithms are correct. We were just asked to know how to perform these algorithms without knowing where they come from and why they are true. Thank you for this video.
I'm working on a 6502-based project which has to display decimal numbers. I already had a general-purpose division subroutine, so I used that to divide by 10, taking the remainder each time until the answer is 0 and storing the remainders + 48 (to get the ASCII code for the digit character) in memory; then displaying these ASCII codes in reverse order.
I thought of an easier way to do this, it’s not a new method and you probably mentioned it later on in the video, but I did come Up with it on my own when I was designing a calculator in Minecraft. Here’s what I did. Step 1: I used bcd of course to represent numbers 1 through 9. (I later gave zero an arbitrary value of 10 in binary and gave the calculator rules on what to do when I type a zero) If you are wondering how I tackled number order entry when typing higher digit numbers like (124), I used a sort of 1 bit-snake that uses locking repeaters. It will take a small second of input and save it to a repeater. I had 4 lines of snakes like that (one for each bit) and they were all linked together in order to move at once even when a Line didn’t receive a 1 bit signal thus representing off bits (0s). This allowed me to enter four digit binary numbers one after the other and they would just slide over to the left when a new number was written. So I could type 1-2-4 on a keypad, it would go through an encoder and then be represented as 1, 01, 100 in binary. As for the displaying the numbers on screen as decimal, I had made 3 copies of logic gate systems that decode the binary input for each digit into a single output representing the values (1-10) and then had those value lines linked to another set of 3 decoders linked to 7- segment display faces that would take the 1-10 signals and divide each one across seven segments.so if the value line representing 5 was triggered for a digit. The digits decoder would read the 5 and follow the instruction I built for which segments to light up The last part was just to add the logic gates for addition, and us3 a switch to reverse them for subtraction, and then Wire it up to only show the answers after I’ve entered both my numbers and pressed calculate. Then the answer will just be wired back into the same bcd to decimal decoders to show it on screen Btw the addition logic for this is not as simple as using just an adder since I have it where there are 3 different adders, one for each bcd calculation. You have to make Rules that include carrying a 1 to the next bcd adder when a calculation is larger than 9 and then the answers from the adders needs to go into subtracters that subtract 10 when you get a number higher than 9. Then you have your true answer
It works, but i'm kind of afraid you're wasting about 5 values / hex number, which, for larger applications, can sum up to a lot (you also lose a lot of nifty advantages of computing in bare binary)
@@alexp6013 I actually agree, I ran into a few problems with my design that made it inaccurate sometimes, so I tried fixing it many times but ended up scrapping the idea. I was hoping it would be simpler than using bare binary but it turns out it required more just to do what bare binary could. Only reason I liked it was because it was easy to convert to decimal. I still haven’t quite figured out how to make a decimal converter that can read and show an 11 digit binary number
Man, an assembler! 40 years ago I had to hand code in octal or hex. Does this take me back! Keep it up. back then memory was precious and any byte or processor cycle saved was important. This is why I'm a fan of the current plethora of small microprocessors. Back to basics and efficiency.
Hi Ben! Nice work! You don't need the second byte for your mod10 though. Unless you want to divide by anything that is greater than one byte, it does nothing.
I can't believe you made this video when you did. I was just wondering how I was going to do this if I ever got back into electronics personally, and couldn't find a way to frame the question in a way that a search would help. Always love your videos and their uncanny ability to pop up shortly after I have an idea.
And why not,for this example, just push characters to the stack after a 0 then when done just pull and print until you hit that 0 terminator? Or just store to an incremented memory location, then read off backwards with a decrement loop, avoiding the stack all together?
Yeah, there are a handful of ways to handle it. Me thinks Ben chooses the paths he takes to show as much of the underlying process as possible. When we're "getting back to basics" like this, it's important to show how we get from A to...well, X and Y. haha But yeah, there are more cycle efficient ways to tackle some spots, but he intends to illustrate how the CPU arrives at its solutions. It's up to the student, as an exercise in critical thinking, to come up with different ways to arrive at the same answer. It's the best way to learn and way too many people want the answer just handed to them. Educators like Ben are becoming increasingly rare, as the demand for shortcuts has led many to cave to pressure and not dive as deeply into the ever important 'why.' For example, if we used all stack for storage along the way, we risk reducing available stack space that might be needed elsewhere in our program. Sure, it makes not a hill of beans in such simple code like this, but it definitely could in a much larger/complex program, like a game that might need to do a LOT of division all at once. You could easoly burn through the stack and lose your pointers.
@@talideon Z80: *Grins knowingly and points at all those extra clock cycles to access the memory* (Edit: I agree that the 6502 has some cool memory addressing modes. I love the PCR address instructions which allow a program to be made completely relocatable)
me: *laughs in modern x86 processor with one register capable of storing both values, most likely already has an instruction to do this, can run at a billion instructions per second*
The funy thing is, I watched the whole video when it came out (have you subscribed and turned on notifications yet?) and then, just 3 days later, found myself going back through the video, trying to use it in a project. Just gotta do a little manual 6502 -> Z80 ASM conversion, but shouldn't be too bad. Love your videos!
I would have put the null termination in the last location (message+5) and added characters at message+4, message+3, etc. This would have required a soft pointer, but the 6502's zero page addressing would have made this simple. Also, each time a decimal digit is determined, three more most significant bits are guaranteed to be zero in the dividend and we can use that fact to time-optimize the code. For 16-bits this is not entirely essential, but for 128 or 256 bits, it becomes quite noticeable. These are more advanced methods for viewers to consider and are not intended as criticisms.
I had a 'moment' about 13 minutes in..."Where the hell have I seen this before!?" Then, in the last 2 seconds of the video, it all became clear. I'm a relatively new Patreon supporter and saw the draft version a while back. 🤦♂️Seeing my name in the credits was my...um...clue. 🤣 Wow...glad I can still surprise MYSELF on occasion. 🙄
Another way of doing it is to count-down the digits with a simple series of subtractions. So, for example, take the value 65125. Start on the 10,000's digit, count 6 times. That gives you "6" and leaves 5125. Next the thousands digit, count 5 times, leave 125. Hundreds (1), tens (2), and that leaves the value 5 in the 1s digit. If more performance is required, a binary search can be used for each digit at the cost of code space. e.g. if the worst case count is 9 per digit but you can cut that to 6 by testing the 5-count first to get 0-4 or 5-9. And cut it down to 3 if you recurse twice. Theoretically it winds up being O(N log 10) where N is the number of digits. That said, the extra code required for the binary search was roughly similar to the inner subtract loop so it didn't make sense to cut it down more than once or twice (or even at all). Often when I wrote code for the 6502 (back in the Commodore Pet and C64 days), performance wasn't the problem... space was. The only time performance was an issue was when we were using quarter-block graphics to plot stuff. So being able to reuse the same code loop for all digits and making it as compact as possible wound up being more important than anything else.
There's another way to convert a binary number into Binary Coded Decimal that doesn't use division at all: Shift the number bit by bit into a zeroed register, and in that register, look at the bits in groups of 4. Any time a 4-bit group reaches or exceeds 5, then you add 3 to it. Just keep shifting and applying the conditional adding to the groups until the number has been fully shifted out of the old register. And now you're done! View the number as Hexadecimal, and it will look just like the Decimal value. It's basically a clever way of making the digits roll over every Ten instead of every Sixteen. Normally when a 5 gets shifted (doubled) it would just become an A. But if you add 3 before the shift, it becomes an 8 that when shifted becomes a 10, behaving just like decimal numbers should. It's really quite clever! I've done it in hardware before, but never tried a software implementation.
I appreciate the amount of effort you put into these videos Ben, thank you. Another great video, which makes me appreciate old school computing even more.
Brings some memories (albeit on Z80)! Another, way is to just keep subtracting 10000, then 1000, then 100, and 10 and keep counting how many times we could subtract those values without underflowing.
I remember my first victory in learning to code was when I needed to display the decimal value of an accumulated number. Computer programming pushed me into the unknown, and it was fun... and hard.
I personally did that by separating the bits, reversing their order and multiplying them by a variable that starts at 1 and doubles every bit processed and then adding the processed bits together
Bro🙏🙏, your videos are awesome, You are one of the greatest teachers of all time and mark my words - if you continue to make these videos regularly you will become the greatest online educator of all time... Besides, I have few suggestions for the future videos : 1)Make a team and upload good videos faster 2)Make an app to scale this online education on to next level 3)Make videos on all the topics related to electronics, for example, Radio communication (I desperately want to know about them more), oscillators, fm and am, gpu, dc to ac transformation, explaining how typical circuits such as fm receivers, camera and so on.... And one thing more there are millions of students around the world who needs teachers like you. So, make this teaching your passion, profession or business (whatever you call it) but be there always for us... Finally, I want to say that you're a legend bro and we all love you... So, keep up the good work, bro... Love from India❤️
Math was never my thing but man, seeing it used in this way is really fascinating. And just seeing all the stuff that makes computers tick on such a deep, fundamental level is so eye opening. After watching your videos I can really appreciate how powerful computers have become. And it just makes me think how much ingenuity it took to create these modern computers when this is what it takes just to convert binary to decimal. Amazing.
I just finished the first part of the clock module for the 8-bit computer. This is extra curriculum... btw, register manipulation seems a little bit like playing Towers of Hanoi.
The topics you choose for making videos are just perfect, Division makes sense since CPU is able to do just addition, substraction and multiplication. I imagine the next video could be Binary Coded Decimal Operations or just Floating/Fixed Point Decimal Operations since computers are used to do financial operations too. Thank you.
I am so glad that people much smarter than me invented programming languages where you can just use "/" to divide numbers. Very useful to know what's going on behind to scenes, but holy-moly, that's just madness!
@@thorham1346 They don't even have to be more modern, even the 8088 had a divide instruction... it was apparently slower than doing it this way, though!
I remember reading about how hackers at MIT, back in the '60s/'70s were often trying to write smaller and smaller decimal print routines. Of course, they had mainframes with larger words than the 6502, and maybe more versatile instruction sets. That might have helped a little.
First of all, since you never subtract more than 10, I think you can do this with 3 bytes, instead of 4. Secondly, since numbers are ofter right-aligned, you could create an altered version of the print_char subroutine that decrements the counter instead of adding to it. That saves you from having to write the string to memory before printing it. Finally I'd like to say: great video! :)
@@kallewirsch2263 The thing is there is a fast by 5 division algorithm, I don't remember the name but there is a fast divider algorithm for all primes below 7 and I say this because I don't remember if there was one for 11, but will not be surprised if the list is longer. And if you only require the mod part there are even fast modulus algorithms for all merssene primes
I never knew the humble 6502 wasn't capable of doing division or multiplication innately. Although thinking it over for a second makes you realize that a little bit of memory is required, something which the processor could assume absolutely nothing about. Does this mean that machines like the Commodore 64 had to implement these algorithms in the kernal (sic!)? Or was it deferred even to the BASIC ROM?
Other approach I use in assembler (I mostly do AVR assembler) is by doing packed BCD Arithmetic by testing each bit in the binary number, adding it's weight in packed BCD (using Decimal Adjust Algorithm, Intel 8051 had this instruction called DA, in AVR I had to program the algorithm) and then spread the final result to have something to display in the LCD Module
38:25 I think it would be better to move 5th to 6th, then 5th to 6th, ... 1st to 2nd, and then store the character from the stack to the 1st spot. That way, in each of the 5 iterations, there is one load and one store, and no stack interaction. Basically start from the right and move to the left.
I think you could have made it a bit simpler by having "mod10" be just 1 byte. If you're dividing by 10, the remainder will always fit in 8 bits. When you're substracting 10, you don't need the highest byte, it will always be "0 - 0". So, you'd only need 3 bytes of RAM, and the substraction process would be simpler because you don't need to be fiddling with the Y register. Love your videos by the way! This is super nitpicky, I know :)
For uni I had to build a program in assembly to convert a decimal number to a nibble. You also have to factor in the ASCII value that needs to be converted 🤧
Do you plan on showing how floating point numbers work? Are they using any of the base functions of a processor, or are they abstracted to another layer?
In the end of the day, the cpu only needs to check if one floating point number is higher than or less than or equal to another floating point value. Just like 00000001 in binary might mean the number 1 in decimal, in floating point 00000001 might represent "0.000001" or it's "lowest unit" and the comparisons would be the same way the cpu checks if one number is higher than the other in binary like how it does it with decimal.
I was bored, so I went and implemented this in java since I don't have a 6502. I had to remake subtraction as well since java doesn't have anything like an overflow/underflow flag. I had to remake addition too so I could use of 2's complement subtraction. While I was at it I made multiplication too, all without +, ++, -, or --.
I'd like to see you try and tackle floating-point numbers. I imagine you'd shift the bits of the mantissa to the left by the exponent's value (or right if negative), then recursively calculate the modulo base ten, then the quotient's modulo base ten, then that quotient's modulo base ten until you run out of didgits.
“I was able to print that out pretty easily - well, it took 9 videos” - and this is why we love this channel
It's like a mathematician say "it's trivia" to save a twenty-page long proof.
and 9 months
I also love vulkan for having to write 1000 lines of code to render single triangle
Yeach, I know, you can write everything in a single line of C/C++ code
@@krzysztof-ws9og well, who cares, people can make(and probably already have made) libraries for easier use. It's still fatser anyway.
@@krzysztof-ws9og after these videos machine language makes more sense to me than C probably ever will..
Kudos to every programmer who solved these problems in assembly long before I started programming.
In the real early days of computers, doing anything at all on them was a long series of hard problems that had to be solved one at a time. As we (humans in general) got better and better at it, we built up libraries of routines that we knew how to call.
You want to know why Linux and related operating systems have so many small command line programs in them that you string together on the command line to accomplish a larger job? This is why. Every single task was viewed as a problem that needed a solution. You would write a program that did that one task as well as it could possible be done. Then when you have a big job requiring many different tasks to be strung together, you just call into all the little task programs, passing the inputs and outputs of each task in a big line. That kind of logic can be extended to solve a great many different kinds of jobs, all while using tested and time honored code to do small tasks, one at a time, as well as possible.
As computers matured, and different philosophies were developed about how computers should work, new ways doing things were invented. Linux kept its model of small tasks strung together into big jobs. Other environments like Windows decided to go with a more user friendly approach.
In the early days, if you wanted to write a book, you would use a program to type in text, and save it to a file. Then you can run a program on that file to output spelling errors (any word not in a dictionary). Then you run that into a formatting program to paginate, format, etc. your text, and save it as a new file on the computer. Then you can send that formatted file to the printer and it will physically print the document.
On Windows, you open a program specially written to allow you to enter text, format it as you go, check for spelling errors on the fly, allow pagination and printing, all in one program. The downside? What happens if you want to do combine two documents into one? In Linux, you can just concatenate the text files right on the command line with a pre-written tool. In Windows, you have to hope your "does everything" program has this functionality built in, or use a different program to combine them.
What is you want to print different kinds of files? In Linux, the same program that sends data to the printer can take any pre-formatted input and send it to the printer. No need to reinvent the wheel for printing, just write a utility to convert your existing file into a language the printer understands, and use the already existing print program to finish. In Windows, every program that needs a print function has to implement their own logic for how to handle this. Different programs can end up with different printing features because they implemented it differently.
In more modern times, converting a file into something the printer can handle is usually accomplished by the printer driver. Your program just converts whatever it needs to print into effectively a big image, and then the print driver turns that into directions for the printer. This varies of course).
I'm just scratching the surface of an enormous amount of complexity, of course, but hopefully you get a sense of how difficult those early days were, and how different philosophies dictated different platform designs.
Things were just different back then. Life was simpler and programs less sophisticated. I once had to take the square root of a 96bit binary number which took a bit of research and then a couple of days to program in assembler. Great fun and very satisfying. We never wasted clock cycles because processing power was precious. These days it's squandered in the most appalling way.
@@rogerfroud300 I think the largest waste of processing power we face today is the myriad of interpreted languages. Since nearly every web site used at least a little JavaScript, basically all of us are affected by it at least a little, but I'm thinking more along the lines of python used for heavy data manipulation, or PHP and all those myriad of interpreted web hosting languages running in data centers.
Relatively few modern applications are actually compiled down to machine language. Most of them only compile to an intermediate language of some sort, like C# and VB to, and I think that includes Java (but I haven't used it personally). I wouldn't be surprised to find out that huge sections of our operating systems were written this way.
Those extra clock cycles get turned directly into wasted energy and increased CO2 in our atmosphere. It's not a big deal performance-wise today because our modern computers are thousands of times faster and more efficient than anything we had back then. But still, it seems like a waste.
As a C# programmer myself, I'm not going out of my way to change, because these levels of abstraction really help us get our work done and hold costs down.
@@WarrenGarabrandt: JIT
@ For the record, I started programming about 5 years years before I was first able to dial in to my university's VAX. I learned to program from books and magazines in the early 80's. What amazes me is the early programmers didn't have ANY references, just their brains and the basic tools the hardware provided.
I was way too delighted when that second long division problem folded out from behind the first. I love your style of presenting.
Me too. :)
Me 3
Me 2 mod 2
when he's dividing 10001 he borrows from the first one. But all the consecutive 0s are 1? how? What am I confused about?
@@yarik12341 That's only when it tries to substract 1010 from 1000 (not 10001), and since 1000 is smaller than 1010, it ends up with negative numbers. It's all 1 at the beginning because it rolls over, and incidentally that's how negative numbers are stored, by beginning by 1.
I started out on the 6502 almost 40 years ago. Beyond the nostalgia, it’s great to see, in the comments here, new generations experience the joy and wonder as I did so many years ago. Awesome job, Ben.
Me too. I love this series. Have solved all the problems on my own in the 80s. Assembler was a great experience!
Damn... I'm almost 40 years old, and never went into this stuff until now.
6502 isn't just for nostalgia. It's incredibly elegant for what it is, and can be used for countless everyday tasks. Using more complicated systems for simple tasks is asking for trouble
I taught my self on the Z80
To me, this is the most magical part of technology. It’s not AI, Machine Learning or front end web development frameworks. There is no place I’d rather be than circuitry, processors and low level code :-)
"Binary to decimal can't be that hard, right?" *sees video is 42 minutes long*
It isn't that hard. It's harder to explain it so that someone will understand it.
@@misterhat5823 programing machines = easy. Programing humans = hard
Let's confuse the arduino kids these days 😁
I just jumped directly onto the video without seeing how long it was. Just found out it was 42 minutes after 35 minutes. Pretty entertaining
@@misterhat5823 fr.wikipedia.org/wiki/Double_dabble
Man, I've been struggling how to do that without Decimal Mode for months. I'm working on a calculator program on the NES and have been running into that program again and again. Every time I looked up how to do it on 6502, they always said "Use Decimal Mode". But the NES's 2A03 doesn't have a decimal mode!
I could hug you!
Fun fact: the NES got away with using a 6502 without paying for the patent by doing away with decimal mode. Without decimal mode, the 2A03 no longer fell under the patent protection for 6502 so MOS couldn't stop them. The funny part? The silicon for decimal mode is still on the chip, just with the proper wires cut off to prevent you using it!
To do it efficiently, I'd suggest focusing on a routine which, if A is in the range 0 to 9, will perform a div-mod operation with a value whose upper byte is in A and whose lower byte is fetched via (someZP),Y addressing mode, storing the quotient in (someZP),Y and the remainder in A. If after doing that one decrements Y and loops if it's non-negative, one can easily perform a div-mod by ten for any size of binary number.
If you google "Jones on BCD arithmetic", you will get a tutorial on how to jerry-rig a binary machine to do decimal arithmetic.
And this is why I think he did it this way, vs. using BCD as others suggested.. The concepts here go beyond the 6502. I "grew up" doing 6809 assembly, and was able to follow this, even if the opcodes are different to me. Explaining it with the simplified BCD mode makes it specific to only this processor, and you lose a lot of value IMHO.. THis video was awesome!
@@flatfingertuning727 Yeah, there are lots of ways to do it. (Using tables can really speed things up!). However I like the way this video elegantly describes the concept, and it's quite impressive that the whole thing only uses a few bytes..
8:20 - When you keep leveling up your computer engineering skills, eventually you get the power to infinitely unfold paper with the next calculations already written on it. :)
I remember when this algorithm was first present in a computer architecture course I took. I was in awe of how they managed to take such a complex process and turn it into something so elegant. Your thorough explanation of it here is top notch, and if/when I need a refresher, I'll be sure to come back here!
And what about Double Dabble algorithm ? It looks way better to me...fr.wikipedia.org/wiki/Double_dabble
@@ggldmrd5583 I am not sure about that. First of all, how do you defined "better"? Shorter code or faster execution time? In terms of execution time, it of course all depends on the excact number of instructions and the number of cycles each instruction takes. Here is a high level analysis for a 16-bit number: the long division takes shift 16 loops per decimal digit found, so the worst case runtime is 16x5=80 loops. Double Dabble takes 16 shift loops plus 5 loops within each shift loop to check whether each power of 10 digit is >4 and then add 3 to it. So Double Dabble always takes 16x5 loops, whereas long division can finish in 16 loops for a number 4, add 3 (in the correct position) if necessary - sounds like a lot of instructions and cycles to me.
@@ryanhaart Well, what I defined as "better" was the shortest one in terms of ROM usage (shorter code). To be honest i didn't really check, but i think that i don't take too much risks saying that double dabble implies shorter code, cause the algorithm for the division seems long enough to me for that sort of task, but i might say something false when i say that, cause i didn't check and it's just an intuition. If you prefer the one with the shortest execution time, then i think that it would be more interesting to determine the complexity at worst case depending on the size of the number to convert (instead of the complexity at worst case for a given number of digits). It's not difficult to determine it anyway, the quetion is to know wether it's linear, exponential, quadratic, ...depending on the size of the number.
9:00 you didn’t do the math wrong, a bit just got flipped while transmitting.
It was the cosmic rays, man
@@tech6hutch that's why you need error check, which he also made a tutorial about
7:52 or 8:35, you mean.
Noise in the system.
A few years ago in my first year at university I wrote a 6502 emulator for fun in C#. I only ever got around to testing each instruction individually before I got bored. Your 6502 videos have re-inspired me and now I want to test this program on my emulator!
Another method of extracting the digits is performing repeated subtraction (until it is the last number before going negative) left to right: 255 -> 155 -> 55, this takes 2 subtractions by 100 to get the hundreds digit, then 55 -> 45 -> 35 -> 25 -> 15 -> 5 which takes 5 subtractions by 10 to get the tens, and we now have the ones place which is already there. Its like counting bills but starting at the highest denomination without exceeding the price of a product.
Thank you, i made the algorithm to run in my "sap 8bit computer" and it's working just fine.
Yeah, I got the same idea. I would love to know what are the advantages on each method.
This method seem simpler. But I think that for bigger numbers you may do more iterations.
The number of opcodes seem very similar. It would highly depend on the language. It doesnt use ROR but does need increment (to count the number of subtractions) and a conditional jump on borrow. And it looks like you use the same number of registers.
This method is much faster, because it uses at most 9 subtractions per digit, whereas the division method used as many as there are bits. Also you get the result in the right order. Only downside might me larger code size because you need all the powers of 10 as constants in ROM. For 32 bit numbers that would be an extra 36 bytes.
More complex ISA that actually have a div instruction _still_ do this algortihm underneath automatically in hardware. That's why if you check the datasheet for them, the div instruction takes ~16x cycles to complete than a normal instruction (for the appropriate word size)
There is a huge literature on the design of divider circuits and they get much more complicated than bitwise long division. The tradeoffs to consider are mainly how often does a user need to divide integers vs the energy/space the architecture is willing to spend on it.
@@prophetgab Most compilers are able to optimize away most divisions for this reason as well, replacing them with shifts, for example
@@argus456 Modern CPUs still manage to do the div in one cycle for some reason.
@@paulstelian97 What CPUs are those? Intel Coffee Lake (2019) takes 23-88 cycles for division and AMD Ryzen (2018) takes 13-47
@@WheretIB2 Then I must have recalled wrongly?
I think for me the hard part of binary maths is the cascading carry or borrow.
The rotating of the number automatically pushing the answer into the "memory" spot was elegant as fuck. Nice.
This is gonna be a good one, I can tell. Glad you're back!
The joy I'm feeling being able to witness a demonstration of how a computer does math at the machine level is indescribable! (At least somewhere between machine level and assembly ;p ) I am a visual learner who once seeing a demonstration can picture what a written document is describing. Sort of like needing a Rosetta Stone to understand the syntax of a text. This video series has welcomed me back to an electronics hobby I abandoned some 25 years ago as a teen. Thank you for posting these!
TH-cam is an amazing thing for visual learners like us!
th-cam.com/video/rhgwIhB58PA/w-d-xo.html
this is the only guy that would make a whole iOS app just to solve an assembly problem
That's not praiseworthy. He's dramatically over-complicated things. This video should have been around 10 minutes. At least I remember why I avoid this channel. Ugh.
@@recompile You are pretty fun at parties, huh?
@@recompile he goes over everything in great detail so everybody can understand it and it also gives a massively deeper understanding of what he's trying to teach
@@recompile You sound like that edgy kid who thinks he's better than everyone else. He makes introductory videos on electronics, and is a good teacher. He's not like those channels who are like "So I coded everything off-camera, here's 500 lines of code, good luck understanding that crap". You must be in a happy relationship with that attitude.
@@recompile It's been 4 months and I still don't see your 10 minute video on how to convert binary to decimal using bitwise operations.
Instead of reversing the string with code so it appears "correctly" ordered in RAM, why not just write the values into RAM as you go, and use the Y register to count how many results you get. Then when you're done, just decrement trough the Y index and print each character, thereby removing the need for a code to iterate trough the string to insert a character. Just a suggestion.
Alternatively, push values onto the stack, and then when you pull they'll come out in the reverse order which is exactly what you need. You'll need to know when to stop pulling from the stack, for that you can either use the Y register as suggested above, or just put a special marker value first, which would indicate that the sequence has ended. Given that the only possible values are 0..9, any other value will work. Maybe even better, use zero as a marker value, and put all values onto the stack shifted by one, just don't forget to decrement them back by one when you pull them from the stack.
"So we're going to do this rotate left, right?"
It's like talking to my dad
"So we go left, right?"
"Wait, left, then right?"
"No, left, right?"
"Right?"
"No, left"
"Left?"
"Right!"
🤯
We're talking about insufficient semantic redundancy here. ;)
At least in Polish there are separate words for "right" meaning "ok" and "right" meaning opposite of left
@@krzysztof-ws9og There are words in English too. "We are going right, correct?"
You forget he's American - English is not his first language
"No, my other left!"
6502 assembly is one of the last things I'll forget in old age. By that time I'll probably have too little RAM left to run any code.
I always have a 6502 into my pocket when i get out of my home, who knows, it might be useful some day...
Yes - I'm amazed I can still remember all the mnemonics and hex opcode values. I was only about 15 when I moved out of 6502 asm and into x86 and ARM2 asm.
Can;t wait for the floating point number arithmetics series!
Floating point is just shifts-and-adds but with logarithms. Now, who complained at school that they'd never need logs? :)
@@jgharston I don't see what the problem is, obviously just do math on a normal number and throw a dot in between the digits.
@@puppergump4117 how do your put a dot in a register that can only hold 1 or 0?
@@gorgikalamernikov3260 Just reserve like 4 bits to decide the amount it moves from the center and 1 bit to decide if it's left or right. There's probably problems with it but my original comment was just sarcasm.
@@puppergump4117 Yeah, that's pretty much how it's done actually, there's 8 reserved bits for a float32 to tell where the dot is... But nuance arises which is what the original commenter was excited about i guess.
I have a degree in IT so I have a pretty good understanding of how to USE computers and some of the basics on how they work, but this channel is awesome because it really makes the ultra low-level stuff click to explain how they work on a physical level. Never ceases to fascinate me, I really appreciate the effort that goes into sharing this stuff.
so you have a degree in how to use a keyboard? *g*
@@DarthZackTheFirstI and mouse and monitor
Yeah, it's always disturbing to use the thing and think "man, I have no idea how they built this"; any crumb of extra knowledge is cool
Being a software developer really like your videos for the insights they provide how things work under the hood. Would have been really helpful if u had a playlist for microprocessors and assembly language in general. I can vouch a lot of software folks would be having a blast if you had such a playlist and then would find a video like this much more understandable and enticing.
There's a much easier way to convert binary numbers to decimal on the 6502. Essentially, you left-shift the value out of the input 16-bit word (MSB→LSB) and left-shift the carry flag from that into the output 16-bit word. Mathematically, this just copies the value bit-by-bit from one word to another. Except that instead of using ROL:ROL to rotate the bit into the output word, you ADC the value in the output word to itself plus the carry from the first word, and instead of doing a normal binary addition, you do a Decimal-Mode addition (SED). The result will be in Binary Coded Decimal instead of binary, which is easy to convert into ASCII, and the output word will need to be three bytes in size to hold results over 9999.
I didn't understand that but still enjoyed reading it
I really hope @eaterbc sees this
that was impressive sir ... might be a vid for much later in the series as Ben has not even TOUCHED Decimal mode nor 60% of the ASM calls on the 6502
but I'd love to see Ben keep going into a 6502 master class type of series .. Not that making vid for YT is easy ... Just wish it was a bit faster
This is one of my little joys each month so far :D
Good plan, but perhaps Ben did it the long way to demonstrate the basic method, instead of using the decimal feature on the 6502, which hides/avoids the basics.
@@cjay2: I'm not sure that implementing long division is teaching "basic" 6502 programming.
@@csbruce No, Ben's teaching basic methodology, using the 6502 to do it. Optimal 6502 programming would be an entirely other thing.
Very good video! You have no idea how good you explain stuff. I have literally never seen anything related to assembly other than the fact that its a very low level machine language and I was able to follow along!
The visual representation of the algorithm was excellent. It shows that you really have a passion for teaching which I wholefully appreciate as a comsci student!
Thank you for making this. I will definitely look into your other stuff :D
Ben, where were you back in 1982 when I was learning about binary math. This is some very elegant coding and apart form the print routine there is not one sign of a nasty little jmp instruction, everything is relative calls using bne or beq. You explanation of the math is very clear and my past teachers could learn a lot from your presentation style. Thanks for producing this video, I am sure that a lot of viewers who need to learn the concepts of binary math will benefit greatly from this video ;)
I'm envious of your 6502 computer! It knows the meaning of life. Great video BTW, about half way through now but had to stop and write a comment before I forget. I am very familiar with everything you covered already but I really enjoy a refresher and just to listen to your explanation of things.
Got so excited when this popped up in my notifications!!
me too!!
Me too
Thanks for not skipping things, it really helps to understand the CPU cycles it's gonna take. I have whole new level of respect for long division method now.
Using Ramanujan's number... I see...
Haha yeah. This deserves more likes.
Very interesting :)
And the first example was 42 - The Answer to the Ultimate Question of Life, the Universe, and Everything (in The Hitchhiker's Guide to the Galaxy by Douglas Adams).
Subtle cross-over episode with 3b1b, I think ;)
huh. And I thought this was just a boring number.
I just wanted to say thank for explaining a filed that seems so intimidating in a such understandable way. You helped decide what I'm going to do in university
If you understand this video you should have no problems with CS courses for couple of semesters. I recommend watching linear algebra and calculus series on 3blue1brown channel and that's basicly first year done :D
@@igornoga5362 What you say is completely true. Damn there are lots of Ben Eater subscribers that are also 3Blue1Brown subs lol, and im also part of them.
*_Binary to decimal can't be that hard, right?_*
Me: *There is probably a little twist to it*
_sees video length_
me: *Oh yes, there definitely is a twist to it*
This is why I've subscribed to you long ago: Step-by-step instructions, simple but thorough explanations and no funny background music. Simply brilliant!
Brilliant stuff! Highly educational for all those new to understanding binary arithmetic and machine coding. For the rest of us old-school coders, I think it’s the first time I’ve ever seen someone fully demonstrate long-hand binary division. Certainly the first time I’ve seen someone who appears to have also written an iPad App in order to help demonstrate it? Awesome work Ben! 😊
Nearly 30 years I learnt electronics including most of the digital stuff going on in this channel. I did stuff on Z80, 6502, 8085 and 8086; I used Karnaugh maps for logic chips anf the 555 timer. I don't do this anymore but this channel is such a great trip down memory lane. Thanks so much for it.
Ben, thank you. I have been coding in ASM (6502) for YEARS... I always had trouble converting from binary to decimal (understanding it). You explained it so that my non-technical wife would get it. That is quite a feat.
Ben, this is an excellent channel. I am aspiring to learn about electronics, and I spend a lot of time browsing videos on the topic- your explanations are clear, you include examples of the relevant circuits, and you provide schematics for those circuits. Few channels tick all of those boxes, please keep up the good work. It' blows my mind how many channels that claim to be about learning about electronics and do not bother with a basic schematic, with the expectation that I reverse engineer that schematic by looking at parts on a breadboard.
your videos have been a great help in writing my own 6502 emulator
Thanks! I found a few 16 bit divide routines and wanted to expand them to handle 32 bits. I had no luck. The clear walk thru of this 16 bit divide routine gave me the deeper understanding I needed to easily make it into 32 bits.
Thank you Ben and thank you to all the wicked-smart people contributing comments here! I’ve really enjoyed reading them and learning from ppls input and stories. This is pure gold!
Back in the 80s, I'd always try to avoid writing a division algorithm because of the time it takes to run and the time to debug. For printing a 16 bit number, to avoid a division algorithm, I would count the number of times I need to subtract 10000, add back 10000 at the end of the loop, then repeat the process with 1000, 100 and 10 (at the last step you are left with the units). You'll get the digits out in the order we want (with leading zeros unless you suppress them). It all depends on how much effort you want to go to, and how efficient you want your code.
@Mickey Farley It's not a general division algorithm is what they meant. It's more specialised for a 5 digit base 10 number, where as eater's algorithm can work for any base and any length just by changing the sub 10 to a different base and adding more bytes to the division "register".
This is also a common method.
Remember when the decimal to binary conversion took up the majority of the mainframe? People sure managed to find some really clever solutions to the problem especially given the constraints of that time.
Hold up, when was this?
To me, that's easily the most impressive part. Our ability to work around problem when the stones are set in place.
@@forksandpopsticles9183 1960, IBM 1401, www.righto.com/2015/10/qui-binary-arithmetic-how-1960s-ibm.html
@@var67 I think you can set a flag and then ADC and SBC turn into BCD instructions.
If speed isn't important, the hardware required to perform integer binary to decimal conversion can be amazingly compact. To convert an N bit binary number to a D digit decimal number in NxD steps requires counters that can count from 0 to D and 0 to N, along with an Nx1 shift register for the input and a Dx4 shift register for the output, and a little bit of circuitry which could bit in a 20x5-bit ROM and a 1-bit register, or a modest number of gates.
Alternatives for reversing the string of digits:
- push to head of string in memory, shuffling remaining bytes along string (as shown in video)
- just use stack directly instead of memory, to store digits until output (risks stack overflow, but not in this simple case)
- push digits onto end of string in memory, but then output string from end to start (so reverse as output)
- push first digit to end of string in memory and build it backwards in memory, then output it forwards from start of string
- just output digits to LCD from right to left using cursor control, as seen on a calculator (probably the easiest)
The last one defies the purpose tho
For dividing by 10 you actually don't need two bytes for mod10, as the remainder will always fit into one byte =)
Yes, but it's used so both value and mod10 are the same length, otherwise the algorithm wouldn't work correctly.
@@PewnyPL Actually the algorithm works fine without the second byte for mod10. The carry bit is set correctly after the first sbc #10 from the low byte and nothing is done with the high byte after the sbc #0.
That is fine if you only ever want to divide by 10... which is great for specifically decimal... but stops working if you need to divide by anything over 255... like say 1000? I know the first argument will be that we are not going that high however, the next steps in decimal is hundreds and then thousands, working the opposite direction and jumping to thousandths is where we enter the realms of engineering where that type of precision becomes a huge necessity. The other variation of that is dealing with fractions where it can get a bit strange as well.
Dear Ben Eater, just would like to say that your channel is fantastic! The tutorials are very instructive and I love to see them because it brings back memories, my days using a Apple ][ and programing in assembly language. Thank you for your great job. Good days I had in the 80's. I still have the Apple manuals, books, a few addon boards, DOS and ProDOS 5 1/4" floppy diskettes.
There are 3 points I want to make:
1) The left 16 bit was unnecessary I think. We only used first 8 bit of it.
2) There is a more efficient algorithm to convert binary to binary coded decimal(BCD) that shifts left each time and adds 3 if a BCD digit is more than or equal to 5. An example run is 4 bit binary 1111 which is 15 needs 2 digit BCD so 8 bits
0000 0000 | 1111
0000 0001 | 1110
0000 0011 | 1100
0000 0111 | 1000
0000 1010 | 1000 (since 0111 = 7 >= 5 we added 3 to this number before the shift happens)
0001 0101 | 0000
its the end we have 1 and 5 which are the digits we wanted. Shift only by the number of bits you have at your initial inputs. To know more about this algorithm check out double dabble
3) You could have used a stack structure to invert bits. Push all of them to stack and pop all of them at the end . But you can not use pha and pla since return from subroutine will read the return address from the stack and if you push something it tries to return to another address. You have to implement your own stack in the RAM.
Love it. I thought the same, but didn't know this clever approach up-to-now. Thanks
I don’t think you want to skip out learning a generic integer divide algorithm, and jump straight to the bcd edge case. And the stack is available here if you want to use it, no need to try emulating your own.
Watched this video and compared it with my AVR assembly code for 40-bit conversion. The same and different. But that is how it goes with code. You find the algorithm, convert it in assembly, make it work, after that is has an input and an output. Now I remember I did double dabble. Nice refresher. Up to the next thing I forgot.
The double dabble is quite clever. It is effectively the "double" operation on an extra-wide register that is binary in the bottom and BCD on the top, repeated the exact number of times required to shift all the bits from the bottom register into the top one. It works well in hardware too as the dabbling step is parallelizable.
I presume it can run backwards to convert BCD to binary too, again parallelizable
Doesn't the adjust have to be made to every BCD digit?
Consider an 8 bit number: 1101 1110 ($DE) to BCD; it requires 3 BCD digits as the result (packed into 2 bytes):
0000 0000 0000 | 1101 1110
0000 0000 0001 | 1011 110-
0000 0000 0011 | 0111 10--
0000 0000 0110 | 1111 0---
0000 0000 1001 | 1111 0---
0000 0001 0011 | 1110 ----
0000 0010 0111 | 110- ----
0000 0010 1010 | 110- -----
0000 0101 0101 | 10-- -----
0000 0101 1000 | 10-- -----
0000 1011 0001 | 0--- ----- [oops]
0001 0110 0010 = 162
Adjusting all BCD digits:
...
0000 0101 0101 | 10-- -----
0000 1000 1000 | 10-- -----
0001 0001 0001 | 0--- -----
0010 0010 0010 = 222 as it should be.
The check needs to be made to every BCD digit which means two checks for each byte containing a packed BCD which rather wrecks the efficiency of doing the Decimal Adjust before the shift?
This is just best channel... I could understand deep technical things I thought I never will... thank you very much Ben..
Maybe, after going through all these videos, some people of the "Oh, you can make just one little change, how long can it take?" variety will realize that even the slightest change can involve "little" unanticipated things that make almost any change to hardware or software not a "little change".
Thanks for the videos - after 47 years of system development, it brought back some memories (my first EPROM programmer was a 6502 and peripheral chips - then I added RAM and ported CP/M to the 6502).
Dude I recently discovered this channel... I've always wondered what the LOGIC is behind all the stuff in computers. Seems like nobody is able to properly explain it to me!
Then FINALLY after months of searching I see a vid "sums in binary" and this dude just explains it all with logic gates!! YEESSS FINALLY!!
I'm hooked on this channel! Definitely subbed!
When I did this in the 80s I used a table with the binary representation of decimal values 10000, 1000, 100, 10 and 1. (Talking about 16 bits unsigned numbers here)
Then I compared the number first with 10000 and if it was greater/equal subtracted it until it was smaller than 10000. Counting the subtractions I got the first (most significant) decimal digit. Same for 1000, 100, 10 and 1 to get all five decimal digits.
I challenged myself to create a solution before watching this video and this is exactly what I came up with too. But instead of doing comparisons I just kept subtracting and checking the carry flag. When the carry shows an overflow (i.e I've subtracted too much) I add one lot back on and then continue to the next decimal digit.
Interested to watch the video now and see how Ben solves it.
I think it would be fun to create a BCD doubler circuit, then use it to double each digit and add in the next highest bit from the original number, until the entire set has been processed. A generalized BCD adder with carry in/out is pretty complex, but restricting it to doubling the current digit greatly simplifies it and makes it more practical to create a pure discrete circuit to perform the conversion.
@@ovalteen4404 I think that's what the Double Dabble algorithm does.
You could do it in even fewer steps by trying to subtract in turn
40000, 20000, 10000 for the leftmost digit,
8000, 4000, 2000, 1000 for the next,
800, 400, 200, 100 for the next,
80, 40, 20, 10 for the next,
8, 4, 2, 1 for the last
You still only need a lookup table for 40000, 8000, 800, 80, 8; you can get the rest by shifting those right.
This would mean 19 trial subtractions, compared to up to 16*5 = 80 with the method in the video. Of course, the method in the video goes faster if the result has fewer digits. If you want that, you can start with e.g. comparing if the input is < 10, 100, 1000, 10000, to see how many decimal digits the result should have.
@@possible-realities Looks like it, mostly. My idea was to add 6 on carry rather than add 3 before shift on >=5.
And an alternative noted in the article I read, a small ROM could be turned into a lookup table to calculate the double with carry.
A few notes:
1. You only need 1 byte for the "10" divisor, no need for mod10+1. This means you can take out TAY/LDA mod10+1/SBC#0 and the subsequent STA mod10+1. With those 4 commands gone, it will save you 192 cycles per digit.
2. I suggest writing it as a function, something like "show_readable:" and pass in a reference to a 2 byte number. At the beginning, you can LDA #0/PHA and then for each digit just ADC #"0"/PHA, when it's finished, you can then pull the values off the stack until you reach the #0 and return. A 2 byte number has a maximum of 5 digits to display, I think the stack can handle it lol.
Wait when did you get over 500k subs?? I wasn't aware of it. Good on ya mate!!
Others have mentioned it, but I wanted to say just how thankful I am that you take the time. It took me a very long time to find "the right" presentation on how to solve the various cube puzzles and I have definitely found the right person to help me understand circuits and assembly language. It really is all about finding the presentation that works well for you.
respect for who made high level programming language for us
The message could have been accumulated in reverse and then reversed back in one go using the stack
Thats what I thought
do you actually need a stack for that
Pop. Pop that gem 😁
Since we never used the stack on the conversion problem, at the start of the subroutine we could have stored a null character in the stack, called the function and instead of printing, we could have pushed the ascii to the stack, and then, when the subroutine of bin2dec conversion ends, we just instead of using index register, we could just popped values from the stack to the A register, and printed them until we read a null.
Stack space is often limited. Many micros don't have a user accessible stack. You shouldn't get used to just throwing everything on the stack.
"If you're envious of my extremely capable computer and its ability to display numbers..." This made me laugh 😂
So pleased to see another video from you Ben!
A simpler approach would be to push a zero onto the stack at the start, then have the outer loop push each digit of the result onto the stack. At the end you just pop the digits off the stack and print them until you hit that initial zero.
Indeed! Would be interesting to know why stack wasn't used - perhaps Ben just didn't consider it?
@@silaspoulson9935 It could be that he's looking ahead to a library of string processing functions which wouldn't work very well with a result on the stack. The stack-based algorithm could always copy the popped result into memory and still be more efficient, but I can see that once you've started down the road of passing strings around in memory it could be difficult to spot those situations where the stack can simplify things.
Also, I should note that a stack based option only works here because we know the result will be quite small, no more than 6 bytes. It's not an appropriate option for more general string handling, particularly on the 6502 with it's tiny stack.
Or he might have used the message buffer as a stack by appending each digit to the end of the string concluding with the null byte.
I had the exact same idea but you beat me to posting a comment. :-)
I learned this alhorithm in school as well as many others for dealing with binary numbers in a computer friendly way, but our professor of computer architecture never explained to us why these algorithms are correct. We were just asked to know how to perform these algorithms without knowing where they come from and why they are true. Thank you for this video.
Everyone named Ben is afraid of this guy
LMAO
I'm working on a 6502-based project which has to display decimal numbers. I already had a general-purpose division subroutine, so I used that to divide by 10, taking the remainder each time until the answer is 0 and storing the remainders + 48 (to get the ASCII code for the digit character) in memory; then displaying these ASCII codes in reverse order.
I thought of an easier way to do this, it’s not a new method and you probably mentioned it later on in the video, but I did come
Up with it on my own when I was designing a calculator in Minecraft.
Here’s what I did.
Step 1: I used bcd of course to represent numbers 1 through 9. (I later gave zero an arbitrary value of 10 in binary and gave the calculator rules on what to do when I type a zero) If you are wondering how I tackled number order entry when typing higher digit numbers like (124), I used a sort of 1 bit-snake that uses locking repeaters. It will take a small second of input and save it to a repeater. I had 4 lines of snakes like that (one for each bit) and they were all linked together in order to move at once even when a Line didn’t receive a 1 bit signal thus representing off bits (0s). This allowed me to enter four digit binary numbers one after the other and they would just slide over to the left when a new number was written. So I could type 1-2-4 on a keypad, it would go through an encoder and then be represented as 1, 01, 100 in binary.
As for the displaying the numbers on screen as decimal, I had made 3 copies of logic gate systems that decode the binary input for each digit into a single output representing the values (1-10) and then had those value lines linked to another set of 3 decoders linked to 7- segment display faces that would take the 1-10 signals and divide each one across seven segments.so if the value line representing 5 was triggered for a digit. The digits decoder would read the 5 and follow the instruction I built for which segments to light up
The last part was just to add the logic gates for addition, and us3 a switch to reverse them for subtraction, and then Wire it up to only show the answers after I’ve entered both my numbers and pressed calculate. Then the answer will just be wired back into the same bcd to decimal decoders to show it on screen
Btw the addition logic for this is not as simple as using just an adder since I have it where there are 3 different adders, one for each bcd calculation. You have to make Rules that include carrying a 1 to the next bcd adder when a calculation is larger than 9 and then the answers from the adders needs to go into subtracters that subtract 10 when you get a number higher than 9. Then you have your true answer
It works, but i'm kind of afraid you're wasting about 5 values / hex number, which, for larger applications, can sum up to a lot (you also lose a lot of nifty advantages of computing in bare binary)
@@alexp6013 I actually agree, I ran into a few problems with my design that made it inaccurate sometimes, so I tried fixing it many times but ended up scrapping the idea. I was hoping it would be simpler than using bare binary but it turns out it required more just to do what bare binary could. Only reason I liked it was because it was easy to convert to decimal. I still haven’t quite figured out how to make a decimal converter that can read and show an 11 digit binary number
@@silasxaviertheprod.9734 there’s a joke somewhere here about showing your mother an 11 digit binary number...
Man, an assembler! 40 years ago I had to hand code in octal or hex. Does this take me back! Keep it up. back then memory was precious and any byte or processor cycle saved was important. This is why I'm a fan of the current plethora of small microprocessors. Back to basics and efficiency.
Hi Ben! Nice work! You don't need the second byte for your mod10 though. Unless you want to divide by anything that is greater than one byte, it does nothing.
I can't believe you made this video when you did. I was just wondering how I was going to do this if I ever got back into electronics personally, and couldn't find a way to frame the question in a way that a search would help. Always love your videos and their uncanny ability to pop up shortly after I have an idea.
And why not,for this example, just push characters to the stack after a 0 then when done just pull and print until you hit that 0 terminator? Or just store to an incremented memory location, then read off backwards with a decrement loop, avoiding the stack all together?
...or just print it as it is but scroll the display and reset the cursor :D
gargaj I think the display module even has a right-to-left mode, it’ll reverse the string for you!
This videos are not ment for "for this example" solutions, they're ment for the solutions that teaches more
That is a great idea.
Yeah, there are a handful of ways to handle it. Me thinks Ben chooses the paths he takes to show as much of the underlying process as possible. When we're "getting back to basics" like this, it's important to show how we get from A to...well, X and Y. haha But yeah, there are more cycle efficient ways to tackle some spots, but he intends to illustrate how the CPU arrives at its solutions. It's up to the student, as an exercise in critical thinking, to come up with different ways to arrive at the same answer. It's the best way to learn and way too many people want the answer just handed to them. Educators like Ben are becoming increasingly rare, as the demand for shortcuts has led many to cave to pressure and not dive as deeply into the ever important 'why.'
For example, if we used all stack for storage along the way, we risk reducing available stack space that might be needed elsewhere in our program. Sure, it makes not a hill of beans in such simple code like this, but it definitely could in a much larger/complex program, like a game that might need to do a LOT of division all at once. You could easoly burn through the stack and lose your pointers.
Your videos are fantastic. Thanks for sharing them with everyone.
19:42: "There are not enough CPU registers to store all of this data!"
me: *laughs in Z80*
6502: *shrugs smugly and points at all those sweet, sweet addressing modes, especially zero page addressing*
@@talideon Z80: *Grins knowingly and points at all those extra clock cycles to access the memory*
(Edit: I agree that the 6502 has some cool memory addressing modes. I love the PCR address instructions which allow a program to be made completely relocatable)
Arduino (inserted): watdaheck they are talking about 🤔
me: *laughs in modern x86 processor with one register capable of storing both values, most likely already has an instruction to do this, can run at a billion instructions per second*
Me laughing in my dual core redstone computer with like 1 general purpose register per core lol
The funy thing is, I watched the whole video when it came out (have you subscribed and turned on notifications yet?) and then, just 3 days later, found myself going back through the video, trying to use it in a project. Just gotta do a little manual 6502 -> Z80 ASM conversion, but shouldn't be too bad. Love your videos!
I would have put the null termination in the last location (message+5) and added characters at message+4, message+3, etc. This would have required a soft pointer, but the 6502's zero page addressing would have made this simple. Also, each time a decimal digit is determined, three more most significant bits are guaranteed to be zero in the dividend and we can use that fact to time-optimize the code. For 16-bits this is not entirely essential, but for 128 or 256 bits, it becomes quite noticeable. These are more advanced methods for viewers to consider and are not intended as criticisms.
Now I finally understand why my teachers (way way way back) used to say that divisions were very costly. Thanks for this video, very informative.
I had a 'moment' about 13 minutes in..."Where the hell have I seen this before!?" Then, in the last 2 seconds of the video, it all became clear. I'm a relatively new Patreon supporter and saw the draft version a while back. 🤦♂️Seeing my name in the credits was my...um...clue. 🤣 Wow...glad I can still surprise MYSELF on occasion. 🙄
Looks like the simulation app at 16:00 was also written by you for this video. Quality shows! Wonderful video, as always.
It's always the best idea to start a video with the almighty answer to the meaning of life; 42
Error - Towel missing
And it's binary is 101010... Another good reason to support 42. :-p
Spooky. When I read your comment, you had precisely 42 thumb's up! :|
Two people need to unlike this comment (current value is 44)
Another way of doing it is to count-down the digits with a simple series of subtractions. So, for example, take the value 65125. Start on the 10,000's digit, count 6 times. That gives you "6" and leaves 5125. Next the thousands digit, count 5 times, leave 125. Hundreds (1), tens (2), and that leaves the value 5 in the 1s digit. If more performance is required, a binary search can be used for each digit at the cost of code space. e.g. if the worst case count is 9 per digit but you can cut that to 6 by testing the 5-count first to get 0-4 or 5-9. And cut it down to 3 if you recurse twice.
Theoretically it winds up being O(N log 10) where N is the number of digits. That said, the extra code required for the binary search was roughly similar to the inner subtract loop so it didn't make sense to cut it down more than once or twice (or even at all).
Often when I wrote code for the 6502 (back in the Commodore Pet and C64 days), performance wasn't the problem... space was. The only time performance was an issue was when we were using quarter-block graphics to plot stuff. So being able to reuse the same code loop for all digits and making it as compact as possible wound up being more important than anything else.
There's another way to convert a binary number into Binary Coded Decimal that doesn't use division at all: Shift the number bit by bit into a zeroed register, and in that register, look at the bits in groups of 4. Any time a 4-bit group reaches or exceeds 5, then you add 3 to it. Just keep shifting and applying the conditional adding to the groups until the number has been fully shifted out of the old register. And now you're done! View the number as Hexadecimal, and it will look just like the Decimal value.
It's basically a clever way of making the digits roll over every Ten instead of every Sixteen. Normally when a 5 gets shifted (doubled) it would just become an A. But if you add 3 before the shift, it becomes an 8 that when shifted becomes a 10, behaving just like decimal numbers should. It's really quite clever!
I've done it in hardware before, but never tried a software implementation.
Wow.
I appreciate the amount of effort you put into these videos Ben, thank you. Another great video, which makes me appreciate old school computing even more.
Brings some memories (albeit on Z80)! Another, way is to just keep subtracting 10000, then 1000, then 100, and 10 and keep counting how many times we could subtract those values without underflowing.
I love how much effort you put into your videos and kits.
I remember my first victory in learning to code was when I needed to display the decimal value of an accumulated number. Computer programming pushed me into the unknown, and it was fun... and hard.
I personally did that by separating the bits, reversing their order and multiplying them by a variable that starts at 1 and doubles every bit processed and then adding the processed bits together
Bro🙏🙏, your videos are awesome, You are one of the greatest teachers of all time and mark my words - if you continue to make these videos regularly you will become the greatest online educator of all time...
Besides, I have few suggestions for the future videos :
1)Make a team and upload good videos faster
2)Make an app to scale this online education on to next level
3)Make videos on all the topics related to electronics, for example, Radio communication (I desperately want to know about them more), oscillators, fm and am, gpu, dc to ac transformation, explaining how typical circuits such as fm receivers, camera and so on....
And one thing more there are millions of students around the world who needs teachers like you. So, make this teaching your passion, profession or business (whatever you call it) but be there always for us...
Finally, I want to say that you're a legend bro and we all love you...
So, keep up the good work, bro...
Love from India❤️
Math was never my thing but man, seeing it used in this way is really fascinating. And just seeing all the stuff that makes computers tick on such a deep, fundamental level is so eye opening. After watching your videos I can really appreciate how powerful computers have become. And it just makes me think how much ingenuity it took to create these modern computers when this is what it takes just to convert binary to decimal. Amazing.
I just finished the first part of the clock module for the 8-bit computer. This is extra curriculum... btw, register manipulation seems a little bit like playing Towers of Hanoi.
The topics you choose for making videos are just perfect, Division makes sense since CPU is able to do just addition, substraction and multiplication. I imagine the next video could be Binary Coded Decimal Operations or just Floating/Fixed Point Decimal Operations since computers are used to do financial operations too. Thank you.
6502 doesn't have hardware multiply. I imagine software multiply will be coming up soon.
I am so glad that people much smarter than me invented programming languages where you can just use "/" to divide numbers. Very useful to know what's going on behind to scenes, but holy-moly, that's just madness!
More modern CPUs have division instructions.
@@thorham1346 They don't even have to be more modern, even the 8088 had a divide instruction... it was apparently slower than doing it this way, though!
@@Mnnvint True. 68000 has them also.
I remember reading about how hackers at MIT, back in the '60s/'70s were often trying to write smaller and smaller decimal print routines. Of course, they had mainframes with larger words than the 6502, and maybe more versatile instruction sets. That might have helped a little.
First of all, since you never subtract more than 10, I think you can do this with 3 bytes, instead of 4. Secondly, since numbers are ofter right-aligned, you could create an altered version of the print_char subroutine that decrements the counter instead of adding to it. That saves you from having to write the string to memory before printing it.
Finally I'd like to say: great video! :)
On a good implementation you would do a division by 2 (a rotate) and then a division by 5 instead of by 10
@@kallewirsch2263 The thing is there is a fast by 5 division algorithm, I don't remember the name but there is a fast divider algorithm for all primes below 7 and I say this because I don't remember if there was one for 11, but will not be surprised if the list is longer.
And if you only require the mod part there are even fast modulus algorithms for all merssene primes
The transitions in this channel are so smooth, things just come out of nowhere, I love it xd
*Furiously unfolds paper*
"HOW LONG IS THIS THING"
I never knew the humble 6502 wasn't capable of doing division or multiplication innately. Although thinking it over for a second makes you realize that a little bit of memory is required, something which the processor could assume absolutely nothing about.
Does this mean that machines like the Commodore 64 had to implement these algorithms in the kernal (sic!)? Or was it deferred even to the BASIC ROM?
Other approach I use in assembler (I mostly do AVR assembler) is by doing packed BCD Arithmetic by testing each bit in the binary number, adding it's weight in packed BCD (using Decimal Adjust Algorithm, Intel 8051 had this instruction called DA, in AVR I had to program the algorithm) and then spread the final result to have something to display in the LCD Module
38:25 I think it would be better to move 5th to 6th, then 5th to 6th, ... 1st to 2nd, and then store the character from the stack to the 1st spot. That way, in each of the 5 iterations, there is one load and one store, and no stack interaction. Basically start from the right and move to the left.
I love these videos, the narration sounds like the video is running at 1.25x, so much information packed into so little time.
I think you could have made it a bit simpler by having "mod10" be just 1 byte. If you're dividing by 10, the remainder will always fit in 8 bits. When you're substracting 10, you don't need the highest byte, it will always be "0 - 0". So, you'd only need 3 bytes of RAM, and the substraction process would be simpler because you don't need to be fiddling with the Y register. Love your videos by the way! This is super nitpicky, I know :)
I need to divide by 12 for my project, and I might also use just 3 bytes. But still, wish there were a trick to do faster division and mod
Another great video ... always well prepared and informative
For uni I had to build a program in assembly to convert a decimal number to a nibble. You also have to factor in the ASCII value that needs to be converted 🤧
Great video Mr. Eater! I had fun following along as always and learned a bit lol. I can't wait for the next one maybe some input? Push buttons?
Do you plan on showing how floating point numbers work?
Are they using any of the base functions of a processor, or are they abstracted to another layer?
In the end of the day, the cpu only needs to check if one floating point number is higher than or less than or equal to another floating point value. Just like 00000001 in binary might mean the number 1 in decimal, in floating point 00000001 might represent "0.000001" or it's "lowest unit" and the comparisons would be the same way the cpu checks if one number is higher than the other in binary like how it does it with decimal.
I'm always amazed by how perfectly prepared he is!
I was bored, so I went and implemented this in java since I don't have a 6502. I had to remake subtraction as well since java doesn't have anything like an overflow/underflow flag. I had to remake addition too so I could use of 2's complement subtraction. While I was at it I made multiplication too, all without +, ++, -, or --.
I'd like to see you try and tackle floating-point numbers. I imagine you'd shift the bits of the mantissa to the left by the exponent's value (or right if negative), then recursively calculate the modulo base ten, then the quotient's modulo base ten, then that quotient's modulo base ten until you run out of didgits.