multiplication vs shifting

[Kamikaze47]

ive got to multiply a variable by 25 and i was wondering which of these 2 would be quicker

x = x*25

or

x = x<<4 + x<<3 + x

I have a suspicion that the latter will be quicker, but take up more code space.

[Kamikaze47]

ok, i just did some tests and i was half right and half wrong.

x=x<<4+x<<3+x was quicker (taking 80% of the time that x=x*25 took to execute)

However, what surprised me was that x=x*25 used MORE code space than x=x<<4+x<<3+x. Replacing x=x<<4+x<<3+x with x=x*25 in my program adds 338 bytes.

It appears that x=x<<4+x<<3+x wins on both counts.

[tenaja]

PBP uses a subroutine for performing the multiplication. (For all 16F * calculations, and for 18F * calcs involving more than 8 bits.) If you perform the calculation multiple times, an individual line may be shorter than shifting. However, on just a one-time multiplication, the PBP subroutine will add significant code.

[Ioannis]

No other code, just Variable declaration and END,for a F877:

For BYTE variable:

x=x*25            '40 bytes
x=x<<4+x<<3+x     '43 bytes

For WORD variable:

x=x*25             '43 bytes
x=x<<4+x<<3+x      '49 bytes
x=x<<25            '27 bytes!!!

Ioannis

[Kamikaze47]

whats the point of the last one? shift a word variable 25 times either way and you will just get 0.

i was multiplying a word var and saving into a long var

[Ioannis]

I know 25 shift will not give the result you want.

Just tested to see how much less program space and how faster a shift will be. Useless for you but quite impressive!

Which PIC are you using? Is there any chance to use one with hardware multiplier?

Ioannis

[Darrel Taylor]

To me, the time it takes to execute is more important than the size of the code.
And the fastest way will usually <strike>be the smallest too</strike> not be the smallest.

On a 16F @ 4Mhz with WORD variables ...
<table cellpadding=6 border=1><tr><td align=center>Formula</td><td align=center>Execution Time</td><td align=center>Words per<br>Instance</td><td align=center>Words added<br>to Library</td></tr><tr><td>x = x*25</td><td align=center>230 - 250uS<br>depends on X value</td><td align=center>12</td><td align=center>27</td></tr><tr><td>x = x<<4 + x<<3 + x</td><td align=center>110uS</td><td align=center>34</td><td align=center>13</td></tr><tr><td> T = X << 1
T = T << 1
T = T << 1
X = T << 1 + T + X </td><td align=center>31uS</td></td><td align=center>30</td><td align=center>13<br>adds SHIFTL to library<br>but doesn't use it.</td></tr></table>

I wonder if ASM will help

[Kamikaze47]

Nice work DT.

It's amusing that doing a single shift twice takes less time than a double shift.

I have run into a problem though. Does anyone know why this gives me an incorrect result?

X VAR WORD
T VAR LONG
Y VAR LONG

X=8100

T = X << 1
T = T << 1
T = T << 1
Y = T << 1 + T + X

LCDOUT $FE,$80,"T=",DEC T
LCDOUT $FE,$C0,"Y=",DEC Y

T is 64800 (as expected), but Y is 2516719364 ?!

I'm guessing that its something about long variables that I am missing.

[Darrel Taylor]

Nice find Kamikaze!

There's a small bug in the pbppi18l.mac file.
The SHIFTL?NCN macro should be changed as follows. (3's in red)

SHIFTL?NCN macro Nin, Cin, Nout
    if ((Cin) == 1)
        bcf     STATUS, C
      if ((Nout) == (Nin))
        CHK?RP  Nout
        rlcf    Nout, F
        rlcf    (Nout) + 1, F
        rlcf    (Nout) + 2, F
        rlcf    (Nout) + 3, F
      else
        CHK?RP  Nin
        rlcf    Nin, W
        MOVE?AB Nout
        CHK?RP  Nin
        rlcf    (Nin) + 1, W
        MOVE?AB (Nout) + 1
        CHK?RP  Nin
        rlcf    (Nin) + 2, W
        MOVE?AB (Nout) + 2
        CHK?RP  Nin
        rlcf    (Nin) + 3, W     ; was 2
        MOVE?AB (Nout) + 3
      endif
    else
        MOVE?NN Nin, R0
        movlw   Cin
        L?CALL  SHIFTL
        MOVE?ANN R0, Nout
    endif
    endm
SHIFTL_USED = 1
  endmod

I'll let the guys know.
<br>

[Kamikaze47]

Yep, that fixed it. Thanks DT.

I'm surprised that the bug hasn't been found before now.

Out of curiosity, why did it only affect the shift on the last line, and not the first three?

T = X << 1
T = T << 1
T = T << 1
Y = T << 1 + T + X

[Darrel Taylor]

why did it only affect the shift on the last line, and not the first three?

Exactly, that was the question I had too.

But as it turns out, the problem was in the 3rd/4th byte, only when shifting 1 place. Found that easily using the ISIS simulator.
So shifting 8100 the first time, wasn't big enough for the 3rd/4th byte to matter.

With the second and third shift it uses a different part of the macro.
The Input and Output variables are the same (Nout) == (Nin), so it uses the code in Red (4 instructions)

Then on the last line, the Input and Output variables were different, so it used the code in blue, the number was big enough, and the 3rd byte was corrupt.
--Error-- Danger Will Robinson, Danger, Danger.

SHIFTL?NCN macro Nin, Cin, Nout
    if ((Cin) == 1)
        bcf     STATUS, C
      if ((Nout) == (Nin))
        CHK?RP  Nout
        rlcf    Nout, F
        rlcf    (Nout) + 1, F
        rlcf    (Nout) + 2, F
        rlcf    (Nout) + 3, F
      else
        CHK?RP  Nin
        rlcf    Nin, W
        MOVE?AB Nout
        CHK?RP  Nin
        rlcf    (Nin) + 1, W
        MOVE?AB (Nout) + 1
        CHK?RP  Nin
        rlcf    (Nin) + 2, W
        MOVE?AB (Nout) + 2
        CHK?RP  Nin
        rlcf    (Nin) + 3, W     ; was 2
        MOVE?AB (Nout) + 3
      endif
    else
        MOVE?NN Nin, R0
        movlw   Cin
        L?CALL  SHIFTL
        MOVE?ANN R0, Nout
    endif
    endm
SHIFTL_USED = 1
  endmod

To answer your previous question.

When you shift more than 1 place at a time, it copies the variable to a system register, saves how many bits to shift, then calls a Library routine (SHIFTL) to loop through the number of shifts required. There's quite a bit of overhead in that saving and looping. (the Magenta code)

Avoiding that is how I got the speed increase in my previous post.
Although my previous numbers have no bearing on PBPL.

If that actually made any sense, I will eat a bug.

[Kamikaze47]

If that actually made any sense, I will eat a bug.

Made sense to me, so eat up.

Thanks DT for your in depth analysis. All is clear now.