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

You are not logged in.

- Topics: Active | Unanswered

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

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

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

@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

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

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

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

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

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

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

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

i want more!!!

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

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

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

Offline

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

so?

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

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

Offline

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

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

Offline

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

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.

Offline

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

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

Offline

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

how?

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

Offline

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

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

Offline

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

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

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

Offline

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

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

Offline

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

oooooh,ok.nice to know that.

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

Offline

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

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

Offline

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

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

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

Offline

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

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

Offline

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

ok.

so for the second one:3?

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

Offline

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

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

Offline

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

ok.next?

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

Offline

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

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

Offline

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

which ones?

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

Offline

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

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

Offline