6 ms·
Multiplying and Dividing on the 6502 (2021)
- ddingus 4y agoOften, on this chip you want to come up with a very specific dedicated purpose multiply that's fast and that gives you enough precision to do the work. The other tricks are all worth learning, cordic, shifts, look up tables and the other tricks we use when add shifts and rotates and bit opps are the only thing the CPU can do.
- kbelder 4y agoRight. I remember on the C64 using, for instance, y * 40 + x for screen positioning, since it had a 40 column screen. Since y * 40 is (y * 8) + (y * 32), you'd take x, left-shift three times, save the result, shift left two more times, and add the two together. Pretty fast. You'd do stuff like this everywhere you knew the coefficients in advance.
- ddingus 4y agoBingo! I did the same on an Atari. Also, a lookup table for the Y address, plus a fixed X address can get bitmaps blitted to the screen quickly. For special case graphics, just code in the addresses, unroll the loop and use index X or Y to handle screen positioning. LDX XPOS LDA IMAGE0 STA SCREEN0, X LDA IMAGE1 STA SCREEN1, X LDA IMAGE2 STA SCREEN2, X . . . No multiply needed. Y addresses either coded at fixed position, or generated at runtime based on some event and or when there is time to compute it all off screen. Trade RAM for speed!
- commandlinefan 4y agoSigh... I remember doing a lot of this stuff as a teenager, looking forward to the day when I'd be getting paid to do it. But by the time I got paid to do stuff, there was no market for this kind of low-level optimization any more. Shame.
- ddingus 4y agoI hear ya! Today, I mostly do it for fun on my old Apple machine. It is enjoyable to see what can be done. 1Mhz is actually quite a lot when one looks at the resolution and overall task to complete. And where to put it? Things like having the game run at 30Hz or 15Hz so more can be computed in game, in real time. Then, when it comes to drawing everything, often a simple screen clear, or page flip then draw does not make sense. Two screens takes too much RAM, etc... Single buffer, draw fast, only draw deltas, using XOR, all add up! Getting paid? I have done some assembly for money on Propeller chips, PIC, AVR, and the like. There are times in embedded land where doing these fun things pays off and makes sense. For what it is worth, a little fun can be had for income, but not much.
- krylon 4y agoWould I be very wrong to suspect that early RISC CPUs forced programmers and compilers to pull similar stunts? The major difference was probably that RISC systems had compilers, while on the 6502, it was BASIC or assembly. So programmers might not have noticed?
- Turing_Machine 4y agoThere were numerous compilers for the 6502.
- sllabres 4y agoI'll remember well UCSD Pascal https://en.wikipedia.org/wiki/UCSD_Pascal https://en.wikipedia.org/wiki/UCSD_Pascal especially as compiling on a system with one floppy drive required 5-6 changes of the floppy disk even for a 'hello world'. So one would think twice before starting the compiler only to find a simple syntax error after a minute or two. :)
- dwheeler 4y agoAbsolutely true, there were and are MANY compilers for the 6502. However, the 6502 was a challenge to implement high-level languages on, IF you also wanted speed and small code size. But since the 6502s were slow compared to modern chips, and could only address 64KiB directly, you typically also wanted speed and small size. I posted some links to some approaches here: https://dwheeler.com/6502/ https://dwheeler.com/6502/
- buescher 4y agoI always thought Action! was very crisply tailored to these small systems. It turns out to have been a port of a language called Micro-SPL from the Xerox Alto that (originally) targeted the Alto microcode directly. Atalan and Plasma look nice.
- kjs3 4y agoSure...they were amazingly widespread machines back in the day so lots of people took a whack at a 6502 compiler (at college if nothing else). But how many could take on non-trivial programs and emit code that would be considered production level? I know Apple Pascal was supposed to be pretty good, but what else?
- diydsp 4y ago> (The above routine is based on some code I found on a Commodore-64-related web page, which, unfortunately, I haven't been able locate again. The method doesn't seem to have been widely known among Apple II programmers.) Here's one possible source from an excellent website that includes many more 6502 algorithms! https://codebase64.org/doku.php?id=base:6502_6510_maths https://codebase64.org/doku.php?id=base:6502_6510_maths
- djmips 4y agoMy contribution there. :) https://codebase64.org/doku.php?id=base:8bit_multiplication_16bit_product_fast_no_tables https://codebase64.org/doku.php?id=base:8bit_multiplication_...
- kstrauser 4y agoMy favorite commentary on this is from https://codebase64.org/doku.php?id=base:kernal_floating_point_mathematics#multiply https://codebase64.org/doku.php?id=base:kernal_floating_poin... : > Numerous advantages are gained improving the speed of the multiply. Routines that rely on it can be copied from the ROM and pointed to the new routine to improve performance. The following example relies on the Steve Judd's fast multiplication and reduces the number of cycles to multiply from around 2300 to little over 1400. That's a nice speed increase from 435 multiplies/sec to 714 ops/sec. It's downright spritely! There's also a faster log function that > executes in around 13000 cycles, where the built-in routine takes 19000. ...jumping from 53 to 77 ops/sec. Smokin'!
- jacquesm 4y agoThe 6809 had a 'mul' instruction: https://atjs.mbnet.fi/mc6809/Information/6809.htm https://atjs.mbnet.fi/mc6809/Information/6809.htm 8x8 unsigned. I started out programming assembler on the KIM, then moved to the Dragon 32 which had a 6809 and then back to the BBC micro again, which in almost every way felt like a huge step forward and in that one way felt like a step back, the lack of 8x8 multiply in hardware. Here is a very neat (and pretty quick) multiplication routine: http://www.txbobsc.com/aal/1986/aal8603.html http://www.txbobsc.com/aal/1986/aal8603.html
- FatalLogic 4y agoI'm surprised that the 6809 MUL instruction seems to have a fixed execution time (11 cycles, if I am interpreting the specs correctly). This implies to me that it might be heavily based on look-up tables, yet the 6809 surely had very limited die space for that
- jacquesm 4y agoBarrelshifter!
- OnlyMortal 4y agoThis might be of interest… https://archive.org/details/dr_dobbs_journal_vol_01/page/n207/mode/2up https://archive.org/details/dr_dobbs_journal_vol_01/page/n20... Wozniak floating point code.
- mwcampbell 4y agoI thought the whole reason why Apple ended up using a Microsoft BASIC implementation for the Apple II was that Woz didn't write floating-point routines. Am I missing something here?
- OnlyMortal 4y agoApparently he did. I took an interest due to the C64.
- deleted 4y ago[deleted]
- commandlinefan 4y ago> Easy: Just write the binary equivalent of the constant, and look for the 1 bits I love that there was a time when "just write the binary equivalent" was the easy solution.