Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!brl-adm!adm!Alan_T._Cote.OsbuSouth@Xerox.COM
From: Alan_T._Cote.OsbuSouth@Xerox.COM
Newsgroups: comp.lang.c
Subject: Re: We need  H E L P (!!!!) with an algorithm.
Message-ID: <9826@brl-adm.ARPA>
Date: Fri, 16-Oct-87 21:10:59 EDT
Article-I.D.: brl-adm.9826
Posted: Fri Oct 16 21:10:59 1987
Date-Received: Sun, 18-Oct-87 02:41:58 EDT
Sender: news@brl-adm.ARPA
Lines: 110

The following C function should get you started.  I once coded the
algorithm in 68000 assembler, and benchmarked on a 68010 as faster than
the corresponding instruction on a 370 mainframe.

Enjoy.

--------------- CUT HERE ------------
typedef struct		s_bigint
  {
  long		low;
  long		high;
  }	BIGINT;

/*	The bigdiv() function performs signed division of a 64-bit signed
 *	dividend by a 32-bit signed divisor, yielding a 32-bit signed
 *	quotient and a 32-bit signed remainder.  The approach taken is that
 *	of binary long division.  The method is easily extended to cases
 *	in which all operands are 64-bit, to deal with the situation where
 *	the quotient must be >32 bits (which can happen -- just try dividing
 *	0x100000000000000 by 2, yielding a 32-bit result!).
 *
 *	If the division is successful, bigdiv() returns 0.  If quotient
 *	overflow is detected (eg: division by 0), 1 is returned.
 */

int		bigdiv(	dividend,
			divisor,
			quotient,
			remainder )

BIGINT		*dividend;
long		divisor;
long		*quotient;
long		*remainder;

{

unsigned long	dividend_high;
unsigned long	dividend_med;
unsigned long	dividend_low;
unsigned long	temp_quotient;
unsigned long	temp_divisor;
int		quotient_is_negative;
int		bit;

/*	Initialize							*/

temp_quotient = 0;
dividend_high = 0;
quotient_is_negative = 0;

if( dividend->high < 0 )
  {
  quotient_is_negative = !quotient_is_negative;
  dividend_med = ~ dividend->high;
  dividend_low = ( ~ dividend->low ) + 1;
  if( dividend->low == 0 )
    if( ++dividend_med == 0 )
      ++dividend_high;
  }
else
  {
  dividend_med = dividend->high;
  dividend_low = dividend->low;
  }

if( divisor < 0 )
  {
  quotient_is_negative = !quotient_is_negative;
  temp_divisor = -divisor;
  }
else
  temp_divisor = divisor;

/*	Do the division							*/

for( bit = 0; bit < 64; bit++ )
  {
  /*	check for overflow						*/
  if( ( temp_quotient & 0x80000000L ) != 0 )
    return( 1 );
  /*	shift dividend and temporary quotient left one bit		*/
  dividend_high = ( dividend_high << 1 ) + ( ( dividend_med >> 31 ) & 1
);
  dividend_med = ( dividend_med << 1 ) + ( ( dividend_low >> 31 ) & 1 );
  dividend_low <<= 1;
  temp_quotient <<= 1;
  /*	if dividend_high is divisible by temp_divisor, divide them	*/
  if( dividend_high >= temp_divisor )
    {
    dividend_high -= temp_divisor;
    ++temp_quotient;
    }
  }

/*	Establish final results						*/

if( quotient_is_negative )
  *quotient = -temp_quotient;
else
  *quotient = temp_quotient;

if( dividend->high < 0 )
  *remainder = -dividend_high;
else
  *remainder = dividend_high;

return( 0 );

}