Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

Login

Username

Password

Not registered yet?

#201 2012-02-13 08:18:21

bobbym
Administrator

Offline

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

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.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#202 2012-02-13 08:22:00

anonimnystefy
Real Member

Offline

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

@bobbym

well not just Big Oh.anything from AA.


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#203 2012-02-13 08:26:10

bobbym
Administrator

Offline

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

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.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#204 2012-02-13 08:58:43

anonimnystefy
Real Member

Offline

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

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

anyway,let's do some numerical analysis then.


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#205 2012-02-13 09:04:19

bobbym
Administrator

Offline

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

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.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#206 2012-02-13 09:05:58

anonimnystefy
Real Member

Offline

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

i want more!!! big_smile


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#207 2012-02-13 09:09:55

bobbym
Administrator

Offline

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

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.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#208 2012-02-13 09:20:34

anonimnystefy
Real Member

Offline

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

so?

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


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#209 2012-02-13 09:28:06

bobbym
Administrator

Offline

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

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?


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#210 2012-02-13 09:30:20

anonimnystefy
Real Member

Offline

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

hi bobbym

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


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#211 2012-02-13 09:31:14

bobbym
Administrator

Offline

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

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


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#212 2012-02-13 09:51:35

anonimnystefy
Real Member

Offline

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

how?


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#213 2012-02-13 09:56:30

bobbym
Administrator

Offline

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

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


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#214 2012-02-13 09:59:39

anonimnystefy
Real Member

Offline

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

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


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#215 2012-02-13 10:00:58

bobbym
Administrator

Offline

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

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


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#216 2012-02-13 10:02:43

anonimnystefy
Real Member

Offline

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

oooooh,ok.nice to know that.


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#217 2012-02-13 10:05:14

bobbym
Administrator

Offline

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

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.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#218 2012-02-13 10:07:16

anonimnystefy
Real Member

Offline

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

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


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#219 2012-02-13 10:08:43

bobbym
Administrator

Offline

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

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.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#220 2012-02-13 10:18:01

anonimnystefy
Real Member

Offline

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

ok.

so for the second one:3?


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#221 2012-02-13 10:19:39

bobbym
Administrator

Offline

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

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.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#222 2012-02-13 10:20:14

anonimnystefy
Real Member

Offline

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

ok.next?


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#223 2012-02-13 10:24:17

bobbym
Administrator

Offline

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

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


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

#224 2012-02-13 10:25:52

anonimnystefy
Real Member

Offline

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

which ones?


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#225 2012-02-13 10:27:53

bobbym
Administrator

Offline

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

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


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Board footer

Powered by FluxBB