division through a constant
That was by hand. Though the infinite series of powers of two that makes up 1/3 is very well behaved, so it was a lot easier to do than it looks.
What is the range of values for X? If they're not too large, you can use SiCrane's great code, just use the first few shifts and discard the rest. His algorithm begins:
(X >> 6) + (X >> 8) + (X >> 10) + (X >> 12)
If X is always less than 4096, X >> 12 will always be zero, as will all the terms to the right of it in the original algorithm. Therefore you can just use:
(X >> 6) + (X >> 8) + (X >> 10)
And get perfectly accurate results every time. And that may be faster than doing the division. Profile it.
EDIT: Nevermind, SiCrane is wrong. He forgot he's dealing with integer math. For example, take 48*7 = 336. Passed through his algorithm:
(336/64) + (336/256) + (336/1024) ...
Taken as integers, you get 5+1+0 = 6. Taken as floating-point numbers, you get 5.25 + 1.3125 + 0.328125 = 6.89, and doing the other divisions/additions will bring it to exactly 7.
~CGameProgrammer( );
-- Post screenshots of your projects. There's already 134 screenshot posts.
[edited by - CGameProgrammer on February 21, 2004 8:01:25 AM]
(X >> 6) + (X >> 8) + (X >> 10) + (X >> 12)
If X is always less than 4096, X >> 12 will always be zero, as will all the terms to the right of it in the original algorithm. Therefore you can just use:
(X >> 6) + (X >> 8) + (X >> 10)
And get perfectly accurate results every time. And that may be faster than doing the division. Profile it.
EDIT: Nevermind, SiCrane is wrong. He forgot he's dealing with integer math. For example, take 48*7 = 336. Passed through his algorithm:
(336/64) + (336/256) + (336/1024) ...
Taken as integers, you get 5+1+0 = 6. Taken as floating-point numbers, you get 5.25 + 1.3125 + 0.328125 = 6.89, and doing the other divisions/additions will bring it to exactly 7.
~CGameProgrammer( );
[edited by - CGameProgrammer on February 21, 2004 8:01:25 AM]
No, I remembered that this was integer math. It''s just that it''s easier to explain the derivation of the broken formula than it is to explain the derivation of the actual correct bitshift division method. And the broken formula is sufficient to explain why it''s a bad idea.
If you want an actual correct division by 48 method using shifts, here it is (for 32 bit unsigned ints):
(((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - 0) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1) >> 4)
If you want an actual correct division by 48 method using shifts, here it is (for 32 bit unsigned ints):
(((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - ((n - 0) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1)) >> 1) >> 4)
> I''m using pure integer math, can''t multiply by 1/48
Oh, but you can! Use fixed-point arithmetic. Derivation:
(from a previous thread)
Oh, but you can! Use fixed-point arithmetic. Derivation:
quote:Problem: calculate a/b. If we can''t shift or divide, we have to multiply a by (1/b). First thought: let r = c/b, then q = (r * a) / c (c > a,b). Unfortunately, q <= a/b, due to truncation during the divisions. We can avoid this by ''padding'' the numerator: r = ((c+b-1)/b). Finally, choose c = 0x100000000, and we can divide by c for free - the "mul r" instruction places the upper 32 bits of the product into edx, which is then equal to a/b.
(from a previous thread)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
