Modern Electronics (was Re: List charter mods & headcount... ;

William> Probably, as I remember multiplying can be done in a number William> of odd ways, some of which can speed up things quite a William> lot. I remember from the old 100K ECL books the strange William> "Wallace Tree" adder chip, specifically designed to add nine William> bits all at once. This was part of a 64 bit multiplier. William> I always assumed there were equally odd way of doing William> division. I don't think so. Multiplication can be optimized lots of ways. Division has always been the annoying exception that refuses to go much faster no matter how hard you beat on it. The standard algorithm is essentially classic elementary school long division, in base 2 -- which means you get one bit of result per cycle. Some implementations, going back at least as far as the CDC 6600 in 1964, add a pile of extra logic to compute multiple bits of result per cycle -- 2 bits in the case of the 6600, which doubles the speed at a cost of MORE than 2x in logic. Then there are special cases: the Cray and Alpha integer units, which don't offer divide at all. Instead, you're supposed to multiply by the reciprocal of the divisor. This works well, because you can actually do that faster than the straightforward one bit at a time division even if you have to calculate the reciprocal at runtime. In the Alpha case at least, the system library divide routine would find the reciprocal by table lookup for small divisors, and the compiler would find it for any divisor if it's a compile time constant. GCC (in recent versions) does the same for any processor. paul