460,022 Members | 1,372 Online Need help? Post your question and get tips & solutions from a community of 460,022 IT Pros & Developers. It's quick & easy.

# Efficient division/remainder in C

 P: n/a I can't find any discussion of this question in this NG. I'd like to implement some variable precision integer arithmetic in C, and do it efficiently. A problem arises with the divide/remainder operations. I'm using gcc on x86, but a lot of what I say applies to other architectures. First, I assume the div and ldiv functions are more efficient than using / and % (obviously it depends on the compiler and level of optimization, but it's one operation instead of two). However, div and ldiv require the length of the quotient, divisor, dividend and remainder to all be the same. Now all the machines I've ever worked with at the machine language level (quite a few of them) implement integer division with a dividend that is twice as long as the divisor, quotient and remainder. Moreover, this is what naturally arises in multiple precision arithmetic, you get dividends twice as long as everything else. So suppose I'm using 16-bit divisors, quotients and remainders, but 32-bit dividends. If I were writing in assembly language, I would use the instructions that divide 16 bits into 32. But when I write in C, I'm forced to use the ldiv function, since one of the operands is 32-bits. (Let's say int=16-bit and long=32-bit, as on my machine.) Then the compiler has to implement this ldiv function by using the instruction that divides 32-bits into 64-bits, since the divisor is now 32-bits. In other words, the compiled code is forced to use a divide instruction with operands twice as large as needed, due to the design of the div and ldiv functions. Anybody know a way around this (apart from inserting assembly code in my C program)? Thanks in advance... Jan 13 '06 #1
