Searching \ for 'How do you test Math Routines?' in subject line. ()
Help us get a faster server
FAQ page: www.piclist.com/techref/method/math.htm?key=math
Search entire site for: 'How do you test Math Routines?'.

Truncated match.
'How do you test Math Routines?'
1997\10\02@083618 by

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   raydsp-systems.com
private email to:- raynetspace.net.au  http://www.dsp-systems.com

1997\10\02@115749 by
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}

>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   raydsp-systems.com
private email to:- raynetspace.net.au  http://www.dsp-systems.com
On Fri, 3 Oct 1997, Ray Gardiner wrote:

>
> Hi Shane, you got it wrong..it's 12345679....note NOT 123456789
>

So it's true!  You (meaning me) really do see what you excpect to
see, as opposed to what is actually in front of you.

.scn
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.

>                                    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?

More... (looser matching)
- Last day of these posts
- In 1997 , 1998 only
- Today
- New search...