CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: General Discussions: General Questions:
Math...

 



Pro_4
User

Feb 25, 2002, 3:33 PM

Post #1 of 7 (5318 views)
Math... Can't Post

I was just thinking yesterday, and i was wondering how computers go about solving math problems? 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). Im sure there are many other ways to taking apart a simple multiplication problem but thats just what came to mind at first. 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). Also square roots, i can't understand how the computer does this, does it just do guess work until it hits the spot?( i am still in high school so maybe there is a magical equation to making this easier) I was just thinking about this stuff so i could better understand how the computer looks at thinks and maybe in turn help me to look at things in different ways. 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. The more i sit here and type the more i continue to think about this.... i better stop before i make a fool out of myself Tongue



Anyways thanks for just looking over this, sorry if it is in the wrong board.


freddo
User

Feb 26, 2002, 4:55 PM

Post #2 of 7 (5302 views)
Re: [Pro_4] Math... [In reply to] Can't Post

Hello Pro_4,

Happy to see you around Sly!!!

What kind of answer do you expect? Electronics or Programming? (i can only help on the last one anyway)

I guess that for the board, the General Question is perhaps more appropriate?

Freddo
;---


mhx
Enthusiast

Feb 26, 2002, 11:19 PM

Post #3 of 7 (5296 views)
Re: [Pro_4] Math... [In reply to] Can't Post

Oooh, nice topic! Wink

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...


In Reply To
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:


Code
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.


In Reply To
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. Unimpressed


In Reply To
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:

Code
      x = sqrt(y)

which can by squaring both sides be transformed to

Code
      x^2     = y 
x^2 - y = 0

Now, we can write this as a function

Code
      f(x) = x^2 - y

This function is zero for +/- sqrt(y). Newton's iteration scheme for finding zeroes is

Code
      x[n+1] = x[n] - f( x[n] ) / f'( x[n] )

where f'(x) is the derivation of f(x), in our case simply

Code
      f'(x) = 2x

Now, the iteration scheme is

Code
      x[n+1] = x[n] - (x[n]^2 - y) / (2*x[n])

Let's say we want the square root of 2:

Code
      x[n+1] = x[n] - (x[n]^2 - 2) / (2*x[n])

We start with an initial value of x[0] = 2:

Code
      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.


In Reply To
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 Cool 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:

Code
      z1 = x1 + i y1 
z2 = x2 + i y2

Then z1 * z2 becomes:

Code
      (x1 + i y1) * (x2 + i y2)

Remembering that i^2 = -1, you can turn that into

Code
      x1*x2 + i (x1*y2 + x2*y1) + (-1) y1*y2

So, the real and imaginary parts of the result z=x+iy are

Code
      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. Wink


In Reply To
Anyways thanks for just looking over this, sorry if it is in the wrong board.


I fixed that already. Angelic

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



yapp
User

Feb 27, 2002, 6:51 AM

Post #4 of 7 (5291 views)
Re: [mhx] Math... [In reply to] Can't Post


In Reply To
No, it doesn't sum one number up several times. That would be really too slow.


Oh boy... FrownShockedLaugh

for our first semester, I created this (we needed to try out some basic 8085)

Code
; Calculates (5 + (8 * 15)) * 2 
; Keeps track of overflow errors,
; and a "times 0" is trapped aswell.


mvi d,8H ; D = 8
mvi e,EH ; E = 14
push d ; D en E op stack
call Multiply ; Do a Multiply!!
call Add5 ; Add 5
call Times2 ; Times 2

hlt ; End of program
; A is now EA, so 234


;===============================
; Subroutines


; Gets two bytes from the stack,
; and leaves the result in the acc
MULTIPLY: ; Subroutine Multiplies: A=B*C
mvi a,0
pop h ; POP Program Counter
pop b
cmp c
jnz DoMulti
push h
ret

DoMulti:
add b ; A = A + B
jc Overflow ; Is Overflow?
dcr c
jnz DoMulti
push h ; Push back Program Counter
ret

; Adds 5 to the acc and tests for overflow
ADD5:
adi 5H ; A = A + 5
jc Overflow ; Is Overflow?
RET

; Multiplies A with 2, and tests for overflow
TIMES2:
add a ; A = A + A (A*2)
jc Overflow ; Is Overflow?
RET



; Fake some overflow message,
; set all registers to FF and break,halt
OVERFLOW:
mvi a,FFH
mvi b,FFH
mvi c,FFH
mvi d,FFH
mvi E,FFH
mvi H,FFH
mvi L,FFH
;BREAK
HLT



Yet Another Perl Programmer

_________________________________
~~> [url=http://www.codingdomain.com]www.codingdomain.com <~~
More then 3500 X-Forum [url=http://www.codingdomain.com/cgi-perl/downloads/x-forum]Downloads! Cool

(This post was edited by yapp on Feb 27, 2002, 6:52 AM)


Pro_4
User

Feb 27, 2002, 12:31 PM

Post #5 of 7 (5279 views)
Re: [mhx] Math... [In reply to] Can't Post

Wow... i never thought about it that way. That is pretty cool. PLz forgive my stupidness in math, heh i am only in 10th grade taking Algebra 2 Frown I thought the computer would use approximations for the square rooting but i thought that would take a immense ammount of time(if you want to find a lot of decimals). Oh well the computer will always thinks 10000000000000000 times faster than i ever will Tongue. Where did you learn all that, college courses you took? I am planning to take a few college courses over the summer about programming/computers, what would you suggest?



Heh, thanks for moving my post. Took a while to find tho.... heh i looked in Intermediate and it wasnt there. Right after i submitted that i kept on getting 520(or something like that) errors from the server so i wasnt sure if it went through.


mhx
Enthusiast

Feb 27, 2002, 1:01 PM

Post #6 of 7 (5278 views)
Re: [Pro_4] Math... [In reply to] Can't Post


In Reply To
Wow... i never thought about it that way. That is pretty cool. PLz forgive my stupidness in math, heh i am only in 10th grade taking Algebra 2 Frown


Then you're probably going to see some of the stuff in the near future (at least, I hope so). I don't know very much about the educational system in the U.S., but here in Germany, you learn about that stuff in the 11th to 13th grade. (Uh, it's been awhile, hard to remember when exactly it was...)


In Reply To
I thought the computer would use approximations for the square rooting but i thought that would take a immense ammount of time(if you want to find a lot of decimals).


It takes some time, but it's still pretty fast. Normally, only a few iterations are required to achieve enormous accuracy.


In Reply To
Oh well the computer will always thinks 10000000000000000 times faster than i ever will Tongue. Where did you learn all that, college courses you took? I am planning to take a few college courses over the summer about programming/computers, what would you suggest?


All of the math stuff I learned mainly at school, but most of it is really easy if you have a closer look. I never understood why so many of my classmates disliked complex numbers. They're in no way more complicated than other numbers, and on the plus side you can do really beautiful things with them. If you've ever seen the Mandelbrot Set, you'll know what I'm talking about.

Please don't ask me for a suggestion on college courses. Rather ask someone who has been to college Wink
I'd take everything that would seem interesting to me. This is usually where I learn the most.


In Reply To
Heh, thanks for moving my post. Took a while to find tho.... heh i looked in Intermediate and it wasnt there. Right after i submitted that i kept on getting 520(or something like that) errors from the server so i wasnt sure if it went through.


Didn't I notify you in a private message? Shocked If not, sorry for that.

-- 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



Pro_4
User

Feb 27, 2002, 1:26 PM

Post #7 of 7 (5275 views)
Re: [mhx] Math... [In reply to] Can't Post

Yeah i just checked my messages and noticed you sent me one.

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives