Algorithms proof

This is a discussion on Algorithms proof within the C Programming forums, part of the General Programming Boards category; I built an order of arithmetic operations algorithm and i want to ask something before I am writing this algorithm ...

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    22

    Question 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............
    thanking you in advance

  2. #2
    Sweet
    Join Date
    Aug 2002
    Location
    Tucson, Arizona
    Posts
    1,812
    Ummm Test It?
    Woop?

  3. #3
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Proform a mathimatical proof.

  4. #4
    Registered User
    Join Date
    Nov 2005
    Posts
    22
    how can i perform a mathematical proof?

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  6. #6
    Registered User
    Join Date
    Nov 2004
    Location
    India
    Posts
    515
    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.
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  7. #7
    Registered User
    Join Date
    Nov 2005
    Posts
    22
    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?
    please help me understand.
    thanking you in advance.

  8. #8
    Registered User
    Join Date
    Nov 2004
    Location
    India
    Posts
    515
    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.
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  9. #9
    Registered User
    Join Date
    Nov 2005
    Posts
    22
    Ok i will explain here with more details.
    im doing a program that receive an math exercise to linked list(every sign in NODE).
    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.

  10. #10
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  11. #11
    Registered User
    Join Date
    Nov 2005
    Posts
    22
    anyone can answer to my question? please

  12. #12
    Registered User
    Join Date
    Nov 2004
    Location
    India
    Posts
    515
    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.
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  13. #13
    Registered User
    Join Date
    Nov 2005
    Posts
    22
    but there is infinity cases.

  14. #14
    Registered User
    Join Date
    Nov 2004
    Location
    India
    Posts
    515
    just give us some examples of the sort of "infinite " cases that you are talking about..
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  15. #15
    Registered User
    Join Date
    Nov 2005
    Posts
    22
    2*(7+5*(4-5)+(11-1))
    2+2*(11-3)
    10-45*(7+8-(8+0-(9-8+(11-5))))
    .........

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 02:33 PM
  2. Understanding formulas, shapes, algorithms etc
    By hardi in forum A Brief History of Cprogramming.com
    Replies: 26
    Last Post: 04-16-2007, 02:23 PM
  3. God
    By datainjector in forum A Brief History of Cprogramming.com
    Replies: 746
    Last Post: 12-22-2002, 12:01 PM
  4. relative strength of encryption algorithms (blowfish, des, rinjdael...)
    By duck-billed platypus in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 12-30-2001, 04:20 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21