Dividing without dividing

[Jacob Roman]

I'm curious on how I would divide without using the '/' symbol and the '\' symbol. It involves multiplying by a decimal or something. I've seen this before. I know C++ can do it using bit shifting. So how would I do it? Bare in mind, this is for speed purposes, so don't give me slow methods. Thanks in advance you all.

[BluEyes]

man, to multiply by a decimal, or to divide takes the same cpu effort... what's the point? besides that, the mathematical logic in it is pretty simple and obvious, you're *multiplying* by just a part of an integer ('entire') numer. so what you get is a piece of that integer ('entire') number, just like in a division you get a piece of another number. hope it's clear enough, I ain't no math-brain...
BluEyes.

[dglienna]

10 / 5 =
10 * .2 =
2

10 / (1/3) =
10 * 3=
30

Thought you were in college ?

[Jacob Roman]

No BluEyes. Dividing takes more assembly instructions than multiplying. And multiplying is super fast when in comparison to dividing. So no it doesn't take as much CPU effort. Maven would say the same thing.

[BluEyes]

Yeah, but isn't that what compiler-level'ed code optimization is for?
BluEyes.

[randem]

Jacob Roman,

Multiply by .5

[Jacob Roman]

No, I wanna be able to somehow use a certain formula or method to multiply or bitshift just about any value to simulate division. I know I can create a DLL file in C++ to allow realtime bitshifting in VB, not to mention use ASM in C++ for VB.

[Illiad]

What is this for?

[Jacob Roman]

Just need something that's faster than dividing, which can come in handy in many of my programs.

[penagate]

You can make a program to output a table of decimals to use when dividing, e.g.

to divide by 4 ... (1 / 4) = 0.25
to divide by 3 ... (1 / 3) = 0.333333333 etc.

Then use those in your code instead.

If you know you can call ASM in C++ from VB, why not do that instead?

[CodeBlock]

Just need something that's faster than dividing, which can come in handy in many of my programs.

Hi there.

You have not understood how "/" and "\" differ in VB.

Here is the differenciation:

a = 11 / 2
 ' a = 5.5
 
 b = 15 / 4
 ' b = 3.75

a = 11 \ 2
 ' a = 5
 
 b = 15 \ 4
 ' b = 3

The \ operator just ignores the mantissa part (numbers after the decimal point) and returns a whole number.

Whats the point?
There is. The operator is like your C++ Floor function and can be made to get a custom Mod functionality.

Function GetReminder(iDividend As Integer, iDivisor As Integer)
    GetReminder = iDividend - ((iDividend \ iDivisor) * iDivisor)
End Function
 
    MsgBox 10 Mod 3
    MsgBox GetReminder(10, 3)
    ' U get the same result: 1

Still, Mod is faster in performance. But u can use this logic in any applicable where u dont find Mod (may be in another programming language where there is no % operator, [Never mind VB guys, % is the Mod operator there] .. hehe)

HTH
Neo

[westconn1]

assuming you are dividing by a variable, any function to get an inverse to mutiply by, i would assume, would have to take as long as dividing in the first place, unless you are going to be doing multiple divisions by a single value.

pete

[Joacim Andersson]

No, I wanna be able to somehow use a certain formula or method to multiply or bitshift just about any value to simulate division. I know I can create a DLL file in C++ to allow realtime bitshifting in VB, not to mention use ASM in C++ for VB.

Of course you could create a library that does this, however using that lib in VB will of course be much slower then actually just do a simple division. The reason is that you need to make an API call. Just to make the call, before the C/C++ code is starting to execute will probably take longer then doing the division in the first place.

You have to remember that VB does two function calls for every API call you make, the call you specify + a call to GetLastError which is always called to populate the Err.LastDLLError property.

Bitshifting would be an integer division since you can only do bitshifting on integer data types.

You always have these speed issue questions Jacob, and there is nothing wrong with that per say, but if you're really that interested in squeezing out the speed in every single operation you should consider using another language. However to be perfectly honest I think you're exaggerating the whole deal

[vbNeo]

but if you're really that interested in squeezing out the speed in every single operation you should consider using another language.

Go Java!!

[penagate]

Of course you could create a library that does this, however using that lib in VB will of course be much slower then actually just do a simple division. The reason is that you need to make an API call. Just to make the call, before the C/C++ code is starting to execute will probably take longer then doing the division in the first place.

You have to remember that VB does two function calls for every API call you make, the call you specify + a call to GetLastError which is always called to populate the Err.LastDLLError property.

Just out of interest, what is the performance like when using a callback function from say a C++ DLL? Does anything extra happen there?

I ask because (if you confused yourself enough) you could probably swap it around so it is in fact the C/C++ code calling the VB code, to eliminate that extra API call. Not something I'd do, but just curious to what the performance would be like.

[Joacim Andersson]

Go Java!!

