Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

How do we test a solution to the 2-3-5 problem?

January 03, 2009

In looking through the voluminous comments on my previous notes on this problem, one theme emerges that I think it is important to deal with before looking at solutions in more detail: How can we be sure that we have actually solved the problem? In other words, suppose we have a program that purports to solve the problem. How can we be sure that it actually does so? The obvious way to start is to solve the problem in the simplest way we can think of, and verify that the simple solution’s output matches the one we are trying to test. An earlier post suggests such a solution:

    for (int n = 1; n < limit; ++n) {
        int i = n;
        while ((i % 2) == 0) i /= 2;
        while ((i % 3) == 0) i /= 3;
        while ((i % 5) == 0) i /= 5;
        if (i == 1)
            cout << n << “\n”; 
    }

This piece of code prints all the element of the 2-3-5 sequence that are less than the variable "limit."  Testing another program that purports to compute the elements of the sequence in order should surely begin by verifying that the program being tested produces the same output as this test program.

Of course, we should decide whether we are willing to wait for the test program to run.  In the case of this particular program, we should be able to see that checking whether a particular value n is in the sequence requires no more than one iteration for each time 2, 3, or 5 is a factor of n, which in turn is O(log n) operations.  Therefore, producing the values of the sequence up to "limit" should take O(limit x log(n)) operations, which is likely to be acceptable in practice.

After all, if our goal is to produce a huge number of elements of the sequence, we don't have to test them all.  If the program correctly produces every element of the sequence less than a million, one can be reasonably confident that it is working correctly--or at least, if the nature of the algorithm being used is such that one cannot be confident, then we had better prove that the algorithm is correct.

So we have a reasonable way of doing at least a cursory test of a purported algorithm.  The next problem is seeing whether we can do better than O(limit x log(n)).  In particular, it would be nice to come up with an algorithm with a run time that depends on the number of elements produced, rather than depending on the elements' value.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video