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: 103,722

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.****If it ain't broke, fix it until it is.** **A number by itself is useful, but it is far more useful to know how accurate or certain that number is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

@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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.** **A number by itself is useful, but it is far more useful to know how accurate or certain that number is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.** **A number by itself is useful, but it is far more useful to know how accurate or certain that number is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

so?

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

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

hi bobbym

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

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

how?

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

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

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

oooooh,ok.nice to know that.

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

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

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

ok.

so for the second one:3?

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

ok.next?

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,015

which ones?

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 103,722

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.****If it ain't broke, fix it until it is.**

Offline