
mhx
Enthusiast
Feb 26, 2002, 11:19 PM
Post #3 of 7
(10797 views)
|
Oooh, nice topic! First of all, I'm no processor architect, so my information may be a little inaccurate. But I'll try to answer one question after another...
For example, 10 * 10 , does a computer do 10 + 10 +10 +10 +10 +10 +10 +10 +10 +10 or use rules ( 10 * 10, take ending zeros and add to the top number, 100 * 1). No, it doesn't sum one number up several times. That would be really too slow. To start to think like a processor, stop thinking decimal and switch to binary. I'll use the suffix d for decimals in the following. Multiplying 10d with 10d will look like this for an 8-bit microprocessor:
00001010 * 00001010 ------------------- 00001010 00001010 1 ------------------- 01100100 => 64d+32d+4d => 100d So, this may look familiar to you. It's the normal way of multiplying two numbers, with the only difference that you have no more than two digits left. From the above, we can see that it takes at most n additions and n shifts to perform a multiplication of two n-bit numbers. However, modern processors have optimized multiplication units that can do a few steps at once.
Also for division, does a computer take one number at a time and divide out...( 100/2, 2 goes into 1 zero times, 2 goes into 10 five times, 2 goes into 0 zero times answer = 50). Division is a bit more complicated, although it would be possible to implement it in a similar way. If my memory isn't too bad, I can recall that I have implemented a division algorithm in assembler on a microcontroller that wasn't able to do divisions a couple of years ago. But it was really slow.
Also square roots, i can't understand how the computer does this, does it just do guess work until it hits the spot? Square root values can be computed by using an approximation. One of the most famous approximation schemes can be easily used here: Newton's method for finding the zeroes of a function. What you actually want to do is solve the equation: which can by squaring both sides be transformed to Now, we can write this as a function This function is zero for +/- sqrt(y). Newton's iteration scheme for finding zeroes is
x[n+1] = x[n] - f( x[n] ) / f'( x[n] ) where f'(x) is the derivation of f(x), in our case simply Now, the iteration scheme is
x[n+1] = x[n] - (x[n]^2 - y) / (2*x[n]) Let's say we want the square root of 2:
x[n+1] = x[n] - (x[n]^2 - 2) / (2*x[n]) We start with an initial value of x[0] = 2:
x[0] = 2 x[1] = 2 - (2^2 - 2) / (2*2) = 2 - 1/2 = 1.5 x[2] = 1.5 - (1.5^2 - 2) / (2*1.5) = 1.416666... x[3] = 1.417 - (1.417^2 - 2) / (2*1.417) = 1.4142163 You can see that after only 3 iterations, we're pretty close to the real value of 1.4142136. And everything was implemented with simple operations like addition, multiplication and division. Again, modern processors are very optimized and use tables to speed up divisions and square root and trigonometric function computations. Because this is highly sophisticated, I'm not trying to explain it (I know far too little about the topic). But here's how [url=http://www.stanford.edu/class/ee486/lecture/ee486_lect20_ho.pdf]AMD's K7 does divisions and square roots. This is, however, a very scientific paper. But here's something more practical, an implementation of a [url=http://www.mactech.com/articles/mactech/Vol.14/14.01/FastSquareRootCalc/]fast square root calculation, also based upon Newton's scheme.
Lastly how do computers interpret i, imaginary numbers, they dont exists so it isnt possible to calculate out some equations with imaginary numbers(some are possible when they have i to the second, etc.) or are imaginary numbers like variables and something that computers just dont really like. First of all, although they're called imaginary numbers, they do exist The computer doesn't care too much about i, since you can express imaginary or complex math with real equations. If you keep in mind is that i^2 = -1, complex math is really easy. Say you want to multiply two complex numbers z1 and z2, you can do the multiplication by splitting the complex numbers into their real and imaginary part:
z1 = x1 + i y1 z2 = x2 + i y2 Then z1 * z2 becomes:
(x1 + i y1) * (x2 + i y2) Remembering that i^2 = -1, you can turn that into
x1*x2 + i (x1*y2 + x2*y1) + (-1) y1*y2 So, the real and imaginary parts of the result z=x+iy are
x = x1*x2 - y1*y2 y = x1*y2 + x2*y1 You see, no i required to perform complex math as long as you know the rules.
Anyways thanks for just looking over this, sorry if it is in the wrong board. I fixed that already. Hope this was understandable. Just ask me again if I wasn't clear. -- mhx
At last with an effort he spoke, and wondered to hear his own words, as if some other will was using his small voice. "I will take the Ring," he said, "though I do not know the way."-- Frodo
|