Yeah sure, cause Java is sooo much faster then VB... (I was ironic if you didn't notice).

Just out of interest, what is the performance like when using a callback function from say a C++ DLL? Does anything extra happen there?

I don't understand what that would really accomplish, you would make an API call that calls back to your own code... and then what? When should the callback occur? Every time the library thinks you want to make a division? How would it know? Besides if it's a callback where would the division takes place? Sorry, but the question you asked confuses me

[penagate]

Yeah sure, cause Java is sooo much faster then VB... (I was ironic if you didn't notice).

No, JavaScript is the best

I don't understand what that would really accomplish, you would make an API call that calls back to your own code... and then what? When should the callback occur? Every time the library thinks you want to make a division? How would it know? Besides if it's a callback where would the division takes place? Sorry, but the question you asked confuses me

Having thought about it, I don't think it would accomplish anything at all in this situation ... I was just wondering what it is like for a performance point of view.

You say for every external call from VB, VB makes an extra call; I was wondering if you make an external call to a VB procedure from a C/C++ dll, is it just one call or does VB play any other funny tricks?

Sorry for confusing you

[Harsh Gupta]

hey JR!
as far as i remember, even in assembly language, the concept used is by shifting the bits. coz the cpus that support mult also support div and those which dont support mult can never support div, so i doubt if any other method exists than bit shifting (in cpus that never supported mult n div)........but if any such method exists i will let u know soon......i need to get back to my old books, so it will take some time.

[vbNeo]

Yeah sure, cause Java is sooo much faster then VB... (I was ironic if you didn't notice).

Ehm.. It is... And in some occasions, even faster than C++...

VB is just optimized for Win32...

[Jacob Roman]

I got it. You multiply the inverse of the number you are dividing.

Y / X = Y * 1 / X

Unfortunately you are still dividing, since the inverse is 1 / X.

Is it possible to create an inverse of a number using bitshifting, or Mod, or anything other than dividing? If I can figure this one out, I'll do a performance test and see what I get.

[penagate]

I got it. You multiply the inverse of the number you are dividing.

Y / X = Y * 1 / X

Unfortunately you are still dividing, since the inverse is 1 / X.

Is it possible to create an inverse of a number using bitshifting, or Mod, or anything other than dividing? If I can figure this one out, I'll do a performance test and see what I get.

But then you would be doing 2 things instead of only 1.

It is better to work out the inverse manually, if you can't do that, then division is the next best thing.

[DaveBo]

FYI, a few points,
1/x is the "reciprocal" of x (oops/apology, it is also called "inverse")

and, yes, that's a division, unless you've precalculated those reciprocals and loaded them into constants ahead of time. This assumes you have a fairly small set of values you want to divide by.

I think bit shifting will only provide you with division/multiplication by powers of 2, and you might run into problems with real numbers ?

I'm pretty sure Java and JavaScript are 2 very different animals, and I would assume that anything with the word "script" in it will tend to be a bit slower.
BTW, this is the "VB" forum, isn't it?

JA, I don't think you were being "ironic", sarcastic maybe.

[Joacim Andersson]

JA, I don't think you were being "ironic", sarcastic maybe.

Irony and sarcasm goes hand in hand, since they are actually synonyms.

[DaveBo]

Irony and sarcasm goes hand in hand, since they are actually synonyms.

You're right. Sorry about that.

[VBAhack]

Getting back to the original question, I remember seeing a clever algorithm for dividing very large integers (200+ significant digits) using addition and compare only. I don't see why it couldn't be done for the numbers we ordinary deal with, but I don't know if there would be a speed gain or not (my guess is no). It went something like this:

235 / 5:

Store the following sequence (doubling each pair of numbers by adding to itself) until the result exceeds 235

5 1
10 2
20 4
40 8
80 16
160 32
320 64

starting at the last entry that's less than 235 (i.e. 160 32), keeping adding each term until you reach/exceed 235:

result = 160 + 40 + 10 + 5 = 235
ans = 32 + 8 + 2 + 1 = 47

So, 235 / 5 = 47

The algorithm is buried in the divide routine for xNumbers:

http://digilander.libero.it/foxes/index.htm

VBAhack

[Jacob Roman]

Yeah that is pretty interesting, VBAhack.

I know there has to be a way to create an inverse without dividing. I was close when thinking about this:

10 / 2 = 5

10 * (1 / 2) = 5

10 * (2 * (1 / 2 ^ 2)) = 5 <-------- Yikes, another inverse is needed!

10 * (2 * (1 / 4)) = 5

So bagging that idea, I think there should be another way to create an inverse without dividing. I'll figure it out eventually. In math, there is always a way. If I'm succesful at this, and it turns out to be faster than dividing when I give it a performance test, I think this would make me famous. But the operations may have to be limited down to two or three cause otherwise it would probably be slower than dividing.

[moeur]

As Joacim stated, all this bit shifting and the above method only work for integers.
If your working with floating point, then divide and multiply operations will be sent to the FPU and require about the same amount of time.

Also note, as stadted above, that any generic routine you create will incure overhead because you will be putting it into a subroutine.

There are many libraries out there (some for free) that contain the complex calculations commonly performed in graphics manipulations and other tasks. These libraries have been optimized and would be hard to beat performance-wise by something any of us could write. So my suggestion is to look for one of these that contain the calculations you need to do.

[Joacim Andersson]

Jacob, before you trying to find the inversion of an operand without doing division (which I find hard to do). Why don't you do a performance test comparing the integer division operator (the backslash) and the multiply operator. I find it hard to believe there will be any CPU overhead to perform an integer division compared to a multiplication.

[Jacob Roman]

Because I'm not worried about that. The integer backslash I already know is faster than the regular slash, but when working with variables declared as Single when the decimals are needed, well you get the picture.

[Joacim Andersson]

I'm sorry Jabob but I find this discussion a teeny bit silly. The reason a division operation will be more strain full for the CPU is because of the floating point inaccuracy you might encounter. This would be the same with a muliplication if you would be able to use the correct numbers but you can't.

Let's take an example: Say you would like to divide a number with 3, that would be the same thing as multiply the number with 0.33333333333333333333333...... However you will not be able to store such number in a Single or Double data type so you would need to round it before you do the multiplication. To be able to round it you will need to first determent how exact you would like the result. Let's say that you only need a two decimal accuracy in which case you can multiply the number with 0.33 but by doing so you've already calculated for the floating point error you will get. 2 * 0.33 = 0.66 which is far less accurate then 2 / 3, which in a Double would end up as 0.666666666666667 and in a Single as 0.6666667. If you only needed 2 decimal accuracy the most accurate number would be 0.67 rather then 0.66 so maybe to get a 2 decimal accuracy you need to multiply with 0.333 instead of 0.33. That would lead to 0.666 which is closer to 0.67 then 0.66 is. But you would still need to round the result 0.666 ~ 0.67.

Now how much CPU does it take to first multiply with 0.333 and then round the result to two decimals compared to do the division by three in the first place?

1 / 3 = 0.33333333
3 * 0.33333333 = 0.99999999 hmmm... we need to round this to 1 to get a correct result.

The question is when do and how do you determent how exact you want the division (made with multiplication) should be and how will you round the result to get an as accurate number as possible. How much CPU will these calculation take compared to doing the division with either a Single or a Double in the first place. When you do the division you can easily determent how accurate you want the result by either do an integer division (that in speed is the same as a multiplication) or using either Single or Double precision floating point data types. What ever method you choose I'm convinced that you will get a more accurate result faster then trying to do it through multiplication.

EDIT:
Another thing: VB's native compiler creates the same binary code as the VC++ compiler. So you would get the most speed gain by removing the Integer overflow check and the Floating point error check, rather then spending time figuring out which number you should multiply an operand with when you actually want to do a division.

To get even more speed you can even allow unrounded floating point operations however keep in mind that that could lead to other errors when you compare two floating point values.

These are the optimizations I would use if I did a lot of calculations and needed to squeeze every little bit of speed out of it.

[chemicalNova]

As Joacim stated, all this bit shifting and the above method only work for integers.
If your working with floating point, then divide and multiply operations will be sent to the FPU and require about the same amount of time.

I assume you're using this for your Turntable simulation Jacob, in which case, the above would be true, because your RPM (when I looked anyway), was floating point.

Also, I agree with Joacim.

chem

[VBAhack]

I think there should be another way to create an inverse without dividing.

Jacob, there is an iterative method for finding an inverse that uses only multiplication and subraction. Here's the formula:

Ij = Ii(2-V*Ii)

where

Ij = new estimate of inverse of V
Ii = previous estimate of inverse of V
V = number for which you want the inverse

I think it's Newton's Method, or something. Let us know your result.

VBAhack

edit: yep, Newton's Method
http://www.ugrad.math.ubc.ca/coursed...ox/newton.html

[Jacob Roman]

Ok I'll try it and see what I get

[Jacob Roman]

It seemed like an idea at the time but when using this formula for, lets say for example, finding the inverse of 10, you again need to find out the inverse of 10 to even use the formula!

1/10 = 0.1

New formula:

Ij = Ii(2 - V * Ii)

0.1 = 0.1 * (2 - 10 * 0.1)

To find the other 0.1's in the formula, you obviously have to know ahead of time what the answer was, which means back to dividing. Damn.

[Joacim Andersson]

I think you misunderstood this Jacob. Newton's Method is about iteration and using linear approximation. It basically means that put in a number (any number) for Ii and test if that works. If not check if it's to high or to low and then try a new number... If you really think that using Newton's Method will be faster then the way your computer is doing division in the first place then good luck showing that

[moeur]

You just have to make a guess at the initial value.
For instance, if you want the inverse of 3, guess .1
In this case it takes about seven iterations to get a reasonable answer.
This method then takes about 50 times as long as just calculating 1/3.
The closer your initial estimate the fewer iterations you'll have to do.

But, I think you'll find that just running the calculation one time is slower than simply dividing 1/3.

[Joacim Andersson]

Hey Jacob, when you have found a faster way of doing division then the way the CPU is already doing it (and there obviously have to be one since everyone knows that componies like Intel tries do make their CPUs as slow as possible ) what will be the next step? May I suggest finding a faster way of multiplying numbers perhaps? There must be a way since the CPU isn't optimized for best performance already