Perl Guru Forums: General Discussions: General Questions: Math...

CGI/Perl Guide | Learning Center | Forums | Advertise | Login

Site Search: in


	MAIN INDEX	SEARCH POSTS	WHO'S ONLINE	LOG IN

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

Pro_4
User

Feb 25, 2002, 3:33 PM

Post #1 of 7 (4768 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 (4752 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 (4746 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 (4741 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...

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 (4729 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 (4728 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 (4725 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)

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