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

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

Pro_4
User

Feb 25, 2002, 3:33 PM

Post #1 of 7 (11974 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

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 (11958 views)
 Re: [Pro_4] Math... [In reply to] Can't Post
Hello Pro_4,

Happy to see you around !!!

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 (11952 views)
 Re: [Pro_4] Math... [In reply to] Can't Post
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:

 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.

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:
 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])`
 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.

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

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

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 (11947 views)
 Re: [mhx] Math... [In reply to] Can't Post
No, it doesn't sum one number up several times. That would be really too slow.

Oh boy...

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

(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 (11935 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 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 . 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 (11934 views)
 Re: [Pro_4] 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

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

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.

Oh well the computer will always thinks 10000000000000000 times faster than i ever will . 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
I'd take everything that would seem interesting to me. This is usually where I learn the most.

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? 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 (11931 views)
 Re: [mhx] Math... [In reply to] Can't Post
Yeah i just checked my messages and noticed you sent me one.

 Announcements     PerlGuru Announcements Perl Programming Help     Frequently Asked Questions     Beginner     Intermediate     Advanced     Regular Expressions     mod_perl     DBI     Win32 Programming Help Fun With Perl     Perl Quizzes - Learn Perl the Fun Way     Perl Golf     Perl Poetry Need a Custom or Prewritten Perl Program?     I need a program that...     I Need a Programmer for Freelance Work     Throw Down The Gauntlet General Discussions     General Questions     Feedback     Tutorial/Article Suggestions for The Learning Cent     Internet Security Other Programming Languages     Javascript     PHP

 Search this forum this category all forums for All words Any words Whole Phrase (options) Powered by Gossamer Forum v.1.2.0