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

You are not logged in.

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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

@bobbym

well not just Big Oh.anything from AA.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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

i want more!!! big_smile


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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

so?

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


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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

how?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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

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


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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

oooooh,ok.nice to know that.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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

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


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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

ok.

so for the second one:3?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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

ok.next?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,657

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

which ones?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,485

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 agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

Board footer

Powered by FluxBB