Same sample, but from Win live writer

– Visual Studio’s syntax coloring is gone, but the tabbing seems to survive…

 

// These are ‘public’
int factorial_iterative(__in unsigned __int32 input, __out unsigned __int32 &output);
int factorial_recursive(__in unsigned int input, __out unsigned int &output);
int factorial_lookup_table(__in unsigned int input, __out unsigned int &output);

// There are ‘private’, i.e. not for general use.
int factorial_recursive_internal(__in unsigned int input, __out unsigned int &output);
int factorial_unit_test();

 

// Samples library.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "factorial.h"

// As we don’t have ATL to re-use their error code (no ATL in the standard V C++ 2k5 express),
// we have to define our own error code.
// As a standard from main(…) 0 is success code
// 1 is arithmetic overflow
// 2 is unspecified error. Great for test code and request dev to take a look, but terrible in release code.

// When does int overflows?
// An unsigned integer with n bits can encode up to the number (2^n) -1.
// Assuming 32 bits per unsigned int32
// Google tells us logarithm base 2 of 12! with 28 bits consumption fits, but 13! with slightly over 32 won’t.

int factorial_iterative(__in unsigned __int32 input, __out unsigned __int32 &output)
{
    int iResult = 0;
    output = 1; // for better predictability output is initialized even if we stop on overflow
    if (input >= 13)
    {
        iResult = 1;
    }
    else
    {
        // Note that input of zero will skip this loop
        // and cause the function to properly keep output at 1.
        for (; input > 1; input–)
        {
            output *= input;
        }
    }
    return iResult;
}

// Caller should take in consideration this recursion will eat some stack – up to 12 recursion.
// The quick arithmetic overflow limits this drastically.
int factorial_recursive(__in unsigned int input, __out unsigned int &output)
{
    int iResult = 0;
    if (input >= 13)
    {
        output = 1;
        iResult = 1;
    }
    else
    {
        iResult = factorial_recursive_internal(input, output);
    }
    return iResult;
}

// With preFAST we could add a range definition on input to limit it to 0..12
int factorial_recursive_internal(__in unsigned int input, __out unsigned int &output)
{
    int iResult = 0;
    if (input > 1)
    {
        iResult = factorial_recursive_internal(input – 1, output);
        output = output * input;
    }
    else
    {
        output = 1;
    }
    return iResult;
}

// Now as 12 is so few values… Why not compute them in advance?
int factorial_lookup_table(__in unsigned int input, __out unsigned int &output)
{
    int iResult = 0;
    if (input >= 13)
    {
        output = 1;
        iResult = 1;
    }
    else
    {
        unsigned int lookup_table[13] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600};
        output = lookup_table[input];
    }
    return iResult;
}

int factorial_unit_test()
{
    // A the set of input values accepted by our factorial functions is limited,
    // we can afford an almost exhaustive testing.
    int iResult = 0;
    for (unsigned __int32 i = 0; iResult == 0 && i < 1000; i++)
    {
        int iResult_iterative, iResult_recursive, iResult_lookup = 0;
        unsigned __int32 output_iterative, output_recursive, output_lookup = 0;
        iResult_iterative = factorial_iterative(i, output_iterative);
        iResult_recursive = factorial_recursive(i, output_recursive);
        iResult_lookup = factorial_lookup_table(i, output_lookup);
        if ((iResult_iterative != iResult_recursive) || (iResult_recursive != iResult_lookup))
        {
            printf("Return value mistmatch for i=%x\n", i);
            iResult = 2;
        }
        if ((output_iterative != output_recursive) || (output_recursive != output_lookup))
        {
            printf("Output value mistmatch for i=%x\n", i);
            iResult = 2;
        }
    }

    if (iResult == 0)
    {
        printf("All unit tests for factorial completed with success.\n");
    }

    return iResult;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int iResult = 0;
    // Eat the return value, we’ll look at the text output.
    factorial_unit_test();
    return iResult;
}

This entry was posted in Non classé. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s