Aug 12 15:27 1996  fig10_38.c Page 1


        #include <stdio.h>

typedef double Matrix[ 2 ][ 2 ];

/* START: fig10_38.txt */
        /* Standard matrix multiplication */
        /* Arrays start at 0 */

        void
        MatrixMultiply( Matrix A, Matrix B, Matrix C, int N )
        {
            int i, j, k;

            for( i = 0; i < N; i++ )  /* Initialization */
                for( j = 0; j < N; j++ )
                    C[ i ][ j ] = 0.0;

            for( i = 0; i < N; i++ )
                for( j = 0; j < N; j++ )
                    for( k = 0; k < N; k++ )
                        C[ i ][ j ] += A[ i ][ k ] * B[ k ][ j ];
         }
/* END */

main( )
{
    Matrix A = { { 1, 2 }, { 3, 4 } };
    Matrix C;

    MatrixMultiply( A, A, C, 2 );
    printf( "%6.2f %6.2f\n%6.2f %6.2f\n", C[ 0 ][ 0 ], C[ 0 ][ 1 ],
          C[ 1 ][ 0 ], C[ 1 ][ 1 ] );
    return 0;
}





























Aug 12 15:27 1996  fig10_40.c Page 1


#include <stdio.h>

/* START: fig10_40.txt */
        /* Compute Fibonacci numbers as described in Chapter 1 */

        int
        Fib( int N )
        {
            if( N <= 1 )
                return 1;
            else
                return Fib( N - 1 ) + Fib( N - 2 );
        }
/* END */

/* START: fig10_41.txt */
        int
        Fibonacci( int N )
        {
            int i, Last, NextToLast, Answer;

            if( N <= 1 )
                return 1;

            Last = NextToLast = 1;
            for( i = 2; i <= N; i++ )
            {
                Answer = Last + NextToLast;
                NextToLast = Last;
                Last = Answer;
            }

            return Answer;
        }
/* END */

main( )
{
    printf( "%d\n%d\n", Fib( 7 ), Fibonacci( 7 ) );
    return 0;
}






















Aug 12 15:27 1996  fig10_43.c Page 1


#include <stdio.h>

/* START: fig10_43.txt */
        double
        Eval( int N )
        {
            int i;
            double Sum;

            if( N == 0 )
                return 1.0;
            else
            {
                Sum = 0.0;
                for( i = 0; i < N; i++ )
                    Sum += Eval( i );
                return 2.0 * Sum / N + N;
            }
        }
/* END */

main( )
{
    printf( "%f\n", Eval( 10 ) );
    return 0;
}





































Aug 12 15:27 1996  fig10_45.c Page 1


#include <stdio.h>
#include <stdlib.h>
#include "fatal.h"


/* START: fig10_45.txt */
        double
        Eval( int N )
        {
            int i, j;
            double Sum, Answer;
            double *C;

            C = malloc( sizeof( double ) * ( N + 1 ) );
            if( C == NULL )
                FatalError( "Out of space!!!" );

            C[ 0 ] = 1.0;
            for( i = 1; i <= N; i++ )
            {
                Sum = 0.0;
                for( j = 0; j < i; j++ )
                    Sum += C[ j ];
                C[ i ] = 2.0 * Sum / i + i;
            }

            Answer = C[ N ];
            free( C );

            return Answer;
        }
/* END */

main( )
{
    printf( "%f\n", Eval( 10 ) );
    return 0;
}

























Aug 12 15:27 1996  fig10_46.c Page 1


        #include <stdio.h>
        #include <limits.h>

        typedef long int TwoDimArray[ 5 ][ 5 ];
        #define Infinity INT_MAX

/* START: fig10_46.txt */
        /* Compute optimal ordering of matrix multiplication */
        /* C contains number of columns for each of the N matrices */
        /* C[ 0 ] is the number of rows in matrix 1 */
        /* Minimum number of multiplications is left in M[ 1 ][ N ] */
        /* Actual ordering is computed via */
        /* another procedure using LastChange */
        /* M and LastChange are indexed starting at 1, instead of 0 */
        /* Note: Entries below main diagonals of M and LastChange */
        /* are meaningless and uninitialized */

        void
        OptMatrix( const long C[ ], int N,
                   TwoDimArray M, TwoDimArray LastChange )
        {
            int i, k, Left, Right;
            long ThisM;

            for( Left = 1; Left <= N; Left++ )
                M[ Left ][ Left ] = 0;
            for( k = 1; k < N; k++ )   /* k is Right - Left */
                for( Left = 1; Left <= N - k; Left++ )
                {
                    /* For each position */
                    Right = Left + k;
                    M[ Left ][ Right ] = Infinity;
                    for( i = Left; i < Right; i++ )
                    {
                        ThisM = M[ Left ][ i ] + M[ i + 1 ][ Right ]
                                + C[ Left - 1 ] * C[ i ] * C[ Right ];
                        if( ThisM < M[ Left ][ Right ] ) /* Update min */
                        {
                            M[ Left ][ Right ] = ThisM;
                            LastChange[ Left ][ Right ] = i;
                        }
                    }
                }
        }
/* END */

