Oh,Oh,Oh,merry analysis!!!

bobbym · 2012-02-12 09:18:21

Hi;

In post #135 and post #137 you asked for harder stuff and some numerical analysis. I presumed because you understand Big O and I am out of those type questions.

To cover asymptotic analysis requires some knowledge of the other fields. Big O, I have none left that could be difficult for you.

anonimnystefy · 2012-02-12 09:22:00

@bobbym

well not just Big Oh.anything from AA.

bobbym · 2012-02-12 09:26:10

That will be very difficult without background material. That means some numerical analysis. The Horner problem is designed to get your feet wet so to speak.

Asymptotic analysis as I understand it is for getting asymptotic forms for various series, integrals and functions. To me it is just a an offshoot of NA. But you do not want that so you have set me an impossible problem of finding problems for you.

anonimnystefy · 2012-02-12 09:58:43

well if the water is cold,wouldn't i after that get cold feet xD

anyway,let's do some numerical analysis then.

bobbym · 2012-02-12 10:04:19

You have been doing some.

Numerical analysis deals with algorithms and numbers. It shows what can and can not be done by computer. To get and understand asymptotic analysis you first have to understand why and when something is feasible or not feasible to compute. That does not always mean using a computer.

anonimnystefy · 2012-02-12 10:05:58

i want more!!!

bobbym · 2012-02-12 10:09:55

For instance the problem of factoring a 200 digit number into prime factors is feasible. It cabn be done in a reasonable amount of time. The problem of factoring a 1000 digit number is currently infeasible. Even though there is a simple algorithm to do this.

anonimnystefy · 2012-02-12 10:20:34

so?

i want problems in NA,and want them now!!!

bobbym · 2012-02-12 10:28:06

They are coming. One simple way to know whether one algorithm is better than another is by counting the number of operations it requires.

Now back to the original question:

Which algorithm is superior for evaluating f(3) and why?

anonimnystefy · 2012-02-12 10:30:20

hi bobbym

the first one does 9 operations,and the second one does 6 operations,so the second one is superior.

bobbym · 2012-02-12 10:31:14

That is close to the correct answer. Can you trim both algorithms down?

anonimnystefy · 2012-02-12 10:51:35

how?

bobbym · 2012-02-12 10:56:30

I will show you for the standard algorithm on the left.

1) We compute x*x and store it. 1 multiplication

2) We times that stored valued by x and store it. 1 multiplication.

So far 2 multiplications.

3) Times the x^3 by 4 that is 1 multiplication.

4) Times the x^2 by 5 that is 1 multiplication.

5) Times the x by 6 that is 1 multiplication.

Total 5 multiplications for this algorithm to get f(x).

anonimnystefy · 2012-02-12 10:59:39

oh,so only multiplication?i thought there should be addition too.

bobbym · 2012-02-12 11:00:58

Multiplication is O(n^2) while addition is O(n). O(n^2 + n) = n^2

anonimnystefy · 2012-02-12 11:02:43

oooooh,ok.nice to know that.

bobbym · 2012-02-12 11:05:14

When you do 3 x 3 digit multiplication it takes 9 individual multiplications using the school method. When you double the size of the numbers 6 x 6 takes 36 multiplications. The amount of multiplications went up by 2^2 and not by 2. Multiplication is an n^2 operation.

anonimnystefy · 2012-02-12 11:07:16

@bobbym -.-' don't you think i knew that?

bobbym · 2012-02-12 11:08:43

Hmmm, yes. But applying mathematics and knowing it are not the same things. You did include additions when you should not have.

Which part? In posts 214 and 216 you say that you did not know that.

I should not have to guess as to what you know and do not. I do not read minds. If you already knew that then consider it to be review and you can never get too much of that.

anonimnystefy · 2012-02-12 11:18:01

ok.

so for the second one:3?

bobbym · 2012-02-12 11:19:39

Correct! Now you see that the algorithm on the left is almost twice as slow. Not a small improvement. Also, it is less numerically stable.

anonimnystefy · 2012-02-12 11:20:14

ok.next?

bobbym · 2012-02-12 11:24:17

Do you know there are much better ways to multiply large numbers than the ones we were taught in school?

anonimnystefy · 2012-02-12 11:25:52

which ones?

bobbym · 2012-02-12 11:27:53

There are two well known ones. One was invented by Katerina Karatsuba and the other is call FFT. They are not O(n) but they are less than O(n^2).

Math Is Fun Forum

#201 2012-02-12 09:18:21

Re: Oh,Oh,Oh,merry analysis!!!

#202 2012-02-12 09:22:00

Re: Oh,Oh,Oh,merry analysis!!!

#203 2012-02-12 09:26:10

Re: Oh,Oh,Oh,merry analysis!!!

#204 2012-02-12 09:58:43

Re: Oh,Oh,Oh,merry analysis!!!

#205 2012-02-12 10:04:19

Re: Oh,Oh,Oh,merry analysis!!!

#206 2012-02-12 10:05:58

Re: Oh,Oh,Oh,merry analysis!!!

#207 2012-02-12 10:09:55

Re: Oh,Oh,Oh,merry analysis!!!

#208 2012-02-12 10:20:34

Re: Oh,Oh,Oh,merry analysis!!!

#209 2012-02-12 10:28:06

Re: Oh,Oh,Oh,merry analysis!!!

#210 2012-02-12 10:30:20

Re: Oh,Oh,Oh,merry analysis!!!

#211 2012-02-12 10:31:14

Re: Oh,Oh,Oh,merry analysis!!!

#212 2012-02-12 10:51:35

Re: Oh,Oh,Oh,merry analysis!!!

#213 2012-02-12 10:56:30

Re: Oh,Oh,Oh,merry analysis!!!

#214 2012-02-12 10:59:39

Re: Oh,Oh,Oh,merry analysis!!!

#215 2012-02-12 11:00:58

Re: Oh,Oh,Oh,merry analysis!!!

#216 2012-02-12 11:02:43

Re: Oh,Oh,Oh,merry analysis!!!

#217 2012-02-12 11:05:14

Re: Oh,Oh,Oh,merry analysis!!!

#218 2012-02-12 11:07:16

Re: Oh,Oh,Oh,merry analysis!!!

#219 2012-02-12 11:08:43

Re: Oh,Oh,Oh,merry analysis!!!

#220 2012-02-12 11:18:01

Re: Oh,Oh,Oh,merry analysis!!!

#221 2012-02-12 11:19:39

Re: Oh,Oh,Oh,merry analysis!!!

#222 2012-02-12 11:20:14

Re: Oh,Oh,Oh,merry analysis!!!

#223 2012-02-12 11:24:17

Re: Oh,Oh,Oh,merry analysis!!!

#224 2012-02-12 11:25:52

Re: Oh,Oh,Oh,merry analysis!!!

#225 2012-02-12 11:27:53

Re: Oh,Oh,Oh,merry analysis!!!

Board footer