_USING THE MULTIPLE-PRECISION LIBRARY_
by John Rogers

Listing One

/* Copyright (c) 1994 by John Rogers. All rights reserved.
 * FUNCTION - MPHelp.h declares routines which are "helpers" to users of the 
 * multiple precision (MP) library. The routines declared here are:
 * miseven(number), misodd(number), misprime(number), miszero(number)
 * All of these functions return "boolean" values in "int" types, where 0 
 * means false and 1 means true.
 * AUTHOR - JR (John Rogers), CompuServe: 72634,2402
 *      Internet: 72634.2402@CompuServe.com
 */

#ifndef MPHELP_H
#define MPHELP_H

#include <mp.h>         /* MINT or mint typedef. */

/* Define NEED_MINT in makefile if local mp.h does not provide the typedef. 
 * In that case, we define the MINT type here.
 */
#ifdef NEED_MINT
typedef mint MINT;
#endif

/* ROUTINES, in alphabetical order: */

int  /* Note: return values are 0=false and 1=true. */
miseven(
   const MINT  * Number);
int  /* Note: return values are 0=false and 1=true. */
misodd(
   const MINT  * Number);
int  /* Note: return values are 0=false and 1=true. */
misprime(
   const MINT  * Number);
int  /* Note: return values are 0=false and 1=true. */
miszero(
   const MINT  * Number);
#endif /* MPHELP_H */


Listing Two

/* Copyright (c) 1994 by John Rogers. All rights reserved.
 * FUNCTION - MPHelp.c contains the MP "helpers": miseven(number), 
 * misodd(number), misprime(number), miszero(number). All of these functions 
 * return "boolean" values in "int" types, where 0 is false and 1 means true.
 * AUTHOR - JR (John Rogers), CompuServe: 72634,2402
 *      Internet: 72634.2402@CompuServe.com
 */

#include <assert.h>     /* assert(). */
#include <mp.h>         /* MINT typedef. */
#include "mphelp.h"     /* My prototypes. */

/* ROUTINES, in alphabetical order: */
int  /* Note: return values are 0=false and 1=true. */
miseven(
   const MINT  * Number)
{
   MINT   * Quotient;
   short  Remainder;
   int    ReturnValue;   /* 0=false, 1=true. */

   /* Initialize MINT variable (any value will do), so MP routines 
    * allocate space. */
   Quotient = itom(7);  /* Dummy value. */

   /* Divide Number by two and look at remainder. */
   sdiv(
         Number,        /* dividend - input */
         2,             /* divisor - input */
         Quotient,      /* quotient - output */
         & Remainder);  /* remainder - output */
   /* We'll return "true" if-and-only-if Remainder is zero. */
   ReturnValue = ( Remainder == 0 );

   mfree( Quotient );  /* Free space used by temp. */

   return (ReturnValue);

} /* miseven */

