# Algorithms proof

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 11-14-2005
snaidis
Algorithms proof
I built an order of arithmetic operations algorithm and i want to ask something before I am writing this algorithm in the compiler:
How can i be sure that my algorithm works in every case,
in a trivial cases and also in very complicated cases like brackets in bracket in brackets+brackets............
• 11-15-2005
prog-bman
Ummm Test It?
• 11-15-2005
Thantos
Proform a mathimatical proof.
• 11-15-2005
snaidis
how can i perform a mathematical proof?
• 11-15-2005
Prelude
>Proform a mathimatical proof.
First let me say that I don't think much of mathematical proofs. The only thing you prove is that you can bend reality to your will with math. I could use mathematics to correctly prove that the sky is always a nice shade of lilac, but that doesn't make it true.

>How can i be sure that my algorithm works in every case
I was always partial to logical induction. You make sure that the simple cases work, then assume that the more complex cases work through that. It's very effective when the correctness of complex cases relies on the correctness of simple cases. For example, if you know that a[0]+a[1] is correct, and a[0]+a[1]+a[2] is correct, you can assume that a[0]+a[1]...+a[n] is correct, for any value of n.

Arithmetic operations have very well defined semantics, so you can easily use induction to prove that they work in all cases.
• 11-15-2005
PING
Quote:

how can i perform a mathematical proof?
Consider a general value 'n' and using mathematical formulae, check if u get the desired result for the general case.

suppose, you are writing a factorial program, and consider that you have written this piece of code

for(var,fact=1;var>0;var-=1)
fact=fact*var;

now, just take a certain value say 'n' and punch it into the code..the result that you are going to get thru the code is n*(n-1)*(n-2)...till ...2*1. Now this is the desired output that you are supposed to get for a manual calculation of the factorial of any number.. voila, your algorithm works perfectly fine.
• 11-15-2005
snaidis
but in my algorithm could be many cases:
2*(3+4*(3+5-(11+0)+(0+0)))
or
2*7-(11+4)
and a lot of more so how can i assume facility if i have so many cases?
• 11-15-2005
PING
i really dont understand what you mean to say..the evaluation of brackets is common for all compilers following the standard..so i really dont think you will have any problems there. Get a copy of the standard or search on google to know more how the brackets are evaluated. The end of the whole bracket fiasco will give one single value with which you can verify your algorithm.
• 11-15-2005
snaidis
Ok i will explain here with more details.
The program will solve this math Ex by using order of arithmetic operations.
Now, I wrote an algorithm that doing this but how can i be sure that my algorithm solves the Ex in every case.
• 11-15-2005
IfYouSaySo
Quote:

First let me say that I don't think much of mathematical proofs. The only thing you prove is that you can bend reality to your will with math. I could use mathematics to correctly prove that the sky is always a nice shade of lilac, but that doesn't make it true.
I just wanted to say that I know of a Discrete Math professor who would disagree strongly with this. He would form his argument as a proof by induction.
• 11-15-2005
snaidis
• 11-15-2005
PING
test your code with some cases..if it stands true for case 1 and case 2, and for case 2 n case 1 combined, it is going to be true for all complicated cases which can be reduced to combinations of case1 and case2.
• 11-15-2005
snaidis
but there is infinity cases.
• 11-15-2005
PING
just give us some examples of the sort of "infinite " cases that you are talking about..
• 11-15-2005
snaidis
2*(7+5*(4-5)+(11-1))
2+2*(11-3)
10-45*(7+8-(8+0-(9-8+(11-5))))
.........
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last