29 Replies

 P: n/a ne*****@wigner.berkeley.edu wrote On 01/13/06 17:47,: [...] First, I assume the div and ldiv functions are more efficient than using / and % (obviously it depends on the compiler and level of optimization, but it's one operation instead of two). [...] But when I write in C, I'm forced to use the ldiv function, since one of the operands is 32-bits. (Let's say int=16-bit and long=32-bit, as on my machine.) Then the compiler has to implement this ldiv function by using the instruction that divides 32-bits into 64-bits, since the divisor is now 32-bits. In other words, the compiled code is forced to use a divide instruction with operands twice as large as needed, due to the design of the div and ldiv functions. The leap from "I assume" to "I'm forced" seems a risky one. What have your measurements shown about the efficiencies of /, %, both / and %, and ldiv? You *have* made measurements, haven't you? HAVEN'T YOU???? -- Er*********@sun.com Jan 13 '06 #2

 P: n/a Use inline assembly for the system you are on. Use macros to determine which routine depending on your system. Burst into flames. ne*****@wigner.berkeley.edu wrote: I can't find any discussion of this question in this NG. I'd like to implement some variable precision integer arithmetic in C, and do it efficiently. A problem arises with the divide/remainder operations. I'm using gcc on x86, but a lot of what I say applies to other architectures. First, I assume the div and ldiv functions are more efficient than using / and % (obviously it depends on the compiler and level of optimization, but it's one operation instead of two). However, div and ldiv require the length of the quotient, divisor, dividend and remainder to all be the same. Now all the machines I've ever worked with at the machine language level (quite a few of them) implement integer division with a dividend that is twice as long as the divisor, quotient and remainder. Moreover, this is what naturally arises in multiple precision arithmetic, you get dividends twice as long as everything else. So suppose I'm using 16-bit divisors, quotients and remainders, but 32-bit dividends. If I were writing in assembly language, I would use the instructions that divide 16 bits into 32. But when I write in C, I'm forced to use the ldiv function, since one of the operands is 32-bits. (Let's say int=16-bit and long=32-bit, as on my machine.) Then the compiler has to implement this ldiv function by using the instruction that divides 32-bits into 64-bits, since the divisor is now 32-bits. In other words, the compiled code is forced to use a divide instruction with operands twice as large as needed, due to the design of the div and ldiv functions. Anybody know a way around this (apart from inserting assembly code in my C program)? Thanks in advance... Jan 13 '06 #3

 P: n/a On 2006-01-13, ne*****@wigner.berkeley.edu wrote: I can't find any discussion of this question in this NG. I'd like to implement some variable precision integer arithmetic in C, and do it efficiently. A problem arises with the divide/remainder operations. I'm using gcc on x86, but a lot of what I say applies to other architectures. First, I assume the div and ldiv functions are more efficient than using / and % (obviously it depends on the compiler and level of optimization, but it's one operation instead of two). Not really - it requires a function call and use of a structure, and any compiler should optimize use of / and % with the same operands anyway. But when I write in C, I'm forced to use the ldiv function, since one of the operands is 32-bits. (Let's say int=16-bit and long=32-bit, as on my machine.) Then the compiler has to implement this ldiv function by using the instruction that divides 32-bits into 64-bits, since the divisor is now 32-bits. In other words, the compiled code is forced to use a divide instruction with operands twice as large as needed, due to the design of the div and ldiv functions. i'm pretty sure that there are instructions on x86 take 32 bits for both operands. Anybody know a way around this (apart from inserting assembly code in my C program)? just use / and %. Jan 14 '06 #4

 P: n/a You are right. Suppose I have declarations unsigned int quot,rem,dvsr; unsigned long dvnd; and then I say quot=dvnd/dvsr; rem =dvnd%dvsr; If the compiler is smart enough to generate a single divide instruction (that's all that's required on the x86 hardware), then I have what I want. Maybe I will try to figure out how to list assembly output from gcc to see what instructions it actually generates. Thanks for the reply! Jan 14 '06 #5

 P: n/a On 2006-01-14, ne*****@wigner.berkeley.edu wrote: Maybe I will try to figure out how to list assembly output from gcc to see what instructions it actually generates. gcc -S Jan 14 '06 #6

 P: n/a ne*****@wigner.berkeley.edu writes: You are right. [...] About what? Most of us can't easily see the article to which you're replying. Please read . [...] Maybe I will try to figure out how to list assembly output from gcc to see what instructions it actually generates. gcc -S -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Jan 14 '06 #7

 P: n/a Jordan Abel wrote: On 2006-01-13, ne*****@wigner.berkeley.edu wrote: First, I assume the div and ldiv functions are more efficient than using / and % (obviously it depends on the compiler and level of optimization, but it's one operation instead of two). Not really - it requires a function call and use of a structure, and any compiler should optimize use of / and % with the same operands anyway. just use / and %. Some of the responses make me wonder if your question was understood. You want both "/" and "%" but don't want to needlessly repeat the division. Do compilers find this optimization? Someone from Sun implies that speed comparison tests are appropriate. He should preach this in-house. It was trivial to beat memcpy() on Sun-3 (which was optimized for Sun-2). The early Sparc's integer multiply could not only be bettered by rewriting the assembly, it *could be beaten without assembly in a C routine!* (In either way the speed improvement was huge.) James Jan 14 '06 #8

 P: n/a Keith Thompson wrote: ne*****@wigner.berkeley.edu writes: [...] Maybe I will try to figure out how to list assembly output from gcc to see what instructions it actually generates. gcc -S I use: gcc -gstabs+ -Wa,-ahldn -c and pipe the result to less. -- "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers." - Keith Thompson More details at: Jan 14 '06 #9

 P: n/a James Dow Allen wrote: Someone from Sun implies that speed comparison tests are appropriate. He should preach this in-house. It was trivial to beat memcpy() on Sun-3 (which was optimized for Sun-2). How many employees from 20 years ago do you think are still there? :-) - Logan Jan 14 '06 #10

 P: n/a In article <11*********************@f14g2000cwb.googlegroups. com>, "James Dow Allen" wrote: Jordan Abel wrote: On 2006-01-13, ne*****@wigner.berkeley.edu wrote: First, I assume the div and ldiv functions are more efficient than using / and % (obviously it depends on the compiler and level of optimization, but it's one operation instead of two). Not really - it requires a function call and use of a structure, and any compiler should optimize use of / and % with the same operands anyway. just use / and %. Some of the responses make me wonder if your question was understood. You want both "/" and "%" but don't want to needlessly repeat the division. Do compilers find this optimization? Someone from Sun implies that speed comparison tests are appropriate. He should preach this in-house. It was trivial to beat memcpy() on Sun-3 (which was optimized for Sun-2). The early Sparc's integer multiply could not only be bettered by rewriting the assembly, it *could be beaten without assembly in a C routine!* (In either way the speed improvement was huge.) The probably didn't measure it. That's why he is telling you: Measure it. Or are you suggesting that measuring the speed of code before trying to optimise it for speed is a bad idea, because it was suggested by someone who works for a company who shipped some sub-optimal code twenty years ago? Jan 14 '06 #11

 P: n/a On 13 Jan 2006 18:03:25 -0800, ne*****@wigner.berkeley.edu wrote: You are right. Suppose I have declarations unsigned int quot,rem,dvsr; unsigned long dvnd;and then I say quot=dvnd/dvsr; rem =dvnd%dvsr;If the compiler is smart enough to generate a single divide instruction(that's all that's required on the x86 hardware), then I have what Iwant.Maybe I will try to figure out how to list assembly output from gcc tosee what instructions it actually generates.Thanks for the reply! You should check as well if the optimiser results are different for signed and unsigned integer types, since there is a slight complication with the sign of the modulo and the way it is rounded if one of the incoming values are negative. Jim Jan 16 '06 #12

 P: n/a Christian Bau wrote: In article <11*********************@f14g2000cwb.googlegroups. com>, "James Dow Allen" wrote: Someone from Sun implies that speed comparison tests are appropriate. He should preach this in-house. It was trivial to beat memcpy() on Sun-3 (which was optimized for Sun-2). The early Sparc's integer multiply could not only be bettered by rewriting the assembly, it *could be beaten without assembly in a C routine!* (In either way the speed improvement was huge.) I'm surprised no one was curious about the fast C-code multiply. It typically takes shorts in, long out -- a common case. If you've not seen the trick before, consider it a puzzle to reverse engineer it from the fragment: c = arr[x+y] - arr[x-y]; /* c = x * y */ It gives competitive performance even on some machines with blazingly fast multiplies. The probably didn't measure it. That's why he is telling you: Measure it. Mr. Sosman's comment was of course excellent. I thought this went without saying. What in my post implied otherwise? (I deliberately removed an attribution to reduce risk that my comment would somehow be seen as opposing.) Or are you suggesting that measuring the speed of code before trying to optimise it for speed is a bad idea, ... Hunh? I'll admit to a sardonic tone that is sometimes confusing, but what's with the blatant misconstruction? The only point I was alluding to is that even big organizations with which one would *like* to associate technical excellence, often fail sharply. ... so sharply it almost seems unfair here to chastise OP. James Jan 16 '06 #13

 P: n/a On 2006-01-16, James Dow Allen wrote: Christian Bau wrote: In article <11*********************@f14g2000cwb.googlegroups. com>, "James Dow Allen" wrote: > Someone from Sun implies that speed comparison tests are appropriate. > He should preach this in-house. It was trivial to beat memcpy() on > Sun-3 (which was optimized for Sun-2). The early Sparc's integer > multiply > could not only be bettered by rewriting the assembly, it *could be > beaten > without assembly in a C routine!* (In either way the speed improvement > was huge.) I'm surprised no one was curious about the fast C-code multiply. It typically takes shorts in, long out -- a common case. If you've not seen the trick before, consider it a puzzle to reverse engineer it from the fragment: c = arr[x+y] - arr[x-y]; /* c = x * y */ It gives competitive performance even on some machines with blazingly fast multiplies. OK, i'll bite - what goes in the array? Jan 17 '06 #14

 P: n/a Jordan Abel wrote: On 2006-01-16, James Dow Allen wrote: I'm surprised no one was curious about the fast C-code multiply. It typically takes shorts in, long out -- a common case. If you've not seen the trick before, consider it a puzzle to reverse engineer it from the fragment: c = arr[x+y] - arr[x-y]; /* c = x * y */ It gives competitive performance even on some machines with blazingly fast multiplies. OK, i'll bite - what goes in the array? Corners. /* BEGIN new.c */ #include int main(void) { unsigned x, y, arr; for (x = 0; 255 > x; ++x) { arr[x] = x * x / 4; } for (x = 0; 127 > x; ++x) { for (y = 0; 127 > y; ++y) { printf("%u * %u is %u\n", x, y, x > y ?arr[x+y] - arr[x-y] :arr[x+y] - arr[y-x]); } } return 0; } /* END new.c */ -- pete Jan 17 '06 #15

 P: n/a Jordan Abel wrote: On 2006-01-16, James Dow Allen wrote: .... snip ... I'm surprised no one was curious about the fast C-code multiply. It typically takes shorts in, long out -- a common case. If you've not seen the trick before, consider it a puzzle to reverse engineer it from the fragment: c = arr[x+y] - arr[x-y]; /* c = x * y */ It gives competitive performance even on some machines with blazingly fast multiplies. OK, i'll bite - what goes in the array? A table of squares. The result needs a division by 2. -- "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers." - Keith Thompson More details at: Jan 17 '06 #16

 P: n/a Jordan Abel wrote: On 2006-01-16, James Dow Allen wrote:Christian Bau wrote:In article <11*********************@f14g2000cwb.googlegroups. com>, "James Dow Allen" wrote: Someone from Sun implies that speed comparison tests are appropriate.He should preach this in-house. It was trivial to beat memcpy() onSun-3 (which was optimized for Sun-2). The early Sparc's integermultiplycould not only be bettered by rewriting the assembly, it *could bebeatenwithout assembly in a C routine!* (In either way the speed improvementwas huge.)I'm surprised no one was curious about the fast C-code multiply.It typically takes shorts in, long out -- a common case.If you've not seen the trick before, consider it a puzzleto reverse engineer it from the fragment: c = arr[x+y] - arr[x-y]; /* c = x * y */It gives competitive performance even on some machines withblazingly fast multiplies. OK, i'll bite - what goes in the array? In addition to the other answers, see e.g. http://www.mccw.hetlab.tk/92/Multiplication/en.html for an "explanation". Cheers Michael -- E-Mail: Mine is an /at/ gmx /dot/ de address. Jan 18 '06 #17

 P: n/a pete wrote: Jordan Abel wrote: On 2006-01-16, James Dow Allen wrote: c = arr[x+y] - arr[x-y]; /* c = x * y */ OK, i'll bite - what goes in the array? ... printf("%u * %u is %u\n", x, y, x > y ?arr[x+y] - arr[x-y] :arr[x+y] - arr[y-x]); I just want to point out that a solution can simultaneously (a) accept signeds, not just unsigneds (b) avoid the x > y ? timewaster (c) obey the rules of standard C. Again this is left as an exercise. James Jan 18 '06 #18

 P: n/a James Dow Allen wrote: pete wrote: Jordan Abel wrote: On 2006-01-16, James Dow Allen wrote: > c = arr[x+y] - arr[x-y]; /* c = x * y */ OK, i'll bite - what goes in the array? ... printf("%u * %u is %u\n", x, y, x > y ?arr[x+y] - arr[x-y] :arr[x+y] - arr[y-x]); I just want to point out that a solution can simultaneously (a) accept signeds, not just unsigneds (b) avoid the x > y ? timewaster (c) obey the rules of standard C. Again this is left as an exercise. /* BEGIN new.c */ #include int main(void) { int x, y, arr, *ptr; ptr = arr + 128; for (x = -128; 127 > x; ++x) { ptr[x] = x * x / 4; } for (x = -63; 64 > x; ++x) { for (y = -63; 64 > y; ++y) { printf("%d * %d is %d\n", x, y, ptr[x + y] - ptr[x - y]); } } return 0; } /* END new.c */ -- pete Jan 18 '06 #19

 P: n/a On 2006-01-18, James Dow Allen wrote: pete wrote: Jordan Abel wrote: > On 2006-01-16, James Dow Allen wrote: > > c = arr[x+y] - arr[x-y]; /* c = x * y */ > OK, i'll bite - what goes in the array? ... printf("%u * %u is %u\n", x, y, x > y ?arr[x+y] - arr[x-y] :arr[x+y] - arr[y-x]); I just want to point out that a solution can simultaneously (a) accept signeds, not just unsigneds How, by passing a possibly negative offset into an array? Or by testing both vars to be < 0? (b) avoid the x > y ? timewaster (c) obey the rules of standard C. Again this is left as an exercise. James Jan 18 '06 #20

 P: n/a pete wrote: Jordan Abel wrote: James Dow Allen wrote: > I'm surprised no one was curious about the fast C-code multiply. > It typically takes shorts in, long out -- a common case. > If you've not seen the trick before, consider it a puzzle > to reverse engineer it from the fragment: > c = arr[x+y] - arr[x-y]; /* c = x * y */ > It gives competitive performance even on some machines with > blazingly fast multiplies. OK, i'll bite - what goes in the array? .... snip ... int main(void) { unsigned x, y, arr; for (x = 0; 255 > x; ++x) { arr[x] = x * x / 4; } And how do you conclude that x*x is divisible by 4? (or even x)? -- "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers." - Keith Thompson More details at: Jan 18 '06 #21

 P: n/a Chuck F. wrote: pete wrote: Jordan Abel wrote: James Dow Allen wrote: > I'm surprised no one was curious about the fast C-code multiply. > It typically takes shorts in, long out -- a common case. > If you've not seen the trick before, consider it a puzzle > to reverse engineer it from the fragment: > c = arr[x+y] - arr[x-y]; /* c = x * y */ > It gives competitive performance even on some machines with > blazingly fast multiplies. OK, i'll bite - what goes in the array? ... snip ... int main(void) { unsigned x, y, arr; for (x = 0; 255 > x; ++x) { arr[x] = x * x / 4; } And how do you conclude that x*x is divisible by 4? (or even x)? I simply choose not to care, and the problem goes away by itself, just like everything else in C programming: 8 * 3 == 8 + 3 == 11 8 - 3 == 5 arr == 121 / 4 == 30 arr[ 5] == 25 / 4 == 6 30 - 6 == 24 8 * 3 == 24 -- pete Jan 18 '06 #22

 P: n/a pete wrote: Chuck F. wrote: pete wrote: Jordan Abel wrote: James Dow Allen wrote:> I'm surprised no one was curious about the fast C-code> multiply. It typically takes shorts in, long out -- a> common case. If you've not seen the trick before,> consider it a puzzle to reverse engineer it from the> fragment: c = arr[x+y] - arr[x-y]; /* c = x * y */ It> gives competitive performance even on some machines with> blazingly fast multiplies. OK, i'll bite - what goes in the array? ... snip ... int main(void) { unsigned x, y, arr; for (x = 0; 255 > x; ++x) { arr[x] = x * x / 4; } And how do you conclude that x*x is divisible by 4? (or even x)? I simply choose not to care, and the problem goes away by itself, just like everything else in C programming: 8 * 3 == 8 + 3 == 11 8 - 3 == 5 arr == 121 / 4 == 30 arr[ 5] == 25 / 4 == 6 30 - 6 == 24 8 * 3 == 24 Are you trying to force me to write modular diophantine equations and prove this? :-) I can conceive it may compensate, and may look later. -- "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers." - Keith Thompson More details at: Jan 18 '06 #23

 P: n/a pete wrote: Chuck F. wrote: And how do you conclude that x*x is divisible by 4? (or even x)? x*x need not be divisible by 4, but it is always of residue class 0 or 1! The residues thus aren't big enough to cause trouble!! I simply choose not to care, and the problem goes away by itself, just like everything else in C programming: I'm also a fan of C, but didn't realize it was *that* good! James Jan 19 '06 #24

 P: n/a On Wed, 18 Jan 2006 23:50:09 -0800, James Dow Allen wrote: pete wrote: Chuck F. wrote: > And how do you conclude that x*x is divisible by 4? (or even x)? x*x need not be divisible by 4, but it is always of residue class 0 or 1! The residues thus aren't big enough to cause trouble!! More precisely: if the only possible remainders are 0 and 0.25, this implies that the remainder must be identical for the two expressions (it's no doubt possible to prove this more directly), so that removing the remainders in the expressions through integer conversion has the same result as cancelling them in the subtraction. (those expressions being (a+b)**2 / 4, from which (a-b)**2 / 4 is subtracted, where ** is exponentiation) In any case, it was an interesting technique that you shared. Doing some quick calculations, assuming a short int of 16 bits and int of 32 bits, and allowing for signed multiplication, the complete table would consume approx 524,292 bytes (halved if you add a conditional to reuse a positive index when the index is negative). So you can exchange half a meg memory for faster multiplication of short ints on platforms where the technique is actually fast enough to warrant it. I simply choose not to care, and the problem goes away by itself, just like everything else in C programming: I'm also a fan of C, but didn't realize it was *that* good! Perhaps pete's symbiosis with C is as poetic as his postings. -- http://members.dodo.com.au/~netocrat Jan 19 '06 #25

 P: n/a "Chuck F. " wrote: pete wrote: Chuck F. wrote: pete wrote: Jordan Abel wrote:> James Dow Allen wrote:>> I'm surprised no one was curious about the fast C-code>> multiply. It typically takes shorts in, long out -- a>> common case. If you've not seen the trick before,>> consider it a puzzle to reverse engineer it from the>> fragment: c = arr[x+y] - arr[x-y]; /* c = x * y */ It>> gives competitive performance even on some machines with>> blazingly fast multiplies.>> OK, i'll bite - what goes in the array? ... snip ... int main(void) { unsigned x, y, arr; for (x = 0; 255 > x; ++x) { arr[x] = x * x / 4; } And how do you conclude that x*x is divisible by 4? (or even x)? I simply choose not to care, and the problem goes away by itself, just like everything else in C programming: 8 * 3 == 8 + 3 == 11 8 - 3 == 5 arr == 121 / 4 == 30 arr[ 5] == 25 / 4 == 6 30 - 6 == 24 8 * 3 == 24 Are you trying to force me to write modular diophantine equations and prove this? :-) I can conceive it may compensate, and may look later. If x==2a, y==2b, then x+y==2a+2b, ((x+y)**2)/4 == (4aa+8ab+4bb)/4 == aa+2ab+bb; x-y==2a-2b, ((x-y)**2)/4 == (4aa-8ab+4bb)/4 == aa-2ab+bb; ((x+y)**2)/4 - ((x-y)**2)/4 == aa+2ab+bb - (aa-2ab-bb) == 4ab == xy. If x==2a+1, y==2b+1, then x+y==2a+2b+2, ((x+y)**2)/4 == (4aa+8ab+4bb+8a+8b+4)/4 == aa+2ab+bb+2a+2b+2; x-y==2a-2b, ((x-y)**2)/4 == (4aa-8ab+4bb)/4 == aa-2ab+bb; ((x+y)**2)/4 - ((x-y)**2)/4 == aa+2ab+bb+2a+2b+1 - (aa-2ab+bb) == 4ab+2a+2b+1 == (2a+1)*(2b+1) == xy. If x==2a+1, y==2b, then x+y==2a+2b+1, ((x+y)**2)/4 == (4aa+8ab+4bb+4a+4b+1)/4 == aa+2ab+bb+a+b; x-y==2a-2b+1, ((x-y)**2)/4 == (4aa-8ab+4bb+4a-4b+1)/4 == aa-2ab-bb+a-b; ((x+y)**2)/4 - ((x-y)**2)/4 == aa+2ab+bb+a+b - (aa-2ab+bb+a-b) == 4ab+2b == (2a+1)*2b == xy. If x==2a, y==2b-1, then x+y==2a+2b+1, ((x+y)**2)/4 == (4aa+8ab+4bb+4a+4b+1)/4 == aa+2ab+bb+a+b; x-y==2a-2b-1, ((x-y)**2)/4 == (4aa-8ab+4bb-4a+4b+1)/4 == aa-2ab-bb-a+b; ((x+y)**2)/4 - ((x-y)**2)/4 == aa+2ab+bb+a+b - (aa-2ab+bb-a+b) == 4ab+2a == 2a*(2b+1) == xy. Note: integer divisions throughout, rounding down, as in C. Note on the note: this only matters if _either_ x or y is odd, not if both are. Richard Jan 19 '06 #26

 P: n/a Chuck F. wrote: diophantine you me friend good -- pete Jan 19 '06 #27

 P: n/a Netocrat wrote: On Wed, 18 Jan 2006 23:50:09 -0800, James Dow Allen wrote: pete wrote: Chuck F. wrote: > And how do you conclude that x*x is divisible by 4? (or even x)? I simply choose not to care, and the problem goes away by itself, just like everything else in C programming: I'm also a fan of C, but didn't realize it was *that* good! Perhaps pete's symbiosis with C is as poetic as his postings. I was just kidding around. -- pete Jan 19 '06 #28

 P: n/a Netocrat wrote: On Wed, 18 Jan 2006 23:50:09 -0800, James Dow Allen wrote: x*x need not be divisible by 4, but it is always of residue class 0 or 1! The residues thus aren't big enough to cause trouble!! More precisely: if the only possible remainders are 0 and 0.25, ... A residue of 3 would also not cause trouble, as long as you remember to make the remainder -0.25 instead of 0.75. My blood pressure goes up a little (when I forget my meds) whenever I divide a negative number because of the sadness that >>2 and /4 no longer work the same on 2's-complement machines. Fortunately there is no hypertension risk here, since x*x is never negative. In any case, it was an interesting technique that you shared. Doing some quick calculations, assuming a short int of 16 bits and int of 32 bits, and allowing for signed multiplication, the complete table would consume approx 524,292 bytes... That's assuming your multipliers use the full 16-bit range; often you'll get away with much less. The technique may be obsolescent now since hard-wired multipliers have become so frisky. I *did* use the technique on The World's Fastest Jpeg Compressor (tm), but only on Sun's early Sparc with its bizarrely slow multiplication. James Jan 20 '06 #29

 P: n/a In article <11*********************@o13g2000cwo.googlegroups. com>, "James Dow Allen" writes: That's assuming your multipliers use the full 16-bit range; often you'll get away with much less. The technique may be obsolescent now since hard-wired multipliers have become so frisky. I suspect that's true for general-purpose CPUs, with their fast integer multiplication and cache sensitivities (which weigh against table-based approaches in general). But it might still be useful for some embedded applications with simple processors, particularly if as you say the domain is restricted. Thanks for posing this puzzle, by the way. I spent 10 minutes or so working out values for the array on paper (using simultaneous equations; I didn't bother digging out my number theory textbooks, so I took the simple route). Interestingly, I came up with a different way to compute the series: {(i/2)**2, (i/2)**2 + i/2, ...} for i from 1 to N. That is, the first, third, and so on elements are the squares, and the second, fourth, etc are the squares plus their roots. Anyway, it was an amusing exercise. -- Michael Wojcik mi************@microfocus.com Some seem to live on credit as naturally as they breathe, and I remember the surprise of one of these: "What! You don't owe anybody anything! Good Lord! man, lend me half a sovereign." -- Arthur Ransome Jan 20 '06 #30

### This discussion thread is closed

Replies have been disabled for this discussion. 