Preserved Topic: Bytesize: optimizing using common binary tricks. (Page 1 of 1)

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Thanks for sharing InI!
I acctually understood what you were talking about I don't know how to use this newly gained knowledge right now, but I'm sure it will come in handy later on.

_________________________
Anyone who has lost track of time when using a computer knows the propensity to dream, the urge to make dreams come true and the tendency to miss lunch.
- copied from the wall of cell 408 -

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Actually, I recently tried this with my Javascript Raytracer. Using binary & instead of modulus with numbers that are powers of 2. ((x % (2^a)) is the same as (x & (2^a-1)))

I'm not sure if it makes as much of a different in JavaScript, but it's sorta cool to be working with individual bits, anyway =)

Slime: care to explain that a little bit more? I thought that the binary & only could return true or false. And the modulus operator can return a lot of different numbers... So how is it possible to exchange them with each other like that?

_________________________
Anyone who has lost track of time when using a computer knows the propensity to dream, the urge to make dreams come true and the tendency to miss lunch.
- copied from the wall of cell 408 -

*logical* && (two ampersands) can only return true or false. *binary* & (one ampersand) goes through each bit of the two numbers, and for each bit that is "1" in *both* numbers, the coresponding bit in the returned number will be 1. For instance:

13 % 8 = 5. similarly, since 8 = 2^3:

13 & (2^3-1) = 5 as follows:

13 = 1101
2^3-1 = 0111

1101 & 0111 = 0101

and 0101 = 6.

=)

Bit shifting is fun.

I found it really interesting when I found out Java could perform a bit shift operation, then I found out it had a bitwise & and that blew my socks off. Java takes the programmer so far away from the byte level and actually touching memory locations and then it gives you some operands that do just that.

But yes, it does make for some faster computations. The speed gains are negligable on the whole since computers are so fast no a days, but it is a change from:

n = number to be multiplied or divided by
m = number of bit shifts

so you would have run times of O(n^2) for the multiplication or division by the clasical multiplication algorithm or O(logn) for divide and conquer. While you would be looking at O(m) time where m is a constant, which would leave you with a run time of O(1).

At any rate by inspection you can see the difference in the number of operations as:

div

Hmm, I never did learn how multiplication is actually calculated.

Thanks for the explanation Slime. I was mixing the logical and binary operators as you probably figured out, but with that sorted out I understand what you said as well. But I think 0101 = 5 and not 6 as you have in the end of your last post

Due to WarMage's post above I start to see that this can realy speed things up. But most of the programs I make now (in Java) use float or double variables for almost every calculation, so I was wondering if there is a safe way do do bit operations on them? The only times I have used bit operations before have been on integers so I'm heading into unfamiliar terriory, for me at least...


_________________________
Anyone who has lost track of time when using a computer knows the propensity to dream, the urge to make dreams come true and the tendency to miss lunch.
- copied from the wall of cell 408 -

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

You're welcome. I found it in the POV-Ray source, actually, and they took it from Ken Perlin's old Perlin Noise code =)

And yes, that last 6 should have been a 5.

That's funny to see people (re)discovering the power of binary
Pals, you should have a look at the MMX instructions, they are so powerfull to handle bits and packed instructions.
For instance AFAIR, InI's code snippet can be done in 7 MMX instructions and run in ~5 clock cycles.


Mathieu "POÏ" HENRI

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

I don't think it's possible to willingly use the MMX instructions in anything else than assembly ( or inline assembly as it's possible in C/C++ ).
And obviously it would ruin the compatibility but the advantages of MMX are really strongs. It handles some 8bytes registers as if they were 8 single bytes / 4 single words / 2 single dword and can add and multiply those registers in the same instruction. You have some saturated addition an substractions in one instruction. etc.... If you plan to release some software ( especially graphic applications ) on PC, it shouldn't hurt to have a look at the MMX references.

Mathieu "POÏ" HENRI

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Multiplication is different depending on the architecture and what you are working with..

for example

X = X + 20;

under most Intels as integers gets changed to

MOV EAX, X;
SHL EAX, $02;
LEA EAX, [EAX + EAX * 4]

all this means is ... shift left twice.. (*4) and then multiply by 5;

also... its not wise to use & and

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Just remember that shifting is a feature of the processor too.. this ends up actually being slower on other processors that don't support bit shifting.

Rahly

Java Drivers?

In theory it's best to write your source code to do explicitly what you want it to do (multiply by 2), than to apply the optimization of turning it into bitshifting yourself. If your compiler is a decent one, it'll make that optimization for you.

Theory has a tendency to hit the wall in practical application though; especially when it comes to code that runs on a VM. In that case, you're usually best served by reducing the number of VM ops executed, regardless of what they actually do at a lower level, since you're paying a substantial price in CPU time for each opcode dispatch (JIT notwithstanding, but then a good JIT engine should optimize multiplication by powers of 2 to bit shifts if that's best for your CPU, so it goes both ways).

And of course, it goes without saying that you should never optimize without profiling first.