CompuServe Messages

Kirk, approximating the initial square root: assume that the input value is a binary integer of some size, or can be looked at as one (e.g. the mantissa of a floating point number). There are a certain number of leading zeros, followed by a 1, and then some digits that are either 0 or 1: 000…0001xxx…xxx a crude approximation of the square root of this number is: 000…0001xxx…xxx where the new string of xxx….xxx is half as many bits long as the old one. This will be correct within a factor of 2. My first impulse was to use all zeros for the new xxx, but then I realized it would make more sense to use the next few bits of the original value. E.g., if you're taking the square root of 00001abcdefghij then use an initial value of 00001abcde I don't have any proof, but it seems to me that will always be closer than straight zeros. How do you create that value? Something like this: Assume Value contains the number to be square-rooted ApproxSqrt=Value Temp=Value While Temp isn't 0 Shift Temp right by two bits Shift ApproxSqrt right by one bit End while I believe a slight improvement is: Assume Value contains the number to be square-rooted ApproxSqrt=Value Temp=Value While Temp isn't 0 or 1 Shift Temp right by two bits Shift ApproxSqrt right by one bit End while If Temp is 1, multiply ApproxSqrt by the square root of 2 (for approximation purposes, multiply by 1.5 — ApproxSqrt=ApproxSqrt + ApproxSqrt shift-right by 1) I might have some of the logic slightly wrong, but I'm sure the idea is valid. However: how close does the approximate square root have to be? Is a factor of 2 unacceptably far off (needs too many iterations to fix up)? – Bela PS: an article in this month's Computer Language examines the assembly language of the IBM RT PC. It mentions an instruction to count the number of leading 0 bits in a register. Boy, that would be handy in this operation…