Hi users,
I am looking for 32bit/32bit divide code.
Now, I am implementing the PNS random generator for MPEG4 AAC.
I find some divide floating point code in the PNS as followings:
scale = 0x10000000/energy
Of course, energy represents the 32bit fixed point formant. I think two
variables regard as a Q0 format.
Does anybody give me the divide code or explain the theory of integer
divide?
I appreciate it.
integer 32bit/32bit divide code
Started by ●January 5, 2006
Reply by ●January 6, 20062006-01-06
My dear tommy, The theory of the integer division is explained in the 3rd class of the elementary school. I feel real sorry about the software engineers like you... VLV tommy wrote:> Hi users, > I am looking for 32bit/32bit divide code. > Now, I am implementing the PNS random generator for MPEG4 AAC. > I find some divide floating point code in the PNS as followings: > scale = 0x10000000/energy > Of course, energy represents the 32bit fixed point formant. I think two > variables regard as a Q0 format. > Does anybody give me the divide code or explain the theory of integer > divide? > > I appreciate it. >
Reply by ●January 6, 20062006-01-06
tommy wrote:> Hi users, > I am looking for 32bit/32bit divide code. > Now, I am implementing the PNS random generator for MPEG4 AAC. > I find some divide floating point code in the PNS as followings: > scale = 0x10000000/energy > Of course, energy represents the 32bit fixed point formant. I think two > variables regard as a Q0 format. > Does anybody give me the divide code or explain the theory of integer > divide? > > I appreciate it.There are many ways to do division on a computer. The best way depends on the hardware that your computer has. If it has a good multiplier, one good way would use Newton's method to find the reciprocal, then multiply. You need to understand your resources in order to use them well. Are you aware that the width of your ALU matters? You haven't told it to us. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●January 6, 20062006-01-06
The post by the Troll does has an element of insight to it; the reference to 3rd year elementary school. By this I mean, this is about the time that students are introduced to long division. Integer division can be worked out in the same fashion. As an example, lets divide 100b by 10b (or 8 by 4 in decimal). Following the (elementary school) algorithm, we would first ask, how many times does "10" go into "10", with the answer being 1, which is the first digit of the answer. We would then put '1' times 10 below the 100b and subtract leaving a (remainder) of '0' as a carry down. Next we realize that "10" will go into "0", "0" times, so the next digit is a 0. We could either stop here, or place a decimal (binary) point and continue to append zeros and continue the process. At the end we would wind up the the binary result of 10.0 , where the '.' is the binary point. In decimal 10b is '2' which is the correct answer. I have seen software algorithms implemented in this fashion, though I am sure that a search would turn up shortcuts that are more efficient. As a user / designer, it is important to understand that the computer will simply perform the raw calculation on the numbers and it is your responsibility to make sure that the numbers make sense. One potential problem is that a 32 bit number divided by a 32 bit number could very well "overflow". For example, in unsigned 2s complement for simplicity, lets say we have the maximum value and that it represents as close to 1 as we can get (.999999etc) = 0x(.)FFFFFFFF. If we divide this by .5 = 0x(.)10000000 where I have included the fictational binary points for clarity, we are i n trouble. The answer, which would be 2 wont fit in our result. Consequently, one normally divides a 2N bit number by a N bit number to ensure that there is enough space for the result.
Reply by ●January 6, 20062006-01-06
Ooops, I noticed an error in my above post, 100b and 10b are 4 and 2, not 8 and 4. Initially I was going to use 1000 and 100 but decided to simplify the example.
Reply by ●January 6, 20062006-01-06
See rules for fixed-point division in http://www.digitalsignallabs.com/fp.pdf --RY #include <stdint.h> uint64_t Divide32(uint32_t y, uint32_t x) { uint16_t n; uint64_t answer; uint64_t remainder; uint64_t divisor; answer = 0; remainder = x; divisor = (uint64_t)y << 32; for (n = 0; n < 32; n++) { divisor = divisor >> 1; if (remainder >= divisor) { remainder -= divisor; answer |= (uint64_t)1 << (63 - n); } } for (n = 0; n < 32; n++) { remainder = remainder << 1; if (remainder >= divisor) { remainder -= divisor; answer |= (uint64_t)1 << (31 - n); } } return answer;
Reply by ●January 6, 20062006-01-06
"tommy" <parcor@gmail.com> writes:> Hi users, > I am looking for 32bit/32bit divide code. > Now, I am implementing the PNS random generator for MPEG4 AAC. > I find some divide floating point code in the PNS as followings: > scale = 0x10000000/energy > Of course, energy represents the 32bit fixed point formant. I think two > variables regard as a Q0 format. > Does anybody give me the divide code or explain the theory of integer > divide?I describe how to perform fixed-point division here: http://www.digitalsignallabs.com/fp.pdf and the routine you seek (for unsigned ints) is here: uint64_t Divide32(uint32_t y, uint32_t x) { uint16_t n; uint64_t answer; uint64_t remainder; uint64_t divisor; answer = 0; remainder = x; divisor = (uint64_t)y << 32; for (n = 0; n < 32; n++) { divisor = divisor >> 1; if (remainder >= divisor) { remainder -= divisor; answer |= (uint64_t)1 << (63 - n); } } for (n = 0; n < 32; n++) { remainder = remainder << 1; if (remainder >= divisor) { remainder -= divisor; answer |= (uint64_t)1 << (31 - n); } } return answer; } -- % Randy Yates % "She's sweet on Wagner-I think she'd die for Beethoven. %% Fuquay-Varina, NC % She love the way Puccini lays down a tune, and %%% 919-577-9882 % Verdi's always creepin' from her room." %%%% <yates@ieee.org> % "Rockaria", *A New World Record*, ELO http://home.earthlink.net/~yatescr
Reply by ●January 7, 20062006-01-07
Randy Yates wrote:> See rules for fixed-point division in > > http://www.digitalsignallabs.com/fp.pdf > > --RY > > #include <stdint.h> > > uint64_t Divide32(uint32_t y, uint32_t x) > { > uint16_t n; > uint64_t answer; > uint64_t remainder; > uint64_t divisor; > > answer = 0; > remainder = x; > divisor = (uint64_t)y << 32; > > for (n = 0; n < 32; n++) > { > divisor = divisor >> 1; > if (remainder >= divisor) > { > remainder -= divisor; > answer |= (uint64_t)1 << (63 - n); > } > } > > for (n = 0; n < 32; n++) > { > remainder = remainder << 1; > if (remainder >= divisor) > { > remainder -= divisor; > answer |= (uint64_t)1 << (31 - n); > } > } > > return answer;I used to do this in assembly, shifting the quotient into a register a bit at a time as the dividend shifted out of the same register. I could do this on most DSPs, too, but their multipliers make finding the reciprocal and multiplying much more efficient. Repeating from an earlier post on mine in the thread, "You need to understand your resources in order to use them well." Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●January 7, 20062006-01-07
Jerry Avins <jya@ieee.org> writes:> [...] > Repeating from an earlier post on mine in the thread, "You need to > understand your resources in order to use them well."Yes, that's true. However... I don't view the OP as being unclear in his original request. He asked for a 32-bit division and I gave him one. I have been frustrated in the past by folks attempting to "second-guess" me and I am treating tommy the way I would like to be treated: to simply answer the question that was asked. Offering more information is OK too, but first and foremost, answer the question. -- % Randy Yates % "Remember the good old 1980's, when %% Fuquay-Varina, NC % things were so uncomplicated?" %%% 919-577-9882 % 'Ticket To The Moon' %%%% <yates@ieee.org> % *Time*, Electric Light Orchestra http://home.earthlink.net/~yatescr
Reply by ●January 7, 20062006-01-07
Randy Yates wrote:> Jerry Avins <jya@ieee.org> writes: > >>[...] >>Repeating from an earlier post on mine in the thread, "You need to >>understand your resources in order to use them well." > > > Yes, that's true. However... > > I don't view the OP as being unclear in his original request. He > asked for a 32-bit division and I gave him one. > > I have been frustrated in the past by folks attempting to > "second-guess" me and I am treating tommy the way I would > like to be treated: to simply answer the question that was > asked. Offering more information is OK too, but first and > foremost, answer the question.You gave him good cross-platform code, and if he hasn't yet thanked you for it, I'm sure he will. His application might not tolerate the time it takes, and I want him to know that there may well be more efficient ways to divide on his computer, and maybe even an algorithm (fraction saving?) that avoids the need. If you took my comment as a slur on you, I framed it badly. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
