The present invention relates to the determination of the equivalence of two algebraic functions, such as those used in computer programs. The present invention includes a method and apparatus for carrying out such a determination and also to a computer program product including a computer readable medium having recorded thereon a computer program for performing such determination.
The present invention has, for its object, a technique which is specifically relevant to the determination of whether or not two algebraic expressions share a common template or function definition. Expressed mathematically, the objective is applicable as follows.
Given an algebraic expression f(x1, x2, . . . , xn) of n-variables denoted by the symbol set {x1, x2, . . . , xn} and another expression g(y1, y2, . . . , yn)of n-variables denoted by the symbol set {y1, y2, . . . , yn} determine if there exists a permutation "sgr" of degree n on the set {y1, y2, . . . , yn} such that
g(y1, y2, . . . , yn)xe2x89xa1f("sgr"(y1), "sgr"(y2), . . . , "sgr"(yn)), n greater than 0 
where x1="sgr"(y1), x2="sgr"(y2), . . . , xn="sgr"(yn). 
An identity would imply that f( ) and g( ) share a common template or function definition as mentioned earlier. The term xe2x80x9cpermutationxe2x80x9d is defined as follows.
Let xcexa9 be a set consisting of n distinct objects, which we may denote either by digits or by letters, say
xcexa9={1,2, . . . , n}. 
Then a permutation on xcexa9 implies the mapping of objects 1 to n to the same objects but in a different orderxe2x80x94this is called mapping of xcexa9 onto itself. A permutation "sgr" of degree n is an operation on the set xcexa9 which maps the digit i to the digit "sgr"(i) in such a way that "sgr"(i)xe2x89xa0"sgr"(j) when ixe2x89xa0j. We write   σ  =      (                            1                          2                          …                          n                                                  σ            ⁡                          (              1              )                                                            σ            ⁡                          (              2              )                                                …                                      σ            ⁡                          (              n              )                                            )  
where the numbers "sgr"(1), "sgr"(2), . . . , "sgr"(n) are an arrangement of the numbers 1, 2, . . . , n.
Note that since there are n! distinct arrangements possible of n objects, there are n! distinct permutations in the form given above. For example, the permutation of degree 5 given by   σ  =      (                            1                          2                          3                          4                          5                                      3                          5                          4                          1                          2                      )  
in which "sgr"(1)=3, "sgr"(2)=5 . . . , "sgr"(5)=2, may equally well be written in the form   σ  =      (                            4                          2                          3                          1                          5                                      1                          5                          4                          3                          2                      )  
The invention comprises a method, apparatus and program product for determining the equivalence of two algebraic functions. In the invention, an algorithm is involved which comprises determining the symbol sets of the two functions; forming a matrix having a row for each symbol of one function and a column for each symbol of the other function; subjecting the functions to predetermined tests and incrementing the elements in the matrix in accordance with the results of said tests; and testing the matrix against predetermined rules for the symmetry of the matrix.
The algorithm may include comparing said symbol sets to determine whether they contain the same numbers of symbols.
The invention further provides a method, program and apparatus for determining the equivalence of two algebraic functions f( ) and g( ) having respective symbol sets {x1, x2, . . . , xn} and {y1, y2, . . . , yn} having equal numbers of symbols, the method comprising the steps of forming a matrix M with n rows and n columns and made up of elements Mij corresponding to respective pairs of said symbols xi and yj where Mij is calculated by initialising the values of Mij to zero; putting xi=0 in f( ) and yj=0 in g( ) and replacing each other variable in f( ) and g( ) with a predetermined string character, then arranging the terms of f( ) and g( ) in ASCII order and comparing them and, if they match, incrementing the current value of Mij; putting xi=1 in f( ) and yj=1 in g( ) and replacing each other variable in f( ) and g( ) with a predetermined string character, then arranging the terms of f( ) and g( ) in ASCII order and comparing them and, if they match, incrementing the current value of Mij; putting xi=xe2x88x921 in f( ) and yj=xe2x88x921 in g( ) and replacing each other variable in f( ) and g( ) with a predetermined string character, then arranging the terms of f( ) and g( ) in ASCII order and comparing them and, if they match, incrementing the current value of Mij; ensuring that every element Mij is either a zero or a three and that each row of the matrix M contains at least one three; for each entry Mij which has the value three, exchanging the contents of columns i and j one with another; and inspecting the matrix M with the exchanged columns to determine if it is symmetrical.
The method and apparatus may further comprise analysing computer code containing first and second algebraic functions f(x1, x2, . . . , xn) and g(y1, y2, . . . , yn), the method being operable for analysing a relationship between said first and second functions and comprising the steps of:
(a) in each term in each function, replacing each variable name in that term with a predetermined symbol to form two character strings F( ) and G( ) each composed of sub-strings corresponding to respective terms of the respective function;
(b) arranging the sub-strings of each string in a like predetermined order; and
(c) comparing the strings one with another to determine equivalence of the two functions.
Preferably, the method further includes taking each variable xi of the first function f(x1, x2, . . . , xn) and running through variables yj of the second function g(y1, y2, . . . , yn) one-by-one and carrying out the steps of:
(a) removing all the terms in the first function which contain xi and all the terms in the second function which contain yj and, in each remaining term of each function, replacing each variable with a predetermined symbol and rearranging said terms in a predetermined order to form two character strings f0( ) and g0( );
(b) replacing each variable xi and yj by the value 1, replacing each remaining variable with a single predetermined symbol, and rearranging the terms of the functions in a predetermined order as two character strings f1( ) and g1( );
(c) replacing each variable xi and yj by the value xe2x88x921, replacing each remaining variable with a single predetermined symbol, and rearranging the terms of the functions in a predetermined order as two character strings fxe2x88x921( ) and gxe2x88x921( );
(d) carrying out respective character string matching operations to determine if f0( ) is identical to g0( ), if f1( ) is identical to g1( ), and if fxe2x88x921( ) is identical to gxe2x88x921( ).
USPTO Backgrounds
USPTO Backgrounds