int  /* Note: return values are 0=false and 1=true. */
misodd(
   const MINT  * Number)
{
   return ( !miseven( Number ) );
}
int  /* Note: return values are 0=false and 1=true. */
misprime(
   const MINT  * Candidate)
{
   int   CompareResult;
   MINT  * Constant_Two = itom(2);
   MINT  * Divisor = NULL;
   MINT  * MaxDivisor = NULL;
   MINT  * Quotient = NULL;
   MINT  * Remainder = NULL;
   int   ReturnValue;   /* 0=false, 1=true. */

   /* Check for easy cases:
    *    -infinity <= x <= 1    not prime
    *    x = 2                  prime
    *    x > 2, x is even       not prime
    */
   CompareResult = mcmp(Candidate, Constant_Two);
   if (CompareResult < 0) {
      /* Anything less than 2 isn't prime. */
         ReturnValue = 0;  /* false */
         goto Cleanup;
   } else if (CompareResult == 0) {
      /* Exactly two, yes that is a prime. */
      ReturnValue = 1;  /* true */
      goto Cleanup;
   }
   assert( CompareResult > 0 );
   if (miseven(Candidate)) {
      ReturnValue = 0;  /* false */
      goto Cleanup;
   }
   /* Well, all that's left is the hard stuff. Try all of the odd divisors
    * from 3 up to the square root of the candidate. */
   assert( misodd( Candidate ) );

   Divisor = itom( 3 );
   MaxDivisor = itom( 1 );
   Quotient = itom( 1 );   /* don't care value */
   Remainder = itom( 1 );   /* don't care value */

   msqrt(
         Candidate,    /* input value */
         MaxDivisor,   /* square root */
         Remainder );  /* remainder */
   for ( ; ; ) {  /* loop forever */
      /* Try dividing this one. */
      mdiv(
            Candidate,  /* dividend */
            Divisor,
            Quotient,
            Remainder);
      /* Does this divisor divide evenly? */
      if ( miszero( Remainder ) ) {
         /* If we were dividing by Candidate, then Candidate must be prime. */
         if (mcmp( Candidate, Divisor ) == 0) {
            ReturnValue = 1;  /* true */
            goto Cleanup;
         } else {
            /* Otherwise, if this divisor divides evenly, it factors the 
             * candidate, which therefore cannot be prime.  */
             ReturnValue = 0;  /* false */
            goto Cleanup;
         }
      }
      /* Have we gone as far as we can? If so, this must be prime! */
      if (mcmp( Divisor, MaxDivisor ) >= 0) {
         ReturnValue = 1;  /* true */
         goto Cleanup;
      }
      /* Bump to next odd divisor. We shouldn't use MP routines to
       * update Divisor in place, so use a temporary for result of madd(). */
#define RandomTemp  Quotient
      madd(
            Divisor,       /* a value */
            Constant_Two,  /* 2nd value */
            RandomTemp );  /* the sum */
      move(
            RandomTemp,    /* source */
            Divisor );     /* dest */
      assert( misodd( Divisor ) );
   } /* loop forever */
Cleanup:
   /* Free memory used by temp vars. */
   if (Constant_Two != NULL) {
      mfree( Constant_Two );
   }
   if (Divisor != NULL) {
      mfree( Divisor );
   }
   if (MaxDivisor != NULL) {
      mfree( MaxDivisor );
   }
   if (Quotient != NULL) {
      mfree( Quotient );
   }
   if (Remainder != NULL) {
      mfree( Remainder );
   }
   return (ReturnValue);
} /* misprime */
int  /* Note: return values are 0=false and 1=true. */
miszero(
   const MINT  * Number)
{
   MINT  * Constant_Zero = itom(0);
   int   ReturnValue;   /* 0=false, 1=true. */
   /* We'll use the standard mcmp (MP compare) function for this. 
    * mcmp(a,b) returns  <0  if  a<b
    *                    =0  if  a=b
    *                    >0  if  a>b
    */
   if ( mcmp( Number, Constant_Zero ) == 0 ) {
      ReturnValue = 1;  /* true */
   } else {
      ReturnValue = 0;  /* false */
   }
   mfree( Constant_Zero );
   return (ReturnValue);
} /* miszero */


Listing Three

/* Copyright (c) 1994 by JR (John Rogers). All rights reserved.
 * FUNCTION - This program takes a given number and
 *      determines whether or not it is prime.
 * SYNTAX - IsPrime -n number
 * AUTHOR - JR (John Rogers) CompuServe: 72634,2402
 *      Internet: 72634.2402@CompuServe.com
 */

#include <assert.h>     /* assert(). */
#include <mp.h>         /* MINT typedef, itom(). */
#include "mphelp.h"     /* misprime(). */
#include "sample.h"     /* Die(), StringToM(). */
#include <stdio.h>      /* printf(). */
#include <stdlib.h>     /* EXIT_SUCCESS. */
#include <unistd.h>     /* getopt(), optind, optarg. */

#define USAGE \
 "This program determines if a number is prime.\n" \
 "Usage: IsPrime -n number\n" \
 "Or:    IsPrime -?\n\n" \
 "where:\n" \
 "       -n number   gives number to check\n" \
 "       -?          displays this message\n\n" \
 "Author: JR (John Rogers).\n"

int main(
   int   argc,
   char  * argv[])
{
   const char  * MyOpts = "n:N:";
   MINT        * Number = NULL;
   int         ThisOpt;
   int         ValueIsPrime; /* 0=false, 1=true */

   /* Do initial setup and argument handling. */
   while ((ThisOpt=getopt(argc,argv,MyOpts)) != EOF) {
      switch (ThisOpt) {
      case 'n':
      case 'N':
         Number = StringToM( optarg );
         assert(Number != NULL);
         break;
      case '?':
         Die( USAGE );
         /*NOTREACHED*/
      default:
         Die( "bad return value from getopt");
         /*NOTREACHED*/
      }
   }
   /* Handle missing number. */
   if (Number == NULL) {
      Die( USAGE );
      /*NOTREACHED*/
   }
   /* Call an MP helper to do the hard work. */
   ValueIsPrime = misprime( Number );
   /* Tell user what we found out. */
   mout( Number );
   if (ValueIsPrime) {
      printf("NUMBER IS PRIME!\n");
   } else {
      printf("NUMBER IS NOT PRIME!\n");
   }
   /* Free temp storage. */
   if (Number != NULL) {
      mfree( Number );
   }
   /* All done; set exit code. */
   if (ValueIsPrime) {
      return(EXIT_SUCCESS);
   } else {
      return(EXIT_FAILURE);
   }
} /* main */


