3 ms·
A long time ago on the 6502 I was trying to figure out how to quickly multiply by 3 in assembly and I came up with: 1. Shift-left 2. Add original value For m
by efitz 2y ago
A long time ago on the 6502 I was trying to figure out how to quickly multiply by 3 in assembly and I came up with:
1. Shift-left
2. Add original value
For multibyte values use rotate left which carries, and do the rotates from LSB to MSB. Then clear carry, then do the adds from LSB to MSB with carries. Should work for any word size.
Ofc I was a teenager but this seemed clever and simple to me.
Was (am) I just missing something?
- bean-weevil 2y agoThis is covered in the article. See the section "Implementing a fast ×3 circuit with carry lookahead"
- efitz 2y agoThank you. I stopped reading after the octal discussion.
- russdill 2y agoFor most assembly, I'm not sure how this has an advantage over two adds.
- jonsen 2y agoA shift is faster than an add.
- russdill 2y agoOn 6502 they are both 2 cycles. On the vast majority of processors I'm aware of, "simple" alu operarations don't vary in execution time
- kragen 2y agoOn 8086 or ARM you can get a shift "for free" with your add, although on the 8086 you have to use the LEA instruction.
- ksherlock 2y agoADC #immediate is 2 cycles, as is ASL. Are you really multiplying a constant by 3 at runtime? Probably not. ADC zp is 3 cycles. Plus 2 cycles for the CLC.
- ForOldHack 2y agoThe M68020 added a dedicated barrel shifter, which could execute much faster then the M68000.
- FromTheSteppe 2y agoShift add used to execute much faster than multiplication in 8088 days and people would use it when they had to multiply an int by a known scalar (shift took 4 clocks and add took 12).
- funny_falcon 2y agoCompilers still prefer LEA to multiply on 3,5 and 9, which performs shift+add I believe.