Hacker News Reader

Comment by efitz | Hacker News Reader

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?

View on HN

This is covered in the article. See the section "Implementing a fast ×3 circuit with carry lookahead"

Thank you. I stopped reading after the octal discussion.

For most assembly, I'm not sure how this has an advantage over two adds.

Shift 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).

Compilers still prefer LEA to multiply on 3,5 and 9, which performs shift+add I believe.

A shift is faster than an add.

On 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

On 8086 or ARM you can get a shift "for free" with your add, although on the 8086 you have to use the LEA instruction.

ADC #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.

The M68020 added a dedicated barrel shifter, which could execute much faster then the M68000.

Reply on news.ycombinator.com