Using shifting for multiplication and division

BlitzMax Forums/BlitzMax Programming/Using shifting for multiplication and division

plash

(Posted 2009) [#1]

http://en.wikipedia.org/wiki/Bit_shift#Bit_shifts

I knew ShiftRight was faster than division, but wasn't sure by how much.

Timed test:


SuperStrict

Framework brl.blitz
Import brl.standardio
Import brl.math

Const div_normal:Int = 4, div_shift:Int = 2
Const mul_normal:Int = 4, mul_shift:Int = 2
Const num_of_cycles:Long = 10000001

Local time:Int, value:Long

Print("Doing " + String(num_of_cycles) + " cycles...")

WriteStdout("Division normal: ")
time = MilliSecs()
For Local n:Long = 1 To num_of_cycles
	
	value = n / div_normal
	
Next
PrintTimeFrom(time)

WriteStdout("Division using ShiftRight: ")
time = MilliSecs()
For Local n:Long = 1 To num_of_cycles
	
	value = n Shr div_shift
	
Next
PrintTimeFrom(time)

WriteStdout("Multiplication normal: ")
time = MilliSecs()
' Multiplication test: Using standard multiplication
For Local n:Long = 1 To num_of_cycles
	
	value = n * mul_normal
	
Next
PrintTimeFrom(time)

WriteStdout("Multiplication using ShiftLeft: ")
time = MilliSecs()
' Multiplication test: Using ShiftLeft
For Local n:Long = 1 To num_of_cycles
	
	value = n Shl mul_shift
	
Next
PrintTimeFrom(time)


Function PrintTimeFrom(time:Int)
	
	Print(String(MilliSecs() - time) + "ms")
	
End Function

Results (release and command-line build, specs in signature):

Doing 10000001 cycles...
Division normal: 538ms
Division using ShiftRight: 262ms
Multiplication normal: 280ms
Multiplication using ShiftLeft: 252ms

Even though Shr and Shl can only be used with 2^n values, it's nice to know.

xlsior

(Posted 2009) [#2]

Yup...

Doing 10000001 cycles...
Division normal: 307ms
Division using ShiftRight: 178ms
Multiplication normal: 214ms
Multiplication using ShiftLeft: 187ms

matibee

(Posted 2009) [#3]

You can shift with non^2 numbers, eg. x * 200 = (x * 128) + (x * 64) + (x * 8) if you wanted to hard code that in an inner loop somewhere. I was kind of hoping (couldn't be arsed to test) that multiplying an int by a constant ^2 int or hard coded ^2 number, would have been optimised to a shift. Your test proves otherwise.

Are those timings from a release build?

_JIM	(Posted 2009) [#4]

I was kind of hoping (couldn't be arsed to test) that multiplying an int by a constant ^2 int or hard coded ^2 number, would have been optimised to a shift

It might be that the added verification time minus the chance to have multiplication by an exact ^2 number was not worth it. Would probably be a good solution at compile-time, but that would be a too small speedup, as there's very few hardcoded ^2 div/mul operations, and if you really need the speed for those, you can do it by shifting.

At execution time, as I previously said, it might just be too slow just to check considering the favorable cases are rare.

plash

(Posted 2009) [#5]

Are those timings from a release build?

Results (release and command-line build, specs in signature)

Yap.

Shortwind

(Posted 2009) [#6]

Blitzmax does not have a optimized Integer Division? If not then "Why not?" Shouldn't be hard for the developers of Blitz to incorporate that into the next build.

_JIM	(Posted 2009) [#7]

"Why not?" Shouldn't be hard for the developers of Blitz to incorporate that into the next build.

Read my post above :-)

ImaginaryHuman

(Posted 2009) [#8]

Check out the `bit twiddling hacks` page which features some other useful operations you can do to speed things up...

http://graphics.stanford.edu/~seander/bithacks.html

Amongst others, I use the lookup table array for figuring out how many bits are set in an integer, or what the index is of the lowest bit that is set. Much faster than trying to do it in normal code.