Listing Four

/* Copyright (c) 1994 by JR (John Rogers). All rights reserved.
 * FUNCTION - This program generates a table of powers
 *      of 2, using the MP library routines.
 * SYNTAX - PowTable -n number
 * AUTHOR - JR (John Rogers) CompuServe: 72634,2402
 *      Internet: 72634.2402@CompuServe.com
 */

#include <assert.h>     /* assert(). */
#include <mp.h>         /* MINT, itom, rpow, mfree. */
#include "sample.h"     /* Die(), StringToShort(). */
#include <stdio.h>      /* stdout. */
#include <stdlib.h>     /* EXIT_SUCCESS. */
#include <unistd.h>     /* getopt(), optind, optarg. */

/* Only define this if m_out is supported at all. */
/* #define MP_SUPPORTS_M_OUT */

/* Only define this if m_out supports bases > 10. */
/* #define MP_OUTPUT_SUPPORTS_LARGE_BASES */

#define MY_USAGE \
      "Usage: PowTable -n number\n" \
      "Author: JR (John Rogers).\n\n"
static void
DisplayOneTableEntry(
   short  PowerToCompute )
{
   MINT  * Two      = itom(2);
   MINT  * PowerOf2 = itom(42);  /* Dummy value. */

   /* Compute regular power (2 ** N). */
   rpow(
         Two,             /* number to raise */
         PowerToCompute,  /* exponent (short) */
         PowerOf2);       /* result */
   /* Write the power of two for this one. */
   printf( "\n\n2 ** %d is:\n", (int) PowerToCompute );
#ifdef MP_SUPPORTS_M_OUT
   /* Write 2**N in binary, octal, decimal, hex. */
   m_out( PowerOf2,  2, stdout );
   m_out( PowerOf2,  8, stdout );
   m_out( PowerOf2, 10, stdout );
#ifdef MP_OUTPUT_SUPPORTS_LARGE_BASES
   m_out( PowerOf2, 16, stdout );
#endif

#else
   /* Output in decimal (only base supported). */
   mout( PowerOf2 );
#endif
   mfree( Two );       /* Free temps */
   mfree( PowerOf2 );
} /* DisplayOneTableEntry */
static void
GeneratePowerTable(
   short   MaxPower )  /* >= 1 */
{
   short   CurrentPower = 1;
   for (;;) {
      DisplayOneTableEntry( CurrentPower );
      ++CurrentPower;
      /* Have we gone far enough? */
      if (CurrentPower > MaxPower) {
         break;  /* done; go cleanup and return */
      }
   }
} /* GeneratePowerTable */
int
main(
   int   argc,
   char  * argv[])
{
   short       MaxPower = 0;
   const char  * MyOpts = "n:N:";
   int         ThisOpt;
   /* Do initial setup and argument handling. */
   while ((ThisOpt=getopt(argc,argv,MyOpts)) != EOF) {
      switch (ThisOpt) {
      case 'n':
      case 'N':
         MaxPower = StringToShort( optarg );
         assert(MaxPower != 0);
         break;
      case '?':
         Die( MY_USAGE );
         /*NOTREACHED*/
      default:
         Die( "bad return value from getopt");
         /*NOTREACHED*/
      }
   }
   /* Handle missing argument. */
   if (MaxPower == 0) {
      Die( MY_USAGE );
      /*NOTREACHED*/
   }
   /* Generate the table. */
   GeneratePowerTable( MaxPower );
   return(EXIT_SUCCESS);
} /* main */


Example 1:

#include <mp.h>

#ifdef NEED_MINT
typedef mint MINT;
#endif



Example 2:

MINT * One;
MINT * Three;
MINT * Sum;
 ...
One = itom(1);
Three = itom(3);
Sum = itom(7);  /* dummy value */



Example 3:

madd(
   One,    /* first input */
   Three,  /* second input */
   Sum);   /* result - set */