Post by thread:How do you test Math Routines?

After developing some 64-bit math routines (multiply and divide), I got to wondering how I would properly verify them. I realize the best way (let's say for the divide routine) would be to divide every possible number by every possible divisor and then check to see that the answer is correct. That would take a very long time (understatement of the year :-). Does anybody have suggestions for ways to give math routines a 99.9% test that possibly could be performed in a reasonable period of time? What I am thinking is to examine the algorithm and find the different paths and be sure all are tested. I realize that approach ignores problems that may occur with different combinations of paths. I just don't want my epitaph to read "this man got 14% through a total test of the divide routine". :-) Any suggestions?

> After developing some 64-bit math routines (multiply and divide), I got to > wondering how I would properly verify them. I realize the best way (let's > say for the divide routine) would be to divide every possible number by > every possible divisor and then check to see that the answer is correct. > That would take a very long time (understatement of the year :-). > > Does anybody have suggestions for ways to give math routines a 99.9% test > that possibly could be performed in a reasonable period of time? Well, unless your algorithm is particularly complicated, just feeding it a bunch of random numbers should be good. To avoid correlation effects, I'd recommend reading data 64 bits at a time from a DES-encrypted file; if that isn't possible then try to come up with something that will avoid correla- tion effects between the generated numbers. In addition to testing with "purely" random numbers, you might want to do some testing with numbers that have more "1"'s or more "0"'s to make sure you don't have any problems in any of those cases. To "flog out" those cases, you may generate your 64-bit input values by taking (for each input value) two 64-bit "random" numbers and either AND or OR them together. This will give you val- ues which contain predominantly zeroes or predominantly ones. Note, BTW, that while random testing can heardly be an exhaustive test, it can often find problem cases that a human tester might not consider (e.g. on a Pentium-60, running random divides will hit the bug once every few hours). So if your algorithms do that many random divides (nb: it would alas take a bit longer than a Pentium-60 doing them) without errors it's at least as well tested as Intel's chips. >:*3

>After developing some 64-bit math routines (multiply and divide), I got to >wondering how I would properly verify them. I realize the best way (let's >say for the divide routine) would be to divide every possible number by >every possible divisor and then check to see that the answer is correct. >That would take a very long time (understatement of the year :-). > >Does anybody have suggestions for ways to give math routines a 99.9% test >that possibly could be performed in a reasonable period of time? What I am >thinking is to examine the algorithm and find the different paths and be >sure all are tested. I realize that approach ignores problems that may >occur with different combinations of paths. I just don't want my epitaph to >read "this man got 14% through a total test of the divide routine". :-) >Any suggestions? Hi Lou, What I do is test all the combinations of +ve and -ve with small and large numbers, and make sure I cover the byte boundaries. Then run for a reasonable time with random numbers. A quick and dirty check is as follows... This a trick, which i believe relates back to the abacus days where you multiply 12345679 by any two numbers adding to 9 and you will get a repeating digit. ie: 12345679 * 18 = 222222222 and 12345679 * 27 = 333333333 etc... You can do the reverse for divide ie (222222222)/18 = 12345679 This of course doesn't cover the range you need for 64bit, but maybe you can extend the idea. Ray Gardiner Technical Director DSP Systems spam_OUTrayTakeThisOuTdsp-systems.com private email to:- .....rayKILLspam@spam@netspace.net.au http://www.dsp-systems.com

On Fri, 3 Oct 1997, Ray Gardiner wrote: > A quick and dirty check is as follows... > This a trick, which i believe relates back to the abacus days where > you multiply 12345679 by any two numbers adding to 9 and you will get > a repeating digit. > > ie: 12345679 * 18 = 222222222 and > 12345679 * 27 = 333333333 etc... I just had to try it and... 123456789 * 18 = 2222222202 ... Unless you only want the first 8 Most Significant Digitis in which case you were correct... .scn

12345679 * 18 = 222222222 123456789 * 18 = 2222222202 See the difference (hint: there is no '8' in the first equation) -Randie {Quote hidden}> From iKILLspamCHEETAH.SPOTS.AB.CA Thu Oct 2 08:58:47 1997 > MIME-Version: 1.0 > Date: Thu, 2 Oct 1997 09:57:55 -0600 > From: Shane Nelson <.....iKILLspam.....CHEETAH.SPOTS.AB.CA> > Subject: Re: How do you test Math Routines? > To: EraseMEPICLISTspam_OUTTakeThisOuTMITVMA.MIT.EDU > > On Fri, 3 Oct 1997, Ray Gardiner wrote: > > > A quick and dirty check is as follows... > > This a trick, which i believe relates back to the abacus days where > > you multiply 12345679 by any two numbers adding to 9 and you will get > > a repeating digit. > > > > ie: 12345679 * 18 = 222222222 and > > 12345679 * 27 = 333333333 etc... > > I just had to try it and... > > 123456789 * 18 = 2222222202 > ... > > Unless you only want the first 8 Most Significant Digitis in > which case you were correct... > > > .scn >

>On Fri, 3 Oct 1997, Ray Gardiner wrote: > >> A quick and dirty check is as follows... >> This a trick, which i believe relates back to the abacus days where >> you multiply 12345679 by any two numbers adding to 9 and you will get >> a repeating digit. >> >> ie: 12345679 * 18 = 222222222 and >> 12345679 * 27 = 333333333 etc... > >I just had to try it and... > >123456789 * 18 = 2222222202 >... > >Unless you only want the first 8 Most Significant Digitis in >which case you were correct... > Hi Shane, you got it wrong..it's 12345679....note NOT 123456789 Ray Gardiner Technical Director DSP Systems rayspam_OUTdsp-systems.com private email to:- @spam@rayKILLspamnetspace.net.au http://www.dsp-systems.com

I would send your routine bit patterns that might be likely to trigger errors, ie: 1000000000000000000000 0100000000000000000000 0010000000000000000000 0001000000000000000000 : 1100000000000000000000 0110000000000000000000 : 1110000000000000000000 0111000000000000000000 : You should test operands/results that start with a 0 and a 1 in every (possible) bit position, preferrably also checking all possible permutations for a single bit (0/0 --> 0, 0/0 -> 1, 0/1 -> 0, 0/1 -> 1, etc (depending on the nearby bits and carries, etc, of course.) In addition to 12345679* (9*d) -> ddddddddd, there is also 37037037037... * (3*d) -> dddddddd... (ie more digits.) You can also run some series approximation involving multiplication and division, and see if it comes out pretty close. (ie calculate PI*2^63) BillW

Ray Gardiner wrote: > A quick and dirty check is as follows... > This a trick, which i believe relates back to the abacus days where > you multiply 12345679 by any two numbers adding to 9 and you will get > a repeating digit. > > ie: 12345679 * 18 = 222222222 and > 12345679 * 27 = 333333333 etc... Cool, but perhaps more intuitive if you make a few simplifications. First, the "any two numbers adding to 9" statement implies that the multiplier is divisible by 9. In other words, if you have a two digit decimal number: ab = a*10 + b and (a + b) mod 9 = 0 then (a*10+b) mod 9 = 0 "proof": ab = a*10 + b = a*9 + (a + b) Since a is an integer, a*9 is divisible by 9. And so if ab is divisible by 9 then (a+b) is divisible by 9. This concept is also extendable to multidigit decimal numbers. And this is why Bill Westfield wrote Ray's trick as: 12345679 * d*9 = ddddddddd Next, multiply the 9 and 12345679: 12345679 * d * 9 = 111111111 * d I doubt this will be useful for testing 64bit math routines though. One perhaps obvious way to simplify the testing is to pair inverse operations. I.e. multiplication with division and addition with subtraction. Then you can do things like compute z = x*y and then check that z/x == y etc. This could save the arduous task of having to pre-compute a bunch of stuff. This also tacitly assumes that double errors don't nullify one another. Lou Calkins asked: > I just don't want my epitaph to > read "this man got 14% through a total test of the divide routine". :-) > Any suggestions? RIP? Scott

It is a tough problem to test math routines. A number of the standard test suites have different approaches to the problem. All of them do the basic stuff of making a list of magic known problem values and running them. These are 0, 1 -1 max negative and values specifically designed to exercise multibyte carry logic. Some of the standard test suites (like Plum Hall) have modes where a form of Monte Carlo testing is done. Numbers are generated for a list or are random with a specific distribution or random and constained. Walter Banks http://www.bytecraft.com > > After developing some 64-bit math routines (multiply and divide), I got to > wondering how I would properly verify them. I realize the best way (let's > say for the divide routine) would be to divide every possible number by > every possible divisor and then check to see that the answer is correct. > That would take a very long time (understatement of the year :-). > > Does anybody have suggestions for ways to give math routines a 99.9% test > that possibly could be performed in a reasonable period of time? What I am > thinking is to examine the algorithm and find the different paths and be > sure all are tested. I realize that approach ignores problems that may > occur with different combinations of paths. I just don't want my epitaph to > read "this man got 14% through a total test of the divide routine". :-) > Any suggestions?