main( )
{
    long C[ ] = { 50, 10, 40, 30, 5 };
    long M[ 5 ][ 5 ], LastChange[ 5 ][ 5 ];
    int i, j;

    OptMatrix( C, 4, M, LastChange );
    for( i = 1; i <= 4; i++ )
    {
        for( j = 1; j <= 4; j++ )







Aug 12 15:27 1996  fig10_46.c Page 2


            printf( "%14d", M[ i ][ j ] );
        printf( "\n" );
    }
    for( i = 1; i <= 4; i++ )
    {
        for( j = 1; j <= 4; j++ )
            printf( "%14d", LastChange[ i ][ j ] );
        printf( "\n" );
    }
    return 0;
}




















































Aug 12 15:27 1996  fig10_53.c Page 1


        #include <stdio.h>

        #define NotAVertex (-1)
        typedef int TwoDimArray[ 4 ][ 4 ];

/* START: fig10_53.txt */
        /* Compute All-Shortest Paths */
        /* A[ ] contains the adjacency matrix */
        /* with A[ i ][ i ] presumed to be zero */
        /* D[ ] contains the values of the shortest path */
        /* N is the number of vertices */
        /* A negative cycle exists iff */
        /* D[ i ][ i ] is set to a negative value */
        /* Actual path can be computed using Path[ ] */
        /* All arrays are indexed starting at 0 */
        /* NotAVertex is -1 */

        void
        AllPairs( TwoDimArray A, TwoDimArray D,
                        TwoDimArray Path, int N )
        {
            int i, j, k;

            /* Initialize D and Path */
/* 1*/      for( i = 0; i < N; i++ )
/* 2*/          for( j = 0; j < N; j++ )
                {
/* 3*/              D[ i ][ j ] = A[ i ][ j ];
/* 4*/              Path[ i ][ j ] = NotAVertex;
                }

/* 5*/      for( k = 0; k < N; k++ )
                /* Conider each vertex as an intermediate */
/* 6*/          for( i = 0; i < N; i++ )
/* 7*/              for( j = 0; j < N; j++ )
/* 8*/                  if( D[ i ][ k ] + D[ k ][ j ] < D[ i ][ j ] )
                        {
                            /* Update shortest path */
/* 9*/                      D[ i ][ j ] = D[ i ][ k ] + D[ k ][ j ];
/*10*/                      Path[ i ][ j ] = k;
                        }
        }
/* END */

main( )
{
    TwoDimArray A = { { 0, 2, -2, 2 }, { 1000, 0, -3, 1000 },
                      { 4, 1000, 0, 1000 }, { 1000, -2, 3, 0 } };
    TwoDimArray D, Path;
    int i, j;

    AllPairs( A, D, Path, 4 );
    for( i = 0; i < 4; i++ )
    {
        for( j = 0; j < 4; j++ )
            printf( "%6d ", D[ i ][ j ] );







Aug 12 15:27 1996  fig10_53.c Page 2


        printf( "\n" );
    }

    for( i = 0; i < 4; i++ )
    {
        for( j = 0; j < 4; j++ )
            printf( "%6d ", Path[ i ][ j ] );
        printf( "\n" );
    }


    return 0;
}


















































Aug 12 15:27 1996  fig10_55.c Page 1


        /* Bad random number generator */

        #include <stdio.h>

/* START: fig10_55.txt */
        static unsigned long Seed = 1;

        #define A 48271L
        #define M 2147483647L
        #define Q ( M / A )
        #define R ( M % A )

        double
        Random( void )
        {
            long TmpSeed;

            TmpSeed = A * ( Seed % Q ) - R * ( Seed / Q );
            if( TmpSeed >= 0 )
                Seed = TmpSeed;
            else
                Seed = TmpSeed + M;

            return ( double ) Seed / M;
        }

        void
        Initialize( unsigned long InitVal )
        {
            Seed = InitVal;
        }
/* END */

main( )
{
    int i;

    for( i = 0; i < 20; i++ )
        printf( "%6f\n", Random( ) );
    return 0;
}






















Aug 12 15:27 1996  fig10_62.c Page 1


        #include <stdio.h>
        #include <stdlib.h>

        typedef long HugeInt;

        HugeInt
        RandInt( HugeInt Low, HugeInt High )
        {
            return rand( ) % ( High - Low + 1 ) + Low;
        }


/* START: fig10_62.txt */
        /* If Witness does not return 1, N is definitely composite */
        /* Do this by computing ( A ^ i ) mod N and looking for */
        /* non-trivial square roots of 1 along the way */
        /* We are assuming very large numbers, so this is pseudocode */

        HugeInt
        Witness( HugeInt A, HugeInt i, HugeInt N )
        {
            HugeInt X, Y;

            if( i == 0 )
                return 1;

            X = Witness( A, i / 2, N );
            if( X == 0 )  /* If N is recursively composite, stop */
                return 0;

            /* N is not prime if we find a non-trivial root of 1 */
            Y = ( X * X ) % N;
            if( Y == 1 && X != 1 && X != N - 1 )
                return 0;

            if( i % 2 != 0 )
                Y = ( A * Y ) % N;

            return Y;
        }

        /* IsPrime: Test if N >= 3 is prime using one value of A */
        /* Repeat this procedure as many times as needed for */
        /* desired error rate */

        int
        IsPrime( HugeInt N )
        {
            return Witness( RandInt( 2, N - 2 ), N - 1, N ) == 1;
        }
/* END */

main( )
{   int i;

    for( i = 101; i < 200; i += 2 )







Aug 12 15:27 1996  fig10_62.c Page 2


        if( IsPrime( i ) )
            printf( "%d is prime\n", i );

    return 0;
}